文章目录

[ARC058B] Iroha and a Grid[ARC058C] Iroha and Haiku[ARC059C] Children and Candies[ARC059D] Unhappy Hacking[ARC060B] Digit Sum[ARC060C] Tak and Hotels[ARC060D] Best Representation[ARC061C] Snuke's Subway Trip[ARC063C] Integers on a Tree[ARC064C] Cosmic Rays

标黄的表示看了题解。

[ARC058B] Iroha and a Grid

简单计数题，总方案减不合法的即可，不合法的可以枚举 $A\times B$ 的矩形的一个对角线计算。

#include <bits/stdc++.h> const int MAXN = 200000; const int MOD = 1000000007; int H, W, A, B; inline int Add(const int &x, const int &y) { return (x + y >= MOD) ? (x + y - MOD) : (x + y); } inline int Mul(const int &x, const int &y) { return (long long)x * y % MOD; } int Pow(int x, int y) { int ret = 1; while (y) { if (y & 1) ret = Mul(ret, x); x = Mul(x, x); y >>= 1; } return ret; } int Fac[MAXN + 5], Inv[MAXN + 5]; inline int Calc(const int &n, const int &m) { return Mul(Fac[n + m - 2], Mul(Inv[n - 1], Inv[m - 1])); } int main() { scanf("%d%d%d%d", &H, &W, &A, &B); int N = H + W; Fac[0] = 1; for (int i = 1; i <= N; i++) Fac[i] = Mul(Fac[i - 1], i); Inv[N] = Pow(Fac[N], MOD - 2); for (int i = N - 1; i >= 0; i--) Inv[i] = Mul(Inv[i + 1], i + 1); int X = Calc(H, W), Y = 0; for (int i = H - A + 1; i <= std::min(H, H - A + B); i++) { int j = B - (i - (H - A)) + 1; Y = Add(Y, Mul(Calc(i, j), Calc(H - i + 1, W - j + 1))); } printf("%d", (X - Y + MOD) % MOD); return 0; }

[ARC058C] Iroha and Haiku

用二进制第 $i$ 位 $1$ 的数来表示数 $i$，例如 $4\to 1000$，$2\to 10$，那么数相加可以把这些数对应的转化过后的数依次排列起来就能看出后缀和是多少了。那么这样处理过后原问题的合法定义变为存在四个 $1$（最末尾视为有一个 $1$），相邻两个 $1$ 之间的距离分别为 $X,Y,Z$（距离定义为两个 $1$ 位置之差）。反向考虑比较简单，即不存这样的情况，状压 DP 即可。

#include <bits/stdc++.h> const int MAXN = 40; const int MAXL = 17; const int MOD = 1000000007; inline void AddTo(int &x, const int &y) { x += y; if (x >= MOD) x -= MOD; } int N, X, Y, Z; int Dp[MAXN + 5][(1 << MAXL) + 5]; int main() { scanf("%d%d%d%d", &N, &X, &Y, &Z); int Ans = 0, M = (1 << (X + Y + Z)) - 1; int Bad = (1 << (Z - 1)) | (1 << (Z + Y - 1)) | (1 << (Z + Y + X - 1)); Dp[0][0] = 1; for (int i = 0; i < N; i++) for (int j = 0; j <= M; j++) if (Dp[i][j]) { for (int k = 1; k <= 10; k++) { int p = ((j << k) | (1 << (k - 1))) & M; if ((p & Bad) != Bad) AddTo(Dp[i + 1][p], Dp[i][j]); } } for (int i = 0; i <= M; i++) AddTo(Ans, Dp[N][i]); int All = 1; for (int i = 1; i <= N; i++) All = (long long)All * 10 % MOD; printf("%d", (All - Ans + MOD) % MOD); return 0; }

[ARC059C] Children and Candies

要根据分配律全部一起计算，因此直接定义 $dp[i][j]$ 表示前 $i$ 个人分了 $j$ 个糖的答案，转移就显然了。看到多重方案数嵌套求和的不要想多了，一起算就行了。

