U1S1，最近CF手速场好多，难道是国外友人在家无聊？， 发现自己代码能力好差， 很多简单题写了很多小毛病， Rank比学弟还低裂开
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