Codeforces Round 921 (Div. 2)题解（A-C）

本文主要是介绍Codeforces Round 921 (Div. 2)题解（A-C），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A

We Got Everything Covered!

思路

可以采用划分区域的思想。

共划分为 n 个区域
每一个区域含有所包含的前 k 个字母

证明：

正确性：无论所要求的字符串str为什么，只需要在区域i中取出 $s t r [i]$ 即可
最优性：若需要的字符串全部是a，那么s必定含有n个a，对于其他的字母同理。
最后可以得到，s最少的字母数量为 $\cdot k$

代码

#include<bits/stdc++.h>
using namespace std;inline void Print(int k){for(int i = 0; i < k; i++){putchar('a' + i);}
}
int main()
{int T;cin >> T;while(T--){int n, k;scanf("%d%d", &n, &k);for(int i = 1; i <= n; i++){Print(k);}puts("");}return 0;
}

B

A Balanced 问题集et?

思路

暴力枚举gcd。

如果一群数字的gcd已经确定，那么其他数字的值便为gcd的倍数。

n 不可以整除 gcd：在这种情况下，这群数字的和一定不会是n（舍去这种情况）
n 可以整除gcd，但是商却小于k，这种情况下，即使每一个数字均为gcd，结果仍然大于n，不可能。
n 可以整除gcd，商大于等于k，此时可以把若干个gcd合并为数组中的一个元素。

代码

#include<bits/stdc++.h>
using namespace std;
int ans;int x, n;inline void solve(int k){if(x / k >= n){ans = max(ans, k);}
}
int main()
{int T;cin >> T;while(T--){scanf("%d%d", &x, &n);ans = 0;for(int i = 1; (long long)i * i <= (long long)x; i++){if(x % i == 0){solve(i);solve(x / i);}}printf("%d\n", ans);}return 0;
}

C

Did We Get Everything Covered?

思路

首先对所给定的s进行分组，从左向右扫描，当刚好扫描满一个区间的时候，确定边界，继续扫描下一个区间。

区间为包含所有前 k 个字母的区间

如果已有的区间大于等于n，那么根据A中的知识，必定满足条件
如果区间个数不足n，那么进行构造。
- 我们选取每一个区间的最后一个元素（每个区间最后一个元素一定仅仅出现一次，这使得这一个元素将用完一个区间）
- 当超过已有的区间的时候，我们选取最后一个不完整区间中的没有出现的元素。

代码

#include<bits/stdc++.h>
using namespace std;
int n,  k, m;
typedef bitset<30> bs;
bs last, target;
const int N = 2e3;
char s[N];inline int getNum(char x){return x - 'a' + 1;
}bool solve(vector<pair<int, int>> &fenzu){bs tmp;int lpos = 1;tmp.reset();for(int i = 1; i <= m; i++){tmp.set(getNum(s[i]));if(tmp.count() >= k){tmp.reset();fenzu.push_back({lpos, i});lpos = i + 1;if(fenzu.size() >= n){return true;}}}last = tmp;return false;
}
int main()
{int T;cin >> T;while(T--){scanf("%d%d%d", &n, &k, &m);vector<pair<int, int>> fenzu;scanf("%s", s + 1);target.reset();for(int i = 1; i <= k; i++){target.set(i);}if(solve(fenzu)){puts("YES");}else{puts("NO");int cnt = 0;for(auto t : fenzu){putchar(s[t.second]);cnt++;}char theChar;for(int i = 1; i <= k; i++){if(!last.test(i)){theChar = 'a' - 1 + i;break;}}while(cnt < n){putchar(theChar);cnt++;}puts("");}}return 0;
}