Codeforces Round #700 (Div. 2) 题解

链接 https://codeforces.com/contest/1480

闲着没事翻了翻以前的博客，感觉自己之前的文章质量太低了，尤其是很多题解东一篇西一篇的非常乱，以后类似题解之类的就整套整套地写好了。

Round 700 Div.2给人的感觉是手速场，基本上没有什么很需要思考的点。

A. Yet Another String Game

题意：给出一个长度为 $n$ 的小写字符组成的字符串 $s$ , Alice 和 Bob 两个人轮流操作, Alice 先手. 每次操作为, 选 $s$ 中的一个字符 $s_i$ , 将其变成任意一个与其自身不同的小写字符 $c$ . 字符串的每一个字符最多只能被操作一次, 当所有的字符都被操作过后游戏结束. Alice 想让字符串的字典序尽可能小, Bob想让字符串的字典序尽可能大. 要求在上述约束下输出最后的游戏结束后的结果.

数据范围: 多组数据, 最多可能有 $1000$ 组, 每个字符串长度 $\le 50$, 小写字母.

题解: 直接暴力模拟游戏过程, 每次从前往后找到第一个可操作的位置, 然后根据现在操作的人是 Alice 还是 Bob 对字符尽可能地变小或者变大.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;

bool done[64];

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t;
    string s;
    cin>>t;
    while(t--){
        cin>>s;
        int len=s.length();
        memset(done,0,sizeof(done));
        for(int i=0;i<len;++i){
            for(int j=0;j<len;++j){
                if(!done[j]){
                    done[j]=true;
                    if(i&1){
                        s[j] = (s[j] == 'z' ? 'y' : 'z');
                    }else {
                        s[j] = (s[j] == 'a' ? 'b' : 'a');
                    }
                    break;
                }
            }
        }
        cout<<s<<"\n";
    }
}

B. The Great Hero

题意: 一个英雄要与怪兽进行回合制作战, 英雄的攻击力为 $A$ , 血量为 $B$ , 总共有 $n$ 个怪兽, 第 $i$ 个怪兽的攻击力为 $a_i$ , 血量为 $b_i$ . 每个回合中, 英雄只能与一只怪兽战斗. 本回合结束之后, 英雄的血量 $-b[i]$ , 怪兽的血量 $-B$ , 可以认为两方掉血是同时发生的. 现在问英雄采取最优策略的话能不能杀死所有的怪兽, 即使在杀死所有的怪兽之后英雄也死了也没关系. “死” 的定义为 血量 $\le 0$.

数据范围: 多组数据, 最多可能有 $10^5$ 组输入. $1≤A≤10^6$, $1≤B≤10^6$ , $1≤n≤10^5$, $1\le a_i \le 10^6$, $1\le b_i \le 10^6$. 保证所有输入中的 $n$ 之和不超过 $10^5$.

题解: 显然采取不同的策略只能影响到最后一个回合的成败, 例如英雄的攻击力为 $4$ , 血量为 $4$ , 怪物 $1$ 攻击力和血量分别为 $5$ 和 $3$ , 怪物 $2$ 攻击力和血量分别为 $3$ 和 $3$ , 那么英雄先攻击怪物 $1$ 的话一个回合下来就会直接死掉, 但是如果他选择先攻击 $2$ 的话就可以把二者都杀死 (虽然最后自己也死了) . 在杀死最后一个怪兽之前, 所有的攻击和掉血都是完全确定的, 也就是说英雄必须承受杀死其他 $n-1$ 只怪物时的攻击. 因此我们只需要判断让哪只怪物做最后一个就可以了.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;

long long a[maxn],b[maxn],loss[maxn],id[maxn];

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    long long t,A,B,n;
    cin>>t;
    while(t--){
        cin>>A>>B>>n;
        for(int i=1;i<=n;++i){
            cin>>a[i];
        }
        for(int i=1;i<=n;++i){
            cin>>b[i];
        }
        ll sum=0;
        for(int i=1;i<=n;++i){
            id[i]=i;
            loss[i]=(b[i]+A-1)/A*a[i];
            sum+=loss[i];
        }
        sort(id+1,id+1+n,[](int i,int j){
            return a[i]<a[j];
        });// 没必要排序,只需要找最大的a[i],懒得改了
        if(sum-B<a[id[n]]){
            cout<<"YES\n";
        }else{
            cout<<"NO\n";
        }
    }
}

