比赛链接
本文发布于博客园，会跟随补题进度实时更新，若您在其他平台阅读到此文，请前往博客园获取更好的阅读体验。
跳转链接：https://www.cnblogs.com/TianTianChaoFangDe/p/18799072
开题 + 补题情况
和前三场比起来前期的签到题发挥稳定了许多，没有被卡很久，不过 1001 还是因为自己读错题挂了三发，不太应该。
虽然 rank 比之前有提升了，但是还是没有开出除了签到题之外的题，开的题价值不大，自己能力的提升还任重道远啊。
1006 - 进步
第一题就开的这个题。
此题涉及到修改某一天的进步量，查询某个时间区间的进步量，所以是单点修改，区间查询，很容易想到使用树状数组来维护。
点击查看代码
#include <bits/stdc++.h> #define inf32 1e9 #define inf64 2e18 #define ls o << 1 #define rs o << 1 | 1 using i64 = long long; using u64 = unsigned long long; using u32 = unsigned int; const int N = 2e5 + 9; template<typename T> struct BIT { std::vector<T> t; int n; BIT(int n) { this -> n = n; t = std::vector<T>(n + 1, T(0)); } int lowbit(int x) { return x & -x; } void add(int ix, T v) { for(int i = ix;i <= n;i += lowbit(i)) { t[i] += v; } } T query(int ix) { T res = 0; for(int i = ix;i > 0;i -= lowbit(i)) { res += t[i]; } return res; } }; void solve() { int n, q;std::cin >> n >> q; std::vector<i64> a(n + 1); for(int i = 1;i <= n;i ++) { std::cin >> a[i]; } BIT<i64> t(n + 1); for(int i = 1;i <= n;i ++) { t.add(i, a[i]); } i64 ans = 0; int sum = 0; while(q --) { int op;std::cin >> op; if(op == 1) { int x, y;std::cin >> x >> y; t.add(x, y - a[x]); a[x] = y; } else { sum ++; int l, r;std::cin >> l >> r; i64 e = t.query(r); i64 s = t.query(l - 1); e = e / 100; s = s / 100; ans ^= ((e - s) * sum); } } std::cout << ans << 'n'; }
1008 - 制衡
一开始看到题目，以为是一个需要人类智慧的 DP 题，直到发现了这两个重要线索：
- 允许某些段留空。
- (j) 的最大值刚好就是 (k)。
那么转化一下就可以发现，我们的选择，只会往下方及右下方转移。
那么 DP 转移方程就很明显了：(dp_{i, j} = max(dp_{i - 1, l}) + a_{i, j},l in [1, j])。
因此，在处理完了每一行的 DP 值后，要转化为前缀最值，便于优化转移。
时间复杂度：(O(nk))。
点击查看代码
#include <bits/stdc++.h> #define inf32 1e9 #define inf64 2e18 #define ls o << 1 #define rs o << 1 | 1 using i64 = long long; using u64 = unsigned long long; using u32 = unsigned int; const int N = 2e5 + 9; void solve() { int n, k; std::cin >> n >> k; std::vector<std::vector<int>> a(n, std::vector<int>(k)); auto dp = a; for(auto &i : a) { for(auto &j : i) { std::cin >> j; } } for(int j = 0;j < k;j ++) { dp[0][j] = a[0][j]; if(j > 0)dp[0][j] = std::max(dp[0][j], dp[0][j - 1]); } for(int i = 1;i < n;i ++) { for(int j = 0;j < k;j ++) { dp[i][j] = dp[i - 1][j] + a[i][j]; } for(int j = 1;j < k;j ++) { dp[i][j] = std::max(dp[i][j], dp[i][j - 1]); } } std::cout << dp[n - 1][k - 1] << 'n'; }
1005 - 持家
这个题和 CF2078D 有异曲同工之妙。
首先，根据小学数学知识可以知道，打 (x) 折的意思是当前价格乘 (x / 10)。
也就是说，打折是和当前价格相关的，而减价是和当前价格无关的，无论当前价格多少，减的是多少就是多少。
而根据乘法的知识我们又能知道，若当前的价格越高，优惠力度会越大，因此对于打折券，一定是价格越高的时候用越好。
那么，如果我们使用了降价券，就一定不会再次使用任何一张打折券，因为此时只需要交换打折券和降价券的使用顺序，先打折后降价，我们就能获得更大的优惠力度。
因此，此题的做法就很明显了，我们枚举打折券的使用数量，剩下的就是降价券的使用数量，对于打折券，越低的折扣越优先使用，对于降价券，越高的降价越优先使用，因此可以对两种券分别排序，然后记录一下前缀乘积和前缀和，然后枚举计算取最优解即可。
时间复杂度：(O(n))。
点击查看代码
#include <bits/stdc++.h> #define inf32 1e9 #define inf64 2e18 #define ls o << 1 #define rs o << 1 | 1 using i64 = long long; using u64 = unsigned long long; using u32 = unsigned int; const int N = 2e5 + 9; void solve() { double p;std::cin >> p; int n, k;std::cin >> n >> k; std::vector<double> dazhe; std::vector<i64> jian; for(int i = 1;i <= n;i ++) { int op;std::cin >> op; i64 v;std::cin >> v; if(op == 0) { dazhe.push_back(1.0 * v / 10); } else { jian.push_back(v); } } sort(dazhe.begin(), dazhe.end()); sort(jian.begin(), jian.end(), std::greater()); for(int i = 1;i < dazhe.size();i ++) { dazhe[i] *= dazhe[i - 1]; } for(int i = 1;i < jian.size();i ++) { jian[i] += jian[i - 1]; } double ans = p; for(int i = 0;i <= std::min(k, (int)dazhe.size());i ++) { int d = i; int j = k - d; if(d > dazhe.size() || j > jian.size())continue; double tmp = p; if(d <= 0) { tmp = tmp - jian[j - 1]; } else if(j <= 0) { tmp = tmp * dazhe[d - 1]; } else { tmp = tmp * dazhe[d - 1] - jian[j - 1]; } ans = std::min(ans, tmp); ans = std::max(ans, 0.00); } std::cout << ans << 'n'; } int main() { std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0); std::cout << std::fixed << std::setprecision(2); int t = 1;std::cin >> t; while(t --)solve(); return 0; }
1001 - 战斗爽
就是这个题，读假了，读成了怪物每多受一次攻击，下次受到的伤害就要继续减半。
这个题纯模拟题，按题意模拟即可。
我们开一个结构体，存储怪物的编号，血量，攻击力，被攻击次数的信息，并且按题意重载小于号运算符，存入一个优先队列 (pq)。
再开一个结构体，存储怪物的攻击力，编号信息，并且按攻击力从小到大重载小于运算符，存入一个优先队列 (sha)。
再开一个数组，存储怪物的血量。
然后就可以开始模拟了，只要我们还活着，并且怪物还有活着的，就从优先队列 (pq) 中取出堆顶的怪物，并对它进行攻击，更新怪物的血量和被攻击次数，如果他还有血量，并且被攻击次数不满 (k) 次，就放回优先队列 (pq) 中，若没有血量了，就添加到答案中，然后检查优先队列 (sha) 的堆顶怪物是否存活，若死亡，则弹出优先队列，直到堆顶怪物存活，并对我们进行攻击，按照此逻辑模拟至我们死掉或是怪物全死掉为止，输出答案。
时间复杂度：(O(tnlog n))，非常的极限。
点击查看代码
#include <bits/stdc++.h> #define inf32 1e9 #define inf64 2e18 #define ls o << 1 #define rs o << 1 | 1 using i64 = long long; using u64 = unsigned long long; using u32 = unsigned int; const int N = 2e5 + 9; struct monster { int id, g, x, cnt; bool operator < (const monster &v) const { if(x != v.x)return x > v.x; else if(g != v.g)return g > v.g; else if(id != v.id)return id > v.id; } }; struct guai { int id, g; bool operator < (const guai &v) const { return g < v.g; } }; void solve() { int n, u, k, h;std::cin >> n >> u >> k >> h; std::vector<int> a(n + 1); std::priority_queue<monster> pq; std::priority_queue<guai> sha; for(int i = 1;i <= n;i ++) { int g, x;std::cin >> g >> x; a[i] = x; pq.push({i, g, x, 0}); sha.push({i, g}); } int ans = 0; while(h && pq.size()) { monster now = pq.top(); pq.pop(); if(now.cnt)now.x -= u / 2; else now.x -= u; now.cnt ++; now.x = std::max(0, now.x); a[now.id] = now.x; if(now.x && now.cnt < k)pq.push(now); if(!now.x)ans ++; while(sha.size() && a[sha.top().id] == 0) { sha.pop(); } if(sha.size()) { h -= sha.top().g; h = std::max(h, 0); } } std::cout << ans << 'n'; }
