经验总结

  1. 首页 > 生活 > >

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

生活百科

E题解知识点：线性dp 。
考虑设 \(dp[i]\) 为造成不少于 \(i\) 点伤害的最小时间 。
先考虑 \(p_1,p_2\) 单独射击的转移：
dp[i] = min(dp[max(0LL, i - (p1 - s))] + t1, dp[max(0LL, i - (p2 - s))] + t2);再考虑，\(p_2\) 在 \(p_1\) 的 \(j\) 轮时间中调整，配合 \(p_1\) 在第 \(j\) 轮同时射击 。此时\(p_1\) 伤害是 \((j-1)(p_1 - s)\) ，\(p_2\) 伤害是 \(\lfloor\frac{(j\cdot t_1 - t_2)}{t_2}\rfloor(p_2-s)\) ，同时射击伤害 \(p_1+p_2-s\) ，共计 \((j-1)(p_1 - s) + \lfloor\frac{(j\cdot t_1 - t_2)}{t_2}\rfloor(p_2-s) + (p_1+p_2-s)\)。（同理 \(p_1\) 配合 \(p_2\) 同时射击） 。
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(h^2)\)
空间复杂度 \(O(h)\)
代码#include <bits/stdc++.h>#define ll long longusing 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;}F题解知识点：排列组合，枚举 。
我们考虑每个点对答案的贡献，显然是从他第一次出现开始计算 。
比如某点在第 \(i\) 组区间出现，那么已经进行了 \(i-2\) 次操作了，产生 \(3^{i-2}\) 个集合 。在这之后还有 \(n-i+1\) 次操作，如果操作时另一个区间有这个点，那么或和且能继承这个点继续；如果没有这个点，那么或和异或能继承这个点继续，注意无论以后有没有这个点都只有两个分支能使这个点有贡献，所以共 \(2^{n-i+1}\) 个集合是有这个点的，最后总贡献是 \(3^{i-2}2^{n-i+1}\)。
要特别注意，第一个区间出现的点，之前的操作也是 \(0\) 次 ，并且之后的操作也只有 \(n-1\) 次，最终通式是 \(3^{\max(i-2,0)}2^{\min(n-i+1,n-1)}\)。
接下来考虑如何记录某个点第一次出现的位置 \(lst[i]\)。朴素枚举是 \(n^2\) 的，我们需要优化 。显然出现过的点之后跳过就行了，我们记录每个点能跳跃到的位置 \(nxt[i]\) 即可，对于区间 \([l,r]\) ，如果某个点 \(i\) 没出现过，那么 \(nxt[i]\) 可以更新为 \(r[i]\) ；否则出现过，我们需要跳跃，同时更新这个点以后能跳跃到的位置，\(nxt'[i] = \max(nxt[i],r),i = nxt[i]\)，注意需要保存一下旧位置，再更新完 \(nxt[i]\) 再更新 \(i\)。
时间复杂度 \(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;}

经验总结扩展阅读


上一篇：函数柯里化实现sum函数

下一篇：Spring 深入——IoC 容器 02