Codeforces Round 910 (Div. 2) (A~E)
qfl_zzz
编辑于 2023年11月20日 11:03

简单说一下这场吧，赛时写D题时犯大病了，赛后才发现求线段最大间隔就行了，E题最后改完bug的时候差几秒钟交上去，赛后交了一发过了，又错失了一次上大分的机会qwq。

A. Milica and String 模拟即可。

代码块
C++
自动换行
复制代码
ll n,k;
inline void qfl_zzz(){
    n=read(),k=read();
    string s=sread();
    ll cnt=0;
    for(ll i=1;i<=n;++i)
        cnt+=(s[i]=='B');
    if(cnt==k){
        writen(0);
        return;
    }
    if(cnt>k){
        cnt-=k;
        for(ll i=1;i<=n;++i){
            cnt-=(s[i]=='B');
            if(cnt==0){
                writen(1),writet(i),printf("A\n");
                return;
            }
        }
    }
    else{
        cnt=k-cnt;
        for(ll i=1;i<=n;++i){
            cnt-=(s[i]=='A');
            if(cnt==0){
                writen(1),writet(i),printf("B\n");
                return;
            }
        }
    }
}
复制成功

B. Milena and Admirer 注意到从 a_i 中拆出来的 x 是被放在前面的，所以如果我们从前往后操作的话，可能会破坏前面单调不降的限制，于是考虑从后往前考虑操作； 对于 a_i ，我们假设他后面的数字是 pre ，那么我们可以求出把 a_i 的每一份都尽可能分成 pre 最多可以分成多少份，显然是 cnt%3D%5Clceil%20%5Cfrac%7Ba_i%7D%7Bpre%7D%20%5Crceil%20 ，每一份不超过 pre 保证了单调不降的限制； 一个数字被分成了 cnt 份显然是进行了 cnt-1 次操作，然后我们把 pre 更新成 %5Clfloor%20%5Cfrac%7Ba_i%7D%7Bcnt%7D%20%5Crfloor%20 即可。

代码块
C++
自动换行
复制代码
ll n,a[200005];
inline void qfl_zzz(){
    n=read();
    for(ll i=1;i<=n;++i)a[i]=read();
    ll ans=0,pre=1e18;
    for(ll i=n;i>=1;--i){
        if(a[i]<=pre){
            pre=a[i];
            continue;
        }
        ll cnt=(a[i]+pre-1)/pre;
        ans+=cnt-1,pre=a[i]/cnt;
    }
    writen(ans);
}
复制成功

C. Colorful Grid 首先我们可以很容易地知道从起点到终点的曼哈顿距离 n%2Bm-2 ，而对于 k%3En%2Bm-2 的情况，我们需要通过在图上 “绕圈” 或者 “多花两步拐一个弯代替一次直走” 来抵消掉多余的路程； 不难发现，绕圈每一次花费 4 步路程，绕弯代替直走则多花费 2 步路程，因此，我们可以通过这两个操作抵消掉偶数长度的额外路程，所以当 k-n-m%2B2 是奇数时，无解； 显然，我们可以指定一个角落进行绕圈操作，指定另外一个角落进行绕弯操作，这两个角落可以直接选在起点和终点的位置以便输出答案，具体实现方式有很多，笔者给出其中比较拙劣的一种。

