A. Set
题目描述
给你一个正整数 \(k\) 和由 \(l\) 至 \(r\) （含）的所有整数组成的集合 \(S\) 。
您可以执行以下两步运算的任意次数（可能为零）：
- 首先，从集合 \(S\) 中选择一个数字 \(x\) ，使得 \(S\) （包括 \(x\) 本身）中至少有 \(k\) 个 \(x\) 的倍数；
- 然后，从 \(S\) 中删除 \(x\) （注意没有删除任何其他内容）。
求可以进行的最大运算次数。
题解
如果\(x\)有\(k\)个倍数在集合\(S\)里，那这\(k\)个倍数一定包含\(x,2x,3x,\dots,kx\)。
故问题即为有多少数\(\times k \leq R\)。
二分找到最大的\(x\)满足此条件即可。
代码如下：
#include <bits/stdc++.h>
using namespace std;
#define lld long long
const int N = 1e6;
lld l, r, L, R, k;
void solve(){
scanf("%lld%lld%lld", &l, &r, &k);
L = l, R = r;
while(l < r){
lld mid = (l+r+1)>>1;
if(mid*k <= R) l = mid;
else r = mid-1;
}
if(L*k <= R) printf("%lld\n", l-L+1);
else printf("0\n");
}
int main(){
int t; scanf("%d", &t);
while(t--) solve();
return 0;
}
注意要开long long，要特判左边界是否能满足条件（即不能进行任何操作）。
B. Replacement
题目描述
您有一个长度为 \(n\) 的二进制字符串 \(^{\text{∗}}\) 。长度为 \(n\) 的二进制字符串 \(s\) ，而 Iris 会给出另一个长度为 \(n-1\) 的二进制字符串 \(r\) 。
艾里斯要和你玩一个游戏。在游戏过程中，你将对 \(s\) 执行 \(n-1\) 次操作。在第 \(i\) 次运算中 ( \(1 \le i \le n-1\) )：
- 首先，你要选择一个索引 \(k\) ，使得 \(1\le k\le |s| - 1\) 和 \(s_{k} \neq s_{k+1}\) 。如果无法选择这样的索引，那么就输了；
- 然后将 \(s_ks_{k+1}\) 替换为 \(r_i\) 。请注意，这样会使 \(s\) 的长度减少 \(1\) 。
如果所有的 \(n-1\) 操作都成功执行，那么你就赢了。
请判断你是否有可能赢得这盘棋。
\(^{\text{∗}}\) 二进制字符串是指每个字符都是 \(\mathtt{0}\) 或 \(\mathtt{1}\) 的字符串。
题解
考场上看错题了：“然后将\(s_ks_{k+1}\)替换为\(r_k\)”，百思不得其解。
实际上这是一道脑残题。
只要剩下的字符串中既有\(0\)又有\(1\)，我们就可以进行替换。（这是显然的）
在一次替换中，相当于将\(0\)和\(1\)的数量各自减少\(1\)，再将\(r_i\)的数量加上\(1\)。如果在最后一次替换结束前，\(0\)或\(1\)的数量减为\(0\)，则无法继续操作，否则则可能赢得这盘棋。
代码如下：
P.S.我偷懒了，这是CF题解代码
#include <bits/stdc++.h>
#define all(s) s.begin(), s.end()
using namespace std;
using ll = long long;
const int _N = 1e5 + 5;
void solve() {
int n; cin >> n;
string s, t; cin >> s >> t;
int cnt0 = count(all(s), '0'), cnt1 = n - cnt0;
for (int i = 0; i < n - 1; i++) {
if (cnt0 == 0 || cnt1 == 0) {
cout << "NO" << '\n';
return;
}
if (t[i] == '1') cnt0--;
else cnt1--;
}
cout << "YES" << '\n';
}
int main() {
int T; cin >> T;
while (T--) {
solve();
}
}
C. New Rating
题目描述
Hello, Codeforces Forcescode!
凯文曾经是 Codeforces 的参与者。最近，KDOI 团队开发了一个名为 Forcescode 的新在线裁判。
凯文参加过 Forcescode 上的 \(n\) 比赛。在第 \(i\) 次竞赛中，他的表现评分为 \(a_i\) 。
现在，他黑进了 Forcescode 的后台，将选择一个时间间隔 \([l,r]\) ( \(1\le l\le r\le n\) )，然后跳过这个时间间隔内的所有比赛。之后，他的评分将按以下方式重新计算：
- 最初，他的评分为 \(x=0\) ；
- 每次 \(1\le i\le n\) ，在第 \(i\) 次比赛之后、
- 如果 \(l\le i\le r\) ，则跳过这次比赛，评分保持不变；
- 否则，他的评级将根据以下规则更新：
- 如果 \(a_i>x\) ，他的评分 \(x\) 将增加 \(1\) ；
- 如果 \(a_i=x\) ，他的评分 \(x\) 将保持不变；
- 如果 \(a_i<x\) ，他的评分 \(x\) 将减少 \(1\) 。
如果凯文以最佳方式选择了区间 \([l,r]\) ，您必须帮助他找到重新计算后的最大可能评分。注意凯文至少要跳过一次比赛。
题解
简单题。
首先我们有一个性质：无论从哪一场比赛开始计分，开始时的评分越高越好。
总之就是评分越高越好。
我们可以贪心，将第\(i\)场比赛作为时间间隔\([l,r]\)的\(r+1\)，考虑此时的初始评分，一定源于前缀\([1,l]\)的累计评分。
令初始评分最高，求一个前缀最大值即可。
设\(mx(i)\)表示\(i\)的最高初始评分，于是我们有了一个dp方程。
\[f(i) = g(i,\max\{f(i-1), mx(i)\}) \]\(g(i, j)\)表示\(a_i\)和\(j\)相比较更新积分的操作过程，具体见题面。
答案即为\(\max\{f(n),\max_{i=1}^{n}mx(i)\}\)。
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5+5;
int n, a[N], st[N];
void solve(){
scanf("%d", &n);
int x = 0; st[0] = 0;
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
// a[i] = min(a[i], i);
st[i] = max(st[i-1], x);
if(a[i] > x) x++;
if(a[i] < x) x--;
} x = 0; int ans = 0;
for(int i = 1; i <= n; i++){
x = max(x, st[i]);
ans = max(ans, st[i]);
if(a[i] > x) x++;
if(a[i] < x) x--;
} if(x == n) x--;
ans = max(ans, x);
if(ans == n) ans--;
printf("%d\n", ans);
return ;
}
int main(){
int t; scanf("%d", &t);
while(t--) solve();
return 0;
}
注意必须选择至少一场比赛不参加，所以要特判答案\(=n\)的情况。
E. Common Generator
题目描述
对于两个整数 \(x\) 和 \(y\) ( \(x,y\ge 2\) )，当且仅当 \(x\) 可以通过执行下面的操作变换为 \(y\) 时，我们才说 \(x\) 是 \(y\) 的生成器：
- 选择 \(x\) 的除数 \(d\) （ \(d\ge 2\) ），然后将 \(x\) 增加 \(d\) 。
例如
- \(3\) 是 \(8\) 的生成器，因为我们可以进行以下运算： \(3 \xrightarrow{d = 3} 6 \xrightarrow{d = 2} 8\) ;
- \(4\) 是 \(10\) 的产生子，因为我们可以进行以下运算： \(4 \xrightarrow{d = 4} 8 \xrightarrow{d = 2} 10\) ;
- \(5\) 不是 \(6\) 的生成器，因为我们无法通过上述操作将 \(5\) 转化为 \(6\) 。
现在，凯文给出了一个数组 \(a\) ，它由一对不同的整数 \(n\) 组成（ \(a_i\ge 2\) ）。
你必须找到一个整数 \(x\ge 2\) ，使得每个 \(1\le i\le n\) 的生成数 \(x\) 都是 \(a_i\) 的生成数，或者确定这样的整数不存在。
题解
考场使用了更复杂的做法并WA on pretest3。
该分讨时就分讨啊。
由\(x\)转化为\(y\)的过程：\(x \rightarrow lcm(x, minp(y)) \rightarrow y\)。由此可见，若\(x > \frac{y}{minp(y)}\)且\(x \neq minp(y)\)，则\(x\)不能转化为\(y\)。
对于合数，\(2\)可以作为答案。
对于质数，其自身可以作为答案。
因此，如果有质数，将其作为答案，判断是否合法；没有质数时，将\(2\)作为答案，判断是否合法
；有多个质数时，必然无解。
代码还没写，但总之就是这样了。
后记
题图。
