Educational Codeforces Round 137 (Rated for Div. 2) A-F

比赛链接

知识点：数学。

44 位密码，由两个不同的数码组成，一共有 C24C42 种方案。从 10−n10−n 个数字选两个，有 C210−nC10−n2 种方案。结果为 3(10−n)(9−n)3(10−n)(9−n)。

时间复杂度 O(n)O(n)

空间复杂度 O(1)O(1)

#include <bits/stdc++.h>#define ll long long using namespace std; bool solve() { int n; cin >> n; for (int i = 1;i <= n;i++) { int x; cin >> x; } cout << 3 * (10 - n) * (9 - n) << '\n'; return true;} int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0;}

知识点：构造。

显然最小价值是 22 。把 11 和 22 分两端放即可。

时间复杂度 O(n)O(n)

空间复杂度 O(1)O(1)

#include <bits/stdc++.h>#define ll long long using namespace std; bool solve() { int n; cin >> n; for (int i = 2;i <= n;i++) cout << i << ' '; cout << 1 << '\n'; return true;} int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0;}

知识点：贪心。

发现，可以将一段连续的盖子向左移，等效于把最后一个盖子移到第一个左边。因此，找到一个无盖且右边连续有盖的位置，从连续有盖的一段选一个最小的和无盖的位置交换，如果最小的比无盖的大那就不交换。

时间复杂度 O(n)O(n)

空间复杂度 O(n)O(n)

#include <bits/stdc++.h>#define ll long long using namespace std; int a[200007];bool solve() { int n; cin >> n; string s; cin >> s; s = "?" + s; for (int i = 1;i <= n;i++) cin >> a[i]; for (int i = 1;i <= n - 1;i++) { if (s[i] == '0' && s[i + 1] == '1') { int mi = i; for (int j = i + 1;j <= n && s[j] == '1';j++) { if (a[j] < a[mi]) mi = j; } swap(s[i], s[mi]); } } int sum = 0; for (int i = 1;i <= n;i++) { if (s[i] == '1') sum += a[i]; } cout << sum << '\n'; return true;} int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { if (!solve()) cout << -1 << '\n'; } return 0;}

知识点：枚举。

第一个串显然是从第一个 11 开始截取到最后，现在考虑从第一个串截取出第二个串填补第一个串的 00 。

显然要从第一个 00 开始填。注意到，只有 00 前面的 11 可以通过截取向右移动与 00 重合。枚举前面每个 11 通过截取与第一个 00 重合即可，截取方法有很多，第一种，以各个 11 为起点，截取固定长度，保持 11 与 00 重合；第二种，从第一个 11 开始截取，截取不同长度，使各个 11 和 00 重合。

发现复杂度是和从第一个 11 开始连续 11 的长度有关，但因为是随机数据，因此不可能太长，可以看作常数。

时间复杂度 O(n)O(n)

空间复杂度 O(n)O(n)

#include <bits/stdc++.h> using namespace std; int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; string s; cin >> s; int pos = s.find('1'); if (!~pos) { cout << 0 << '\n'; return 0; } string s1 = s.substr(pos); pos = s1.find('0'); string ans = s1; for (int i = 0;i < pos;i++) { string s2 = s1; for (int j = pos;j < s1.size();j++) { if (s1[j - pos + i] == '1') s2[j] = '1'; } ans = max(ans, s2); } cout << ans << '\n'; return 0;}/* #include <bits/stdc++.h> using namespace std; string elz(string s) { for (int i = 0;i < s.size() - 1;i++) if (s[i] == '1') return s.substr(i); return s.substr(s.size() - 1);}int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; string s; cin >> n >> s; bitset<1000005> a(s), b(s); string ans = a.to_string(); for (int i = 1;i <= 10;i++) ans = max(ans, (a | (b >> i)).to_string()); cout << elz(ans) << '\n'; return 0;} */

知识点：线性dp。

考虑设 dp[i]dp[i] 为造成不少于 ii 点伤害的最小时间。

先考虑 p1,p2p1,p2 单独射击的转移：

dp[i] = min(dp[max(0LL, i - (p1 - s))] + t1, dp[max(0LL, i - (p2 - s))] + t2);

再考虑，p2p2 在 p1p1 的 jj 轮时间中调整，配合 p1p1 在第 jj 轮同时射击。此时 p1p1 伤害是 (j−1)(p1−s)(j−1)(p1−s) ，p2p2 伤害是 ⌊(j⋅t1−t2)t2⌋(p2−s)⌊(j⋅t1−t2)t2⌋(p2−s) ，同时射击伤害 p1+p2−sp1+p2−s ，共计 (j−1)(p1−s)+⌊(j⋅t1−t2)t2⌋(p2−s)+(p1+p2−s)(j−1)(p1−s)+⌊(j⋅t1−t2)t2⌋(p2−s)+(p1+p2−s) 。（同理 p1p1 配合 p2p2 同时射击）。

