坐地铁时口糊了6题，回来写时结果爆
long long，0没有逆元，卡了好久
A – Online Shopping (abc332 A)题目大意
线上购物，买了\(n\)种物品，分别给出它们的单价和数量。
若总价少于\(s\)元，则需要支付 \(k\)元邮费，否则包邮。
问总价多少。
解题思路
求个和判断下是否加邮费即可。
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, s, k; cin >> n >> s >> k; int tot = 0; while (n--) { int p, q; cin >> p >> q; tot += p * q; } if (tot < s) tot += k; cout << tot << '\n'; return 0;}B – Glass and Mug (abc332 B)题目大意
一个容量为\(G\)的玻璃杯和一个容量为 \(K\)的马克杯。依次进行以下操作 \(k\)次：
- 若玻璃杯水满了，则把水倒掉
- 否则，若马克杯空的，则马克杯装满水
- 否则，将马克杯的水导入玻璃杯，直到马克杯没水了或玻璃杯满了
问最后玻璃杯和马克杯的水的容量。
解题思路
\(k\)只有 \(100\)，按照上述操作模拟即可。
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int k, g, m; cin >> k >> g >> m; int l = 0, r = 0; while (k--) { if (l == g) l = 0; else if (r == 0) r = m; else { int d = min(r, g - l); l += d; r -= d; } } cout << l << ' ' << r << '\n'; return 0;}C – T-shirts (abc332 C)题目大意
有a衬衫和b衬衫。初始有\(m\)件a衬衫。
给定 \(n\)天，每天要么洗衣服，要么吃饭，要么打比赛。
- 吃饭的话，可以选择穿一件a衬衫或一件b衬衫。
- 打比赛的话，只能穿一件b衬衫。
- 洗衣服的话，之前穿过的衬衫在之后都可以再穿。
问最少需要多少件\(b\)衬衫才能满足要求。
解题思路
对于吃饭，我们肯定是能穿a衬衫就穿a衬衫。
因此记录已经穿了的a衬衫和b衬衫件数，每到洗衣服天就重置使用过的 a衬衫和b衬衫。
这期间b衬衫的最大值即为答案。
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; string s; cin >> n >> m >> s; int cnt = 0, ans = 0; int plain = m; for (auto& i : s) { if (i == '0') { plain = m; cnt = 0; } else if (i == '1') { if (plain > 0) --plain; else { ++cnt; ans = max(ans, cnt); } } else if (i == '2') { ++cnt; ans = max(ans, cnt); } } cout << ans << '\n'; return 0;}D – Swapping Puzzle (abc332 D)题目大意
给定两个矩阵\(a,b\)。
对矩阵\(a\)操作，问最小的操作次数变成 \(b\)。
每次操作，交换相邻两行或者交换相邻两列。
解题思路
注意到矩阵大小只有\(5 \times 5\)，因此最终的情况数只有 \(5! \times 5! = 1e4\)，因此直接\(BFS\)搜索即可。
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int h, w; cin >> h >> w; vector<vector> a(h, vector(w, 0)), b(h, vector(w, 0)); for (auto& i : a) for (auto& j : i) cin >> j; for (auto& i : b) for (auto& j : i) cin >> j; queue<pair<int, vector<vector>>> team; set<vector<vector>> dis; team.push({0, a}); dis.insert(a); int ans = -1; while (!team.empty()) { auto [c, u] = team.front(); if (u == b) { ans = c; break; } team.pop(); for (int i = 0; i < h - 1; ++i) { auto v = u; v[i].swap(v[i + 1]); if (dis.find(v) == dis.end()) { team.push({c + 1, v}); dis.insert(v); } } for (int i = 0; i < w - 1; ++i) { auto v = u; for (int j = 0; j < h; ++j) swap(v[j][i], v[j][i + 1]); if (dis.find(v) == dis.end()) { team.push({c + 1, v}); dis.insert(v); } } } cout << ans << '\n'; return 0;}E – Lucky bag (abc332 E)题目大意
给定\(n\)个商品的价值\(w_i\)，分成 \(d\)个袋子里，使得 \(\frac{\sum_{i=1}^{d}(x_i-\bar{x})^2}{d}\)最小，其中 \(x_i\)表示第 \(i\)个袋子的价值和。允许有空袋子。
解题思路
注意到\(\bar{x}\)和\(d\)都是固定的，实际上问题就是确定每个袋子的 \(x_i\)。
注意到\(n\)只有 \(15\)，可以设最朴素的 \(dp[i][j]\)表示将 \(i\)——二进制表示的商品分成 \(j\)个袋子的\(\sum_{i=1}^{d}(x_i-\bar{x})^2\)的最小值。
转移则枚举\(i\)的子集作为一个新袋子，计算该袋子的代价来转移。时间复杂度是 \(O(n3^n)\)，这个时间比较紧 ，预处理每个商品表示\(i\)的价值和，时间复杂度是\(O(n2^n + 3^n)\)
枚举子集的方法和复杂度可参见oi-wiki
这做法貌似就是2023CCPC秦皇岛的签到题J题
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, d; cin >> n >> d; vector w(n); for (auto& i : w) cin >> i; int tot = accumulate(w.begin(), w.end(), 0); double ave = 1. * tot / d; int up = (1 << n); double inf = numeric_limits::max(); vector cost(up, 0); for (int i = 0; i < up; ++i) { for (int l = 0; l > l) & 1)); } cost[i] = (cost[i] - ave) * (cost[i] - ave); } vector dp(up, inf); dp[0] = 0; for (int j = 1; j <= d; ++j) { vector dp2(up, inf); for (int i = 0; i < up; ++i) { for (int k = i; 1; k = ((k - 1) & i)) { if (dp[i ^ k] != inf) { dp2[i] = min(dp2[i], dp[i ^ k] + cost[k]); } if (k == 0) break; } } dp.swap(dp2); } cout << fixed << setprecision(10) << dp.back() / d << '\n'; return 0;}注意到\(\bar{x}\)可以通分，使得 \(dp\)的计算不涉及浮点数，但注意此时 \(dp\)值会爆 long long值（可达\(1e20\)）。
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, d; cin >> n >> d; vector w(n); for (auto& i : w) cin >> i; int tot = accumulate(w.begin(), w.end(), 0); int up = (1 << n); __int128 inf = numeric_limits::max(); vector sum(up, 0); for (int i = 1; i < up; ++i) { for (int l = 0; l > l) & 1)); } } vector dp(up, inf); dp[0] = 0; for (int j = 1; j <= d; ++j) { vector dp2(up, inf); for (int i = 0; i < up; ++i) { for (int k = i; 1; k = (k - 1) & i) { if (dp[i ^ k] != inf) { __int128 cost = sum[k]; __int128 w = (1ll * d * cost - 1ll * tot) * (1ll * d * cost - 1ll * tot); dp2[i] = min(dp2[i], dp[i ^ k] + w); } if (k == 0) break; } } dp.swap(dp2); } cout << fixed << setprecision(10) << dp.back() * 1. / (d * d * d) << '\n'; return 0;}F – Random Update Query (abc332 F)题目大意
给定一个数组\(a\)，以及 \(m\)次操作。
每次操作，给定 \(l,r,x\)，随机对 \(a[l..r]\)中的一个元素改成 \(x\)。
问每个 \(x\)的期望值。
解题思路
考虑一个操作对其中一个数的影响，如果原来数的期望值是\(a\)，则进行这次操作后，设 \(len = r – l + 1, p = \frac{1}{len}, q = 1 – p\)，则 \(a = a * q + x * p\)。
这是一个区间乘+区间加的操作，用线段树维护即可。
神奇的代码
#include using namespace std;using LL = long long;const int N = 2e5 + 8;const int mo = 998244353;class segment {#define lson root << 1#define rson root << 1 | 1 public: LL k[N << 2]; LL b[N << 2]; LL lazyk[N << 2]; LL lazyb[N <> 1; build(lson, l, mid); build(rson, mid + 1, r); k[root] = 1; b[root] = 0; lazyk[root] = 1; lazyb[root] = 0; } void pushdown(int root) { if (lazyk[root] != 1 || lazyb[root] != 0) { k[lson] = k[lson] * lazyk[root] % mo; lazyk[lson] = lazyk[lson] * lazyk[root] % mo; b[lson] = (b[lson] * lazyk[root] % mo + lazyb[root]) % mo; lazyb[lson] = (lazyb[lson] * lazyk[root] % mo + lazyb[root]) % mo; k[rson] = k[rson] * lazyk[root] % mo; lazyk[rson] = lazyk[rson] * lazyk[root] % mo; b[rson] = (b[rson] * lazyk[root] % mo + lazyb[root]) % mo; lazyb[rson] = (lazyb[rson] * lazyk[root] % mo + lazyb[root]) % mo; lazyk[root] = 1; lazyb[root] = 0; } } void update(int root, int l, int r, int L, int R, int vk, int vb) { if (L <= l && r > 1; if (L mid) update(rson, mid + 1, r, L, R, vk, vb); } array get(int root, int l, int r, int pos) { if (l == r) { return {k[root], b[root]}; } pushdown(root); int mid = (l + r) >> 1; if (pos >= 1; } return qwq;}long long inv(long long x) { return qpower(x, mo - 2); }int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector a(n); for (auto& i : a) cin >> i; seg.build(1, 1, n); for (int i = 0; i > l >> r >> x; int len = (r - l + 1); int p = inv(len); int q = 1 - p; if (q < 0) q += mo; seg.update(1, 1, n, l, r, q, 1ll * p * x % mo); } for (int i = 0; i = mo) ans -= mo; cout << ans << " \n"[i == n - 1]; } return 0;}也可以依次考虑每个位置，所有操作对这个位置的影响。从左到右考虑每个位置时，会有一些操作有影响，有一些操作没有影响。
对于当前位置\(i\)，第 \(j\)个操作对其的贡献为， \(x_j \times p_j\) \times q_{tot}\(,\)p,q$就是上述提到的成功概率（修改该数）和失败概率（修改了其他数）。而这个 \(q\)就是该操作之后的所有操作的失败概率的乘积。
换句话说，当第\(j\)个操作有影响时，它对前面的操作的贡献都会乘以 \(q_j\)，当它没影响时，则乘以\(q_j\)的逆元。 这需要一个区间乘的操作，但有个问题， 当\(q_j\)为 \(0\)（即 \(len=1\)）时，其是没有逆元的。 因此可能无法消除影响。
为了避免逆元，我们将这类影响体现在合并上：对于每个操作，维护两个值\(b = xp, k = q\)，即成功的期望值和失败概率。两个操作合并时，成功期望值的和与失败概率则变为 \(b = b_l \times k_r + b_r, k = k_l \times k_r\)。最后答案就是\(a_i \times k_1 + b_1\)。消除该操作影响，则令 \(b=0, k=1\)即可。这就需要单点修改和区间查询。
神奇的代码
#include using namespace std;using LL = long long;const int N = 2e5 + 8;const int mo = 998244353;class segment {#define lson root << 1#define rson root << 1 | 1 public: LL k[N << 2]; LL b[N <> 1; build(lson, l, mid); build(rson, mid + 1, r); k[root] = 1; b[root] = 0; } void modify(int root, int l, int r, int pos, int vk, int vb) { if (l == r) { k[root] = vk; b[root] = vb; return; } int mid = (l + r) >> 1; if (pos = mo) b[root] -= mo; }} seg;long long qpower(long long a, long long b) { long long qwq = 1; while (b) { if (b & 1) qwq = qwq * a % mo; a = a * a % mo; b >>= 1; } return qwq;}long long inv(long long x) { return qpower(x, mo - 2); }int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector a(n); for (auto& i : a) cin >> i; vector<array> op(m); for (auto& i : op) { cin >> i[0] >> i[1] >> i[2]; --i[0]; --i[1]; } vector add(m), mine(m); iota(add.begin(), add.end(), 0); iota(mine.begin(), mine.end(), 0); ranges::sort(add, [&](int a, int b) { return op[a][0] < op[b][0]; }); ranges::sort(mine, [&](int a, int b) { return op[a][1] < op[b][1]; }); seg.build(1, 1, m); auto l = add.begin(), r = mine.begin(); for (int i = 0; i < n; ++i) { while (l != add.end() && op[*l][0] <= i) { int len = op[*l][1] - op[*l][0] + 1; LL p = inv(len); LL q = (1 - p); if (q < 0) q += mo; seg.modify(1, 1, m, *l + 1, q, p * op[*l][2] % mo); l = next(l); } while (r != mine.end() && op[*r][1] = mo) ans -= mo; cout << ans << " \n"[i == n - 1]; } return 0;}G – Not Too Many Balls (abc332 G)题目大意
给定\(n\)个颜色球的数量\(a_i\)和 \(m\)个盒子的容量\(b_i\)，以及一个附加条件：第 \(j\)个盒子最多能放的第 \(i\)种颜色的球的数量为 \(i \times j\)。
问最多能放多少个球。
解题思路
一类感觉一个决策会牵着到很多条件的决策问题，容易想到使用网络流解决。
- 源点\(S \to\)颜色\(i\)，容量为 \(a_i\)
- 颜色\(i \to\)盒子\(j\)，容量为 \(i \times j\)
- 盒子\(i \to\)汇点\(t\)，容量为 \(b_i\)
跑个最大流即为答案。
但边数有\(5e2 \times 5e5 = 2e8\)，寄。
考虑到最大流等于最小割，我们需要割去最小代价的边集，使得\(S \to T\)无法到达。
注意到上述边分了三类，且第一类的边数量很少，只有 \(500\)。
假定我们选择割去若干条第一类边，即对应的颜色被割去了，而与源点相连的点（颜色）集合为 \(X\)。 考虑盒子点\(j\)，此时仍有\(S \to X \to j \to T\)这样的路径，对与该盒子点来说，就两种决策：
- 决策1:把 \(j \to T\)这条边割掉，代价是 \(b_j\)
- 决策2:把 \(X \to j\)这些边割掉，代价是 \(j \times \sum_{i \in X} i\)
很显然我们贪心地选择代价小的割掉，且各个盒子点的决策都是独立的。因此问题就剩下如何决定割去的颜色，这会影响到\(\sum_{i \in X}\)的值。
注意到 \(\sum_{i \in X}\)的大小只有 \(O(n^2)\)，可以枚举这个和\(x\)，当这个和固定后，问题就是我选择编号和为 \(x\) 的最小\(a_i\) 和是多少，这是一个简单的\(0/1\)背包问题 ，设\(dp[i]\)表示割去颜色标号和为 \(i\) 的最小\(a_i\)和，转移则考虑每个颜色是否割去两种情况。
得到 \(dp[i]\)后，如果枚举 标号和再依次判断每个盒子点的决策，复杂度是 \(O(n^2m)\)，这还是过不了。
注意到 判断决策的条件是\(l \times j – b_j < 0\)，即\(l < \frac{b_j}{j}\)。当从小到大枚举割去的颜色标号和\(i\)时， 未被割去的颜色标号和\(l = \sum_{k=1}^{n} k – i\)是递减的。因此会有越来越多的盒子点决策从决策2变成决策1。
因此事先对盒子点根据\(\frac{b_i}{i}\)降序排列，然后类似双指针的方式维护决策2和决策1的边界。最终的时间复杂度是 \(O(n^3 + n + m)\)
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector a(n), b(m); for (auto& i : a) cin >> i; for (auto& i : b) cin >> i; int up = 0; for (int i = 1; i <= n; ++i) up += i; constexpr LL inf = 1e18; LL totb = accumulate(b.begin(), b.end(), 0ll); vector dp(up + 1, inf); dp[0] = 0; for (int i = 1; i = i; --j) { dp[j] = min(dp[j], dp[j - i] + cost); } } LL ans = inf; vector id(m); iota(id.begin(), id.end(), 0); ranges::sort(id, [&](int x, int y) { return b[x] * (y + 1) > b[y] * (x + 1); }); auto pos = id.begin(); LL cost2 = 0; LL cost3 = totb; for (int i = 0; i <= up; ++i) { LL cost1 = dp[i]; LL l = up - i; while (pos != id.end() && l * (*pos + 1) <= b[*pos]) { cost2 += *pos + 1; cost3 -= b[*pos]; pos = next(pos); } ans = min(ans, cost1 + l * cost2 + cost3); } cout << ans << '\n'; return 0;}