坐地铁时口糊了6题，回来写时结果爆
long long，0没有逆元，卡了好久
A - Online Shopping (abc332 A)
题目大意
线上购物，买了\(n\)种物品，分别给出它们的单价和数量。
若总价少于\(s\)元，则需要支付 \(k\)元邮费，否则包邮。
问总价多少。
解题思路
求个和判断下是否加邮费即可。
神奇的代码
#include <bits/stdc++.h>
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 <bits/stdc++.h>
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 <bits/stdc++.h>
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 <bits/stdc++.h>
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<int>> a(h, vector<int>(w, 0)), b(h, vector<int>(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<int>>>> team;
set<vector<vector<int>>> 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 <bits/stdc++.h>
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<int> 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<double>::max();
vector<double> cost(up, 0);
for (int i = 0; i < up; ++i) {
for (int l = 0; l < n; ++l) {
cost[i] += (w[l] * ((i >> l) & 1));
}
cost[i] = (cost[i] - ave) * (cost[i] - ave);
}
vector<double> dp(up, inf);
dp[0] = 0;
for (int j = 1; j <= d; ++j) {
vector<double> 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 <bits/stdc++.h>
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<int> w(n);
for (auto& i : w)
cin >> i;
int tot = accumulate(w.begin(), w.end(), 0);
int up = (1 << n);
__int128 inf = numeric_limits<__int128>::max();
vector<int> sum(up, 0);
for (int i = 1; i < up; ++i) {
for (int l = 0; l < n; ++l) {
sum[i] += (w[l] * ((i >> l) & 1));
}
}
vector<__int128> dp(up, inf);
dp[0] = 0;
for (int j = 1; j <= d; ++j) {
vector<__int128> 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 <bits/stdc++.h>
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 << 2];
void build(int root, int l, int r) {
if (l == r) {
k[root] = 1;
b[root] = 0;
lazyk[root] = 1;
lazyb[root] = 0;
return;
}
int mid = (l + r) >> 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 <= R) {
k[root] = k[root] * vk % mo;
b[root] = (b[root] * vk % mo + vb) % mo;
lazyk[root] = lazyk[root] * vk % mo;
lazyb[root] = (lazyb[root] * vk % mo + vb) % mo;
return;
}
pushdown(root);
int mid = (l + r) >> 1;
if (L <= mid)
update(lson, l, mid, L, R, vk, vb);
if (R > mid)
update(rson, mid + 1, r, L, R, vk, vb);
}
array<LL, 2> 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 <= mid)
return get(lson, l, mid, pos);
else
return get(rson, mid + 1, r, pos);
}
} 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<LL> a(n);
for (auto& i : a)
cin >> i;
seg.build(1, 1, n);
for (int i = 0; i < m; ++i) {
int l, r, x;
cin >> 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 < n; ++i) {
auto [p, q] = seg.get(1, 1, n, i + 1);
int ans = a[i] * p % mo + q;
if (ans >= 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 <bits/stdc++.h>
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];
void build(int root, int l, int r) {
if (l == r) {
k[root] = 1;
b[root] = 0;
return;
}
int mid = (l + r) >> 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 <= mid)
modify(lson, l, mid, pos, vk, vb);
else
modify(rson, mid + 1, r, pos, vk, vb);
k[root] = k[lson] * k[rson] % mo;
b[root] = b[lson] * k[rson] % mo + b[rson];
if (b[root] >= 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<LL> a(n);
for (auto& i : a)
cin >> i;
vector<array<int, 3>> op(m);
for (auto& i : op) {
cin >> i[0] >> i[1] >> i[2];
--i[0];
--i[1];
}
vector<int> 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] < i) {
seg.modify(1, 1, m, *r + 1, 1, 0);
r = next(r);
}
LL ans = a[i] * seg.k[1] % mo + seg.b[1];
if (ans >= 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 <bits/stdc++.h>
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<LL> 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<LL> dp(up + 1, inf);
dp[0] = 0;
for (int i = 1; i <= n; ++i) {
LL cost = a[i - 1];
for (int j = up; j >= i; --j) {
dp[j] = min(dp[j], dp[j - i] + cost);
}
}
LL ans = inf;
vector<int> 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;
}
- Beginner AtCoder Contest 332beginner atcoder contest 332 contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 334 beginner atcoder contest 328 beginner atcoder contest 310 beginner atcoder contest 315