[C++知识库]Codeforces Round #776 (Div. 3) A B C D E

Codeforces Round #776 (Div. 3) A B C D E

A. Deletions of Two Adjacent Letters

• Tip: Implementation、String

思路： 签到，稍微提一下思路，目标为一个字符，且原字符串长度为奇数。那么我们只要在原字符串中找到下标是奇数的目标字符，那么我们必定可以通过删除其前面偶数个字符和后面偶数个字符来获得最终的目标字符。由于$Sting$的下标是从$0$开始的，所以找到$i$%$2$==$0$即可。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define lowbit(x) (x&-x)
#define pb emplace_back
#define cf int t; cin>>t; for(int i=1;i<=t;i++)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
void solve(){
    string s;
    cin>>s;
    char x;
    cin>>x;
    bool ok=false;
    for(int i=0;i<s.size();i++){
        if(i%2==0&&s[i]==x){//找到了ok变成true
            ok=true;
            break;
        }
    }
    if(ok)cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}
signed main(){
    cf{
        solve();
    }
    return 0;
}

B. DIV + MOD

• Tip:math

思路： 难度感觉放在$div3$的$B$位置稍大，没做过类似的题可能会忽略一个点。正常思考： 要让$DIV+MOD$的值尽可能大，那么最好的值应该是$x/a$和$x$%$a$都处于最大，那么就是$?\frac{r}{a}?$$?$$a?1。$但是会出现两种情况，1：$?\frac{r}{a}?$$?$$a?1<l$ 那么此时最大值一定在$r$，因为接下去在$x$ $from$ $?\frac{r}{a}?$$?$$a?1$ ~ $r$的过程中$DIV$不变，$MOD$值却越来越大。2：$?\frac{r}{a}?$$?$$a?1>=l$，那么我们的最大值一定是在$x$或者$r$两者中的一个，因为$a$可以取到$1$或者$2$，这就使得$?\frac{r}{a}?$$?$$a?1$是最大值在一定情况下会失效，例如：$l=12,r=25,a=1$和$l=12,r=25,a=2$。显然前者和后者按照$?\frac{r}{a}?$$?$$a?1$最终得到的值是$23$和$24$。但实则最大都是$25$，所以在包括这种特殊情况的写法可以通过一个$max$来维护。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define lowbit(x) (x&-x)
#define pb emplace_back
#define cf int t; cin>>t; for(int i=1;i<=t;i++)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
void solve(){
    int l,r,a;
    cin>>l>>r>>a;
    int x=r/a;
    x=x*a-1;
    if(x>=l){
        cout<<max(x/a+x%a,r/a+r%a)<<endl;
    }
    else if(x<l){
        cout<<(r/a+r%a)<<endl;
    }
}
signed main(){
    cf{
        solve();
    }
    return 0;
}

C. Weight of the System of Nested Segments

• Tip:greedy、sortings、implementation

思路： 题意可能会稍微有点难理解，不过感觉也是个大模拟。$n$的意思是你可以构造$n$组连线，$m$代表有$m$个点，我们的任务是在$m$个点中选取$2?n$个点进行连线，且使得最终连线点的数值和最小同时还要满足$n$组连线都是大区间包小区间的形式。题目样例中的有序坐标并不是每个点真正的$id$，展示给我们的是从小到大排序之后的情形，而真正的$id$是通过输入的顺序给予的。所以我们要记录的信息有$id$，坐标$start$和每个点的价值$val$。 由于题目要求最终总贡献最小，那么我们必定要将最大的$m?2?n$个点删掉，不能进行连线操作。通过结构体重载操作，将$val$作为关键字排序，先将不可选点删除。再重载，将$start$作为关键字排序，接下去设$l=1$和$r=m$进行扫描，一旦遇到删除的点就跳过，最终的$n$组数据构造的值就是最小且满足大区间包小区间的要求，输出即可。代码已加注释，易于理解。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define lowbit(x) (x&-x)
#define pb emplace_back
#define cf int t; cin>>t; for(int i=1;i<=t;i++)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
bool st[N];
struct Node{
    int id,start,val;
    bool operator<(const Node &W)const{
        return start<W.start;
    }
}nodes[N];
struct Node2{
    int id,start,val;
    bool operator<(const Node2 &W)const{
        return val>W.val;
    }
}nodes2[N];
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++){//所有点都没被删除
        st[i]=false;
    }
    for(int i=1;i<=m;i++){//读入
        nodes[i].id=i;
        cin>>nodes[i].start>>nodes[i].val;
        nodes2[i].id=nodes[i].id;
        nodes2[i].start=nodes[i].start;
        nodes2[i].val=nodes[i].val;
    }
    sort(nodes+1,nodes+1+m);//start作为关键字sort
    sort(nodes2+1,nodes2+1+m);//val作为关键字sort
    int sum=m-n*2;//最大的sum数量个
    for(int i=1;i<=sum;i++){
        st[nodes2[i].id]=true;//删除
    }
    int l=1,r=m;
    vector<PII>S;//存点
    int all=0;//总贡献
    for(int i=1;i<=n;i++){
        while(st[nodes[l].id])l++;//遇到删除的点跳过
        while(st[nodes[r].id])r--;
        S.push_back({nodes[l].id,nodes[r].id});
        all+=nodes[l].val+nodes[r].val;
        l++,r--;
    }
    cout<<all<<endl;
    for(auto x:S){
        cout<<x.first<<' '<<x.second<<endl;
    }
}
signed main(){
    cf{
        solve();
        if(i!=t)cout<<endl;
    }
    return 0;
}

