来源：Educational Codeforces Round 170 (Rated for Div. 2)
A. Two Screens
题意
给两个屏幕，两种操作，每种操作一秒，求让两个屏幕显示两个指定字符串的最短时间
操作：
- 在一个屏幕的字符串后加任意一个字符
- 把一个屏幕的内容复制粘贴到另一个屏幕
思路
先弄出相同前缀，复制一下，然后不相同的只能用操作1来一个一个加
代码
string s1, s2;
int main() {
IOS;
int t;
cin >> t;
while (t--) {
cin >> s1 >> s2;
int same = 0;
for (int i = 0; i < min(s1.length(), s2.length()); i++) {
if (s1[i] == s2[i]) same++;
else break;
}
cout << s1.length() + s2.length() - same + (same == 0 ? 0 : 1) << endl;
}
return 0;
}
B. Binomial Coefficients, Kind Of
思路
这边建议，复制粘贴给的代码，然后打印一下
代码
const int MOD = 1e9 + 7;
long long ksm(long long a, long long b, long long MOD) {
long long res = 1;
while (b) {
if (b & 1) res = (res * a) % MOD;
a = (a * a) % MOD;
b >>= 1;
}
return res;
}
int main() {
IOS;
// int C[20][20];
// for (int n = 0; n < 20; n++) { // loop over n from 0 to N-1 (inclusive)
// C[n][0] = 1;
// C[n][n] = 1;
// for (int k = 1; k < n; k++) // loop over k from 1 to n-1 (inclusive)
// C[n][k] = C[n][k - 1] + C[n - 1][k - 1];
// }
// for (int n = 0; n < 20; n++) { // loop over n from 0 to N-1 (inclusive)
// for (int k = 1; k < n; k++) { cout << C[n][k] << " "; }
// cout << endl;
// }
int t;
cin >> t;
vector<int> n(t), k(t);
for (int &i : n) cin >> i;
for (int &i : k) cin >> i;
for (int i = 0; i < t; i++) {
cout << ksm(2, k[i], MOD) << endl;
}
return 0;
}
C. New Game
题意
一堆数字，第一次选 \(x\)，以后只能选 \(x\) 或 \(x+1\)
所选牌中不同的牌不超过 \(k\) 张
思路
首先想用个 \(cnt\) 数组存每张牌的数量，用双指针维护一个窗口，窗口内的都是连续的数字
由于每次扩充窗口的时候要判断下一个位置和当前位置差值是不是1，我选择把中间连接的 \(cnt\) 搞成一个负数
遇到负数就重新搞窗口
代码
const int N = 4e5 + 10;
int cnt[N];
map<int, int> mp;
void solve() {
mp.clear();
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
int tmp;
cin >> tmp;
mp[tmp]++;
}
int turn = 0; // 有多少数和间隔
int pre = 0;
for (auto [num, c] : mp) {
if (num != pre && num != pre + 1) {
cnt[++turn] = -1;
}
pre = num;
cnt[++turn] = c;
}
int l = 1, r = 0;
int now = 0;
int ans = 0;
while (r <= turn && l <= turn) {
while (r - l + 1 < k && now + cnt[r + 1] >= now && r + 1 <= turn) now += cnt[++r];
ans = max(ans, now);
if (now + cnt[r + 1] < now || r + 1 > turn) { // 如果是遇到负数
now = 0;
l = r + 2;
r++;
} else {
now -= cnt[l++];
}
}
cout << ans << endl;
}
D. Attribute Checks
题意
升级打怪，给一个序列，按顺序，遇到0就是升级，但是有两个属性
遇到正数和负数分别代表遇到针对两个属性的怪了
只有自身的对应属性大于等于怪才能打败
问最多打得过多少怪（检查点）
思路
一眼dp，但是n范围有点不对劲，先不管
- 思路
\(dp[i][j]\) 表示 到目前为止有 \(i\) 分，这 \(i\) 分有 \(j\) 分分配给智力，也就是 \(k=i-j\) 分给体力那么到第 \(i+1\) 个 \(0\) 之前，最多能过多少检查点
第 \(i\) 分加在智力上
\(dp[i][j]=dp[i-1][j-1] + ([i-1,i]区间内小于j的正数数量) + (区间内小于k的|负数|数量)\)
第 \(i\) 分加在体力上
\(dp[i][j]=dp[i-1][j] + (区间内小于j的正数数量) + (区间内小于k的|负数|数量)\)
比如按如下顺序 \(0(i-1),2, -2, -3, 0(i)\)
当碰到2时，需要对 \(dp[i-1][2\dots(i-1)]\)
每次遇到0的时候都要来一遍状态转移，这是不会t的，但是每次碰到检查点要来一次+1这就是 \(O(mn)\)
- 优化
由于有m分，可以先把两分之间的那些用一个差分数组存起来，每次遇到0的时候再操作一下，t不了一点
代码
空间也可以优化，不过这题都可
在原本的数组后面补一个0，好处理点
const int N = 2e6 + 10;
const int M = 5005;
int a[N];
int dp[M][M];
signed main() {
// IOS;
int n, m;
cin >> n >> m;
rep(i, 0, M) fill_n(dp[i], M, 0);
for (int i = 0; i < n; i++) cin >> a[i];
a[n] = 0;
m++;
n++;
int zero = 0;
vector<int> dif(m + 5, 0);
for (int i = 0; i < n; i++) {
if (a[i] == 0) {
zero++;
for (int j = 1; j <= m + 1; j++) dif[j] += dif[j - 1];
dp[zero][0] = dp[zero - 1][0] + dif[0];
for (int j = 1; j <= zero; j++) {
dp[zero][j] = max(dp[zero - 1][j - 1] + dif[j - 1], dp[zero - 1][j] + dif[j]);
}
for (int j = 0; j <= m; j++) dif[j] = 0;
} else if (a[i] > 0) {
if (a[i] <= zero) {
dif[a[i]]++;
dif[zero + 1]--;
}
} else if (a[i] < 0) {
if (-a[i] <= zero) {
dif[0]++;
dif[zero + a[i] + 1]--;
}
}
}
int ans = 0;
for (int i = 0; i <= zero; i++) {
ans = max(ans, dp[zero][i]);
}
cout << ans;
return 0;
}