Codeforces Round #712 (Div. 2) A~E题解

2023-10-24 18:31:46

文章目录

A. Déjà Vu

  • 解题思路
    我们很容易发现，对于一个回文串，如果其中的字母不全是 a a a，那么我们总能找到一个不对称的地方插入 a a a，使得回文串变成非回文串，最简单的就是直接插入头部或尾部。但有一点要注意的是，对于非回文串，我们插入之后需要判断是否变成了回文串，如果在头部插入不满足要求，那么在尾部插入一定满足要求。
  • AC代码
/**
  *@filename:A
  *@author: pursuit
  *@CSDNBlog:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-04-06 18:45
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;

int t;
string s;
bool check(string s){
    int l=0,r=s.size()-1;
    while(l<=r){
        if(s[l]!=s[r])return false;
        l++,r--;
    }
    return true;
}
void solve(){
    //简单分析一下，如果是回文的，那么如果一直添加a可行，说明该字符串中不是全部的a。
    bool flag=true;
    for(auto &x:s){
        if(x!='a'){
            flag=false;
            break;
        }
    }
    if(!flag){
        cout<<"YES\n";
        if(check(s+"a")){
            cout<<"a"+s<<endl;
        }
        else{
            cout<<s+"a"<<endl;
        }
    }
    else{
        cout<<"NO\n";
    }
}
int main(){
    while(cin>>t){
        while(t--){
            cin>>s;
            solve();
        }
    }
    return 0;
}

B. Flip the Bits

  • 解题思路
    题目要求我们翻转前缀（该前缀 0 , 1 0,1 0,1的数量要相等）使得 a − > b a->b a−>b。那么我们值得注意的就是更改前缀的条件为 0 , 1 0,1 0,1的数量要相等，更改的结果是前缀原来相等的与 b b b不相等，原来不相等的与 b b b相等。 所以我们可以遍历字符串 a a a，统计 0 , 1 0,1 0,1的数量。这里可以利用cnt+=(a[i]=='1')-(a[i]=='0)，这样相当于是 1 1 1就加 1 1 1，是 0 0 0就加 0 0 0，这样保证了 0 , 1 0,1 0,1数量相等的时候 c n t = 0 cnt=0 cnt=0。
    我们知道 b b b是需要由 a a a变过来的，那么在遍历的过程中如果遇到需要更改的地方且更改不了（这里需要更改的意思是此时 a a a和 b b b的连续位置 i , i + 1 i,i+1 i,i+1处存在且仅存在一处不相等，那么我这里必须做出更改，因为这种情况无法通过后续的前缀翻转实现相等。），那么自然是无解的。为了方便判断，我们在 a , b a,b a,b字符串后面加上一个 0 0 0，为了提供最后的参照。

  • AC代码

/**
  *@filename:B
  *@author: pursuit
  *@CSDNBlog:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-04-06 18:58
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;

int t,n;
string a,b;
void solve(){
    //思维题，我们更改前缀的条件就是0和1的数量要相等。那么如果位于需要更改的地方确不能更改，那就无解了。
    int cnt=0;
    a+="0",b+="0";//这么做的目的是为了判断更好的前缀。
    for(int i=0;i<n;i++){
        cnt+=((a[i]=='1')-(a[i]=='0'));//统计0和1的数量是否相等。
        //判断该位置是否可以交换。
        if((a[i]==b[i])!=(a[i+1]==b[i+1])&&cnt!=0){
            //如果出现不相等，且目前不可翻转。
            puts("NO");
            return;
        }
    }
    puts("YES");
}
int main(){
    while(cin>>t){
        while(t--){
            cin>>n;
            cin>>a>>b;
            solve();
        }
    }
    return 0;
}

C. Balance the Bits

  • 解题思路
    核心点就是 1 1 1相同， 0 0 0不同，所以如果我们需要构建一个平衡的括号序列，那么必须满足：

    1. 首尾必须为 1 1 1，因为括号序列第一位必须为(, 最后一位必须为), 即两个序列首尾两个位置必须相同。
    2. 0 , 1 0,1 0,1的个数必须都是偶数，因为 1 1 1会导致两个括号序列 a , b a,b a,b的位置相同，而如果是奇数的，那么会产生一个没有配对的括号给 0 0 0处理，而 0 0 0会让 a , b a,b a,b所填位置不相同，故无法配对构造出两组序列。

    满足了以上，我们就可以构造序列了，双指针扫描序列中的1，左边放左括号，右边放右括号，而剩余的0则轮流放左右括号即可。这样保证了所有的左右括号都能配对上，且构建出的序列 a , b a,b a,b是不相同的。

D. 3-Coloring

  • 解题思路
    我们简单考虑一下，如果没有颜色禁止，我们构造出一个 n × n n\times n n×n的颜色不相邻的矩阵是完全 o k ok ok的，且只需要 2 2 2中颜色，如下，以 4 × 4 4\times 4 4×4的矩阵为例：

    2 1 2 1
    1 2 1 2
    2 1 2 1
    1 2 1 2

    我们是以 x + y x+y x+y的奇偶性来确定颜色填放的，即奇数位放 1 1 1号颜料，偶数位放 2 2 2号颜料。
    那么回到这个问题，现在每轮声明一种禁止的颜色，那么我们该怎么处理呢？实际上已经显而易见了，我们完全可以用 3 3 3代替 1 1 1或 2 2 2来填充。例如当我们的奇数位已经填充完了，而偶数位还没填充，且 2 2 2号颜料已经被禁止了，那么我们就可以使用 3 3 3来填充了，这样保证了相邻单元格颜色不相同。

  • AC代码

/**
  *@filename:D
  *@author: pursuit
  *@CSDNBlog:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-04-07 09:07
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;

vector<pair<int,int> > od,ev;//存储坐标。od存储x+y为奇数的坐标。ev存储x+y为偶数的坐标。
int n;
void solve(){
}
int main(){
    while(cin>>n){
        od.clear(),ev.clear();
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if((i+j)&1){
                    od.push_back({i,j});
                }
                else{
                    ev.push_back({i,j});
                }
            }
        }
        int temp;
        int od_index=0,ev_index=0;//索引。
        for(int i=1;i<=n*n;i++){
            cin>>temp;
            //根据temp判断。
            if(temp!=1&&od_index<od.size()){
                //如果没有禁用颜色1
                cout<<1<<" "<<od[od_index].first<<" "<<od[od_index].second<<endl;
                od_index++;
            }
            else if(temp!=2&&ev_index<ev.size()){
                //如果没有禁用颜色2，就填2.
                cout<<2<<" "<<ev[ev_index].first<<" "<<ev[ev_index].second<<endl;
                ev_index++;
            }
            else{
                //否则根据情况来填充。
                if(od_index<od.size()){
                    cout<<3<<" "<<od[od_index].first<<" "<<od[od_index].second<<endl;
                    od_index++;
                }
                else{
                    cout<<3<<" "<<ev[ev_index].first<<" "<<ev[ev_index].second<<endl;
                    ev_index++;
                }
            }
            cout.flush();
        }
    }
    return 0;
}

E. Travelling Salesman Problem

  • 解题思路
    我们知道 ( i , j ) (i,j) (i,j)的花费为 m a x ( c [ i ] , a [ j ] − a [ i ] ) max(c[i],a[j]-a[i]) max(c[i],a[j]−a[i])，对此进行处理即为 c [ i ] + m a x ( 0 , a [ j ] − ( a [ i ] + c [ i ] ) ) c[i]+max(0,a[j]-(a[i]+c[i])) c[i]+max(0,a[j]−(a[i]+c[i]))。题目中要求每个点只需要走一次，且最后回到起点，这其实就是一个环，所以已知最低的代价就是 ∑ i = 0 n − 1 c [ i ] \sum_{i=0}^{n-1}c[i] ∑i=0n−1​c[i]。由于是环，所以我们的起点可以任意选择，同样路径也是可以由我们决定的，所以我们固然是需要贪心的选择，根据 m a x ( 0 , a [ j ] − ( a [ i ] + c [ i ] ) ) max(0,a[j]-(a[i]+c[i])) max(0,a[j]−(a[i]+c[i]))可知，当 a [ j ] < = ( a [ i ] + c [ i ] ) a[j]<=(a[i]+c[i]) a[j]<=(a[i]+c[i])的时候，我们是可以无额外消耗的直接到达的点，那么我们就可以理解将 a [ i ] + c [ i ] a[i]+c[i] a[i]+c[i]理解为我们所能到达的最远距离，那么这个目标实际上就是将点依次纳入我们已经到达了的点，并统计额外消耗即可。那么我们必然是需要对 a a a进行排序，这样才可以保证我们的额外消耗最小（即抵消的越多）。按顺序维护一个当前的最远距离，不断向后纳入新点并更新最远距离和额外花费。
    e x t r a C o s t = ∑ j = 2 n m a x ( 0 , a [ j ] − m a x ( a [ i ] + c [ i ] ) ) ( i < j ) extraCost = \sum_{j=2}^{n}max(0,a[j]-max(a[i]+c[i]))(i<j) extraCost=∑j=2n​max(0,a[j]−max(a[i]+c[i]))(i<j)， a [ i ] + c [ i ] a[i]+c[i] a[i]+c[i]即当前已经到达的点的最远距离。

  • AC代码

/**
  *@filename:E
  *@author: pursuit
  *@CSDNBlog:unique_pursuit
  *@email: 2825841950@qq.com
  *@created: 2021-04-07 12:26
**/
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 100000 + 5;
const int mod = 1e9+7;

int n;//城市数量。
struct node{
    int a,c;
}citys[maxn];
bool cmp(node &a,node &b){
    return a.a<b.a; 
}
void solve(){
}
int main(){
    while(cin>>n){
        ll ans=0;
        for(int i=0;i<n;i++){
            cin>>citys[i].a>>citys[i].c;
            ans+=citys[i].c;//加上必要花费。
        }
        sort(citys,citys+n,cmp);//排序。
        int maxx=citys[0].a+citys[0].c;//维护一个最远距离。相当于内部是一个集合。
        for(int i=1;i<n;i++){
            ans+=max(0,citys[i].a-maxx);
            maxx=max(maxx,citys[i].a+citys[i].c);
        }
        cout<<ans<<endl;
    }
    solve();
    return 0;
}
上一篇：算法详解：这一篇带你入门贪心算法！！


下一篇：V - Distpicker 一个简单易用的地区选择器