C. Searching Local Minimum

题意: 交互题，给一个$1-n$的排列，要求找到任意一个局部极小值的位置，局部极小的定义是 $a_i<min{a_{i-1},a_{i+1}}$. 每次交互可以问第i个数值是多少，最多问100次就得输出一个你认为的局部极小值的index。另外，定义 $a_0$ $a_{n+1}$ 都为 $+\infty$

数据范围：$1\le i \le 10^5$

题解：cf的交互题终于不是二分了。。换三分了。。但是写起来好像还是二分？这个题可以用类似数形结合的方式来思考。把所有的点连起来当作一条折线，首先判断一下两头的是不是局部极小，如果两个都不是的话说明这条折线的两端斜率方向是相反的。记此时左右两端包含的区间为$[L,R]$，根据微分中值定理可知此时$[L,R]$中必然有一点为局部极小。接下来我们只需要不断地缩小$[L,R]$的范围就可以了。具体地来说，每次取$mid=(L+R)/2$，然后查询 $mid$ 和 $mid+1$的值并计算$mid$处的斜率，如果斜率是正数则令$R$往此处缩减，反之则令$L$往此处缩减。每次缩减需要用掉2次询问，去掉最初的两次也就是有49次缩减的机会，由于是范围是$log_2$式的缩减所以显然可以满足题目数据范围。

代码；

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;

int arr[maxn];

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int l,r,mid,n;
    cin>>n;
    l=1,r=n;
    arr[0]=arr[n+1]=1e9+7;
    if(n<=100){
        for(int i=1;i<=n;++i){
            cout<<"? "<<i<<endl;
            cin>>arr[i];
        }
        for(int i=1;i<=n;++i){
            if(arr[i-1]>arr[i]&&arr[i]<arr[i+1]){
                cout<<"! "<<i<<endl;
                return 0;
            }
        }
    }
    int cnt=100;
    while(l!=r){
        if(r-l<=cnt){
            for(int i=l;i<=r;++i){
                cout<<"? "<<i<<endl;
                cin>>arr[i];
            }
            for(int i=l;i<=r;++i){
                if(arr[i-1]>arr[i]&&arr[i]<arr[i+1]){
                    cout<<"! "<<i<<endl;
                    return 0;
                }
            }
        }
        mid=(l+r)>>1;
        cout<<"? "<<mid<<endl;--cnt;
        cin>>arr[mid];
        cout<<"? "<<mid+1<<endl;--cnt;
        cin>>arr[mid+1];
        if(arr[mid]>arr[mid+1]){
            l=mid+1;
        }else{
            r=mid;
        }
    }
    cout<<"! "<<l<<endl;
}

D1. Painting the Array I

题意：把一个数字序列$a_1, a_2,…,a_n$拆分成两个子序列，每个子序列中各个数字的相对位置与原序列中的相对位置相同，子序列可以为空序列。每个子序列中如果有相邻的一串相同数字就将他们合并为1个。问所有可能的拆分方式中，经过合并之后剩余的两个序列中的数字个数之和最小是多少。

数据范围：$1\le n \le 10^5$, $1\le a_i \le n$

题解：要让剩余的数字最多，那就是让各个数字尽可能地不合并。从前往后挨个考虑每个数字，将两个子序列当作两个栈往里放数，简单的分析可以得出，连续相同数字的长度$len_{eq}$超过2的时候，无论怎么操作都至少要合并掉$len_{eq}-2$个数字，因为我们只有2个子序列可以往里放，也就是说我们最多使得最先入栈的2个数字不被合并，其他的一定会被这2个数字给吞掉。那么这样一来在这个从前往后遍历处理的过程中我们只需要考虑位置$i$和$i+1$就可以了，再后面的数字影响不到。当我们处理到数字$a_i$的时候，只需要考虑两种情况分别做就可以了：

