T1
ZZH 的游戏
二分答案之后，两个点轮流跳到当前能跳到的最小点。如果没法跳了且不都在 \(1\)，那么无解。容易发现这是对的，可以通过建重构树维护。然后发现二分答案不是必要的，只需要每次没法跳的时候手动开大答案即可。复杂度瓶颈在建重构树的并查集。
代码
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++
char buf[1<<21], *p1, *p2, ch;
long long read() {long long ret = 0, neg = 0; char c = getchar(); neg = (c == '-');while (c < '0' || c > '9') c = getchar(), neg |= (c == '-');while (c >= '0' && c <= '9') ret = ret * 10 + c - '0', c = getchar();return ret * (neg ? -1 : 1);
}
int n, s, t;
vector<int> G1[1000005], G2[1000005];
int f1[1000005], f2[1000005];
int mn1[1000005], mn2[1000005];
int dsu[1000005];
int getf(int x) { return (dsu[x] == x ? x : (dsu[x] = getf(dsu[x]))); }
int main() {freopen("game.in", "r", stdin);freopen("game.out", "w", stdout);int tc = read();while (tc--) {for (int i = 1; i <= n; i++) G1[i].clear(), G2[i].clear();n = read();for (int i = 1; i < n; i++) {int u = read(), v = read();G1[u].emplace_back(v);G1[v].emplace_back(u);}for (int i = 1; i < n; i++) {int u = read(), v = read();G2[u].emplace_back(v);G2[v].emplace_back(u);}for (int i = 1; i <= n; i++) {dsu[i] = mn1[i] = i;for (auto v : G1[i]) {if (v < i) {int y = getf(v);dsu[y] = f1[y] = i, mn1[i] = min(mn1[i], mn1[y]);}}}for (int i = 1; i <= n; i++) {dsu[i] = mn2[i] = i;for (auto v : G2[i]) {if (v < i) {int y = getf(v);dsu[y] = f2[y] = i, mn2[i] = min(mn2[i], mn2[y]);}}}cin >> s >> t;int ans = s + t;while (mn1[s] != 1 || mn2[t] != 1) {while ((mn2[t] == 1 || mn1[s] + f2[t] > ans) && (mn1[s] == 1 || f1[s] + mn2[t] > ans)) ++ans;while (1) {bool c = 0;while (mn1[s] != 1 && f1[s] + mn2[t] <= ans) s = f1[s], c = 1;while (mn2[t] != 1 && mn1[s] + f2[t] <= ans) t = f2[t], c = 1;if (!c) break;}}cout << ans << "\n";}return 0;
}
T2
环
\(2p > n\) 的质数没用，扔掉。接下来构造用到剩下所有东西的方案。
把所有东西按照最小质因子分组。对于 \(12 \le 4p \le n\) 的质数，通过 \(2p - p - \cdots - 4p\) 将它接进 \(2\) 里面。对于 \(3p \le n, 4p > n\) 的质数，通过 \(2p_1 - 3p_1 - 3p_2 - 2p_2\) 把它们这样接进来。由于指不定有奇数还是偶数个，最后结尾可能是 \(2\) 也可能是 \(3\)。只需要在后面接 \(6\) 并顺带把 \(3\) 那一组放进来即可。对于 \(n < 12\) 的情况容易特判。
代码
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
int n, X, Y;
vector<int> vec[500005], ans;
vector<int> V;
bool vis[500005], ip[500005], mark[500005];
int main() {freopen("cycle.in", "r", stdin);freopen("cycle.out", "w", stdout);int tc;cin >> tc;while (tc--) {cin >> n;if (n >= 12) {ans.clear(); V.clear();for (int i = 2; i <= n; i++) vec[i].clear(), vis[i] = 0, mark[i] = 0;for (int i = 2; i <= n; i++) {if (mark[i]) continue;ip[i] = 1;if (i * 3 <= n && i * 4 > n) V.emplace_back(i);for (int j = i; j <= n; j += i) if (!mark[j]) vec[i].emplace_back(j), mark[j] = 1;}auto ins = [&](int x) {ans.emplace_back(x * 2);for (auto v : vec[x]) if (!vis[v]) ans.emplace_back(v);ans.emplace_back(x * 4);};if (V.size() & 1) V.emplace_back(-1);// 2X - 3X - 3Y - 2Yfor (int i = 0; i < (int)V.size(); i += 2) {X = V[i], Y = V[i + 1];ans.emplace_back(2 * X), ans.emplace_back(X), ans.emplace_back(3 * X);if (Y != -1) ans.emplace_back(3 * Y), ans.emplace_back(Y), ans.emplace_back(2 * Y);}for (auto v : ans) vis[v] = 1;for (int i = 3; i <= n; i++) if (ip[i] && i * 4 <= n) ins(i);for (auto v : ans) vis[v] = 1;for (int i = 2; i <= n; i += 2) if (!vis[i]) ans.emplace_back(i);cout << ans.size() << "\n";for (auto v : ans) cout << v << " ";} else for (int i = (cout << n / 2 << "\n", 2); i <= n; i += 2) cout << i << " ";cout <<" \n";}return 0;
}
T3
道路的眼泪
路径 \(\min\)，想到重构树。从大往小加点建出，则每个点的 \(V\) 集合即为其所有祖先。
第一问：枚举 LCA 容易计算答案。
第二问：树形 dp 即可。
第三问：由于异或的优秀性质，对于 \(\bigoplus V\) 中的每个点 \(x\)，可以把 \(S\) 集合 \(\oplus \{ x, f_x \}\)，其中 \(f_x\) 为 \(x\) 在重构树的祖先（没有就算了），从而得到对应的 \(S\)。那么这样我们就构造了 \(S\) 和 \(V\) 的双射。那么就做完了。
代码
#include <iostream>
#include <string.h>
#include <vector>
#define int long long
using namespace std;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++
char buf[1<<21], *p1, *p2, ch;
long long read() {long long ret = 0, neg = 0; char c = getchar(); neg = (c == '-');while (c < '0' || c > '9') c = getchar(), neg |= (c == '-');while (c >= '0' && c <= '9') ret = ret * 10 + c - '0', c = getchar();return ret * (neg ? -1 : 1);
}
const int P = 998244353;
int n, m, K, ans;
int pw[2000005];
int h1[2000005], n1[4000005], t1[4000005], e1;
int h2[2000005], n2[2000005], t2[2000005], e2;
void add1(int u, int v) { t1[++e1] = v, n1[e1] = h1[u], h1[u] = e1; }
void add2(int u, int v) { t2[++e2] = v, n2[e2] = h2[u], h2[u] = e2; }
int qpow(int x, int y = P - 2) {int ret = 1;while (y) {if (y & 1) ret = ret * x % P;y >>= 1;x = x * x % P;}return ret;
}
int fac[2000005], ifac[2000005], inv[2000005];
void Cpre(int n) {fac[0] = fac[1] = ifac[0] = ifac[1] = inv[0] = inv[1] = 1;for (int i = 2; i <= n; i++) {fac[i] = fac[i - 1] * i % P;inv[i] = (P - P / i) * inv[P % i] % P;ifac[i] = ifac[i - 1] * inv[i] % P;}
}
inline int C(int n, int m) { return (n < 0 || m < 0 || n < m) ? 0 : fac[n] * ifac[m] % P * ifac[n - m] % P; }
int str;
int sz[2000005];
void dfs1(int x, int d) {sz[x] = 1;int s = 0;for (int i = h2[x]; i; i = n2[i]) {int v = t2[i];dfs1(v, d + 1);sz[x] += sz[v];s += P - pw[sz[v]] + 1;}s = (s + pw[sz[x]] - 1) % P;ans += s * qpow(d, K) % P;
}
int dp[2000005];
void dfs2(int x) {dp[x] = 1;for (int i = h2[x]; i; i = n2[i]) {int v = t2[i];dfs2(v);dp[x] = dp[x] * dp[v] % P;}dp[x] = ((dp[x] - 1) * 2 * K + K + 1) % P;
}
int dsu[2000005];
int getf(int x) { return (dsu[x] == x ? x : (dsu[x] = getf(dsu[x]))); }
signed main() {Cpre(2000000);freopen("tearroad.in", "r", stdin);freopen("tearroad.out", "w", stdout);str = read(), n = read(), m = read(), K = read();pw[0] = 1;for (int i = 1; i <= n; i++) pw[i] = pw[i - 1] * 2 % P, dsu[i] = i;for (int i = 1; i <= m; i++) {int u = read(), v = read();add1(u, v);add1(v, u);}for (int i = n; i; i--) {for (int j = h1[i]; j; j = n1[j]) {int v = t1[j];if (v < i) continue;if (getf(v) != getf(i)) add2(i, dsu[v]), dsu[dsu[v]] = i;}}if (str / 100) {dfs1(1, 1);cout << ans % P << " ";}if ((str / 10) & 1) {dfs2(1);cout << dp[1] - 1 << " ";}if (str & 1) {ans = 0;for (int i = 1; i <= n; i++) ans += C(n, i) * ((i + K - 1) / K) % P;cout << ans % P << "\n";}return 0;
}
T4
田野
离散化，之后的每个格点相当于一个矩形。显然矩形只有四个角是重要的，对所有角跑最短路。
第一问，对于询问点求出在哪个矩形，四个方向过来取 \(\min\) 即可。
第二问，相当于对每个矩形要求它每个时刻扩展了多少点。那么从四个角开始，分别考察每个角扩张的过程。对于某一个角，它一开始扩张的时候贡献是 \(1\)，之后每个时刻比前一个时刻的贡献多 \(1\)。而之后它可能会撞到另外一个角，那么撞完了之后发现每个时刻比前一个时刻的贡献增量就减少了 \(1\)。而之后它可能又要撞到另外一个角，那么撞完了之后每个时刻比前一个时刻的贡献增量就又少了 \(1\)。而之后它可能就要撞到它对面的那个角了，那这么一撞就相当于强制停止这个角的贡献了。于是我们只需要算出这个角分别什么时候撞到两个邻角，什么时候撞到对角，然后使用一些差分维护贡献即可。当然这三个时间的相对顺序也不是一定的，因此需要一些讨论。由于范围很大，需要将所有差分和询问离线处理。
总复杂度 \(\mathcal{O}(n^2\log n + q\log n)\) 或 \(\mathcal{O}(n^2\log n + q\log (n^2 + q))\)。但也可能是类似的，反正就那样。能过。
代码
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <array>
#define int long long
using namespace std;
#define getchar() p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++
char buf[1<<21], *p1, *p2, ch;
long long read() {long long ret = 0, neg = 0; char c = getchar(); neg = (c == '-');while (c < '0' || c > '9') c = getchar(), neg |= (c == '-');while (c >= '0' && c <= '9') ret = ret * 10 + c - '0', c = getchar();return ret * (neg ? -1 : 1);
}
const int inf = 0x3f3f3f3f3f3f3f;
int n, tp, q;
int d_x[1005], dxcnt;
int d_y[1005], dycnt;
/*
01
23
*/
struct node { int x, y, t, dis; };
inline bool operator<(node x, node y) { return x.dis > y.dis; }
priority_queue<node> Q;
bool vis[1005][1005][4];
int dist[1005][1005][4];
int ban[1005][1005];
void _dijkstra() {memset(dist, 63, sizeof dist);int sx = lower_bound(d_x + 1, d_x + dxcnt + 1, 0) - d_x;int sy = lower_bound(d_y + 1, d_y + dycnt + 1, 0) - d_y;Q.push((node) { sx, sy, 0, dist[sx][sy][0] = 0 });while (Q.size()) {node tmp = Q.top(); Q.pop();int x = tmp.x, y = tmp.y, t = tmp.t;if (vis[x][y][t]) continue;vis[x][y][t] = 1;auto chkupd = [&](int tx, int ty, int tt, int ww) {if (!ban[tx][ty] && dist[tx][ty][tt] > dist[x][y][t] + ww) Q.push((node) { tx, ty, tt, dist[tx][ty][tt] = dist[x][y][t] + ww });};if (t == 0) {if (x != 1) chkupd(x - 1, y, 1, 1);if (y != dycnt - 1) chkupd(x, y + 1, 2, 1);chkupd(x, y, 1, d_x[x + 1] - d_x[x] - 1);chkupd(x, y, 2, d_y[y + 1] - d_y[y] - 1);} else if (t == 1) {if (x != dxcnt - 1) chkupd(x + 1, y, 0, 1);if (y != dycnt - 1) chkupd(x, y + 1, 3, 1);chkupd(x, y, 0, d_x[x + 1] - d_x[x] - 1);chkupd(x, y, 3, d_y[y + 1] - d_y[y] - 1);} else if (t == 2) {if (x != 1) chkupd(x - 1, y, 3, 1);if (y != 1) chkupd(x, y - 1, 0, 1);chkupd(x, y, 3, d_x[x + 1] - d_x[x] - 1);chkupd(x, y, 0, d_y[y + 1] - d_y[y] - 1);} else {if (x != dxcnt - 1) chkupd(x + 1, y, 2, 1);if (y != 1) chkupd(x, y - 1, 1, 1);chkupd(x, y, 2, d_x[x + 1] - d_x[x] - 1);chkupd(x, y, 1, d_y[y + 1] - d_y[y] - 1);}}
}
struct Node { int op, s, d, x; };
vector<Node> vec;
int ans[200005];
inline int calc(int s, int d, int len) { int t = s + len * d; return (s * 2 + (len + 1) * d) * len / 2; }
void work() {for (int i = 1; i < dxcnt; i++) {for (int j = 1; j < dycnt; j++) {if (ban[i][j]) continue;int X = d_x[i + 1] - d_x[i], Y = d_y[j + 1] - d_y[j], t;if (X == Y && Y == 1) vec.push_back({ 1, 1, 0, dist[i][j][0] }), vec.push_back({ -1, 1, 0, dist[i][j][0] + 1 });else for (int k : { 0, 1, 2, 3 }) {t = Y - 2 - abs(dist[i][j][k] - dist[i][j][k ^ 2]);int t1 = (t >> 1) + (t & 1) * (k < (k ^ 2)) + max(dist[i][j][k], dist[i][j][k ^ 2]);t = X - 2 - abs(dist[i][j][k] - dist[i][j][k ^ 1]);int t2 = (t >> 1) + (t & 1) * (k < (k ^ 1)) + max(dist[i][j][k], dist[i][j][k ^ 1]);t = X + Y - 3 - abs(dist[i][j][k] - dist[i][j][k ^ 3]);int t3 = (t >> 1) + (t & 1) * (k < (k ^ 3)) + max(dist[i][j][k], dist[i][j][k ^ 3]);if (t1 < dist[i][j][k] || t2 < dist[i][j][k]) continue;(t1 > t2) ? swap(t1, t2) : void();vec.push_back({ 1, 1, 1, dist[i][j][k] });if (t3 < t1) {vec.push_back({ -1, t3 + 2 - dist[i][j][k], -1, t3 + 1 });continue;}vec.push_back({ -1, t1 + 2 - dist[i][j][k], -1, t1 + 1 });vec.push_back({ 1, t1 + 1 - dist[i][j][k], 0, t1 + 1 });if (t3 < t2) {vec.push_back({ -1, t1 + 1 - dist[i][j][k], 0, t3 + 1 });continue;}vec.push_back({ -1, t1 + 1 - dist[i][j][k], 0, t2 + 1 });vec.push_back({ 1, t1 - dist[i][j][k], -1, t2 + 1 });vec.push_back({ -1, max(0ll, t1 - dist[i][j][k] - (t3 - t2)), 1, min(t3 + 1, t2 + 1 + t1 - dist[i][j][k]) });}}}sort(vec.begin(), vec.end(), [](Node x, Node y) { return x.x == y.x ? (abs(x.op) > abs(y.op)) : (x.x < y.x); });int dd = 0, al = 0, k = 0, lst = 0;for (auto v : vec) {dd += calc(al, k, v.x - lst); al += k * (v.x - lst); lst = v.x;if (v.op == 0) ans[v.d] = dd;else if (v.op == 1) al += v.s, k += v.d, dd += v.s;else al -= v.s, k += v.d, dd -= v.s;}
}
array<int, 4> rect[405];
signed main() {freopen("field.in", "r", stdin);freopen("field.out", "w", stdout);n = read(), tp = read(), q = read();for (int i = 1; i <= n; i++) {int &x1 = rect[i][0], &x2 = rect[i][1], &y1 = rect[i][2], &y2 = rect[i][3];x1 = read(), x2 = read(), y1 = read(), y2 = read();d_x[++dxcnt] = x1, d_x[++dxcnt] = x2 + 1;d_y[++dycnt] = y1, d_y[++dycnt] = y2 + 1;}d_x[++dxcnt] = 0, d_x[++dxcnt] = 1;d_x[++dxcnt] = -inf, d_x[++dxcnt] = inf;d_y[++dycnt] = 0, d_y[++dycnt] = 1;d_y[++dycnt] = -inf, d_y[++dycnt] = inf;sort(d_x + 1, d_x + dxcnt + 1); dxcnt = unique(d_x + 1, d_x + dxcnt + 1) - d_x - 1;sort(d_y + 1, d_y + dycnt + 1); dycnt = unique(d_y + 1, d_y + dycnt + 1) - d_y - 1;for (int i = 1; i <= n; i++) {int x1, x2, y1, y2;x1 = lower_bound(d_x + 1, d_x + dxcnt + 1, rect[i][0]) - d_x;x2 = lower_bound(d_x + 1, d_x + dxcnt + 1, rect[i][1] + 1) - d_x;y1 = lower_bound(d_y + 1, d_y + dycnt + 1, rect[i][2]) - d_y;y2 = lower_bound(d_y + 1, d_y + dycnt + 1, rect[i][3] + 1) - d_y;++ban[x1][y1], --ban[x2][y1], --ban[x1][y2], ++ban[x2][y2];}for (int i = 1; i <= dxcnt; i++) {for (int j = 1; j <= dycnt; j++) ban[i][j] += ban[i - 1][j] + ban[i][j - 1] - ban[i - 1][j - 1];}_dijkstra();if (tp == 1) {while (q--) {int x = read(), y = read(), tx, ty, ans;tx = upper_bound(d_x + 1, d_x + dxcnt + 1, x) - d_x - 1;ty = upper_bound(d_y + 1, d_y + dycnt + 1, y) - d_y - 1;ans = min({ dist[tx][ty][0] + x - d_x[tx] + d_y[ty + 1] - y - 1, dist[tx][ty][1] + d_x[tx + 1] - x - 1 + d_y[ty + 1] - y - 1, dist[tx][ty][2] + x - d_x[tx] + y - d_y[ty], dist[tx][ty][3] + d_x[tx + 1] - x - 1 + y - d_y[ty]});cout << (ans >= inf ? -1 : ans) << "\n";}} else {for (int i = 1; i <= q; i++) vec.push_back({ 0, 0, i, read() }); work();for (int i = 1; i <= q; i++) cout << ans[i] << "\n";}return 0;
}
T1。
T3，构造双射以计数。树形 dp。
T4。对每个矩形分开考虑每个角独立的贡献。