2018冬令营模拟测试赛（二）
[Problem A]最小生成树
试题描述
输入
见“试题描述”
输出
见“试题描述”
输入示例
见“试题描述”
输出示例
见“试题描述”
数据规模及约定
见“试题描述”
题解
这是一道坑了我的结论题（考场上推了半天结果得零分，最气的是发现再特判一下就 A 了！！！）
我们不妨让最终的最小生成树长成一条链，然后这条链的边权从左到右依次单调不降。
那么为了构建出 \(m\) 条边的无向图，我们可以贪心地再左边加边，即 \(t\) 从 \(1\) 开始计，每次将前 \(t\) 个点加边加成完全图，然后 \(t\) 加 \(1\)，直到 \(t=n\)（注意最开始要先把所有节点按顺序串成一条链）。
那么一个安排边权的贪心策略来了：将前 \(n-1\) 个点之间连接的所有边的边权安排成 \(1\)，然后剩下的边（即和第 \(n\) 个点连的所有边）边权安排成 \(n-2\)。
这样显然不是最优的，但这给我们提供了一个很好的思路，接下来的算法就是在上面这个建图基础上的。
我们假设一开始所有边权都是 \(0\)，那么有两种选择：一种是将所有边权 \(+1\)，一种是将和最后一个点有关的所有边权 \(+1\)；目标是让生成树的所有边之和 \(=s\)，那么这两种选择就相当于两种物品，背包的容量为 \(s\)，第一种体积为 \(1\)，代价为 \(x\)（即和最后一个点有关的边数）（注意这里用代价是因为我们要最小化这个值，而“价值”是一个褒义词故不用它），第二种物品物品体积为 \(n-1\)，代价为 \(m\)。那么假设我们选择 \(a\) 个第一种物品，\(b\) 个第二种物品，令 \(N = n-1\)，则有 \(a + bN = s\)，要最小化 \(ax + bm\) 的值；把 \(a\) 用 \(b\) 表示得到最小化 \((s-bN)x + bm = sx - Nxb + mb = (m-Nx)b + sx\)，当 \(m-Nx \ge 0\) 时 \(b = 0\) 即可，否则让 \(b\) 取到最大，也即 \(\lfloor \frac{s}{N} \rfloor\)。于是答案可以 \(O(1)\) 得到。
当然不要忘掉一个我考场上漏掉的特殊情况。容易发现我们上面列出的两个并不是全部可选的物品，因为我们还可以选择后任意多个点之间的所有边 \(+1\)——只需要保证每时每刻那条链的边权单调不降就行。这个问题的解决方案是所有边取平均值 \(\frac{s}{m}\)（前面的边下取整，后面的边上取整）就好了。至于为啥，我不知道。
#include#include #include #include #include #include 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--)#define LL long longLL read() { LL 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;}LL calc(int x) { return (LL)x * (x - 1) >> 1; }LL solve(int n, LL m, LL s, LL restm) { if(restm <= calc(n - 1)) return min(restm, calc(n - 1)) + s + 1; n--; restm -= calc(n); restm++; // printf("(1, %lld)\n(%d, %lld)\ns = %lld\n", restm, n, m, s); if(m - restm * n >= 0) return s * restm + m; LL a = s, b = 0; LL k = a / n; b += k; return s * restm + b * (m - restm * n) + m;}LL avg(int n, LL m, LL s) { LL lo = s / (n - 1), hi = (s + n - 2) / (n - 1); if(lo == hi) return m * lo; n--; LL restm = m - 1 - calc(n) + 1, sma = lo * n + n - s, pre = min(calc(sma + 1) - sma + 1, m - n + 1) + sma - 1, suf = m - pre; return pre * lo + suf * hi;}int main() { int T = read(); while(T--) { int n = read(); LL m = read(), s = read() - n + 1, restm = m - 1; printf("%lld\n", min(solve(n, m, s, restm), avg(n, m, s + n - 1))); } return 0;}
[Problem B]没有上司的舞会
试题描述
输入
见“试题描述”
输出
见“试题描述”
输入示例
见“试题描述”
输出示例
见“试题描述”
数据规模及约定
见“试题描述”
题解
用数据结构维护 dp 信息。一句话解决问题。
好吧还是讲讲，我们考虑用 LCT 维护动态加点的操作，每个节点 \(i\) 记录 \(f_0(i)\) 和 \(f_1(i)\) 分别表示不选和选择它自己最多能从它以及它所有 LCT 上“非访问边”中选择多少个节点。\(access\) 操作的时候直接对 \(f_0\) 和 \(f_1\) 进行加减操作实现加入一个儿子和删掉一个儿子。此外在 splay 中搞一个 \(F_{a,b}(i)\)（\(a, b\) 都是 \(0\) 或 \(1\) 的整数）表示对于 splay 中的子树 \(i\)，首、尾选不选的 dp 值，这样就可以方便地合并了。
#include#include #include #include #include #include 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 300010#define oo 2147483647struct LCT { int f[maxn][2], F[maxn][2][2]; int fa[maxn], ch[maxn][2]; bool isrt(int u) { return ch[fa[u]][0] != u && ch[fa[u]][1] != u; } void merge(int to, int l, int r) { int nf[2][2]; nf[0][0] = max(max(F[l][0][1] >= 0 && F[r][0][0] >= 0 ? F[l][0][1] + F[r][0][0] : -1, F[l][0][0] >= 0 && F[r][1][0] >= 0 ? F[l][0][0] + F[r][1][0] : -1), F[l][0][0] >= 0 && F[r][0][0] >= 0 ? F[l][0][0] + F[r][0][0] : -1); nf[0][1] = max(max(F[l][0][1] >= 0 && F[r][0][1] >= 0 ? F[l][0][1] + F[r][0][1] : -1, F[l][0][0] >= 0 && F[r][1][1] >= 0 ? F[l][0][0] + F[r][1][1] : -1), F[l][0][0] >= 0 && F[r][0][1] >= 0 ? F[l][0][0] + F[r][0][1] : -1); nf[1][0] = max(max(F[l][1][1] >= 0 && F[r][0][0] >= 0 ? F[l][1][1] + F[r][0][0] : -1, F[l][1][0] >= 0 && F[r][1][0] >= 0 ? F[l][1][0] + F[r][1][0] : -1), F[l][1][0] >= 0 && F[r][0][0] >= 0 ? F[l][1][0] + F[r][0][0] : -1); nf[1][1] = max(max(F[l][1][1] >= 0 && F[r][0][1] >= 0 ? F[l][1][1] + F[r][0][1] : -1, F[l][1][0] >= 0 && F[r][1][1] >= 0 ? F[l][1][0] + F[r][1][1] : -1), F[l][1][0] >= 0 && F[r][0][1] >= 0 ? F[l][1][0] + F[r][0][1] : -1); memcpy(F[to], nf, sizeof(nf)); return ; } void maintain(int u) { F[u][0][0] = f[u][0]; F[u][1][1] = f[u][1]; F[u][0][1] = F[u][1][0] = -1; if(ch[u][0]) merge(u, ch[u][0], u); if(ch[u][1]) merge(u, u, ch[u][1]); 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; return maintain(y); } void splay(int u) { 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 access(int u) { splay(u); int fson[2]; if(ch[u][1]) { fson[0] = max(F[ch[u][1]][0][0], F[ch[u][1]][0][1]); fson[1] = max(F[ch[u][1]][1][0], F[ch[u][1]][1][1]); f[u][0] += max(fson[0], fson[1]); f[u][1] += fson[0]; } ch[u][1] = 0; maintain(u); while(fa[u]) { splay(fa[u]); if(ch[fa[u]][1]) { fson[0] = max(F[ch[fa[u]][1]][0][0], F[ch[fa[u]][1]][0][1]); fson[1] = max(F[ch[fa[u]][1]][1][0], F[ch[fa[u]][1]][1][1]); f[fa[u]][0] += max(fson[0], fson[1]); f[fa[u]][1] += fson[0]; } fson[0] = max(F[u][0][0], F[u][0][1]); fson[1] = max(F[u][1][0], F[u][1][1]); f[fa[u]][0] -= max(fson[0], fson[1]); f[fa[u]][1] -= fson[0]; ch[fa[u]][1] = u; maintain(fa[u]); splay(u); } return ; } void link(int a, int b) { // b should be a leaf f[b][0] = 0; f[b][1] = 1; maintain(b); access(a); fa[b] = a; ch[a][1] = b; maintain(a); return ; }} sol;int main() { int n = read() + 1, type = read(), lstans = 0; // printf("%d %d\n", n, type); sol.f[1][0] = 0; sol.f[1][1] = 1; sol.maintain(1); rep(i, 2, n) { int fa = (read() ^ type * lstans) + 1; sol.link(fa, i); sol.access(1); printf("%d\n", lstans = max(sol.f[1][0], sol.f[1][1])); } return 0;}
[Problem C]排列问题
试题描述
输入
见“试题描述”
输出
见“试题描述”
输入示例
见“试题描述”
输出示例
见“试题描述”
数据规模及约定
见“试题描述”
题解
我去这题有点毒瘤。
首先你需要想到容斥 dp，其它 dp 方式都无法搞定正解。
令 \(f(i, j)\) 表示对于前 \(i\) 种颜色，序列强行分了 \(j\) 段的方案数，那么转移就简单了，枚举最后一种颜色分多少段即可，然后推式子搞搞成为卷积的形式：\(f(i, j) = \sum_{k=1}^{\mathrm{min}\{ a_i, j \}} { f(i-1, j-k) \cdot C_j^k \cdot C_{a_i-1}^{k-1} } = \sum_{k=1}^{\mathrm{min}\{ a_i, j \}} { f(i-1, j - k) \cdot \frac{j!}{k!(j-k)!} \cdot \frac{(a_i-1)!}{(k-1)!(a_i-k)!} } \Rightarrow \frac{f(i, j)}{j!} = \sum_{k=1}^{\mathrm{min}\{ a_i, j \}} { \frac{f(i-1, j-k)}{(j-k)!} \cdot \frac{(a_i-1)!}{k!(k-1)!(a_i-k)!} }\)
于是令 \(A_i(x) = \sum_{k=1}^{a_i} { \frac{(a_i - 1)!}{k!(k-1)!(a_i-k)!} \cdot x^k }\)，\(F_0(x) = 1\)，那么得到的 \(F_n(x) = F_0(x) \cdot \prod_{i=1}^n {A_i(x)}\) 所有系数就是最后的 \(f(n, i) \cdot i!\)，由于乘法有结合律，可以先分治 FFT 求出后面那一坨 \(A_i(x)\) 乘起来的多项式，然后再用 \(F_0(x)\) 去乘就好了。
然后我们还要容斥，显然上面会重复计算，上面的 dp 会对球序列多分几段，所以要依次减掉多分一段的，加上多分两段的，减去多分三段的……形式化地：令 \(\forall i \in [1, m], g(i) = f(n, i)\)，最终分 \(i\) 段的方案数为 \(Ans_i\)，则 \(Ans_i = \sum_{j=1}^i { (-1)^{i-j} \cdot g(j) \cdot C_{m-j}^{i-j} } \Rightarrow Ans_i \cdot (m-i)! = \sum_{j=1}^i {g(j) \cdot (m-j)! \cdot \frac{(-1)^{i-j}}{(i-j)!} }\)，还是卷积！再 FFT 一下就好了。
#include#include #include #include #include #include #include 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 524288#define MOD 998244353#define Groot 3#define LL long longint rev[maxn];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;}void FFT(vector &A, int len, int tp) { int n = 1 << len; rep(i, 0, n - 1) if(i < rev[i]) swap(A[i], A[rev[i]]); rep(i, 1, len) { int wn = Pow(Groot, MOD - 1 >> i); if(tp < 0) wn = Pow(wn, MOD - 2); for(int j = 0; j < n; j += 1 << i) { int w = 1; rep(k, 0, (1 << i >> 1) - 1) { int al = A[j+k], ar = (LL)w * A[j+k+(1< >1)] % MOD; A[j+k] = (al + ar) % MOD; A[j+k+(1<>1)] = (al - ar + MOD) % MOD; w = (LL)w * wn % MOD; } } } if(tp < 0) rep(i, 0, n - 1) A[i] = (LL)A[i] * Pow(n, MOD - 2) % MOD; return ;}void Mul(vector &A, vector &B) { int n = A.size() - 1, N = 1, len = 0; while(N <= n) N <<= 1, len++; rep(i, 1, N - 1) rev[i] = (rev[i>>1] >> 1) | ((i & 1) << len - 1); FFT(A, len, 1); FFT(B, len, 1); rep(i, 0, N - 1) A[i] = (LL)A[i] * B[i] % MOD; FFT(A, len, -1); return ;}int m, a[maxn], fac[maxn], ifac[maxn];vector GetTrans(int l, int r) { if(l == r) { vector A(a[l] + 1); A[0] = 0; rep(i, 1, a[r]) A[i] = (LL)fac[a[l]-1] * ifac[i] % MOD * ifac[i-1] % MOD * ifac[a[r]-i] % MOD; return A; } int mid = l + r >> 1; vector A = GetTrans(l, mid), B = GetTrans(mid + 1, r); int asiz = A.size(), bsiz = B.size(), siz = asiz + bsiz, need = 1; while(need <= siz - 2) need <<= 1; A.resize(need); B.resize(need); rep(i, asiz, need - 1) A[i] = 0; rep(i, bsiz, need - 1) B[i] = 0; Mul(A, B); vector E(siz-1); rep(i, 0, siz - 2) E[i] = A[i]; return E;}int main() { int n = read(); rep(i, 1, n) a[i] = read(), m += a[i]; fac[0] = ifac[0] = 1; rep(i, 1, m) fac[i] = (LL)fac[i-1] * i % MOD, ifac[i] = (LL)ifac[i-1] * Pow(i, MOD - 2) % MOD; vector A = GetTrans(1, n), F; int siz = A.size(), need = 1; while(need <= siz - 1) need <<= 1; F.resize(need); F[0] = 1; rep(i, 1, need - 1) F[i] = 0; A.resize(need); rep(i, siz, need - 1) A[i] = 0; Mul(F, A); rep(i, 0, siz - 1) F[i] = (LL)F[i] * fac[i] % MOD; // printf("F[0~%d]: ", m); rep(i, 0, m) printf("%d%c", F[i], i < m ? ' ' : '\n'); need = 1; while(need <= (m << 1)) need <<= 1; vector G(need), T(need); G[0] = 0; rep(i, 1, m) G[i] = (LL)F[i] * fac[m-i] % MOD; rep(i, m + 1, need - 1) G[i] = 0; // rep(i, 0, m) printf("%d%c", G[i], i < m ? ' ' : '\n'); rep(i, 0, m) T[i] = (i & 1) ? MOD - ifac[i] : ifac[i]; rep(i, m + 1, need - 1) T[i] = 0; Mul(G, T); rep(i, 0, m) G[i] = (LL)G[i] * ifac[m-i] % MOD; int q = read(); while(q--) { int k = read(); printf("%d\n", G[m-k]); } return 0;}