「杂题选做」八月口胡合集

众所周知，做题的关键在于口胡出解法，而我还是什么都不会……

本篇 Blog 多以口胡为主，杂题居多。

1 Hunger Game

有 $N$ 个箱子，每个箱子有 $a[i]$ 个石头，一开始所有箱子都是关着的。
Alice 和 Bob 轮流操作，每次可以至少打开一个被关闭的箱子，或者选择一个已经开着的箱子拿走里面至少一个石头。
不能操作的输，求先手必胜还是后手必胜。
$1\le N\le 1e5, 0\le a[i]<10^9$

Nim 博弈的经典结论：对于每个状态有 $SG_i=a_i$ ，则终态是 P 态的充要条件是 $a_1\oplus a_2\oplus … \oplus a_n = 0$。

回到本题，如果存在一个 $a_1,a_2,…a_n$ 的子集使其异或和为 0，先手选择一个极大的这样的子集打开，则丢给后手了一个 P 态；此时后手一定要考虑去开新的箱子，但是不存在新的子集使其异或和为 0 了，因此后手并不能挽回局面，故此时为 N 态。
如果不存在呢？那么无论先手怎么开箱子，得到的都一定是 N 态，故此时为 P 态。

因此结论：先手必胜当且仅当存在一个子集使之异或和为 0。
大力枚举 $O(2^n)$ ，可通过线性基降成 $O(n)$ 。

2 Minimum Value of Equation

给定 $k[i],b[i]$，有 $n$ 个函数，第 $j$ 个函数为 $f_j(x)=\sum |k[i]x+b[i]|$，其中$1\le i\le j$。
对于每个 $j=1…n$，求出 $f_j(x)$ 的最小值。
$1\le n\le 10^5 , |k[i]|\le 1000$

提一下公因式变成 $\sum k_i|x+(b_i/k_i)|$ ，即 $x$ 到数轴上的一堆点 $b_i/k_i$ 的距离和，那么 $x$ 取这些点的中位数就好了。

3 DFS Count

给定一个 $n$ 个点的有向图，求合法的 DFS 序的个数。
$n \le 13$

直接搜？？？（雾
设 $f[u,S]$ 表示当前在 $u$ ，没走过的点集为 $S$ 的方案数。$|S|$ 是递减的，可通过其来划分子问题，得到转移：
$$ f[v,T_v \And S]·f[u,S-(T_v \And S)] \to f[u, S] | (u,v)\in E$$
其中 $T_v$ 是 $v$ 能到达的点集。容易发现这次从小集合往大集合转移，则其是可操作的。

4 XOR Product

给定序列 $a_1,…,a_n$ ，求：
$$ \sum\limits_{i<j<k}(a_i\oplus a_j)·(a_j \oplus a_k) $$

把 $j$ 提出来，拆一下柿子：
$$ \sum\limits_j(\sum\limits_{i<j}a_i\oplus a_j)(\sum\limits_{j<k}a_j \oplus a_k) $$
考虑求 $\sum\limits_{i<j}a_i\oplus a_j$ ，把每一位拆开算贡献，则应当统计 $a_1,…,a_{j-1}$ 中这一位上有多少个 1 ，预处理即可。
预处理是 $O(n\log)$ 的，枚举 $j$ 处理前后两个 sigma 是 $O(n\log)$ 的，最后统计答案也是 $O(n)$ 的。

5 SUMXOR

给定序列 $a[1…n]$ 和 $b[1…n]$ ，求：
$$ \bigoplus\limits_{i,j}a_i+b_j $$

依然拆开每一位算，考虑第 $w$ 位的贡献应当是 $2^w\sum[(a_i+b_j)\text{ mod } 2^{w+1} \ge 2^w] \text{ mod }2$。
令 $a_i\gets a_i\text{ mod }2^{w+1},b_i\gets b_i\text{ mod }2^{w+1} $，有两种情况：

1. $a_i + b_j \ge 2^{w+1}$，则应当有 $a_i+b_j-2^{w+1}\ge 2^w$，移项得 $a_i+b_j\ge 2^w+2^{w+1}$
2. $a_i+b_j< 2^{w+1}$，则应当有 $2^w\le a_i+b_j< 2^{w+1}$

于是转化成序列上的查询问题，Two-Pointers 扫即可。

6 The Hanged Man

有一个 $n$ 个点的树，每个点有一个体积 $v[i]$ 和收益 $w[i]$，现在你能选一个独立集，对于每个 $i$ 输出体积和为 $i$ 的收益和最大的独立集的值。
$n\le 50, m\le 5000$

