2018冬令营模拟测试赛（四）
[Problem A]挑战NPC
试题描述
输入
见“试题描述”
输出
见“试题描述”
输入示例
见“试题描述”
输出示例
见“试题描述”
数据规模及约定
见“试题描述”
题解
这题不知为何我暴力 dfs 搜了 (90) 分……
我们可以考虑最苛刻的条件，即 (m = n - 1) 且 (p = 3)。
这样的话就是一棵树，我们要从一个根节点出发，最终回到根节点的某一个儿子。
将树二分染色，令根为黑色。那么对于黑色节点的子树就先经过这个点然后往子树里面跳，最终回到某个儿子（白），然后跳到另一个儿子（白）的一个儿子（黑）中，对于那个黑点重复这种过程；对于白色节点的子树，从前面的过程可以看出我进入这个子树的时候，已经在某个儿子当中了，我的目标就是最后出来的时候踩在这个字数的白根上。这显然是可以实现的，对于黑点我们先输出路径再递归，白点先递归在输出即可。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i++)
#define dwn(i, s, t) for(int i = (s); i >= (t); i--)
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 1010
#define maxm 2010
int n, fa[maxn], col[maxn];
int findset(int x) { return x == fa[x] ? x : fa[x] = findset(fa[x]); }
int m, head[maxn], nxt[maxm], to[maxm];
void AddEdge(int a, int b) {
to[++m] = b; nxt[m] = head[a]; head[a] = m;
swap(a, b);
to[++m] = b; nxt[m] = head[a]; head[a] = m;
return ;
}
void biparate(int u, int pa, int c) {
col[u] = c;
for(int e = head[u]; e; e = nxt[e]) if(to[e] != pa) biparate(to[e], u, 3 - c);
return ;
}
int Path[maxn], cnt;
void solve(int u, int pa) {
if(col[u] == 1) Path[++cnt] = u;
for(int e = head[u]; e; e = nxt[e]) if(to[e] != pa) solve(to[e], u);
if(col[u] == 2) Path[++cnt] = u;
return ;
}
int main() {
n = read(); int m = read(); read();
rep(i, 1, n) fa[i] = i;
rep(i, 1, m) {
int a = read(), b = read(), u = findset(a), v = findset(b);
if(u != v) fa[v] = u, AddEdge(a, b);
}
biparate(1, 0, 1);
solve(1, 0);
rep(i, 1, n) printf("%d%c", Path[i], i < n ? ' ' : '
');
return 0;
}
[Problem B]仙人掌
试题描述
输入
见“试题描述”
输出
见“试题描述”
输入示例
见“试题描述”
输出示例
见“试题描述”
数据规模及约定
见“试题描述”
题解
本题全场最难，看了题解还是觉得很烧脑……
我们一问一问来。
有根树的情况，令 (f_i) 表示 (i) 个节点的有根树的异构体个数，直接转移的话需要枚举有多少个儿子，每个儿子的大小，显然是指数级的复杂度。
考虑换一种 dp 顺序。我们每次把大小为 (i) 的有根树的贡献加进去，即每次都更新一下整个 dp 数组 (f_{i+1} sim f_n)（(f_1 sim f_i) 不可能再被更新了，因为它们撑不下一个大小为 (i) 的子树），在我 dp 进行到第 (i) 轮之前，我的所有子树大小都最多只有 (i-1) 那么大。那么所有 dp 值都缺少 (f_i) 的贡献，于是就给每个 dp 值加上有大小为 (i) 的子树的情况，我们需要枚举它们需要多少个大小为 (i) 的子树：(forall j in (i, n], f_j += sum_{t=1}^{lfloor frac{j}{i} floor} { C_t^{f_i + t - 1} cdot f'_{j-it} }) 注意式中的 (f') 表示的是加入大小为 (i) 的子树之前的 dp 值，在实现的过程中我们可以倒序枚举 (j)，避免前面对后面的影响。注：(C_t^{f_i + t - 1}) 表示的是从 (f_i) 种物品中选择 (t) 个，每种物品可以选无限次的方案数，至于为什么是这个可以自行百度（提示：转化成插板问题）。
这一问 (30) 分：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <map>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i++)
#define dwn(i, s, t) for(int i = (s); i >= (t); i--)
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 3010
#define LL long long
int n, MOD, f[maxn], inv[maxn];
int C[maxn][maxn]; // C[i][j]: f[i] choose j, can choose many times.
int Pow(int a, int b) {
int ans = 1, t = a;
while(b) {
if(b & 1) ans = (LL)ans * t % MOD;
t = (LL)t * t % MOD; b >>= 1;
}
return ans;
}
int main() {
n = read(); MOD = read();
inv[1] = 1;
rep(i, 2, n) inv[i] = (LL)(MOD - MOD / i) * inv[MOD%i] % MOD;
f[1] = 1;
rep(i, 1, n) {
C[i][0] = 1;
rep(t, 1, n / i) C[i][t] = (LL)C[i][t-1] * (f[i] + t - 1) % MOD * inv[t] % MOD;
dwn(j, n, i + 1) rep(t, 1, j / i) {
f[j] += (LL)C[i][t] * f[j-t*i] % MOD;
if(f[j] >= MOD) f[j] -= MOD;
}
}
printf("%d
", f[n]);
return 0;
}
对于无根树，也是这样 dp，只是在根节点上面特判一下每个子树的大小不能超过 (lfloor frac{n}{2} floor)，在上面贡献的时候限制一下就好了。
对于奇数的情况很容易（直接按照上述方法计算即可），因为不会有重复计数的问题，它重心唯一。
但对于偶数，由于是双重心我们可能会重复计算。我的方法是先限制每个子树的大小不超过 (frac{n}{2} - 1)，然后在处理两棵 (frac{n}{2}) 的子树对顶的情况，就是在 (f_{frac{n}{2}}) 中选择两个（可重复），用这个方案加上之前算的 (f_n) 就好了。
这一问 (50) 分：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <map>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i++)
#define dwn(i, s, t) for(int i = (s); i >= (t); i--)
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 3010
#define LL long long
int n, MOD, f[maxn], inv[maxn];
int C[maxn][maxn]; // C[i][j]: f[i] choose j, can choose many times.
int Pow(int a, int b) {
int ans = 1, t = a;
while(b) {
if(b & 1) ans = (LL)ans * t % MOD;
t = (LL)t * t % MOD; b >>= 1;
}
return ans;
}
int main() {
n = read(); MOD = read();
inv[1] = 1;
rep(i, 2, n) inv[i] = (LL)(MOD - MOD / i) * inv[MOD%i] % MOD;
f[1] = 1;
rep(i, 1, (n & 1) ? n / 2 : n / 2 - 1) {
C[i][0] = 1;
rep(t, 1, n / i) C[i][t] = (LL)C[i][t-1] * (f[i] + t - 1) % MOD * inv[t] % MOD;
dwn(j, n, i + 1) rep(t, 1, j / i) {
f[j] += (LL)C[i][t] * f[j-t*i] % MOD;
if(f[j] >= MOD) f[j] -= MOD;
}
}
if(n & 1) printf("%d
", f[n]);
else printf("%lld
", (f[n] + (LL)f[n/2] * (f[n/2] + 1) / 2 % MOD) % MOD);
return 0;
}
接下来就进入到最丧的仙人掌了。首先仙人掌可以转化成“圆方树”，然后“方点”不占体积，且只能连接“圆点”。
(f_i) 的定义不变，现在由于有环，那么方点的儿子就是有序的了，所以我们需要再维护一些值用来辅助计算。
(cac_{0, i}) 表示一个“方点”为根的，子树个数 (ge 1) 个，大小为 (i)（注意方点不算在“大小”中）的异构树的数目；
(cac_{1, i}) 表示一个“方点”为根的，子树个数 (ge 2) 个，大小为 (i) 的异构树的数目；（为什么要分开记呢？因为不能有重边，对于这个有根树，如果它只有一个“圆点”儿子，那么在加上父亲的“圆点”只有两个点构成一个环，就是重边了）。
以上两个我们都还没有考虑环的对称同构，所以会重复计数，下面这个就要考虑了。
(cir_i) 表示一个“方点”为根的，子树个数 (ge 2) 个，大小为 (i) 的异构树的数目（考虑对称同构）。
转移：(cac_{1, i} = sum_{j=1}^{n-1} {cac_{0, j} cdot f_{i-j}})，(cac_{0, i} = cac_{1, i} + f_i)，(cir_i = cac_{1, i} + sum_{j=1}^{lfloor frac{i}{2} floor} {cac_{0, j} cdot f_{i-2j}})。
给 (ge 1) 的“方”根树强塞一个儿子就是 (ge 2) 的“方”根树，(ge 2) 的“方”根树补上只有一个子树的情况就是 (ge 1) 的“方”根树，对称同构就是 (frac{不对称情况+对称情况}{2}) 来去重。
这一问 (100) 分：
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <map>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i++)
#define dwn(i, s, t) for(int i = (s); i >= (t); i--)
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 3010
#define LL long long
int n, MOD, f[maxn], cac[2][maxn], cir[maxn], inv[maxn];
int C[maxn][maxn]; // C[i][j]: f[i] choose j, can choose many times.
int Pow(int a, int b) {
int ans = 1, t = a;
while(b) {
if(b & 1) ans = (LL)ans * t % MOD;
t = (LL)t * t % MOD; b >>= 1;
}
return ans;
}
int main() {
n = read(); MOD = read();
inv[1] = 1;
rep(i, 2, n) inv[i] = (LL)(MOD - MOD / i) * inv[MOD%i] % MOD;
f[1] = 1;
rep(i, 1, n) {
rep(j, 1, i - 1) {
cac[1][i] += (LL)cac[0][j] * f[i-j] % MOD;
if(cac[1][i] >= MOD) cac[1][i] -= MOD;
}
cac[0][i] = (cac[1][i] + f[i]) % MOD;
cir[i] = cac[1][i];
rep(j, 1, i >> 1) {
cir[i] += (LL)cac[0][j] * max(1, f[i-2*j]) % MOD;
if(cir[i] >= MOD) cir[i] -= MOD;
}
cir[i] = (LL)cir[i] * inv[2] % MOD;
C[i][0] = 1;
rep(j, 1, n / i) C[i][j] = (LL)C[i][j-1] * (f[i] + cir[i] + j - 1) % MOD * inv[j] % MOD;
dwn(j, n, i + 1) rep(t, 1, j / i) {
f[j] += (LL)C[i][t] * f[j-i*t] % MOD;
if(f[j] >= MOD) f[j] -= MOD;
}
}
printf("%d
", f[n]);
return 0;
}
[Problem C]森林
试题描述
输入
见“试题描述”
输出
见“试题描述”
输入示例
见“试题描述”
输出示例
见“试题描述”
数据规模及约定
见“试题描述”
题解
又是一道 LCT 维护 dp 信息的题。这题对于虚边连出去的点直接暴力开个 map 维护每个子树的最大深度以及每个最大深度有多少个节点就好了。然后在 splay 中维护到最浅点的信息，由于要换根需要翻转，所以需要再维护一个到最深点的信息。
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <map>
using namespace std;
#define rep(i, s, t) for(int i = (s); i <= (t); i++)
#define dwn(i, s, t) for(int i = (s); i >= (t); i--)
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 400010
int ans;
struct LCT {
int fa[maxn], ch[maxn][2], siz[maxn], Ld[maxn], Lc[maxn], Rd[maxn], Rc[maxn], S[maxn], top;
bool rev[maxn];
map <int, int> tot[maxn];
bool isrt(int u) { return ch[fa[u]][0] != u && ch[fa[u]][1] != u; }
void maintain(int u) {
siz[u] = 1;
map <int, int> :: iterator it = tot[u].end(); it--;
int ls = ch[u][0] ? siz[ch[u][0]] : 0, rs = ch[u][1] ? siz[ch[u][1]] : 0;
Ld[u] = it->first + ls; Rd[u] = it->first + rs; Lc[u] = Rc[u] = it->second;
if(ch[u][0]) {
siz[u] += siz[ch[u][0]];
if(Ld[u] < Ld[ch[u][0]]) Ld[u] = Ld[ch[u][0]], Lc[u] = Lc[ch[u][0]];
else if(Ld[u] == Ld[ch[u][0]]) Lc[u] += Lc[ch[u][0]];
if(Rd[u] < Rd[ch[u][0]] + rs + 1) Rd[u] = Rd[ch[u][0]] + rs + 1, Rc[u] = Rc[ch[u][0]];
else if(Rd[u] == Rd[ch[u][0]] + rs + 1) Rc[u] += Rc[ch[u][0]];
}
if(ch[u][1]) {
siz[u] += siz[ch[u][1]];
if(Ld[u] < Ld[ch[u][1]] + ls + 1) Ld[u] = Ld[ch[u][1]] + ls + 1, Lc[u] = Lc[ch[u][1]];
else if(Ld[u] == Ld[ch[u][1]] + ls + 1) Lc[u] += Lc[ch[u][1]];
if(Rd[u] < Rd[ch[u][1]]) Rd[u] = Rd[ch[u][1]], Rc[u] = Rc[ch[u][1]];
else if(Rd[u] == Rd[ch[u][1]]) Rc[u] += Rc[ch[u][1]];
}
return ;
}
void pushdown(int u) {
if(!rev[u]) return ;
if(ch[u][0]) rev[ch[u][0]] ^= 1, swap(Ld[ch[u][0]], Rd[ch[u][0]]), swap(Lc[ch[u][0]], Rc[ch[u][0]]), swap(ch[ch[u][0]][0], ch[ch[u][0]][1]);
if(ch[u][1]) rev[ch[u][1]] ^= 1, swap(Ld[ch[u][1]], Rd[ch[u][1]]), swap(Lc[ch[u][1]], Rc[ch[u][1]]), swap(ch[ch[u][1]][0], ch[ch[u][1]][1]);
rev[u] = 0;
return ;
}
void rotate(int u) {
int y = fa[u], z = fa[y], l = 0, r = 1;
if(!isrt(y)) ch[z][ch[z][1]==y] = u;
if(ch[y][1] == u) swap(l, r);
fa[u] = z; fa[y] = u; fa[ch[u][r]] = y;
ch[y][l] = ch[u][r]; ch[u][r] = y;
maintain(y);
return ;
}
void splay(int u) {
int t = u; S[++top] = u;
while(!isrt(t)) S[++top] = fa[t], t = fa[t];
while(top) pushdown(S[top--]);
while(!isrt(u)) {
int y = fa[u], z = fa[y];
if(!isrt(y)) {
if(ch[y][0] == u ^ ch[z][0] == y) rotate(u);
else rotate(y);
}
rotate(u);
}
return maintain(u);
}
void AddTotal(int u, int son) {
if(!son) return ;
if(!tot[u].count(Ld[son] + 1)) tot[u][Ld[son]+1] = Lc[son];
else tot[u][Ld[son]+1] += Lc[son];
return ;
}
void DelTotal(int u, int son) {
if(!son) return ;
tot[u][Ld[son]+1] -= Lc[son];
if(!tot[u][Ld[son]+1]) tot[u].erase(Ld[son] + 1);
return ;
}
void access(int u) {
splay(u); AddTotal(u, ch[u][1]); ch[u][1] = 0; maintain(u);
while(fa[u]) {
splay(fa[u]); AddTotal(fa[u], ch[fa[u]][1]);
DelTotal(fa[u], u); ch[fa[u]][1] = u; maintain(fa[u]);
splay(u);
}
return ;
}
void makeroot(int u) {
access(u);
ans -= Lc[u];
rev[u] ^= 1; swap(Ld[u], Rd[u]); swap(Lc[u], Rc[u]); swap(ch[u][0], ch[u][1]);
ans += Lc[u];
return ;
}
void link(int a, int b) {
makeroot(a); access(b);
ans -= Lc[a] + Lc[b];
fa[a] = b; AddTotal(b, a); maintain(b);
ans += Lc[b];
return ;
}
void cut(int a) {
access(a);
ans -= Lc[a];
int b = ch[a][0]; fa[b] = ch[a][0] = 0; maintain(a);
ans += Lc[a] + Lc[b];
return ;
}
} sol;
int n, q;
int main() {
n = read(); q = read(); ans = n;
rep(i, 1, n) sol.tot[i][0] = 1, sol.maintain(i);
rep(i, 1, n) {
int u = read();
if(u) sol.link(i, u);
}
printf("%d
", ans);
while(q--) {
int op = read(), a = read(), b;
if(op == 1) {
b = read();
sol.link(a, b);
}
if(op == 2) sol.cut(a);
printf("%d
", ans);
}
return 0;
}