Codeforces Round #531 (Div. 3) 题解及训练总结

这场A不会B读不懂E写不出来,其他题都比较简单。一开场15分钟A不掉A题,转头看B题,30分钟左右放弃了,读不懂题。开始开C题,一发A,然后开D题,贪心完之后匆匆交题,有点担心不一定会A,也是一发A。E题想出正解之后开始写,写了20mins wa了两发,剩下30mins开F,F并没有在时限内写完。
总结了一下:
1. A,B题开不出来时候,放弃开其他题是可以的。
2. 心态一定要稳住。
题解:

A.
题意:给你一个n,让你把1-n的数分成两拨,使其sum差值最小,n1e9。
思路:跟%4有关,只要是4个数一定可以组合起来,剩下的多出来的,如果=1,2一定不能两两差0。
代码:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int main(){
    IO;
    int n;cin>>n;
    if(n%4==0||n%4==3) cout <<0<<'\n';
    else cout << 1<< '\n';
    return 0;
}

B.
题意:给n(n1e4)个数字,k(1e4)个颜料,染色。要求同色数字权值不一样,且每一个颜料都用过。
思路:判断重复的数字是否超过k,然后构造输出。构造的时候对跑两层循环,对同种权值的数,按编号染色,编号>=kmod即可。
代码:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 5005;
int num[maxn],ans[maxn];
map<int,int>mp;

int main(){
    IO;
    int n,k;cin>>n>>k;vector<int>a(n);forn(i,n)cin>>a[i];
    forn(i,n){
        mp[a[i]]++;
        if(mp[a[i]]>k)return cout << "NO" <<'\n',0;
    }
    cout <<"YES"<<'\n';
    int cnt = 0;
    for(auto x:mp){
        forn(i,n)if(a[i]==x.first) ans[i] = ++cnt,cnt%=k;
    }
    forn(i,n) cout<< ans[i]<<' ';
    cout <<'\n';

    return 0;
}

C
题意:A和B在玩游戏,A可以将一个数字的权值减小x,B可以将一个数字的权值增加y。一个数字但凡<=0,B将不能把它加回去。他们的回合共有10^100次,问给你n个数字,A最多能把多少数字权值减小<=0。n100, 数字权值不超过1e5
思路:很容易想到x>y时一定可以将所有数字变回去,此外则就看A可以一次减回去的数字。
代码:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int main(){
    IO;
    int n,x,y;cin>>n>>x>>y;
    if(x>y) return cout <<n<<'\n',0;vector<int>a(n);
    forn(i,n) cin>>a[i];
    int cnt = 0;
    forn(i,n){
        if(a[i]<=x) cnt++;
    }
    cout << (cnt+1)/2<<'\n';
    return 0;
}

D.
题意:给一个字符串长度3e5,均为012构成。每次可将一个字符改动为0|1|2,现要求最小操作次数情况下,构造字典序最小的012相等个数的字符串。
思路:贪心。

  1. 0个数不够时优先按顺序把非0的改为0
  2. 1个数不够时优先按顺序把多出来的2改为1
  3. 2个数不够时倒着把非2改为2
  4. 此时1个数若还不够倒着把0改为1
    代码:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int num[4];

int main(){
    IO;
    int n;cin>>n;
    string s;cin>>s;
    forn(i,n){
        int x = s[i]-'0';
        num[x]++;
    }
    forn(i,n)if(num[0]<n/3){
        if(num[s[i]-'0']>n/3){
            num[s[i]-'0']--;
            num[0]++;
            s[i] = '0';
        }
    }
    forn(i,n)if(num[1]<n/3){
        if(num[s[i]-'0']>n/3&&s[i]!='0'){
            num[s[i]-'0']--;
            num[1]++;
            s[i] = '1';
        }
    }
    for(int i = n-1;i>=0;i--)if(num[2]<n/3){
        if(num[s[i]-'0']>n/3){
            num[s[i]-'0']--;
            num[2]++;
            s[i] = '2';
        }
    }
    for(int i = n-1;i>=0;i--)if(num[1]<n/3){
        if(num[s[i]-'0']>n/3){
            num[s[i]-'0']--;
            num[1]++;
            s[i] = '1';
        }
    }
    for(auto x:s) cout<<x;
    return 0;
}

E.
题意:给2e5长度的数组a,构造出一个等大小的b数组。要求满足:1. b0=0 2.bi+1 = bi|| bi+1 = bi +1 3. a数组中若ai = aj则bi = bj。求b数组有多少种构造方法。
思路:若下一位可以转变为+1或不变,则方案数2,若不能则方案数1。我们用一个状态数组来构造当前位置是否可以为双状态。
代码:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int maxn = 2e5+5;
const int mod = 998244353;
int pos[maxn];
map<int,int>mp;

int main(){
    IO; 
    int n;cin>>n;
    vector<int>a(n);
    forn(i,n) cin>>a[i];
    forn(i,n){
        if(!mp[a[i]]) mp[a[i]] = i+1;
        else pos[mp[a[i]]-1]--,pos[i]++;
    }
    int cnt = pos[0];ll res = 1;
    for1(i,n-1){
        if(cnt==0) (res *= 2)%=mod; 
        cnt+=pos[i];
    }
    cout <<res<<'\n';





    return 0;
}

F.
题意:给你一个矩阵长n=16,高m=1e4。每次你只能交换其中的任意两行,交换可以无数次,构造出一个矩阵使得按从上到下从左到右的顺序排好,使得任意相邻数相差值>=k。求k最大。
思路:n=16,提示状压。本来有16!个状态,现在缩减到2^16次方用01表示状态。此题不同之处就是需要考虑首尾。
代码:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int maxn = 1e4+5;
const int inf = 0x3f3f3f3f;

int a[20][maxn],d[20][20],dd[20][20],dp[16][1<<16][16];
bool vis[16][1<<16][16];

int main(){
    IO;
    int n,m;cin>>n>>m;
    forn(i,n) forn(j,m) cin>>a[i][j];
    forn(i,n){
        forn(j,n){
            int gg = inf;
            forn(k,m){
                gg = min(abs(a[i][k]-a[j][k]),gg);
            }
            d[i][j] = gg;
            gg = inf;
            forn(k,m-1){
                gg = min(abs(a[i][k+1]-a[j][k]),gg);
            }
            dd[i][j] = gg;
        }
    }
    //cerr<<(1<<4)<<'\n';
    int ans = 0;
    forn(s,n){
        vis[s][1<<s][s] = 1;
        dp[s][1<<s][s] = inf;
        forn(i,1<<n){
            forn(j,n)if(vis[s][i][j]){
                forn(k,n){
                    int x = 1<<k;
                    if(i&x)continue;
                    //cerr<<s<<' '<<i<<' '<<j<<'\n';
                    dp[s][i|x][k] = max(dp[s][i|x][k],min(d[k][j],dp[s][i][j]));
                    vis[s][i|x][k] = 1;
                }
            }
        }
        int gg = 0;
        forn(i,n){
            int x = min(dp[s][(1<<n)-1][i],dd[s][i]);
            gg = max(gg,x);
            //cerr<<x<<'\n';
        }
        ans = max(ans,gg);
    }
    //forn(i,1<<n){
      //  cout<<dp[2][i][3]<<' ';
    //}
   // cerr<<'\n';
    cout << ans <<'\n';

    return 0;
}
上一篇:wordpress 区分多语言站点


下一篇:php 如何将image图片转化为字符串