$O(nm^2)$ 的 DP 显然啊，但是重链剖分 DP 看不懂啊，这个先咕着。

资料：乱搞，重链剖分

附一个 $O(nm^2)$ 的 DP：

int n, m, vi[CN], wi[CN], f[CN][5005][2];
void dfs(int u, int p){
    for(int k = hd[u]; k; k = E[k].nxt){
        int v = E[k].to;
        if(v ^ p) dfs(v, u);
    }
    f[u][ vi[u] ][1] = wi[u];
    for(int k = hd[u]; k; k = E[k].nxt){
        int v = E[k].to; if(v == p) continue;
        for(int V = m; V; V--)
            for(int Vp = 0; Vp <= V; Vp++){
                if(V - Vp >= vi[u]) f[u][V][1] = max(f[u][V][1], f[v][Vp][0] + f[u][V - Vp][1]);
                f[u][V][0] = max(f[u][V][0], max(f[v][Vp][0], f[v][Vp][1]) + f[u][V - Vp][0]);
            }
    }
}

7 Anton and Ira

给定两个排列 $s$ 和 $p$ ，每次可以交换 $p$ 中的两个数，代价为它们间的距离，问最小代价使 $p$ 变为 $s$ ，输出方案。
$n\le 1000$

设 $to[u]$ 是 $u$ 想要去到的位置，可以将其看作一条有向边。根据抽屉原理，某一时刻必然存在一个点使 $to[u]$ 与 $to[to[u]]$ 反向，于是贪心就好了。
设这样得到的答案为 $s$，容易发现对于一种操作方案，必然存在另一种与之互为补集的操作方案，其答案也为 $s$。两者可以组成全集，即有 $2s=\sum|i-to[i]|$，从而 $s=\sum|i-to[i]|/2$。

8 Increasing Shortest Path

有个 $n$ 个点 $m$ 条边的有向图，有 $q$ 个询问：从 $ai$ 到 $bi$，边权递增，经过不超过 $ci$ 条边，权值和最小是多少？
$T$组数据（$T\le 100$）。
$n ≤ 150, m, q ≤ 5000.$

$n$ 比较小，那么考虑 DP。
边权看上去没办法放进状态里面，有一个技巧是把边升序排序，然后按照边来转移状态，即可满足要求。

设 $f[u,v,m]$ 表示 $u\to v$ 经过不超过 $m$ 条边的答案，$O(n)$ 固定起点 $s$，$O(m)$ 枚举一条边 $(u,v,w)$，则有转移：
$$ f[s,u,k]+w\to f[s,v,k+1] $$
这样看上去是 $O(nm^2)$ 的，但是考虑到限制是“至多经过”，而要求最小路径，则一个环不应在路径中出现，即一个点不会被访问超过一次。考虑到一个点之多有一条出边被选中，因此状态第三维的数量实际上是 $O(n)$ 的。对于 $ci> n$ 的询问，其答案一定等于 $ci=n$ 的询问。

复杂度 $O(T(m\log m+n^2m+q))$，瓶颈在于 $O(Tn^2m)$；考虑到时限是 60s， 因此可以通过。

代码：

sort(G + 1, G + m + 1), memset(f, 0x3f, sizeof(f));
for(int i = 1; i <= n; i++) for(int k = 0; k <= n; k++) f[i][i][k] = 0;
    for(int s = 1; s <= n; s++)
        for(int i = 1; i <= m; i++){
            int u = G[i].u, v = G[i].v, w = G[i].w;
            for(int k = 0; k < n; k++) 
                f[s][v][k + 1] = min(f[s][u][k] + w, f[s][v][k + 1]);
        }

9 Increasing Number

一个数是Increasing当且仅当它的十进制表示是不降的，求 $n$ 位不降十进制数中被 $m$ 整除的有多少个。
$n ≤ 10^{18}, m ≤ 500.$

显然有状态 $f[n,p,k]$ 表示考虑第 $n$ 位数字，当前位填 $p$，模 $m$ 等于 $k$ 的方案数，转移可以枚举当前位数字和上一位数字，有关系 $f[n,p,(p\times 10^n+k)\text{ mod }m]\gets f[n-1,p’,k]$，复杂度 $O(100nm)$，不太可行。
对于这种转移关系比较固定的 DP，可以考虑矩乘加速，但是这是 $O((10m)^3\log n)$ 的，看上去也不太行。

