CCF-NOIP-2018 提高组(复赛) 模拟试题(五)

T1 相遇

【问题描述】

在一场奇怪的梦里，小 Y 来到了一个神奇的国度。这个国度可以用一根数轴表示，小 Y 在 N 处，而小 Y 想吃的美食在 K 处。小 Y 有两种方式移动，一种叫做步行，一种叫做瞬移。对于每次步行操作，小 Y 可以从 $x$ 移动到 $x + 1$ 或者 $x – 1$ ，而对于每次瞬移操作小 Y 可以从 $x$ 瞬移到 $2x$ 。那么小 Y 最少要移动多少次才能到达 K 处吃到食物呢？

【输入格式】

仅有两个整数 $N$ 和 $K$

【输出格式】

共一行，包含一个整数，表示最少的移动次数

【样例1】

样例输入
5 17

样例输出
4

数据规模与约定

$0 ≤ N, K ≤ 100,000$

题解

方法很多，然而考试时本蒟蒻只想到了DP的做法。我们设 $f[i]$ 表示从 $n$ 到 $i$ 的最短路径，此时我们已经可以得知所有 $\forall i \le n$ 时的情况，因为当当前位置大于想要到达的位置时，我们只能通过每次移动到 $x-1$ 来逐步逼近位置，即： $f[i] = \begin{cases} 0 & i=n \\ f[i+1]+1 & i < n \end{cases}$
此时我们发现，当 $i>n$ 时，任意一个 $f[i]$ 都可以通过 $f[i-1]$ 到达。特殊的，当 $i$ 为偶数时，每个 $f[i]$ 位置都可以经由 $f[i/2]$ 到达。同时，我们仍然需要考虑 $f[i]=f[i-1]$ 的情况。事实上若 $i$ 为偶数时并不需要考虑，因为从 $f[i+1]$ 到达 $f[i]$ 的步骤必然要大于从 $min(f[i/2],f[i-1])$ 到达的步骤（可以想想为什么）而当 $i$ 为奇数时，我们可以考虑取从 $f[i-1]$ 到达 $f[i]$ 所需步骤和从 $f[(i+1)/2]$ 到达 $f[i]$ 的步骤的最小值。因此，我们的转移方程为：
$f[i] = \begin{cases} 0 & i=n\\ f[i+1]+1 & i<n\\ min(f[i/2]+1,f[i-1]+1) & i>n,i\%2=0\\ min(f[(i+1)/2]+2,f[i-1]+1) & i>n,i\%2=1 \end{cases}$
ps:本蒟蒻的dp水平极低，因此推出的式子极为冗长，但是整体思维层次不高，毕竟本蒟蒻都能AC
代码如下：

#include<bits/stdc++.h>
#define maxn 100000
using namespace std;
long long n,k;
long long f[maxn];
int main(){
    //freopen("meet.in","r",stdin);
    //freopen("meet.out","w",stdout);
    scanf("%d%d",&n,&k);
    f[n]=0;
    for(register long long i=n-1;i>=0;i--)f[i]=f[i+1]+1;
    for(register long long i=n+1;i<=k;i++){
        if(i%2==0){
            f[i]=min(f[i/2]+1,f[i-1]+1);
        }
        else f[i]=min(f[i-1]+1,f[(i+1)/2]+2);
        //cout<<i<<":"<<f[i]<<endl;
    }
    //for(register long long i=0;i<=n;i++)cout<<i<<":"<<f[i]<<endl;
    cout<<f[k]<<endl;
    return 0;
}

T2 秘密邮件

【问题描述】

小 $A$ 收到了一封来自外星球的秘密邮件。邮件由 $n$ 个大写英文字母组成，不巧的是小 $A$ 收到邮件以后一不小心打乱了原来的字母顺序。但是聪明的小 $A$ 记住了原邮件的完整内容，现在她每次可以选择打乱后的邮件中相邻的两个字母进行交换，问最少交换多少次能够将打乱的邮件恢复成原邮件。

【输入格式】

第一行一个整数 $n$ 表示邮件的长度。
第二行一个长度为 $n$ 的只包含大写字母的字符串表示打乱后的邮件。
第三行一个长度为 $n$ 的只包含大写字母的字符串表示原邮件。
为保证打乱后的邮件可以恢复成原邮件，所有的测试数据满足任意一种大写字母在两封邮件中的出现次数相同。

【输出格式】

共一行包含一个整数，表示最少的交换次数。

【样例1】

样例输入
4
ABCD
DBCA

样例输出
5

数据规模与约定

$n \le 1,000,000$ 。

题解

