Educational Codeforces Round 170 (Rated for Div. 2) ABCD来源：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;
}
