AtCoder Grand Contest 043 题解
Visits: 416
Range Flip Find Route
注意到,最后走的路线一定是黑白交替的。
每一次翻转颜色都一定是在进入黑色的时候,将后面一段黑色的路变成白色。
这与最短路很类似,由于边权只有 $0/1$,因此本题用 deque
bfs 即可,时间复杂度 $\mathcal O(nm)$。
const int N = 107, inf = 1e9;
int n, m, d[N][N], v[N][N];
char s[N][N];
deque<pi> q;
int main() {
rd(n), rd(m);
for (int i = 1; i <= n; i++) rds(s[i], m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
d[i][j] = inf;
q.pb(mp(1, 1)), d[1][1] = s[1][1] == '#';
while (q.size()) {
pi x = q.front();
q.pop_front();
if (v[x.fi][x.se]) continue;
v[x.fi][x.se] = 1;
if (x.fi < n) {
if (s[x.fi][x.se] == '.' && s[x.fi+1][x.se] == '#') {
if (d[x.fi+1][x.se] > d[x.fi][x.se] + 1)
q.pb(mp(x.fi + 1, x.se)), d[x.fi+1][x.se] = d[x.fi][x.se] + 1;
} else {
if (d[x.fi+1][x.se] > d[x.fi][x.se])
q.push_front(mp(x.fi + 1, x.se)), d[x.fi+1][x.se] = d[x.fi][x.se];
}
}
if (x.se < m) {
if (s[x.fi][x.se] == '.' && s[x.fi][x.se+1] == '#') {
if (d[x.fi][x.se+1] > d[x.fi][x.se] + 1)
q.pb(mp(x.fi, x.se + 1)), d[x.fi][x.se+1] = d[x.fi][x.se] + 1;
} else {
if (d[x.fi][x.se+1] > d[x.fi][x.se])
q.push_front(mp(x.fi, x.se + 1)), d[x.fi][x.se+1] = d[x.fi][x.se];
}
}
}
print(d[n][m]);
return 0;
}
123 Triangle
首先进行一次绝对值差分,让序列中的数都在 $0 \sim 2$ 中,显然无论什么情况后面的每个数只可能为 $0 \sim 2$。
如果此时的序列中存在 $1$,则意味着答案只可能是 $0$ 或 $1$;如果不存在 $1$,则答案只可能是 $0$ 或 $2$。
对于不存在 $1$ 的情况,我们可以将每个数都 $\div 2$,最后再将答案 $\times 2$,这显然是等价的。
于是现在的答案都只可能是 $0$ 或 $1$ 了,于是显然我们只用在模 $2$ 的情况下讨论。
考虑一次绝对值差分在模 $2$ 意义下的影响,可以发现等价于 $\operatorname{xor}$。
现在问题变为,给定一个 $0/1$ 序列,每次将相邻两个数 $\operatorname{xor}$,求最后剩下的数。
那么考虑每个数会被异或几次即可,设序列长度为 $n$,则位置 $i$ 上的数会被异或 $\binom {n-1}{i-1}$ 次。
这时候我们还要求出模 $2$ 意义下的组合数,一个简单的方法是计算每个阶乘的分解中 $2$ 的次数,将计算组合数时的除法改为做减法。则对于一个组合数,最后如果剩下的 $2$ 的次数为 $0$,则说明 $\bmod 2 = 1$,否则 $\bmod 2 = 0$。
对于阶乘的分解,可以先对每个数简单地求出分解中 $2$ 的次数,然后做前缀和即可。
时间复杂度 $\mathcal O(n)$。
const int N = 1e6 + 7;
int n, a[N], c[N];
char s[N];
int main() {
rd(n), rds(s, n), --n;
for (int i = 1; i <= n; i++) a[i] = abs(s[i] - s[i+1]);
bool ok = 0;
for (int i = 1; i <= n; i++)
if (a[i] == 1) ok = 1;
if (!ok) for (int i = 1; i <= n; i++) a[i] >>= 1;
for (int i = 1; i <= n; i++) {
int x = i;
while (!(x & 1)) ++c[i], x >>= 1;
c[i] += c[i-1];
}
int ans = 0;
for (int i = 1; i <= n; i++)
ans ^= c[n-1] - c[i-1] - c[n-i] ? 0 : (a[i] & 1);
if (!ok) ans <<= 1;
print(ans);
return 0;
}
Giant Graph
以下设 $n,m$ 同阶。
由于 $10^{18}$ 非常大,因此求最大独立集,相当于贪心地从权值大的往小的选,能选则选。
考虑 dp,设 $f_{x,y,z}$ 表示点 $(x,y,z)$ 是否要被选。
转移方程为 $f_{x,y,z} = \prod_{(x^\prime,y^\prime,z^\prime) \to (x,y,z)} [f_{x^\prime,y^\prime,z^\prime} = 0]$,其中 $(x^\prime,y^\prime,z^\prime) \to (x,y,z)$ 表示 $(x^\prime,y^\prime,z^\prime), (x,y,z)$ 之间有边且 $x^\prime + y^\prime + z^\prime \ge x + y + z$。
时间复杂度 $\mathcal O(n^3)$,显然过不了。
考虑如下这样一个博弈问题:
有三张 $n$ 个点的有向图,每张图在某个点上都有一个标记。
有两个人轮流进行移动,每次移动可以将一个标记从一条出边移动过去。
谁不能移动了谁就输了。
对于这样一个博弈问题,用 $\operatorname{SG}$ 函数可以解决。
然后可以发现,这个博弈问题的 $\operatorname{SG}$ 函数和上面那个 dp 的状态是一样的。
而这个博弈问题中,三张图之间相互独立。
这让我们想到了 $\operatorname{Nim}$ 游戏,即我们可以将三张图的 $\operatorname{SG}$ 函数分开算,最后 $\operatorname{xor}$ 起来得到原来的 $\operatorname{SG}$ 函数。$\operatorname{SG}$ 函数为 $0$ 的点,即为原问题中要选择的点。
注意到,对于一个 DAG 博弈转移图,$\operatorname{SG}$ 函数值的上界是 $\mathcal O(\sqrt n)$ 的,因此我们可以 $\mathcal O(n)$ 求出答案。
const int N = 1e5 + 7;
const modint K = 1000000000000000000ll % P;
int n;
modint ans;
struct Graph {
int n, m, sg[N], k;
modint c[N];
vi e[N];
inline Graph() {}
inline Graph(int n) : n(n) {}
int SG(int x) {
if (~sg[x]) return sg[x];
map<int, bool> p;
for (int y : e[x]) p[SG(y)] = 1;
while (p[++sg[x]]);
return sg[x];
}
inline void main() {
rd(m);
for (int i = 1; i <= n; i++) sg[i] = -1;
for (int i = 1, x, y; i <= m; i++) {
rd(x), rd(y);
if (x > y) swap(x, y);
e[x].pb(y);
}
for (int i = 1; i <= n; i++) if (!~sg[i]) SG(i);
for (int i = 1; i <= n; i++) k = max(k, sg[i]), c[sg[i]] += K ^ i;
}
} G[3];
int main() {
rd(n);
for (int i = 0; i < 3; i++) G[i] = Graph(n), G[i].main();
for (int i = 0; i <= G[0].k; i++)
for (int j = 0; j <= G[1].k; j++)
ans += G[0].c[i] * G[1].c[j] * G[2].c[i^j];
print(ans);
return 0;
}
Merge Triplet
考虑已知每个序列,我们是如何构造排列的。
按照题意,每次选择最小的开头放入排列,然后扔掉。
这意味着,由于序列长度为 $3$,排列中一定不会出现连续四个(或以上)的数 $x_{1\dots 4}$,满足 $x_1 > x_{2\dots 4}$。
因此,最终的排列中,按照前缀 $\max$ 的位置划分,每一段的长度不超过 $3$,这是必要条件。
充分吗?不充分,比如 $2\ 1\ 4\ 3\ 6\ 5$ 就不可以。
我们发现,按照前缀 $\max$ 的位置划分,有三个长度为 $2$ 的段,而我们没办法讲其拼成两个长度为 $3$ 的序列。
于是另一个必要条件为,长度为 $2$ 的段个数不超过长度为 $1$ 的段个数。
充分吗?充分,因为一旦满足这个条件,我们就能构造出来序列。
那么考虑如何计数,设 $f_{i,j}$ 表示考虑前 $i$ 个数,长度为 $1$ 的段个数减去长度为 $2$ 的段个数为 $j$ 的方案数。
转移时枚举下一段的长度 $1/2/3$ 即可,如果长度不为 $1$ 还要额外乘上系数,具体见代码。
时间复杂度 $\mathcal O(n^2)$。
const int N = 2e3 + 7, M = N * 3;
int n;
modint f[M][M<<1], ans;
int main() {
rd(n), rd(P), n *= 3;
f[0][M] = 1;
for (int i = 0; i < n; i++)
for (int j = -i; j <= i; j++) {
f[i+1][j+1+M] += f[i][j+M];
f[i+2][j-1+M] += f[i][j+M] * (i + 1);
f[i+3][j+M] += f[i][j+M] * (i + 1) * (i + 2);
}
for (int j = 0; j <= n; j++) ans += f[n][j+M];
print(ans);
return 0;
}
Topology
首先判合法性,显然一个合法点集的所有子集都应该合法,一个非法点集的所有超集都应该非法,特别地,空集必须合法。
判完之后考虑如何构造,考虑一个极小非法点集 $S$。我们如果构造出来一个从 $(0,0)$ 开始的环,使得它在 $S$ 非法,在 $S$ 的真子集合法,那么对于所有的极小非法点集如此构造后,将这些环在 $(0,0)$ 处接起来即可。
考虑对于一个点集 $S$,如何判断一个环合法:
从环的最左端开始,沿一个方向走一圈,穿过第 $i(\in S)$ 条线上方时记录一个 $u_i$,穿过下方时记录一个 $d_i$,这样得到一个字符串。
不断地在字符串中选择两个相邻且相同的字符删掉,如果能清空,则该点集合法,否则非法。
稍微画一下就能证明。
显然如果我们已知这个字符串,是可以还原出这个环的,因此问题转化为构造这个字符串。
考虑如下递归构造,一开始在 $(0,0)$:
- 若此时右边只剩下了一个点,则绕一个圈,即返回 $u_1d_1$。
- 否则穿过第一个点的上方,然后递归,得到字符串 $t$,然后从第一个点上方穿回来。
- 再从第一个点的下方穿过去,按照 $t^r$ 的方式走,然后再从第一个点下方穿回来。
- 返回字符串 $u_1tu_1d_1t^r d_1$。
稍微画一下同样能证明这个构造的正确性。
#define Fail prints("Impossible"), exit(0)
#define vp vector<pi>
int n, f[1<<8|1];
string s;
vp p[1<<8|1], ans(1, mp(0, 0));
inline bool pd(int i) {
for (int j = (i - 1) & i; j; j = (j - 1) & i)
if (s[j] == '0') return 0;
return 1;
}
inline void merge(vp &a, vp b) {
for (pi o : b) a.pb(o);
}
inline vp work(int i) {
if (p[i].size()) return p[i];
int j = i & -i, k = f[j];
p[i].pb(mp(k, 1));
p[i].pb(mp(k + 1, 1));
vp t = work(i - j);
merge(p[i], t);
p[i].pb(mp(k + 1, 1));
p[i].pb(mp(k, 1));
p[i].pb(mp(k, 0));
p[i].pb(mp(k + 1, 0));
p[i].pb(mp(k + 1, 1));
reverse(t.begin(), t.end());
merge(p[i], t);
p[i].pb(mp(k + 1, 1));
p[i].pb(mp(k + 1, 0));
p[i].pb(mp(k, 0));
p[i].pb(mp(k, 1));
return p[i];
}
inline vp get(pi a, pi b) {
vp ret(1, a);
if (a.se != b.se) return ret.pb(b), ret;
while (a != b)
a.fi += a.fi < b.fi ? 1 : -1, ret.pb(a);
return ret;
}
inline vp update(vp a) {
if (a.size() == 1u) return a;
vp b;
for (ui i = 1; i < a.size(); i++) merge(b, get(a[i-1], a[i]));
return b;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> s;
if (s[0] == '0') Fail;
for (int i = 0; i < (1 << n); i++)
if (s[i] == '1')
for (int j = i; j; j = (j - 1) & i)
if (s[j] == '0') Fail;
for (int i = 0; i < n; i++) {
f[1<<i] = i;
p[1<<i].pb(mp(i, 1));
p[1<<i].pb(mp(i + 1, 1));
p[1<<i].pb(mp(i + 1, 0));
p[1<<i].pb(mp(i, 0));
p[1<<i].pb(mp(i, 1));
}
for (int i = 0; i < (1 << n); i++)
if (s[i] == '0' && pd(i))
ans.pb(mp(0, 1)), merge(ans, work(i)),
ans.pb(mp(0, 1)), ans.pb(mp(0, 0));
ans = update(ans);
ans.erase(unique(ans.begin(), ans.end()), ans.end());
prints("Possible");
print(ans.size() - 1);
for (pi o : ans) print(o.fi, o.se);
return 0;
}
Jewelry Box
题目太神仙了,先咕咕咕着。