代码块
C++
自动换行
复制代码
ll n,m,k,r[20][20],c[20][20];
inline void qfl_zzz(){
    memset(r,-1,sizeof(r));
    memset(c,-1,sizeof(c));
    n=read(),m=read(),k=read();
    ll x=k-n-m+2;
    if(x<0||x%2==1){
        printf("NO\n");
        return;
    }
    printf("YES\n");
    r[1][1]=r[2][1]=1;
    c[1][1]=c[2][1]=0;
    if((n+m)%2)r[n][m-1]=c[m-1][n-1]=c[m][n-1]=0,r[n-1][m-1]=1;
    else r[n][m-1]=c[m-1][n-1]=c[m][n-1]=1,r[n-1][m-1]=0;
    for(ll i=m-2;i>=1;--i)r[n][i]=1-r[n][i+1];
    for(ll i=2;i<=n-1;++i)c[1][i]=1-c[1][i-1];
    for(ll i=1;i<=n;++i,printf("\n"))
        for(ll j=1;j<=m-1;++j){
            ll x=r[i][j];
            if(x==-1||x==1)printf("R ");
            else printf("B ");
        }
    for(ll i=1;i<=n-1;++i,printf("\n"))
        for(ll j=1;j<=m;++j){
            ll x=c[j][i];
            if(x==-1||x==1)printf("R ");
            else printf("B ");
        }
}
复制成功

D. Absolute Beauty 将 a_i 和 b_i 当作是线段的两个端点，那么交换 b_i 的值相当于是交换了两个线段的端点，稍加模拟一下就会发现，交换之后多出了两倍的原线段之间的间隔，于是求最大两线段的间隔即可。

代码块
C++
自动换行
复制代码
ll n,a[200005],b[200005];
inline void qfl_zzz(){
    n=read();
    ll ans=0,r=1e9,l=0;
    for(ll i=1;i<=n;++i)a[i]=read();
    for(ll i=1;i<=n;++i)b[i]=read();
    for(ll i=1;i<=n;++i){
        l=max(l,min(a[i],b[i]));
        r=min(r,max(a[i],b[i]));
        ans+=abs(a[i]-b[i]);
    }
    writen(ans+max(0ll,2*(l-r)));
}
复制成功

E. Sofia and Strings 如果暴力地去模拟操作，那么显然复杂度是难以接受的； 于是考虑将操作作为微调的手段，即我们无需去实际进行这些操作，而是当我们需要达到一些目的的时候，思考一下这两个操作能够为我们达到目的提供什么帮助； 对于此题，我们可以从左到右依次考虑 t_i 来自于 s 中的哪一个字符； 对于每一个 t_i ，我们应该选取 s 中当前最早出现 t_i 的位置来进行配对； 如何理解 “当前” ？比如在 t_i 之前，我们已经在 s 中配对了一些与 t_i 相同的字符，那么这些字符在 s 中对应的位置就不能再用于与当前的 t_i 的配对了； 如何理解 “最早” ？显然，在 t_i 后面的可能会存在与 t_i 相同的字符，他们也需要用与 t_i 同样的字符来与 s 中对应的位置来配对，如果不使用最早的，那么就会造成浪费，导致后面的有些字符无法配对； 我们假设 x 为 s 中需要与 t_i 进行配对的位置，那么显然在 x 之前的位置中，不能存在比 t_i 更小的字符； 为什么？因为位置 x 可能不是与 t_i 所在的位置对齐的，所以这时我们需要通过操作2：排序来将 x 对齐到相应位置，如果此时在位置 x 之前有存在更小的字符，设它的位置为 y ，那么与 t_i 对齐的就是 y 而不是 x 了，因为排序后位置 y 对应的字符显然会排在更前面； 那么如果出现了这种 x 之前存在更小字符的情况该怎么办呢？不要忘了我们还有操作1：删除，显然我们可以通过操作 1 将这些在 x 之前的更小字符给逐个删去； 具体实现看代码。

代码块
C++
自动换行
复制代码
ll n,m;
inline void qfl_zzz(){
    n=read(),m=read();
    string s=sread(),t=sread();
    stack<ll> id[26];
    for(ll i=n;i>=1;--i)id[s[i]-'a'].push(i);
    for(ll i=1;i<=m;++i){
        ll e=t[i]-'a';
        if(id[e].size()==0){
            printf("NO\n");
            return;
        }
        for(ll j=0;j<e;++j)
            while(id[j].size()>0&&id[j].top()<id[e].top())
                id[j].pop();
        id[e].pop();
    }
    printf("YES\n");
}
复制成功

cv27814443