D. Twist the Permutation

• Tip:math、implementation、constructive algorithms、brute force

思路： 感觉好好把题意看懂，给的例子看懂就是一眼题。给我们的数组是最终的数组，那么我们每次操作只需要将本应该在当前位子上的数复原即可。范围最大$2e3$直接$n^2$暴力可接受。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define lowbit(x) (x&-x)
#define pb emplace_back
#define cf int t; cin>>t; for(int i=1;i<=t;i++)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e3+10;
int a[N];
int b[N];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    vector<int>cz;
    for(int i=n;i>=1;i--){//将n~1逐步复原，构造。
        int py=i;
        for(int j=1;j<=i;j++){
            if(a[j]==i){
                py=j;
                break;
            }
        }
        int g=py;
        if(py!=i){//py!=i说明有偏移否则没有
            int x=py;
            cz.push_back(x);
            int cnt=0;//用一个b数组将两段连接起来。
            for(int j=g+1;j<=i;j++){//第一段
                b[++cnt]=a[j];
            }
            for(int j=1;j<=g;j++){//第二段
                b[++cnt]=a[j];
            }
            for(int j=1;j<=i;j++){//连接
                a[j]=b[j];
            }
        }
        else cz.push_back(0);
    }
    reverse(cz.begin(),cz.end());//记住要reverse,因为第一个元素是尾巴。
    for(auto x:cz)cout<<x<<' ';
    cout<<endl;
}
signed main(){
    cf{
        solve();
    }
    return 0;
}

E. Rescheduling the Exam

• Tip:data structures、greedy、implementation

思路： 题意就是将导致考试前休息天数最少的一门考试进行移位，使得最终的所有考试前休息天数的最小值最大。看题意好像不是很难，但其实是一道不太好写的一道题，也算有些难度。首先肯定先找到使得$\mu$最小的那门考试的位置，那么将$\mu$变大，假设使得$\mu$最小的那门考试的位置为$idx$，使得$\mu$变大不但可以移动$idx$，同样如果$idx?1>0$也可以进行移动使得$\mu$发生改变。所以需要考虑两种情况(感觉是一个容易疏忽的点)。接下去我们需要找到怎么放置$idx$或$idx?1$这门考试的位置才能使得$\mu$尽可能的大。显然，将$idx$或$idx?1$取出之后，统计最大的空隙，将其放在最大的空隙处会使得最终的$\mu$尽可能趋向最大。同时也要考虑将$idx$或$idx?1$放置$d$处时的情况，那么最终的$\mu$必然从$minx$(最小空隙)、$max((maxn?1)/2,d?run.back()?1)$中取一个最小值。最后再考虑$idx$和$idx?1$移动情况下最大的$\mu$，即为本题答案。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define int long long 
#define re register int
#define lowbit(x) (x&-x)
#define pb emplace_back
#define cf int t; cin>>t; for(int i=1;i<=t;i++)
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
const int N=2e5+10;
int a[N];
int mi,id;
int n,d;
int check(vector<int>run){
    int maxn=0;
    int minx=1e9;
    fer(i,1,n-1){
        minx=min(minx,run[i]-run[i-1]-1);
        maxn=max(maxn,run[i]-run[i-1]-1);
    }
    return min(minx,max((maxn-1)/2,d-run.back()-1));
}
void solve(){
    cin>>n>>d;
    id=0,mi=d;
    fer(i,1,n){
        cin>>a[i];
        if(a[i]-a[i-1]-1<mi){
            mi=a[i]-a[i-1]-1;
            id=i;
        }
    }
    vector<int>run;
    fer(i,0,n){
        if(i==id)continue;
        run.push_back(a[i]);
    }
    mi=0;
    mi=max(check(run),mi);
    if(id>1){
        run[id-1]=a[id];
        mi=max(mi,check(run));
    }
    cout<<mi<<endl;
}
signed main(){
    cf{
        solve();
    }
    return 0;
}