#include <bits/stdc++.h> const int MAXN = 400; const int MOD = 1000000007; inline int Add(const int &x, const int &y) { return (x + y >= MOD) ? (x + y - MOD) : (x + y); } inline int Mul(const int &x, const int &y) { return (long long)x * y % MOD; } inline int Sub(const int &x, const int &y) { return (x - y < 0) ? (x - y + MOD) : (x - y); } int Pow(int x, int y) { int ret = 1; while (y) { if (y & 1) ret = Mul(ret, x); y >>= 1; x = Mul(x, x); } return ret; } int N, C; int A[MAXN + 5], B[MAXN + 5]; int S[MAXN + 5][MAXN + 5], Dp[MAXN + 5][MAXN + 5]; int main() { scanf("%d%d", &N, &C); int Max = 0; for (int i = 1; i <= N; i++) scanf("%d", &A[i]); for (int i = 1; i <= N; i++) scanf("%d", &B[i]), Max = std::max(Max, B[i]); for (int i = 0; i <= C; i++) for (int j = 1; j <= Max; j++) S[i][j] = Add(S[i][j - 1], Pow(j, i)); Dp[0][0] = 1; for (int i = 1; i <= N; i++) for (int j = 0; j <= C; j++) for (int k = 0; k <= j; k++) Dp[i][j] = Add(Dp[i][j], Mul(Dp[i - 1][j - k], Sub(S[k][B[i]], S[k][A[i] - 1]))); printf("%d", Dp[N][C]); return 0; }

[ARC059D] Unhappy Hacking

原串具体长什么样不重要，我们只需要求“$n$ 次按出长度为 $l$ 的串的方案数”然后除以 $2^l$ 次方即可。（因为每种样子的串是等价的），$dp[i][j]$ 表示按 $i$ 次按出长度为 $j$ 的串的方案数，转移显然。

#include <bits/stdc++.h> const int MAXN = 5000; const int MOD = 1000000007; inline int Add(const int &x, const int &y) { return (x + y >= MOD) ? (x + y - MOD) : (x + y); } inline int Mul(const int &x, const int &y) { return (long long)x * y % MOD; } inline int Sub(const int &x, const int &y) { return (x - y < 0) ? (x - y + MOD) : (x - y); } int Pow(int x, int y) { int ret = 1; while (y) { if (y & 1) ret = Mul(ret, x); y >>= 1; x = Mul(x, x); } return ret; } int N, L; int Dp[MAXN + 5][MAXN + 5]; char S[MAXN + 5]; int main() { scanf("%d%s", &N, S + 1); L = strlen(S + 1); Dp[0][0] = 1; for (int i = 1; i <= N; i++) { Dp[i][0] = Dp[i - 1][0]; for (int j = 0; j <= N; j++) { Dp[i][j] = Add(Dp[i][j], Dp[i - 1][j + 1]); Dp[i][j] = Add(Dp[i][j], Mul(Dp[i - 1][j - 1], 2)); } } printf("%d", Mul(Dp[N][L], Pow(Pow(2, L), MOD - 2))); return 0; }

[ARC060B] Digit Sum

$b>\sqrt{n}$ 时 $n$ 的 $b$ 进制表示最多有 $2$ 位，于是 $b\le \sqrt{n}$ 暴力，$b>\sqrt{n}$ 时解个二元一次方程即可。注意特判 $n=s$（因为我们只考虑了 $b\le n$ 的情况）。

#include <bits/stdc++.h> typedef long long LL; LL N, S; LL Sum(LL n, const LL &b) { LL ret = 0; while (n) ret += n % b, n /= b; return ret; } int main() { scanf("%lld%lld", &N, &S); for (int i = 2; (LL)i * i <= N; i++) if (Sum(N, i) == S) return printf("%d", i), 0; LL Ans = -1; // i = 0: j = N if (N == S) return printf("%lld", N + 1), 0; for (int i = 1; (LL)i * i < N && i <= S; i++) { // i * b + j = N (j < b) // i + j = S // i * (b - 1) = N - S // b = (N - S) / i + 1 if ((N - S) % i == 0) { LL b = (N - S) / i + 1; if (S - i < b && b >= 2) { Ans = b; // printf("%d %d %d\n", i, S - i, b); } } } // printf("%lld\n", Sum(N, Ans)); printf("%lld", Ans); return 0; }

[ARC060C] Tak and Hotels

佛了呀倍增写不来 WA 了 5 发最后看了别人的代码才过…… 要写 r < R[l][i] 最后 ans 加一，而不是 r >= R[l][i]（这样边界有问题）。