一个重要的性质：一个合法数字必然是至多 9 个仅由 1 组成的数的和。
则可以按 $111…111$ 模 $m$ 的值将其分类，这样有 $m$ 类，然后对类做 DP 即可。
这也令我们可以得出一个结论：位数小于 $n$ 的不降数的总个数是 $\sum\limits_{i=1}^9\dbinom{i+n-1}{n-1}=\dbinom{n+9}{n}-1$。

10 Little Elephant and Colored Coins

给定 $n$ 个物品，每个物品可以取无限次，每个物品有两种属性：价值 $v$ 和颜色 $c$。
现在有 $q$ 个询问，询问最多能用多少种颜色组成 $S$。
$n ≤ 30, v_i ≤ 2\times 10^5,s\le 10^{18}$

对于这种题目，一般来说技巧是取 $w=\min v_i$ ，把问题转化到模 $w$ 的剩余系下做。这样做的正确性在于：$\mathbb{F}_P$ 中的所有数与 $P$ 的倍数组合能够填满整个整数域。
然后可以设状态 $f[u,k]$ 或 $f[k]$ 表示模 $w$ 为 $k$ 的答案，对于物品的价值 $v$ 可以抽象成一条边的边权，然后套用最短路模型，于是做到 $O(w\log w)$ 转移状态。

对于本题，考虑到硬币种类可能在统计过程中重复，因此设 $f[i,k]$ 表示选至少 $i$ 种，模 $w$ 为 $k$ 的路径的最小长度；用最短路模型来转移看上去也不太行，考虑换成背包模型，即有 $f[i,k]\gets f[i+1,(k+v_i)\text{ mod }w]$，然后按 $i$ 分组 DP 更新即可，复杂度 $O(n^2w)$。

给出大致的代码：

n = read();
for(int i = 1; i <= n; i++) v[i] = read(), w = w ? min(w, v[i]) : v[i];

memset(f, 0x3f, sizeof(f)), f[0][0] = 0;
for(int i = 1; i <= n; i++)
    for(int j = n - 1; j + 1; j--) 
        for(int k = 0; k < w; k++)
            f[j + 1][(k + v[i]) % w] = min(f[j][k] + v[i], f[j + 1][(k + v[i]) % w]);

for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        for(int k = 0; k < w; k++)
            f[i][(k + v[j]) % w] = min(f[i][k] + v[j], f[i][(k + v[j]) % w]);
    
q = read();
while(q--){
    int s = read(), sw = s % w;
    bool flag = false;
    for(int i = n; i && !flag; i--)
        if(f[i][sw] < INF && f[i][sw] <= s) printf("%d", i), puts(""), flag = true;
    if(!flag) puts("-1");
}

11 Balance

一个杠杆，半长为 $n$，$2n+1$ 个整数坐标各有一个质量相同的砝码，取走 $k$ 个，问最终杠杆仍然平衡的方案数。
$n\le 10^4, k\le 10$

整数划分问题。
容易发现两边是完全对称的，那么只需要考虑一边。考虑枚举取的数字和是多少，设 $f[i,k]$ 表示把数字 $i$ 拆分成 $k$ 个小于 $n$ 的不同数字的方案数，有转移：
$$ \begin{aligned}f[i,k]&=f[i-k,k]+f[i-k,k-1]\newline f[i,k]&=f[i,k]-f[i-n-1,k-1] \text{ }\text{ }| \text{ }\text{ }i\ge n + 1 \end{aligned}$$
复杂度 $O(nk^2)$。

代码：

memset(f, 0, sizeof(f)), N = 0;
for(int i = n - K + 1; i <= n; i++) N += i;
for(int i = 1; i <= n; i++) f[i][1] = 1;
for(int k = 2; k <= K; k++)
    for(int i = 1; i <= N; i++)
        f[i][k] = i >= k ? (f[i - k][k] + f[i - k][k - 1]) % p : 0,
        f[i][k] = i > n ? (f[i][k] - f[i - n - 1][k - 1] + p) % p : f[i][k];
int ans = 0;
for(int w = 1; w <= N; w++) for(int j = 1; j < K; j++) ans = (1ll * f[w][j] * f[w][K - j] % p + ans) % p;
for(int w = 1; w <= N; w++) for(int j = 1; j < K - 1; j++) ans = (1ll * f[w][j] * f[w][K - j - 1] % p + ans) % p;

12 Arrangement Count

求有多少个排列 $A\subseteq [n]$，使得 $A$ 中每个位置与相邻位置的数的差不为 1。
$n\le 1000$

设 $f[i,j,0/1]$ 表示考虑 $A\subseteq [i]$，有 $j$ 对相邻位置相差为 1 ，$i$ 是否与 $i+1$ 相邻的方案数，有转移：