蒟蒻的我考试时竟然只写了60分的暴力代码QAQ事实上，这道题比 $T1$ 还要简单。我们只需要给第二个字符串中每个字符一个哈希值，并将这个哈希值带入第一个字符串中，求一下逆序对的数量即可！
贴出代码QAQ

#include <bits/stdc++.h>
using namespace std;
long long a[1000100],b[1000100],ans = 0;
long long n;
void merge_sort(long long l,long long r){
    long long p1,p2,p,mid;
    if(l == r){
        return ;
    }
    mid = (l+r) >> 1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    p1 = l,p2 = mid+1,p = 0;
    while(p1 <= mid || p2 <= r){
        if(p1 <= mid && (p2 > r || a[p1] <= a[p2])){
            b[++p] = a[p1];
            p1++;
        }else{
            b[++p] = a[p2];
            p2++;
            ans += mid-p1+1;
        }
    }
    for(long long i = 1;i <= p;i++){
        a[l+i-1] = b[i];
    }
}
int main(){
    //freopen("letter.in","r",stdin);
    //freopen("letter.out","w",stdout);
    cin >> n;
    string A,B;
    cin >> A >> B;
    queue<int> q[26];
    for(int i = 0;i < A.size();i++){
        q[(int)(A[i]-'A')].push(i+1);
    }
    for(int i = 0;i < B.size();i++){
        a[i+1] = q[(int)(B[i]-'A')].front();
        q[(int)(B[i]-'A')].pop();
    }
    ans = 0;
    merge_sort(1,n);
    cout << ans;
    return 0;
}

T3 小乔

【问题描述】

恋之微风·小乔，是手游《王者荣耀》中的法师型英雄，擅长远程消耗。小乔有一把神奇的扇子，借助灵活的走位可以对敌人造成高额的伤害。小乔是小 $A$ 最喜欢（会玩）的英雄之一。在一场梦里，小 $A$ 与小乔来到了一个异次元世界。异次元世界位于极坐标系中。小乔定义了一个值 $m$ ，以等分 $[-π,π]$ 弧度（详见样例）。小乔还有一把神奇的扇子，她将进行 $n$ 次“绽放之舞”操作。对于第 $i$ 次"绽放之舞”操作，小乔将设定半径 $r_i$ ，起始位置 $s_i$ ，终止位置 $t_i$ ，她借助自己神奇的扇子，以坐标系原点为圆心，) $r_i$ 为半径，将圆心角 $\frac{πs_i}{m}$ 到圆心角 $\frac{πt_i}{m}$ 这部分扇形区域逆时针叠加一层“治愈微笑” 。
小乔想到了一个有趣（奇怪）的问题，她希望知道有多大面积的区域被叠加过至少2层“治愈微笑” 。这个问题难倒了平日里善于发现并解决问题的小 A。现在小 A 求助于你，希望你能帮他解决这个问题。我们设答案的值为 $T$ ，为了方便表达，你只需要输出 $T*\frac{2m}{π}$ (可以证明这是一个非负整数)的值即可。

【输入格式】

第一行是三个整数 $n，m，k$ 。
接下来 $n$ 行，依次描述每个“绽放之舞”操作，每行包含三个整数 $r_i,s_i,t_i$ 。

【输出格式】

输出只包含一个整数，表示 $T*\frac{2m}{π}$ 的值。

【样例输入1】

3 8 2
1 -8 8
3 -7 3
5 -5 5

【样例输出1】

样例输出
76

image

【数据规模与约定】

$1\le n \le 100000，1 \le m \le 10^5$

【题解】

原谅我浅薄的几何知识。

image

#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
 
using namespace std;

typedef long long int64;
const int MAXN=400005;

int n,m,lim;
int na,nb;

struct A{
    int l,r,R;
    A(void){}
    A(int _l,int _r,int _R):l(_l),r(_r),R(_R){}
    inline void print()
    {
        printf("l = %d, r = %d, R = %d.\n",l,r,R);
    }
}a[MAXN],b[MAXN];

struct B{
    int p,r;
    bool f;
    #define SHANCHU 0
    #define CHARU 1
    B(void){}
    B(int _p,int _r,bool _f):p(_p),r(_r),f(_f){}
    friend bool operator < (const B &a,const B &b)
    {
        return a.p<b.p;
    }
}eve[MAXN];
int elen;

struct Size_Balanced_Tree{
    int left,right,size,data;
}SBT[MAXN*5];
int pn,root;

inline void left_rotate(int &p)
{
    int k=SBT[p].right;
    SBT[p].right=SBT[k].left;
    SBT[k].left=p;
    SBT[k].size=SBT[p].size;
    SBT[p].size=SBT[SBT[p].left].size+SBT[SBT[p].right].size+1;
    p=k;
}