#include <bits/stdc++.h> const int MAXN = 100000; const int LOG = 16; int N, L, Q; int X[MAXN + 5]; int R[MAXN + 5][LOG + 5]; int main() { scanf("%d", &N); for (int i = 1; i <= N; i++) scanf("%d", &X[i]); scanf("%d%d", &L, &Q); for (int i = 1; i <= N; i++) R[i][0] = std::upper_bound(X + i + 1, X + N + 1, X[i] + L) - X - 1; for (int j = 1; j <= LOG; j++) for (int i = 1; i <= N; i++) R[i][j] = R[R[i][j - 1]][j - 1]; while (Q--) { int l, r; scanf("%d%d", &l, &r); if (l > r) std::swap(l, r); int Ans = 0; for (int i = LOG; i >= 0; i--) if (r > R[l][i]) l = R[l][i], Ans |= (1 << i); printf("%d\n", Ans + 1); } return 0; }

[ARC060D] Best Representation

KMP 判循环：字符串 $s$ 为循环串当且仅当 $(|s|-fai{l}_{|s|})||s|$，此时 $|s|-fai{l}_{|s|}$ 是最小循环节的长度。然后分三类讨论一下即可。

#include <bits/stdc++.h> const int MAXN = 500000; int N; char S[MAXN + 5]; int Fail1[MAXN + 5], Fail2[MAXN + 5]; void KMP(int *res) { res[1] = 0; for (int i = 2, j = 0; i <= N; i++) { while (j && S[i] != S[j + 1]) j = res[j]; if (S[j + 1] == S[i]) j++; res[i] = j; } } bool Cir(int *Fail, int i) { return Fail[i] && i % (i - Fail[i]) == 0; } int main() { scanf("%s", S + 1); N = strlen(S + 1); KMP(Fail1), std::reverse(S + 1, S + N + 1), KMP(Fail2); if (Fail1[N] && N % (N - Fail1[N]) == 0) { if (Fail1[N] == N - 1) return printf("%d\n1", N), 0; puts("2"); int Ans = 0; for (int i = 1; i < N; i++) if (!Cir(Fail1, i) && !Cir(Fail2, N - i)) Ans++; printf("%d\n", Ans); return 0; } puts("1\n1"); return 0; }

[ARC061C] Snuke’s Subway Trip

对点 $u$ 拆为多个 $u_c$ 表示在 $u$ 处颜色为 $c$，连边 $(u,u_c)$ 代价为 $1$，$u_c,u$ 代价为 $0$ 可实现颜色转换的代价，原图边按 $(u_c,v_c)$ 代价为 $0$ （其中 $c$ 为 $(u,v)$ 的颜色）连即可。

#include <bits/stdc++.h> typedef std::pair<int, int> PII; const int MAXN = 100000; const int MAXM = 200000; const int MAXC = 1000000; struct Edge { int v, w; Edge *nxt; } E[MAXM * 10 + 5]; Edge *Adj[MAXM * 5 + 5], *EdgeCnt = E; int N, M; int U[MAXM + 5], V[MAXM + 5], C[MAXM + 5]; void AddEdge(int u, int v, int w) { (++EdgeCnt)->v = v, EdgeCnt->w = w, EdgeCnt->nxt = Adj[u], Adj[u] = EdgeCnt; } bool Vis[MAXC + 5]; std::map<PII, int> Num; std::vector<int> Col[MAXN + 5]; int Dist[MAXM * 5 + 5]; int Dijkstra(int S, int T) { std::priority_queue<PII, std::vector<PII>, std::greater<PII> > Q; memset(Dist, 0x3f, sizeof Dist); Q.push({ Dist[S] = 0, S }); while (!Q.empty()) { int u = Q.top().second, d = Q.top().first; Q.pop(); if (d > Dist[u]) continue; for (Edge *i = Adj[u]; i; i = i->nxt) { int v = i->v, w = i->w; if (Dist[v] > d + w) Q.push({ Dist[v] = d + w, v }); } } return Dist[T] == 0x3f3f3f3f ? -1 : Dist[T]; } int main() { scanf("%d%d", &N, &M); for (int i = 1; i <= M; i++) { scanf("%d%d%d", &U[i], &V[i], &C[i]); Col[U[i]].push_back(C[i]), Col[V[i]].push_back(C[i]); } int cnt = 0; for (int i = 1; i <= N; i++) { for (int j: Col[i]) if (!Vis[j]) { int u = (Num[{ i, j }] = N + ++cnt); Vis[j] = true; AddEdge(i, u, 1); AddEdge(u, i, 0); } for (int j: Col[i]) Vis[j] = false; } for (int i = 1; i <= M; i++) { int u = Num[{ U[i], C[i] }], v = Num[{ V[i], C[i] }]; AddEdge(u, v, 0); AddEdge(v, u, 0); } printf("%d", Dijkstra(1, N)); return 0; }

