Codeforces Round#634(Div3)解题报告

Codeforces Round#634(Div3)解题报告

U1S1,最近CF手速场好多,难道是国外友人在家无聊?, 发现自己代码能力好差, 很多简单题写了很多小毛病, Rank比学弟还低裂开

634.png

A.Candies and Two Sisters

题意

两个人分糖果, 总共有 $n$ 个糖果,要分成 $a, b$ 两份, 且满足 $a > b$ 问有多少种分法

题解

从中间分开即可

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double,int> P;
const int MAXN = 1e6 + 5;
const int INF = 0x3f3f3f3f;
int a[MAXN];
vector<int> b;
void solve() {
    int n;
    cin >> n;
    if(n % 2){
        cout << n / 2 << endl;
    } else {
        cout << n/2 - 1 << endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int T;
    cin >> T;
    //T = 1;
    while(T--) {
        solve();
    }
    return 0;
}

B.Construct the String

题意

构造一个长度为 $n$ 的字符串满足, 该字符串的任意一个长度为 $a$ 的字串其中包含 $b$ 个不同的字母

题解

两种情况:

  • $a > b$ 时,只需要填充 $b-1$ 个不同的字符,然后再填充 $a-(b-1)$ 个相同的字符, 最后把剩下的字符从头字符串的开头选取到末尾即可
  • $a \leq b$时, 随意填写即可

注意 $ASCLL$ 码, 手残 $WA$ 了好几发

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double,int> P;
const int MAXN = 1e6 + 5;
const int INF = 0x3f3f3f3f;
set<char> S;
int cnt[MAXN];
void solve() {
    int n, a, b;
    cin >> n >> a >> b;
    string ans = "";
    if(a > b) {
        for(int i = 1,j = 'a'; i <= b-1;i++,j++) {
            ans += char(j);
        }
        for(int i = 1,j = 'a' + b - 1;i <= a-b+1;i++){
            ans += char(j);
        }
        for(int i = a+1,j = 0;i <= n;i++,j++){
            ans += ans[j];
        }
    } else {
        for(int i = 1,j = 'a';i <= n;i++,j++){
            ans += char(j);
            if(j == 'z')
            	j = 'a'-1;
        }
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int T;
    cin >> T;
    //T = 1;
    while(T--) {
        solve();
    }
    return 0;
}

C. Two Teams Composing

题意

给定一个长度为 $n$ 的序列,将这个序列分为两组, 序列 $a$保证该序列中所有的 $a_i$ 都不相同, 序列 $b$满足该序列中所有的 $b_i$都相同, 且序列 $a$ 与 $b$ 长度相同, 问能分出的最长长度时多少。

题解

sum 代表一共出现过多少个不同的数字

cnt 出现的次数最多的数字出现的次数
讨论一下这两个的关系即可

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double,int> P;
const int MAXN = 1e6 + 5;
const int INF = 0x3f3f3f3f;
int cnt[MAXN];
int a[MAXN];
vector<int>b;
void solve() {
    int n, sum = 0;
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        cnt[a[i]]++;
        b.push_back(a[i]);
    }
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    int num = b.size(), mx = 0;
    for(int i = 0;i < b.size();++i){
    	mx = max(mx, cnt[b[i]]);
	}
	if(mx == num)
		cout << mx-1 << endl;
	else if(num > mx)
		cout << mx << endl;
	else
		cout << num << endl;
    for(int i = 1;i <= n;i++)
        cnt[a[i]] = 0;
    b.clear();
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int T;
    cin >> T;
    //T = 1;
    while(T--) {
        solve();
    }
    return 0;
}

D.Anti-Sudoku

题意

给定一个 $9*9$ 的数独矩阵, 任意改变一些数字,使得该数独矩阵满足

  • 每一列都有两个相同的数字
  • 每一行都有两个相同的数字
  • 每一个 $3*3$ 的矩阵都有两个相同的矩阵

题解

**题, 随便改就行

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double,int> P;
const int MAXN = 1e6 + 5;
const int INF = 0x3f3f3f3f;
string s[MAXN];
void solve() {
    for(int i = 1;i <= 9;i++){
        cin >> s[i];
    }
    for(int i = 1;i <= 9;i++){
        for(int j = 0;j < 9;j++){
            if(s[i][j] == '2')
            	cout << '3';
            else
            	cout << s[i][j];
        }
        cout << endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int T;
    cin >> T;
    //T = 1;
    while(T--) {
        solve();
    }
    return 0;
}

E.Three Blocks Palindrome

题意

给定一个长度为 $n$ 的序列, 找到该序列的一个子序列满足

$$ \underbrace{a,a\cdots,a}_{x}, \underbrace{b,b\cdots,b}_{y},\underbrace{a,a\cdots,a}_{x} $$

问该能找到的最长的子序列长度为多少

题解

由 $E2$ 的数据范围可知,该题的时间复杂度应该为 $O(200n)$ ,不过我用了 $O(200200*n)$ $cf$评测鸡真快。
记录一个前缀和 $cnt[i][j]$ 代表在 $i$ 位置, $j$ 出现的次数。同时统计 $E[j]$ 统计 $j$ 元素出现的位置。
通过枚举 $a$ 是谁,以及 $a$ 的长度,来推出 $b$, 以及 $b$ 的长度。

8
1 1 2 2 3 2 1 1
1 2 3 4 5 6 7 8

假设 $a$ 为 $1$, 该情况下可以选择的区间为, $a$的长度 $len$ 可以为 $1, 2$。当长度为 $2$时, 那么 $b$ 能取的位置则为 $1$ 中左数第二个出现的位置 $l$ ,与右数第二个出现的位置 $r$ 。有了 $b$ 能取得区间长度,再去枚举这个数字 $k$ 是谁, 通过统计的前缀和可以得出 $k$ 在 $[l, r]$ 内一共出现了 $cnt[r-1][k] - cnt[l][k]$次 ,则该子序列的长度为

$$ ans = max(ans, len*2 + cnt[r-1][k] - cnt[l][k]) $$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double,int> P;
const int MAXN = 1e6 + 5;
const int INF = 0x3f3f3f3f;
int a[MAXN];
vector<int> E[205];
int cnt[200005][200];
void solve() {
    int n;
    cin >> n;
    int mx = 0;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        for(int j = 1;j <= 200;j++){
        	if(j == a[i])
        		cnt[i][j] = cnt[i-1][j]+1;
        	else
        		cnt[i][j] = cnt[i-1][j];
		}
        E[a[i]].push_back(i);
        mx = max(mx, a[i]);
    }
    int ans = 1;
    for(int i = 1;i <= mx;i++){
        ans = max(ans, (int)E[i].size());
        for(int j = 0;j < E[i].size()/2;++j) {
            int posl = E[i][j], posr = E[i][E[i].size() - j - 1] - 1;
            for(int k = 1;k <= mx;k++){
                ans = max(ans, (j+1)*2 + cnt[posr][k] - cnt[posl][k]);
            }
        }
    }
    for(int i = 1;i <= n;i++){
    	for(int j = 1;j <= 200;j++)
    		cnt[i][j] = 0;
	}
    for(int i = 1;i <= 200;i++){
    	E[i].clear();
	}
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T;
    cin >> T;
    //T = 1;
    while(T--) {
        solve();
    }
    return 0;
}

待补

F