inline void right_rotate(int &p)
{
    int k=SBT[p].left;
    SBT[p].left=SBT[k].right;
    SBT[k].right=p;
    SBT[k].size=SBT[p].size;
    SBT[p].size=SBT[SBT[p].left].size+SBT[SBT[p].right].size+1;
    p=k;
}

void maintain(int &p,bool f)
{
    if (!f)
    {
        if (SBT[SBT[SBT[p].left].left].size>SBT[SBT[p].right].size) right_rotate(p);
        else if (SBT[SBT[SBT[p].left].right].size>SBT[SBT[p].right].size) left_rotate(SBT[p].left),right_rotate(p);
        else return;
    }
    else
    {
        if (SBT[SBT[SBT[p].right].right].size>SBT[SBT[p].left].size) left_rotate(p);
        else if (SBT[SBT[SBT[p].right].left].size>SBT[SBT[p].left].size) right_rotate(SBT[p].right),left_rotate(p);
        else return;
    }
    maintain(SBT[p].left,0);
    maintain(SBT[p].right,1);
    maintain(p,0);
    maintain(p,1);
}

void Insert(int &p,int v)
{
    if (!p)
    {
        p=++pn;
        SBT[p].left=SBT[p].right=0;
        SBT[p].size=1;
        SBT[p].data=v;
    }
    else
    {
        SBT[p].size++;
        if (v<SBT[p].data) Insert(SBT[p].left,v);
        else Insert(SBT[p].right,v);
        maintain(p,v>=SBT[p].data);
    }
}

int Delete(int &p,int v)
{
    SBT[p].size--;
    int k=SBT[p].data;
    if (v==k||(v<k&&!SBT[p].left)||(v>k&&!SBT[p].right))
    {
        if (!SBT[p].left||!SBT[p].right) p=SBT[p].left+SBT[p].right;
        else SBT[p].data=Delete(SBT[p].left,v+1);
        return k;
    }
    else
    {
        if (v<k) return Delete(SBT[p].left,v);
        else return Delete(SBT[p].right,v);
    }
}

inline int Find_Kth(int k)
{
    int p=root;
    while (SBT[SBT[p].left].size+1!=k)
    {
        if (SBT[SBT[p].left].size+1<k) k-=SBT[SBT[p].left].size+1,p=SBT[p].right;
        else p=SBT[p].left;
    }
    return SBT[p].data;
}

inline int64 work(A *a,int n)
{
    pn=root=elen=0;
    for (int i=1;i<=n;i++)
    {
        eve[++elen]=B(a[i].l,a[i].R,CHARU);
        eve[++elen]=B(a[i].r,a[i].R,SHANCHU);
    }
    sort(eve+1,eve+elen+1);
    int64 res=0;
    int last=eve[1].p;
    int l=1,r=1;
    while (l<=elen)
    {
        while (r<=elen&&eve[r].p==eve[l].p) r++;
        if (SBT[root].size>=lim)
        {
            int64 x=Find_Kth(SBT[root].size-lim+1);
            res+=x*x*(eve[l].p-last);
        }
        for (int i=l;i<r;i++)
        {
            if (eve[i].f==CHARU) Insert(root,eve[i].r);
            else Delete(root,eve[i].r);
        }
        last=eve[l].p;
        l=r;
    }
    return res;
}

int main()
{
    //freopen("xiaoqiao.in","r",stdin);
    //freopen("xiaoqiao.out","w",stdout);
    scanf("%d%d%d",&n,&m,&lim);
    for (int i=1;i<=n;i++)
    {
        int R,l,r;
        scanf("%d%d%d",&R,&l,&r);
        if (l==m) l=-m;
        if (r==-m) r=m;
        if (l==r) continue;
        if (l<=0&&r<=0)
        {
            if (l<r) a[++na]=A(l,r,R);
            else if (l>r)
            {
                if (l!=0) a[++na]=A(l,0,R);
                if (-m!=r) a[++na]=A(-m,r,R);
                if (0!=m) b[++nb]=A(0,m,R);
            }
        }
        else if (l>=0&&r>=0)
        {
            if (l<r) b[++nb]=A(l,r,R);
            else if (l>r)
            {
                if (l!=m) b[++nb]=A(l,m,R);
                if (0!=r) b[++nb]=A(0,r,R);
                if (-m!=0) a[++na]=A(-m,0,R);
            }
        }
        else if (l<=0&&r>=0)
        {
            if (l!=0) a[++na]=A(l,0,R);
            if (0!=r) b[++nb]=A(0,r,R);
        }
        else if (l>=0&&r<=0)
        {
            b[++nb]=A(l,m,R);
            a[++na]=A(-m,r,R);
        }
    }
    printf("%lld\n",work(a,na)+work(b,nb));
    return 0;
}