1. $f[i,j,0]·j\to f[i+1,j-1,0]$
2. $f[i,j,0]·2\to f[i+1, j + 1, 1], f[i,j,1]·2\to f[i+1, j, 1]$
3. $f[i,j,0/1]·(i-j-1)\to f[i+1,j,0]$

复杂度 $O(n^2)$。

13 Cut Tree

$n$ 个节点的树，点有点权，要切两条边和加一个点使得形成的三个子树点权和相等，最小化新加节点点权的绝对值。
$n \le 10^5$

考虑固定一整棵树的根，对所有 $n$ 棵子树的大小统计其出现次数 $cnt[]$。不妨设当前的根处需要割断一条边，那么枚举其的枚举一个子树 $v$，设其大小为 $sz[v]$ ，则当 $cnt[sz[v]]>1$ 时，可将整棵树切成三个部分：两个 $sz[v]$ 和一个 $n-sz[v]$ ，于是可以更新答案。

但是当前根处不一定会割断边，那么考虑换根。容易发现当根向某个儿子移动时，至多有两个节点的 $sz[]$ 值会发生变化，则简单维护即可。

于是可以做到不漏算答案，时间复杂度 $O(n)$。

14 Number Game

Alice 和 Bob 又双叒叕在玩游戏。
Bob 每次会想一个 $0\text{~}n$ 的数，Alice 每次猜 $k$，Bob 告诉 Alice 大了还是小了。Alice 猜 $k$ 会付出 $a_k$ 的代价，Alice 要最小化代价，Bob 要最大化代价（并在不违反前面询问的情况下改数）。假设二人都绝顶聪明，求 Alice 最后付出多少代价。
$n \le 10^5, a_i\le 9$

本人只会 $O(n^3)$ 的辣鸡 DP……

设 $f[l,r]$ 为考虑区间 $[l,r]$ 的答案，应当有转移：
$$ f[l,r]=\min\limits_k a_k+ \max(f[l,k-1],f[k+1,r]) $$ 边界是 $f[i,i]=a_i$，直接大力 DP 即可做到 $O(n^3)$。

15 Distributs

小 A 带来了 $m$ 种特产，第 $i$ 种特产的数量为 $a_i$。小 A 要把它们全部分给 $n$ 个同学，要求每个同学至少拿到一个特产，问有多少种分法，对 $10^9+7$ 取模。
$n,m \le 1000$

容斥简单题，钦点 $k$ 个人一定分不到，剩下的随便分，在总方案数中减去就好了，则答案是：
$$ \sum\limits_{k=0}^n (-1)^k \dbinom{n}{k}\sum\limits_j \dbinom{a_j+n-k-1}{n-k-1}$$ 复杂度 $O(n^2)$。

16 Solutions of the Equation

有 $n$ 个变量 $x_1…x_n$，每个变量 $0<x\le R$，给定 $S$，求方程 $x_1+x_2+…+x_n=S$有多少组正整数解。
$n \le 1000$

容斥简单题，如果不考虑限制答案是 $\dbinom{S-1}{n-1}$，然后钦点有 $k$ 个变量不合法然后去加加减减，答案是：
$$ \sum\limits_{k=0}^n (-1)^k \dbinom{n}{k}\dbinom{S-kR-1}{n-1} $$ 复杂度 $O(n^2)$。

17 Bohater

在一款电脑游戏中，你需要打败$n$只怪物（从 $1$ 到 $n$ 编号），初始生命值为 $z$。
为了打败第 $i$ 只怪物，你需要消耗 $d_i$ 点生命值，但怪物死后会掉落血药，使你恢复 $a_i$ 点生命值。
任何时候你的生命值都不能降到 0（或 0 以下）。请问是否存在一种打怪顺序，使得你可以打完这 $n$ 只怪物而不死掉。如果存在请输出方案，不存在输出NO。
$1≤n,z≤10^5，0≤d_i,a_i≤10^5$

考虑把怪分成两类，先打加血怪，再打减血怪；考虑打加血怪的过程：应当按 $d_i$ 升序去打。
减血怪呢？考虑打怪的反过程：不打一个怪，血量增加 $d_i$ 而减少 $a_i$。
则反过程应当按 $a_i$ 升序排，正过来就是按 $a_i$ 降序排。

复杂度 $O(n\log n)$。

18 Swap Space