1. 放进两个栈里都不会发生合并。此时要往后多考虑一步第$a_{i+1}$的安排，如果$a_{i+1}$和其中某一个栈顶部的元素相同我们就选择把$a_{i}$放在这里堵住他，可以让后面的$a_{i+1}$不被合并。
2. 一个栈可以合并一个栈不能合并，或者两个栈都能合并。此时尽量选不能自身的就可以，因为即使能像上一步的一样救一个元素也只能救$a_{i+1}$，但是自身被合并了，1换1等于没做。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;

int arr[maxn],dp[maxn][3],cnt[maxn],top;
vector<int> a1,a2;


int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>arr[i];
    for(int i=1;i<=n;++i){
        if(i<n&&(a1.empty()||*a1.rbegin()!=arr[i])&&(a2.empty()||*a2.rbegin()!=arr[i])){
            if(!a1.empty()&&*a1.rbegin()==arr[i+1]){
                a1.push_back(arr[i]);
            }else{
                a2.push_back(arr[i]);
            }
        }
        else if(a1.empty()||*a1.rbegin()!=arr[i]){
            a1.push_back(arr[i]);
        }
        else if(a2.empty()||*a2.rbegin()!=arr[i]){
            a2.push_back(arr[i]);
        }
    }
    ans=max(ans,(int)a1.size()+(int)a2.size());
    cout<<ans;
}

D2. Painting the Array II

题意、数据范围：与上一题相同，只qu是这里要求让拆分成两个子序列、合并相邻元素之后的数字个数最小。

题解：此时的要求相当于要我们尽可能多地合并连续重复数字。首先对原序列直接来个合并去重（显然这个操作不会让结果变差），方便我们分析。依然把两个序列都看成栈，此时对于一个没有连续重复数字的序列，假如我们要合并某两个数字，假设该合并发生在序列1内，那显然这两个数字之间的所有数字都会被原封不动地入栈到序列2，也就是说这其间的数字都不能被合并了。换句话说合并 $a_l$ 和 $a_r$ 的代价是 $l-r$之间的数字都不能被合并了，最多 $a_{l+1}$ 有可能被序列2的栈顶元素合并。那么当我们拿到一个数字$a_i$准备入栈的时候，应该如何选择呢？有以下2种情况：

1. 其中某一个栈可以合并掉$a_i$。此时就直接毫不犹豫地合并就完事了，因为合并了会少一个数字而且完全影响不到后面的其他数字。
2. 两个栈都不能合并$a_i$，那么我们操作时就需要选择保留一个“合并潜力”更大地栈顶元素。衡量这个“合并潜力”便用到了上面的分析：选择合并后一个相同数字所花费代价更小的那个。正式地说，若令$lst[i]$表示第$i$个位置之后的第1个与 $a_i$ 相同的元素位置，那么我们会选择保留 $c=\argmin{lst[Stack[i].top]}, i={1,2}$ ，而将 $a_i$ 放到另一个栈里。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;

int arr[maxn],lst[maxn],pos[maxn],dp[maxn][3],cnt[maxn],top;
vector<pair<int,int> > a1,a2;


int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,ans=0;
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>arr[i];
    }
    cnt[top=1]=1;
    for(int i=2;i<=n;++i){
        if(arr[top]!=arr[i]){
            arr[++top]=arr[i];
            cnt[top]=1;
        }else{
            cnt[top]++;
        }
    }
    memset(pos,0x3f,sizeof(pos));
    for(int i=top;i>=1;--i){
        lst[i]=pos[arr[i]];
        pos[arr[i]]=i;
    }

    for(int i=1;i<=top;++i){
        if(!a1.empty() && (a1.rbegin()->second==arr[i])){
            a1.rbegin()->first=i;
        }else if(!a2.empty() && (a2.rbegin()->second==arr[i])){
            a2.rbegin()->first=i;
        }else if(a1.empty()){
            a1.push_back({i,arr[i]});
        }else if(a2.empty()){
            a2.push_back({i,arr[i]});
        }else{
            if(lst[a1.rbegin()->first]<lst[a2.rbegin()->first]){
                a2.push_back({i,arr[i]});
            }else{
                a1.push_back({i,arr[i]});
            }
        }
    }
    cout<<a1.size()+a2.size();
}

