A – Christmas Present (abc334 A)题目大意
给定两个数\(b,g(b \neq g)\)，如果 \(b\)大则输出 Bat，否则输出Glove。
解题思路
比较大小输出即可。
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int a, b; cin >> a >> b; if (a > b) cout << "Bat" << '\n'; else cout << "Glove" << '\n'; return 0;}B – Christmas Trees (abc334 B)题目大意
给定\(a,m,l,r\)，问有多少个整数 \(k\)满足 \(l \leq a + mk \leq r\).
解题思路
对不等式化简一下即为
\(\frac{l – a}{m} \leq k \leq \frac{r – a}{m}\)
的整数个数。
答案就是\(\lfloor \frac{r – a}{m} \rfloor – \lceil \frac{l – a}{m} \rceil + 1\)。
在C++直接用floor,ceil函数貌似有精度问题。
上下取整的转换是\(\lceil \frac{a}{b} \rceil = \lfloor \frac{a + b – 1}{b} \rfloor\)。
但C++的取整都是向0取整（舍尾），在负数的时候不适用，因此代码里先把它们全部平移到正数。
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); LL a, m, l, r; cin >> a >> m >> l >> r; l -= a; r -= a; if (l < 0) { LL shift = -l; shift += m - shift % m; l += shift; r += shift; } LL R = r / m; LL L = (l + m - 1) / m; LL ans = R - L + 1; cout << ans << '\n'; return 0;}C – Socks 2 (abc334 C)题目大意
给定\(n\)双袜子，编号 \(1-n\)，但丢失了其中 \(k\)双袜子各一只。
现重新俩俩配对，使得每双袜子的编号差的和最小。
解题思路
考虑原本成双的袜子，如果拆开来配对单个袜子的话，发现不会更优。因此仅考虑单个袜子的。
单个袜子的按照编号从小到大一一配对，容易发现这是最小的了，任意交换两个配对方式都会导致差的和更大。
如果是偶数只则完美匹配，如果是奇数只，则需舍弃一只，枚举舍弃的这只（容易发现舍弃了这只后，左边数量一定是偶数，右边数量一定是偶数的情况才更优），剩下的就是从头一一匹配，而从尾一一匹配，这个可以事先预处理得到。时间复杂度是\(O(n)\)。当然可以如代码一样动态维护左右两边匹配的结果。
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, k; cin >> n >> k; vector a(k); for (auto& i : a) cin >> i; LL ans = 0; if (~k & 1) { for (int i = 0; i 1) { LL sum = 0; for (int i = k - 1; i > 0; i -= 2) sum += a[i] - a[i - 1]; ans = sum; for (int i = 0; i < k - 1; i += 2) { sum -= a[i + 2] - a[i + 1]; sum += a[i + 1] - a[i]; ans = min(ans, sum); } } cout << ans << '\n'; return 0;}D – Reindeer and Sleigh (abc334 D)题目大意
有\(n\)个雪橇，第 \(i\)个雪橇需要 \(r_i\)只麋鹿拉。
给定 \(q\)个询问，对于每个询问给定 \(x\)只麋鹿，问最多能拉多少个雪橇。
解题思路
很显然我们优先拉需要的麋鹿数量少的雪橇。
因此先对拉雪橇所需的麋鹿数量\(r_i\)拍个序，找到最大的\(k\)使得\(\sum_{i=1}{k}r_i \leq x\)。
在一个关于\(r_i\)的前缀和数组上 二分找到对应位置即可。时间复杂度是\(O(q\log n)\)
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, q; cin >> n >> q; vector r(n); for (auto& i : r) cin >> i; ranges::sort(r); partial_sum(r.begin(), r.end(), r.begin()); while (q--) { LL x; cin >> x; auto pos = ranges::upper_bound(r, x) - r.begin(); cout << pos << '\n'; } return 0;}E – Christmas Color Grid 1 (abc334 E)题目大意
给定包含 .#的二维网格。现随机将一个 .改成#，问#的期望连通块数量。
解题思路
由于网格大小只有\(1000 \times 1000\)，可以枚举每个 .，计算它变成#后的影响。
考虑如何计算影响，首先计算出原图的所有#的连通块\(block\)，可以用并查集或者BFS。然后考虑当一个.变成#后，它能连通多少个不同的连通块。很显然四个方向，如果有\(x\)个不同的连通块，那么此时连通块数量就变成\(block + 1 – x\)。
所有情况求和，再除以 .的数量即为答案。
神奇的代码
#include using namespace std;using LL = long long;const int mo = 998244353;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 h, w; cin >> h >> w; vector s(h); int red = 0; for (auto& i : s) { cin >> i; red += ranges::count(i, '.'); } vector<vector> own(h, vector(w, 0)); int block = 0; array dx{1, -1, 0, 0}; array dy{0, 0, 1, -1}; auto BFS = [&](int x, int y) { queue<array> team; team.push({x, y}); block++; own[x][y] = block; while (!team.empty()) { auto [x, y] = team.front(); team.pop(); for (int i = 0; i < 4; ++i) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || ny = h || ny >= w || s[nx][ny] != '#' || own[nx][ny]) continue; own[nx][ny] = block; team.push({nx, ny}); } } }; for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) { if (s[i][j] == '#' && !own[i][j]) BFS(i, j); } LL ans = 0; for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) { if (s[i][j] == '.') { set nei; for (int k = 0; k < 4; ++k) { int x = i + dx[k], y = j + dy[k]; if (x < 0 || y = h || y >= w || s[x][y] == '.') continue; nei.insert(own[x][y]); } ans += block + 1 - int(nei.size()); } } ans = ans % mo * inv(red) % mo; cout << ans << '\n'; return 0;}F – Christmas Present 2 (abc334 F)题目大意
二维平面，起点\(st\)，依次去\(n\)个点送礼物，一次只能携带最多 \(k\)个礼物。只能回起点补充礼物。
问从起点出发，送完 \(n\)个点的礼物，并回到起点的最小距离和。
解题思路
考虑当前已经送完了前\(i\)点的礼物，那我接下来的决策就是决定送多少（\(\leq k\)）个礼物 ，不同的决策就有一个距离代价。
由此设\(dp[i]\)表示送完前 \(i\)个点的礼物，并回到起点的最小距离和。考虑上次送了几个礼物，得转移式：
\(dp[i] = \min_{i – k \leq j \leq i – 1}(dp[j] + dis[st \to j+1] + dis[j + 1 \to … \to i] + dis[i \to st])\)
时间复杂度是\(O(n^2)\)。
把中间的\(dis[j+1 \to … \to i]\)用距离前缀和代替 \(sum[i] – sum[j + 1]\)，并把与 \(j\)无关的项抽出来，得
\(dp[i] = \min_{i – k \leq j \leq i – 1}(dp[j] + dis[st \to j+1] – sum[j – 1]) + sum[i] + dis[i \to st]\)
中间是一个关于数组\(cost[j] = dp[j] + dis[st \to j+1] – sum[j – 1]\)的滑动窗口取 \(\min\)，用单调队列优化即可。
时间复杂度是 \(O(n)\)。
当然也可以用线段树（
神奇的代码
#include using namespace std;using LL = long long;int main(void) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, k; cin >> n >> k; vector<array> pos(n + 1); for (auto& i : pos) cin >> i[0] >> i[1]; vector sum(n + 2); auto calc = [&](array& a, array& b) { LL dx = a[0] - b[0]; LL dy = a[1] - b[1]; return sqrt(dx * dx + dy * dy); }; vector dis(n + 2, 0); for (int i = 1; i <= n; ++i) { sum[i] = sum[i - 1] + calc(pos[i], pos[i - 1]); dis[i] = calc(pos[i], pos[0]); } deque<pair> team; vector dp(n + 1); team.push_back({dp[0] + dis[1] - sum[1], 0}); dp[0] = 0; for (int i = 1; i <= n; ++i) { while (!team.empty() && team.front().second = cur) team.pop_back(); team.push_back({cur, i}); } cout << fixed << setprecision(10) << dp.back() << '\n'; return 0;}G – Christmas Color Grid 2 (abc334 G)题目大意
给定包含 .#的二维网格。现随机将一个 .改成#，问#的期望连通块数量。
解题思路
由于网格大小只有\(1000 \times 1000\)，可以枚举每个 #，计算它变成.后的影响。
枚举#，当它变成 .，原本所在的#连通块可能会被拆分成若干块，也可能不会被拆开，这取决于这个点是否是关键点，或者说割点。
我们需要一个描述这样性质的信息，即tarjan里的dfn和low。其中dfn[i]表示第一次访问该点的时间，low[i]表示从该点往下走，通过返祖边能往上返回的最早的节点的时间。
注意一张图可以看作是一颗DFS树和一些返祖边构成，而这些返祖边就是会造成连通块不会被拆开的原因。
因此先对原图进行DFS，得到每个点的dfn和low。然后依次考虑删除每个点\(u\)，对于其儿子点 \(v\)，考虑其是否还和点\(u\)的父亲往上部分连通。
根据定义，如果 \(dfn[u] \leq low[v]\)，说明 \(v\)子树无法回溯到点 \(u\)的父亲往上，也就和上面断开了，此时连通块数量会\(+1\)。。
因此，记\(dfs[u] \leq low[v]\)的 \(v\)的数量为 \(c\)。
如果当前点 \(u\)是根，则删去该点后，连通块 数量会增加\(c-1\)，否则就增加 \(c\)。
这样考虑一个#后的连通块数量就能\(O(1)\)算的，所有情况累加，除以#数量即为答案。
神奇的代码
#include using namespace std;using LL = long long;const int mo = 998244353;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 h, w; cin >> h >> w; vector s(h); int greeen = 0; for (auto& i : s) { cin >> i; greeen += ranges::count(i, '#'); } vector dfn(h * w), low(h * w); int time = 0; int block = 0; auto tr = [&](int x, int y) { return x * w + y; }; auto invtr = [&](int x) -> array { return {x / w, x % w}; }; array dx{1, -1, 0, 0}; array dy{0, 0, 1, -1}; vector<vector> son(h * w); vector f(h * w); auto dfs = [&](auto self, int u, int fa) -> void { ++time; f[u] = fa; dfn[u] = low[u] = time; auto [x, y] = invtr(u); for (int i = 0; i < 4; ++i) { int nx = x + dx[i], ny = y + dy[i]; if (nx < 0 || ny = h || ny >= w || s[nx][ny] == '.') continue; int nu = tr(nx, ny); if (nu == fa) continue; if (dfn[nu]) low[u] = min(low[u], dfn[nu]); else { son[u].push_back(nu); self(self, nu, u); low[u] = min(low[u], low[nu]); } } }; for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) { auto it = tr(i, j); if (s[i][j] == '#' && !dfn[it]) { ++block; dfs(dfs, it, it); } } LL ans = 0; for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) { if (s[i][j] == '#') { int cnt = 0, u = tr(i, j); for (auto& v : son[u]) { cnt += (dfn[u] <= low[v]); } ans += block - 1 + cnt + (f[u] != u); } } ans = ans % mo * inv(greeen) % mo; cout << ans << '\n'; return 0;}