CF #634 div3 题解

视频题解：https://www.bilibili.com/video/BV1YK41157F7

A-Candies and Two Sisters

签到

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int T,N;
int main(){
    // debug;
    ios;
    cin>>T;
    while(T--){
        cin>>N;
        cout<<((N&1)? N/2 : N/2-1)<<'\n';
    }
    return 0;
}

B-Construct the String

循环节

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int T;
int main(){
    // debug;
    ios;
    cin>>T;
    while(T--){
        int n,a,b;cin>>n>>a>>b;
        char c = 'a',e = 'a'+b-1;
        for(int i = 1;i<=n;i++){
            cout<<c;
            c++;
            if(c>e) c = 'a';
        }
        cout<<'\n';
    }
    return 0;
}

C-Two Teams Composing

map

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int T,N;
map<int,int> mp;
int main(){
    // debug;
    ios;
    cin>>T;
    while(T--){
        mp.clear();
        cin>>N;
        for(int i = 1;i<=N;i++){
            int cur;cin>>cur;
            mp[cur]++;
        }
        int ans = 0,sz = mp.size();
        for(auto &p:mp){
            ans = max(ans,min(p.sc,sz-1));
            ans = max(ans,min(p.sc-1,sz));
        }
        cout<<ans<<'\n';

    }



    return 0;
}

D-Anti-Sudoku

思维

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int T;
char str[20][20];
int main(){
    // debug;
    ios;
    cin>>T;
    while(T--){
        for(int i = 1;i<=9;i++){
            for(int j = 1;j<=9;j++){
                cin>>str[i][j];
            }
        }
        for(pii xy:vector<pii>{{1,1},{4,2},{7,3},{2,4},{5,5},{8,6},{3,7},{6,8},{9,9}}){
            int x = xy.fs,y = xy.sc;
            if(++str[x][y] > '9') str[x][y] = '1';
        }
        for(int i = 1;i<=9;i++){
            for(int j = 1;j<=9;j++){
                cout<<str[i][j];
            }
            cout<<'\n';
        }
    }



    return 0;
}

E1-Three Blocks Palindrome (easy version)

枚举

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
using namespace std;

int T,N;
int arr[maxn];
int sz[30][2020];
void init(){
    for(int i = 1;i<=26;i++){
        for(int j = 1;j<=N;j++){
            if(arr[j] == i) sz[i][j] = sz[i][j-1]+1;
            else sz[i][j] = sz[i][j-1];
        }
    }
}
int main(){
    // debug;
    ios;
    cin>>T;
    while(T--){
        cin>>N;
        for(int i = 1;i<=N;i++) cin>>arr[i];
        init();
        int ans = 0;
        for(int l = 1;l<=N;l++){
            map<int,int> mp;int mx = 0;
            for(int r = l;r<=N;r++){
                if(++mp[arr[r]] > mx) mx = mp[arr[r]];
                for(int i = 1;i<=26;i++){
                    ans = max(ans,2*min(sz[i][l-1],sz[i][N] - sz[i][r]) + mx);
                }
            }
        }
        cout<<ans<<'\n';
    }


    return 0;
}

E2-Three Blocks Palindrome (hard version)

枚举优化

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5+10;
using namespace std;

int T,N;
int pre[205][maxn];
int arr[maxn];
int solve(){
    vector<int> adj[201];
    int ans = 0;
    for(int i = 1;i<=200;i++){
        for(int j = 1;j<=N;j++) {
            pre[i][j] = pre[i][j-1] + (arr[j] == i);
            if(arr[j] == i) adj[i].push_back(j);
        }
        ans = max(ans,pre[i][N]);
    }
    for(int i = 1;i<=200;i++){
        int len = adj[i].size();
        for(int j = 0;j<len/2;j++){
            int l = adj[i][j],r = adj[i][len-j-1];
            for(int k = 1;k<=200;k++){
                ans = max(ans,pre[k][r-1] - pre[k][l] + 2*(j+1));
            }
        }
    }
    return ans;
}

int main(){
    // debug;
    ios;
    cin>>T;
    while(T--){
        cin>>N;
        for(int i = 1;i<=N;i++) cin>>arr[i];
        cout<<solve()<<'\n';
    }    

    return 0;
}

F-Robots on a Grid

思维+倍增

#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug  freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
#define PI acos(-1)
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+10;
char col[maxn],dir[maxn],buf[maxn];
bool from[2][maxn];
int nxt[21][maxn];
using namespace std;

int T,N,M;
void init_st(){
    for(int i = 1;i<=N*M;i++){
        if(dir[i] == 'U') nxt[0][i] = i-M;
        if(dir[i] == 'D') nxt[0][i] = i+M;
        if(dir[i] == 'L') nxt[0][i] = i-1;
        if(dir[i] == 'R') nxt[0][i] = i+1;
    }
    for(int i = 1;i<=20;i++){
        for(int j = 1;j<=N*M;j++){
            nxt[i][j] = nxt[i-1][nxt[i-1][j]];
        }
    }
}

void solve(){
    for(int i = 1;i<=N*M;i++){
        int pos = i;
        for(int j = 20;j>=0;j--){
            if((N*M>>j) & 1) pos = nxt[j][pos];
        }
        from[col[i] == '1'][pos] = true;
    }
    int cnt = 0,black = 0;
    for(int i = 1;i<=N*M;i++){
        if(from[0][i]) cnt++,black++;
        else if(from[1][i]) cnt++;
    }
    cout<<cnt<<" "<<black<<'\n';
}

int main(){
    // debug;
    ios;
    cin>>T;
    while(T--){
        cin>>N>>M;
        memset(from,false,sizeof from);
        for(int i = 1;i<=N*M;i++) cin>>col[i];
        for(int i = 1;i<=N*M;i++) cin>>dir[i];
        init_st();
        solve();
    }



    return 0;
}

Ryuichi的算法分享文章被收录于专栏

分享我的一些算法题解，致力于把题解做好，部分题解可能会采用视频的形式来讲解。