E. Continuous City

题意：给出两个数字 $L$、$R$ ， 要求构造一个点数 $n$ 不超过32的有向带权图，满足

1. 从点 $1$ 到 点 $n$ 的所有路径的长度必须在 $[L,R]$之间
2. 对于每一个 $L\le d \le R$，有且仅有一条路径满足其长度等于$d$.

也就是说从点$1$到点$n$的所有路径长度与$[L,R]$之间的正整数形成了一对一的映射。

数据范围：$1\le L \le R \le 10^6$

题解：非常显然的用二进制的思想可以解决的问题，类似于多重背包的二进制优化。不知道为什么会成为E题，感觉没有D难。把$diff=R-L$不断地除以$2$，每次分出来的两小块选其中较小的那一块继续分直到分成了$1$，例如$10$可以分为
“`5 3 1 1“` 这样一个分解集。类似二进制的思想，把这些分解出来的值当作某个进制的权值，则任意一个$[L,R]$之间的整数都可以唯一的由该分解集的一个子集表示。例如$1-10$中，$4=3+1$，$6=5+1$，$7=5+1+1$，这些都是上面分解集的子集，且这种表示是唯一的。

有了这个结果之后只需要把这些权值赋予不同的边就可以了。总共有三种边：

1. 初始边，直接把点1到点2之间的有向边设置为 $L-1$ ，并把$2$设置为初始点（当$L1$的时候则不需要此步，直接令$1$为初始点）。
2. 将从初始点开始的之后的第 $i$ 个点与比他更小的每个点都连接一条入边，且对于该点的所有入边权值均为分解中从小到大的第 $i$ 个元素。另外，为了保证路径的唯一性，若在分块的过程中有某一次分出的两个块大小相同，则只选取其中一个与初始点相连。例如分解出来
   “`5 3 1 1“`，则只有 “`3 1 1“` 会跟初始点直接相连，这样就不会出现有两条长度为5的路径的情况了。
3. 所有的点都向点 $n$ 连一条长度为 $1$ 的边。

画出来应该像一个。。。信号流图？梦回信号与系统课堂：

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+7;

int g[100][100];
vector<int> vec;

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int l,r,cntn=0,cntm=0,base=1;
    cin>>l>>r;
    if(l>1){
        g[1][2]=l-1;cntm++;
        base=2;
    }
    if(r==l){
        cout<<"YES\n"<<"2 1\n"<<"1 2 "<<l<<"\n";
        return 0;
    }else if(l+1==r){
        cout<<"YES\n"<<"3 2\n"<<"1 2 "<<l<<"\n"<<"2 3 1\n";
        return 0;
    }
    for(int diff=r-l;diff;diff>>=1){
        if(diff&1){
            vec.push_back(diff/2+1);
        }else{
            vec.push_back(diff/2);
        }
    }
    sort(vec.begin(),vec.end());
    int len=vec.size(),presum=0;
    cntn=len+1+base;
    g[base][cntn]=1;cntm++;
    for(int i=0;i<len;++i){
        int to=base+i+1;
        for(int j=(presum==vec[i]?0:-1);j<i;++j){
            int from=base+j+1;
            g[from][to]=vec[i];cntm++;
        }
        g[to][cntn]=1;cntm++;
        presum+=vec[i];
    }
    cout<<"YES\n"<<cntn<<" "<<cntm<<"\n";
    for(int i=1;i<cntn;++i){
        for(int j=i+1;j<=cntn;++j){
            if(g[i][j]){
                cout<<i<<" "<<j<<" "<<g[i][j]<<"\n";
            }
        }
    }
}