AtCoder Grand Contest 031 题解
Visits: 376
Colorful Subsequence
对于每种字符，可以选某一个或者不选，最后去掉空的。
const int N = 1e5 + 7;
int n;
char s[N];
int main() {
rd(n), rds(s, n);
map<char, int> c;
for (int i = 1; i <= n; i++) ++c[s[i]];
modint ans = 1;
for (pi o : c) ans *= o.se + 1;
print(ans - 1);
return 0;
}
Reversi
首先去重，显然不影响答案。
考虑 DP，设 $f_i$ 表示以 $i$ 为最终某一段的结尾。
枚举 $i$ 所在的段的长度转移，注意 $i$ 所在的段比如跟 $i$ 的颜色相同，时间复杂度 $\mathcal O(n^2)$。
考虑转移的条件，对于每种颜色记录所有这个颜色的转移和，时间复杂度 $\mathcal O(n)$。
const int N = 2e5 + 7;
int n, a[N];
modint c[N], f[N];
int main() {
rd(n), rda(a, n);
n = unique(a + 1, a + n + 1) - (a + 1);
c[a[1]] = f[0] = 1;
for (int i = 1; i <= n; i++)
f[i] = c[a[i]], c[a[i+1]] += f[i];
print(f[n]);
return 0;
}
Differ by 1 Bit
如果 $a\operatorname{xor}b$ 中有奇数个 $1$ 则 YES，否则 NO。
构造可以递归构造，时间复杂度 $\mathcal O(n2^n)$。
void f(int a, int b, int s) {
if (s) {
int d = (a ^ b) & s;
s ^= d &= -d;
int c = a ^ (s & -s);
f(a, c, s), f(c ^ d, b, s);
} else print(a, ' ');
}
int main() {
int n, a, b;
rd(n, a, b);
if (__builtin_parity(a ^ b)) prints("YES"), f(a, b, (1 << n) - 1);
else prints("NO");
return 0;
}
A Sequence of Permutations
题意
- 对于 $1 \sim n$ 的排列 $p,q$，定义排列 $f(p,q)$，满足 $f(p,q)$ 的第 $p_i$ 个元素为 $q_i$。
- 定义排列的序列 $a$ 满足，$a_1 = p$，$a_2 = q$，$a_{n+2} = f(a_n,a_{n+1})(n \ge 1)$。
- 求 $a_k$。
- $n \le 10^5$，$k \le 10^9$。
题解
注意到 $f(p,q) = qp^{-1}$，另有 $(pq)^{-1} = q^{-1}p^{-1}$，于是有：
$$
\begin{aligned}
a_1 &= p \\
a_2 &= q \\
a_3 &= qp^{-1} \\
a_4 &= qp^{-1}q^{-1} \\
a_5 &= qp^{-1}q^{-1}pq^{-1} \\
a_6 &= qp^{-1}q^{-1}pq^{-1}qpq^{-1} = qp^{-1}q^{-1}p^{2}q^{-1} \\
a_7 &= qp^{-1}q^{-1}p^{2}q^{-1}qp^{-1}qpq^{-1} = qp^{-1}q^{-1}pqpq^{-1} \\
a_8 &= qp^{-1}q^{-1}pqpq^{-1}qp^{-2}qpq^{-1} = qp^{-1}q^{-1}pqp^{-1}qpq^{-1} \\
\end{aligned}
$$
记 $t=qp^{-1}q^{-1}p$，则 $a_7 = tpt^{-1}$，$a_8 = tqt^{-1}$。
于是得到规律：$a_{n+6} = ta_nt^{-1}$，$a_{n+6k} = t^{k}a_nt^{-k}$。
快速幂即可，时间复杂度 $\mathcal O(n \log k)$。
代码
const int N = 1e5 + 7;
int n, k, p[N], q[N], vp[N], vq[N], t[N], vt[N], ans[N];
inline void init(int *a) {
for (int i = 1; i <= n; i++) a[i] = i;
}
inline void inv(int *a, int *b) {
for (int i = 1; i <= n; i++) b[a[i]] = i;
}
inline void mul(int *a, int *b) {
static int c[N];
for (int i = 1; i <= n; i++) c[i] = a[b[i]];
for (int i = 1; i <= n; i++) a[i] = c[i];
}
inline void ksm(int *a, int b) {
static int d[N];
init(d);
while (b) {
if (b & 1) mul(d, a);
mul(a, a), b >>= 1;
}
for (int i = 1; i <= n; i++) a[i] = d[i];
}
int main() {
rd(n, k), rda(p, n), rda(q, n), inv(p, vp), inv(q, vq);
init(t), mul(t, q), mul(t, vp), mul(t, vq), mul(t, p), inv(t, vt);
int r = k % 6 ? k % 6 : 6, w = (k - r) / 6;
ksm(t, w), ksm(vt, w);
init(ans), mul(ans, t);
switch (r) {
case 1 : mul(ans, p); break;
case 2 : mul(ans, q); break;
case 3 : mul(ans, q), mul(ans, vp); break;
case 4 : mul(ans, q), mul(ans, vp), mul(ans, vq); break;
case 5 : mul(ans, q), mul(ans, vp), mul(ans, vq), mul(ans, p), mul(ans, vq); break;
case 6 : mul(ans, q), mul(ans, vp), mul(ans, vq), mul(ans, p), mul(ans, p), mul(ans, vq); break;
}
mul(ans, vt);
printa(ans, n);
return 0;
}
Snuke the Phantom Thief
题意
- 有 $n$ 个两两不同的点，第 $i$ 个点的坐标为 $(x_i,y_i)$，价值为 $v_i$。
- 你要选择一些点，满足 $m$ 条限制，每条限制形如：
L a b，最多选择 $b$ 个 $x_i \le a$ 的点。R a b，最多选择 $b$ 个 $x_i \ge a$ 的点。D a b，最多选择 $b$ 个 $y_i \le a$ 的点。U a b，最多选择 $b$ 个 $y_i \ge a$ 的点。
- 求选择的点的最大价值和。
- $n \le 80$，$m \le 320$。
题解
枚举选择的点的个数 $k$，考虑费用流。
对于每一维，那么最多 $b$ 个 $\le a$ 的点可以转化为按坐标从小到大选择的第 $[b+1,k]$ 个点的坐标要 $\ge a + 1$，最多 $b$ 个 $\ge a$ 的点可以转化为选择的第 $[1,k-b]$ 个点的坐标要 $\le a – 1$。
考虑如何建图，将点 $i$ 拆成两个点 $P_i,Q_i$，另外加入 $2k$ 个点 $X_{1\dots k},Y_{1\dots k}$，表示某一维上选择的第 $i$ 个点。
连边如下：
- $(S, X_i, 1, 0)$。
- $(X_i,P_j,1,0)$，其中点 $j$ 在 $X_i$ 的坐标限制内。
- $(P_j,Q_j,1,-v_j)$。
- $(Q_j,Y_i,1,0)$，其中点 $j$ 在 $Y_i$ 的坐标限制内。
- $(Y_i,T,1,0)$。
跑最小费用最大流即可。
代码
namespace Dinic {
const int N = 1e5 + 7, M = 2e6 + 7;
const ll inf = 1e18;
int n, S, T;
int h[N], hi[N], e[M], t[M], tot;
ll d[N], f[M], c[M], mxf, ans;
bool v[N];
inline void add(int x, int y, ll z, ll w, bool o = 1) {
e[++tot] = y, f[tot] = z, c[tot] = w, t[tot] = h[x], h[x] = tot;
if (o) add(y, x, 0, -w, 0);
}
inline bool bfs() {
for (int i = 1; i <= n; i++) d[i] = inf, v[i] = 0;
queue<int> q;
q.push(S), d[S] = 0, v[S] = 1;
while (q.size()) {
int x = q.front();
q.pop(), v[x] = 0;
for (int i = h[x]; i; i = t[i]) {
int y = e[i];
ll z = f[i], w = c[i];
if (d[y] <= d[x] + w || !z) continue;
d[y] = d[x] + w;
if (!v[y]) q.push(y), v[y] = 1;
}
}
return d[T] != inf;
}
ll dfs(int x, ll now = inf) {
if (x == T) return now;
v[x] = 1;
ll rst = now;
for (int &i = hi[x]; i; i = t[i]) {
int y = e[i];
ll z = f[i], w = c[i];
if (v[y] || d[y] != d[x] + w || !z) continue;
ll k = dfs(y, min(z, rst));
if (!k) d[y] = inf;
else ans += k * w, f[i] -= k, f[i^1] += k, rst -= k;
if (!rst) break;
}
v[x] = 0;
return now - rst;
}
inline void main() {
while (bfs()) {
for (int i = 1; i <= n; i++) hi[i] = h[i];
ll now;
while ((now = dfs(S))) mxf += now;
}
}
inline void init(int _n, int _S, int _T) {
n = _n, S = _S, T = _T, tot = 1, mxf = 0, ans = 0;
for (int i = 1; i <= n; i++) h[i] = 0;
}
}
using Dinic::add;
const int N = 87, M = 327;
int n, m, x[N], y[N], a[M], b[M];
char t[M];
ll v[N], ans;
inline bool in(int l, int x, int r) {
return l <= x && x <= r;
}
inline ll work(int k) {
static int lx[N], rx[N], ly[N], ry[N];
for (int i = 1; i <= k; i++)
lx[i] = ly[i] = 1, rx[i] = ry[i] = 100;
for (int i = 1; i <= m; i++)
switch (t[i]) {
case 'L' : {
for (int j = b[i] + 1; j <= k; j++)
lx[j] = max(lx[j], a[i] + 1);
break;
}
case 'R' : {
for (int j = 1; j <= k - b[i]; j++)
rx[j] = min(rx[j], a[i] - 1);
break;
}
case 'D' : {
for (int j = b[i] + 1; j <= k; j++)
ly[j] = max(ly[j], a[i] + 1);
break;
}
case 'U' : {
for (int j = 1; j <= k - b[i]; j++)
ry[j] = min(ry[j], a[i] - 1);
break;
}
}
for (int i = 1; i <= n; i++)
if (lx[i] > rx[i] || ly[i] > ry[i]) return 0;
static int S, T, P[N], Q[N], X[N], Y[N], C;
S = 1, T = 2, C = 2;
for (int i = 1; i <= n; i++) P[i] = ++C, Q[i] = ++C;
for (int i = 1; i <= k; i++) X[i] = ++C, Y[i] = ++C;
Dinic::init(C, S, T);
for (int i = 1; i <= n; i++) add(P[i], Q[i], 1, -v[i]);
for (int i = 1; i <= k; i++) {
add(S, X[i], 1, 0), add(Y[i], T, 1, 0);
for (int j = 1; j <= n; j++) {
if (in(lx[i], x[j], rx[i])) add(X[i], P[j], 1, 0);
if (in(ly[i], y[j], ry[i])) add(Q[j], Y[i], 1, 0);
}
}
Dinic::main();
return Dinic::mxf == k ? -Dinic::ans : 0;
}
int main() {
rd(n);
for (int i = 1; i <= n; i++) rd(x[i], y[i]), rd(v[i]);
rd(m);
for (int i = 1; i <= m; i++) rdc(t[i]), rd(a[i], b[i]);
for (int k = 1; k <= n; k++) ans = max(ans, work(k));
print(ans);
return 0;
}
Walk on Graph
题意
- 给定一张 $n$ 个点 $m$ 条边的连通无向图，边有长度。
- 定义一条路径的长度为，设这条路径经过的边的长度依次为 $l_{1\dots k}$，则路径长度为 $\sum_{i=1}^{k} l_i2^{i-1}$。
- 有 $q$ 次询问，每次给定 $s,t,r$，求是否存在一条 $s \to t$ 的路径，满足其长度模 $P$ 的值为 $r$。
- $n,m,q \le 5 \times 10^4$，$P \le 10^6$ 且为奇数。
题解
倒过来考虑这个问题，走一条边 $c$ 就是 $x\to 2x+c$，因为 $P$ 是奇数，所以 $2$ 有逆元，即这是一个双射，所以一定能回到自己。
注意到一个点走两次一条边会回到自己，$x\to 4x+3c$，那么如果有另一条边 $c^\prime$，则我们能凑出 $3(c-c^\prime)$。记 $g$ 是所有边权之差以及 $P$ 的 $\gcd$，那么我们只需要在模 $\gcd(3g, P)$ 意义下考虑这个问题即可（此时模数要么是 $g$ 要么是 $3g$）。
假设所有边模 $g$ 都为 $z$，那么令 $x^\prime=x+z$，将边权减去 $z$，走一步后新的 $x^\prime$ 会变成 $2(x^\prime-z) + (c+z) + z = 2x^\prime + c$，和原来的规则一样，所以我们可以认为在新的图中，每条边都是 $g$ 的倍数。
对于 $(1,x)$，其能到的状态可以写成 $(v, 2^px+qg)(0\le q<3)$ 的形式，由之前的变换 $x\to 4x+3c$，且 $c$ 是 $g$ 的倍数，得 $x$ 和 $4x$ 是等价状态，故 $0\le p<2$。这样新的图中点数就只有 $\mathcal O(n)$ 个了，用并查集连一下就好了。
代码
const int N = 5e4 + 7, M = 1e6 + 7;
int n, m, q, P, a[N], b[N], c[N], f[N*6+1], g, z;
bool v[2][M];
inline int get(int x) {
return x == f[x] ? x : f[x] = get(f[x]);
}
inline void merge(int x, int y) {
f[get(x)] = get(y);
}
inline int id(int x, int y, int z) {
return (x - 1) * 6 + y * 3 + z;
}
int main() {
rd(n, m, q), rd(P);
for (int i = 1; i <= m; i++)
rd(a[i], b[i], c[i]), g = __gcd(g, abs(c[i] - c[1]));
g = g ? g : P, P = __gcd(P, 3 * g), z = c[1] % g;
for (int i = 1; i <= 6 * n; i++) f[i] = i;
for (int i = 1; i <= m; i++) {
int w = (c[i] - z) / g;
for (int p = 0; p < 2; p++)
for (int q = 0; q < 3; q++)
merge(id(a[i], p, q), id(b[i], 1 - p, (2 * q + w) % 3)),
merge(id(b[i], p, q), id(a[i], 1 - p, (2 * q + w) % 3));
}
for (int i = 0, j = z; i < P << 1; i++, (j <<= 1) %= P) v[i&1][j] = 1;
for (int i = 1, s, t, r; i <= q; i++) {
rd(s, t, r);
bool ans = 0;
for (int p = 0; p < 2; p++)
for (int q = 0; q < 3; q++)
if (get(id(t, 0, 0)) == get(id(s, p, q)))
ans |= v[p][(r+z+(3-q)*g)%P];
prints(ans ? "YES" : "NO");
}
return 0;
}