ll dmg = (j - 1) * (p1 - s) + (t1 * j - t2) / t2 * (p2 - s) + (p1 + p2 - s);dp[i] = min(dp[i], dp[max(0LL, i - dmg)] + t1 * j);

时间复杂度 O(h2)O(h2)

空间复杂度 O(h)O(h)

#include <bits/stdc++.h>#define ll long long using namespace std; ll dp[5007];int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int p1, p2; ll t1, t2; cin >> p1 >> t1; cin >> p2 >> t2; int h; ll s; cin >> h >> s; dp[0] = 0; for (int i = 1;i <= h;i++) { dp[i] = min(dp[max(0LL, i - (p1 - s))] + t1, dp[max(0LL, i - (p2 - s))] + t2); for (int j = 1;j <= i;j++) { if (t1 * j >= t2) { ll dmg = (j - 1) * (p1 - s) + (t1 * j - t2) / t2 * (p2 - s) + (p1 + p2 - s); dp[i] = min(dp[i], dp[max(0LL, i - dmg)] + t1 * j); } if (t2 * j >= t1) { ll dmg = (j - 1) * (p2 - s) + (t2 * j - t1) / t1 * (p1 - s) + (p1 + p2 - s); dp[i] = min(dp[i], dp[max(0LL, i - dmg)] + t2 * j); } } } cout << dp[h] << '\n'; return 0;}

知识点：排列组合，枚举。

我们考虑每个点对答案的贡献，显然是从他第一次出现开始计算。

比如某点在第 ii 组区间出现，那么已经进行了 i−2i−2 次操作了，产生 3i−23i−2 个集合。在这之后还有 n−i+1n−i+1 次操作，如果操作时另一个区间有这个点，那么或和且能继承这个点继续；如果没有这个点，那么或和异或能继承这个点继续，注意无论以后有没有这个点都只有两个分支能使这个点有贡献，所以共 2n−i+12n−i+1 个集合是有这个点的，最后总贡献是 3i−22n−i+13i−22n−i+1 。

要特别注意，第一个区间出现的点，之前的操作也是 00 次 ，并且之后的操作也只有 n−1n−1 次，最终通式是 3max(i−2,0)2min(n−i+1,n−1)3max(i−2,0)2min(n−i+1,n−1) 。

接下来考虑如何记录某个点第一次出现的位置 lst[i]lst[i] 。朴素枚举是 n2n2 的，我们需要优化。显然出现过的点之后跳过就行了，我们记录每个点能跳跃到的位置 nxt[i]nxt[i] 即可，对于区间 [l,r][l,r] ，如果某个点 ii 没出现过，那么 nxt[i]nxt[i] 可以更新为 r[i]r[i] ；否则出现过，我们需要跳跃，同时更新这个点以后能跳跃到的位置，nxt′[i]=max(nxt[i],r),i=nxt[i]nxt′[i]=max(nxt[i],r),i=nxt[i] ，注意需要保存一下旧位置，再更新完 nxt[i]nxt[i] 再更新 ii 。

时间复杂度 O(n)O(n)

空间复杂度 O(n)O(n)

#include <bits/stdc++.h> using namespace std; const int mod = 998244353; int l[300007], r[300007], lst[300007], nxt[300007];int pow2[300007], pow3[300007];int main() { std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int n; cin >> n; memset(lst, -1, sizeof(lst)); pow2[0] = 1; pow3[0] = 1; for (int i = 1;i <= n;i++) { pow2[i] = 1LL * pow2[i - 1] * 2 % mod; pow3[i] = 1LL * pow3[i - 1] * 3 % mod; } for (int i = 1;i <= n;i++) cin >> l[i] >> r[i]; for (int i = n;i >= 1;i--) { for (int j = l[i];j <= r[i];j++) { if (lst[j] == -1)lst[j] = i, nxt[j] = r[i]; else { int tmp = nxt[j]; nxt[j] = max(nxt[j], r[i]); j = tmp; } } } int ans = 0; for (int i = 0;i <= 300000;i++) { if (lst[i] == -1) continue; ans = (ans + 1LL * pow3[max(lst[i] - 2, 0)] * pow2[min(n - lst[i] + 1, n - 1)]) % mod; } cout << ans << '\n'; return 0;}