你有许多电脑，它们的硬盘用不同的文件系统储存数据。你想要通过格式化来统一文件系统。格式化硬盘可能使它的容量从 $a_i$ 变成 $b_i$。
为了格式化，你需要买额外的硬盘。当然，你想要买容量最小的额外储存设备以便省钱。
你可以按任意顺序格式化硬盘。格式化之前，你要把该硬盘上所有数据移到一个或更多的其他硬盘上，数据可以分割。
格式化后，该硬盘可以立刻开始使用。你没有必要把数据放到它原来所在的硬盘上。数据也可以被放到你额外买的硬盘上。
求最小的额外储存设备容量。
$1≤n≤10^6,1≤a_i,b_i≤10^9$

考虑二分最终的答案 $M$ ，表示一开始购买的硬盘大小，则模型变为：

• 给定一些元素 $(a,b)$ ，选择某个元素会付出代价 $a$ 得到收益 $b$ ，求能否选择所有元素。

这就是上题模型，复杂度 $O(n\log^2n)$，看上去有点卡。

实际上二分大可不必，依然按照上题的思路去做，当代价和多于当前的承受限度时，把多出来的那一部分加到答案里即可，复杂度 $O(n\log n)$。

19 Maximum Value of Linear Function

现在有 $n$ 个一次函数，$f_i(x)=a_ix+b_i$。给定 $x$，并且对于所有的 $f_i(x)$ 可以任意改变顺序嵌套函数，求 $f(f(f(…f(x))…)$ 的最大值。
$n\le 10^6$

容易发现 $x$ 的系数一定，那么只需要考虑常数项最大。
考虑交换，对二元组 $(a_1,b_1)$ 和 $(a_2,b_2)$ ，前者放在外层当且仅当 $a_1(a_2x+b_2)+b_1>a_2(a_1x+b_1)+b_2$，移项得 $(a_1-1)/b_1>(a_2-1)/b_2$，则按照 $(a_i-1)/b_i$ 降序排序，把靠前的放在外层即可。

这个题也可以类比一下「国王游戏」那道题。考虑何时应该交换相邻的两个元素 $i,j$：当且仅当 $\Pi/b_i+(a_i·\Pi)/b_j > \Pi/b_j+(a_j·\Pi)/b_i$，化简得 $(a_j-1)·b_j<(a_i-1)·b_i$，因此按 $(a_i-1)·b_i$ 为关键字排序即可。

20 Kuglarz

$n$ 个杯子排成一排，每个杯子中可能放有也可能没有一个小球。你每次可以花费 $C(i,j)$ 的代价得知区间 $[i,j]$ 的杯子中球的总数的奇偶性。
问最少花费多少代价才能求出每个杯子中是否有小球。
$n\le 1000$

看上去很像 DP，但我的做法假掉了……
建一张图，边 $(u,v)$ 的边权为 $C(u,v)$，则问题等价于求出图上的最小生成树。
时间复杂度 $O(n^2)$。

21 OSU!

一个长度为 $n$ 的 01 串按以下方式生成：第 $i$ 个位置有 $a_i$ 的概率为 1，$1-a_i$ 的概率为 0。01 串的价值如下计算：每一个极长全 1 子串的长度的三次方之和。
求该 01 串的价值的期望。
$n\le 10^5$

考察期望的定义，和应用用贡献法计算每一位的价值期望。
设 $l_1[i]$ 表示末尾一段极长全 1 子串长度的期望， $l_2[i]$ 表示末尾一段极长全 1 子串长度的平方的期望，设 $f[i]$ 为长度为 $i$ 的 01 串价值的期望，考虑到有 $(x+1)^3-x^3=3x^2+3x+1$，则有：
$$ f[i]=f[i-1]+a_i(3l_2[i-1]+3l_1[i-1]+1) $$ 即对最后加入的位置 $i$ 讨论了一下它对答案的贡献。同理有：
$$ \begin{aligned} l_1[i]&=a_i(l_1[i-1]+1) \newline l_2[i]&=a_i(l_2[i-1]+2l_1[i-1]+1) \end{aligned}$$ 于是可以做到 $O(n)$。
注意区分 $f[]$ 和 $l[]$ 的定义，前者是全局的期望价值，后者是末位极长全 1 串的期望价值，同时还需要区分一下 “长度的三次方的期望” 和 “长度的期望的三次方”。

代码：

for(int i = 1; i <= n; i++) l[i] = a[i] * (l[i - 1] + 1);
for(int i = 1; i <= n; i++) l2[i] = a[i] * (l2[i - 1] + 2 * l[i - 1] + 1);
for(int i = 1; i <= n; i++) f[i] = f[i - 1] + a[i] * (3 * l2[i - 1] + 3 * l[i - 1] + 1);