[ARC063C] Integers on a Tree

优先队列维护一下，每次取出最小权值结点扩展其周围的未确定结点的权值即可，因为必然存在一种方案：未确定的点权值不比全场最小的还小。

#include <bits/stdc++.h> const int MAXN = 100000; int N, K; std::vector<int> G[MAXN + 5]; int Ans[MAXN + 5]; struct Node { int i, v; inline bool operator < (const Node &other) const { return v > other.v; } }; std::priority_queue<Node> Q; int main() { scanf("%d", &N); memset(Ans, -1, sizeof Ans); for (int i = 1; i < N; i++) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } scanf("%d", &K); for (int i = 1; i <= K; i++) { Node cur; scanf("%d%d", &cur.i, &cur.v); Q.push(cur), Ans[cur.i] = cur.v; } while (!Q.empty()) { int u = Q.top().i; Q.pop(); for (int i = 0; i < (int)G[u].size(); i++) { int v = G[u][i]; if (Ans[v] == -1) Q.push({ v, Ans[v] = Ans[u] + 1}); else if (Ans[v] != Ans[u] + 1 && Ans[v] != Ans[u] - 1) return puts("No"), 0; } } puts("Yes"); for (int i = 1; i <= N; i++) printf("%d\n", Ans[i]); return 0; }

[ARC064C] Cosmic Rays

$N\le 1000$，暴力最短路即可。

#include <bits/stdc++.h> typedef std::pair<double, int> PDI; //const double EPS = 1e-9; const int MAXN = 1002; const int MAXM = MAXN * (MAXN - 1); int N, K; struct Edge { int v; double w; Edge *nxt; } E[MAXM + 5]; Edge *Adj[MAXN + 5], *EdgeCnt = E; inline void AddEdge(const int &u, const int &v, const double &w) { (++EdgeCnt)->v = v, EdgeCnt->w = w, EdgeCnt->nxt = Adj[u], Adj[u] = EdgeCnt; (++EdgeCnt)->v = u, EdgeCnt->w = w, EdgeCnt->nxt = Adj[v], Adj[v] = EdgeCnt; } struct Circle { int x, y, r; } B[MAXN + 5]; inline double Out(const Circle &i, const Circle &j) { return sqrt((double)(i.x - j.x) * (i.x - j.x) + (double)(i.y - j.y) * (i.y - j.y)) - i.r - j.r; } double Dist[MAXN + 5]; double Dijkstra(const int &S, const int &T) { std::priority_queue<PDI, std::vector<PDI>, std::greater<PDI> > Q; for (int i = 1; i <= N; i++) Dist[i] = 1e18; Q.push({ Dist[S] = 0, S }); while (!Q.empty()) { double d = Q.top().first; int u = Q.top().second; Q.pop(); if (d - Dist[u] > 1e-9) continue; for (Edge *i = Adj[u]; i; i = i->nxt) { int v = i->v; if (Dist[v] > d + i->w) Q.push({ Dist[v] = d + i->w, v}); } } return Dist[T]; } int main() { scanf("%d%d%d%d", &B[1].x, &B[1].y, &B[2].x, &B[2].y); scanf("%d", &N), N += 2; for (int i = 3; i <= N; i++) scanf("%d%d%d", &B[i].x, &B[i].y, &B[i].r); for (int i = 1; i <= N; i++) for (int j = i + 1; j <= N; j++) AddEdge(i, j, std::max(Out(B[i], B[j]), 0.0)); printf("%.10f", Dijkstra(1, 2)); return 0; }