CF补题 950-Div.3-20250102
Dashboard - Codeforces Round 950 (Div. 3) - Codeforces
A：
题目大意：给出一个字符串，要求重复的字母必须 \(\ge m\) ，求缺失字母总个数
#include <iostream>
#include <map>
using namespace std;
map<char, int> mp;
int main()
{
int T;
cin >> T;
while (T--)
{
int n, m;
int ans = 0;
char a;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a;
mp[a]++;
}
for (char i = 'A'; i <= 'G'; i++) {
if (m - mp[i] >= 0)
ans += m - mp[i];
}
cout << ans << endl;
mp.clear();
}
}
用 map 存储字符串中每个字母的个数，最后计算需要增添的字母总个数
B：
题目大意：给出一个序列，标记其中一个元素，从大到小排序后，前 \(k\) 个元素是否能包含这个标记的元素
#include <iostream>
using namespace std;
int a[105];
int fa;
bool cmp(int a, int b) {
return a > b;
}
int main()
{
int T;
cin >> T;
while (T--)
{
memset(a, 0, sizeof a);
int n, f, k;
cin >> n >> f >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (i == f) fa = a[i];
}
sort(a + 1, a + n + 1, cmp);
if (a[k] > fa) cout << "NO" << endl;
else if (a[k] < fa || (a[k] == fa && a[k + 1] < fa)) cout << "YES" << endl;
else cout << "MAYBE" << endl;
}
}
sort 从大到小排序，判断前 \(k\) 个元素是否能包含 \(fa\)
- 第 \(k\) 个元素的值小于 \(fa\) ，绝对包含
- 第 \(k\) 个元素的值大于 \(fa\) ，绝对不包含
- 第 \(k\) 个元素的值等于 \(fa\) ，存在两种可能
- 值为 \(fa\) 的元素只有一个，那么肯定包含
a[k] == fa && a[k + 1] < fa - 值为 \(fa\) 的元素不止一个，有可能包含
- 值为 \(fa\) 的元素只有一个，那么肯定包含
C：
题目大意：给定两个序列a,b，再给定一个修改序列d，问能否通过修改序列使得第一个序列变为第二个序列
\((c_i,d_i)\) 表示 d 序列中的第 \(c_i\) 项能把 a 中一个元素变为 \(d_i\) ，必须依次执行 d 的变化操作
#include <iostream>
#include <map>
using namespace std;
int a[200010];
map<int, int> b, mp;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T;
cin >> T;
while (T--)
{
bool flag = 0;
int n,cnt=0;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
int tb;
for (int i = 1; i <= n; i++) {
cin >> tb;
b[tb]++;
if (tb != a[i]) {
mp[tb]++;
cnt++;
}
}
int m, d;
cin >> m;
for (int i = 1; i <= m; i++) {
cin >> d;
if (mp[d]) {
mp[d]--;
cnt--;
}
if (i == m && !b[d]) flag = 1;
}
if (cnt|| flag == 1) cout << "NO" << endl;
else cout << "YES" << endl;
mp.clear();
b.clear();
}
}
用 map 来存 b和 mp 数组，mp 数组用来 记录那些元素需要发生改变
最后输入 d ，每次判断当前的元素是否能够被用来改变 a 数组，如果能，那么mp数组内的对应元素 \(-1\)
当输入到 d 的最后一个元素时，判断这个元素是否存在 b 中，如果不在 b 中，那么我们就需要把 a 数组内的某个元素改为不需要的值，这样就不能做到把 a 完全转化成 b
多测要清空
D：
题目大意：给定一个序列a，判断删去其中一个数后能否使a的最大公约数数组 b 实现不减序列
#include <iostream>
using namespace std;
int a[200010];
int b[200010];
bool l[200010];
bool r[200010];
int gcd(int x, int y) {//计算gcd
return y == 0 ? x : gcd(y, x % y);
}
int main()
{
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];//读入a
for (int i = 1; i < n; i++) b[i] = gcd(a[i], a[i + 1]);//预处理gcd数组b
l[0] = 1;
for (int i = 1; i < n; i++) l[i] = l[i - 1] && b[i - 1] <= b[i];
r[n] = r[n - 1] = 1;
b[n] = 1e9;
for (int i = n - 2; i > 0; i--) r[i] = r[i + 1] && b[i + 1] >= b[i];
bool ans = l[n - 2] || r[2];
for (int i = 2; i < n; i++) {
int t = gcd(a[i - 1], a[i + 1]);
ans |= l[i - 2] && r[i + 1] && (b[i - 2] <= t && b[i + 1] >= t);
}
if (ans) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
预处理b数组后，从数组两侧进行扫描，判断b数组的什么位置开始，是一段完整的不减序列
l从左侧开始扫描，当b[i]小于b[i-1]时说明截至到i，前面的序列都不减r从右侧开始扫描，当b[i]大于b[i+1]时说明截至到i，之后的序列都不减
可以删去一个数a[i]，这个数会影响到 gcd(a[i-1],a[i])和 gcd(a[i],a[i+1])
判断删去 a[i] 是否合理时，需要判断 l[i-2]和 r[i+1] 是否都处于不减区间内（必要条件）
同时还需要判断 b[i - 2] <= t && b[i + 1] >= t 删去的这个数能否和前后构成不减序列
为什么不枚举 a 数列的两个端点呢？
这是因为端点的影响在 bool ans = l[n - 2] || r[2]; 这一步已经做出了判断
-
l[n - 2]：这个条件检查了如果移除数组a的最后一个元素a[n-1]，剩余数组的最大公约数序列是否非递减 -
r[2]：这个条件检查了如果移除数组a的第一个元素a[1]，剩余数组的最大公约数序列是否非递减
例如 2,4,8,1，这个序列，b数组就为 2,4,1
l = {1, 1, 1, 0, 0}
r = {0, 0, 0, 1, 1}
ans = 1||0