ACM算法实践总结

Info

「ACM算法实践」课程考试总结。

第一章——基础¶

沙海拾贝¶

因为是与运算，只有当这 m 个数的第 k 位上都是 1 的时候才能使得最后的数的第 k 位为 1 。

为了让最后的开心程度最大，我们优先将高位取 1 ，也就是从高位开始枚举，选出数量大于 m 同时在第 k 位上为 1 的所有数，然后再以同样的方法从这些数中选取第 k−1 位为 1 的数，依次选取下去直到可选取的数的数量等于 m 。

Tag :位运算

麦田¶

很容易想到用前缀和然后暴力枚举左上角和右下角，但是复杂度过大，这时候需要使用到状态压缩，将二维变为一维，于是原问题就变成了一道经典双指针问题。

Tag : 前缀和、状态压缩、双指针

时间管理大师¶

一开始想用贪心，但是发现越想越复杂了。

如果观察答案的话可以发现答案是单调的，所以可以使用二分答案的方法，已知最后能支撑的时间的话具体充电方案就很好想了，然后判断是否有可能即可。

Tag : 二分答案

组队¶

正确解法是贪心 + 优先队列。

首先肯定要将 a 数组排序，要使人数最少的队伍人数最多，我们优先将当前的数 $a[i]$ 放到以 $a[i]-1$ 结尾的队伍中人数最少的一个队伍即可。思路很简单，这题的难点在于怎么实现。

如果用一个 queue 来储存当前已经有了的队伍，然后再暴力查找符合要求的人数最少的队伍，时间复杂度 $\mathcal{O}(n^2)$ ，肯定会 T ，于是我们考虑用优先队列来存储每条队伍的人数，查找时只需输出队头即可，这时候又如何存储每条队伍最后一个元素呢？可以开 n 条优先队列，q[i] 表示以 a[i] 结尾的所有队伍的人数，同时我们还需要对 a[i] 进行离散化，这样一来，分别为每一个人分队是 $\mathcal{O}(n)$ 的，priority_queue 的操作是 $\mathcal{O}(n\log{n})$ 的，所以总复杂度是 $\mathcal{O}(n\log{n})$ 。

Tag : 贪心、优先队列

第二章——数据结构基础¶

网上冲浪¶

直接用栈来模拟。

Tag : 栈

情人节¶

首先，如果 flash 和他的两个女朋友在同一条链上，显然选择位于中间的那座城市作为目标城市最优；如果他们分别在不同的子树上，也就是他们两两之间的 LCA 相等，那么就选择这个 LCA 作为目标城市；如果他们中有两个在同一子树上，另一个在不同的子树上，那么选择那两个家伙的 LCA 作为目标城市最优。

然后要注意 fa 数组开大一点，考试时因为这个调了个把小时都没发现。

Tag : LCA

权力宝典¶

因为 l 和 r 的范围很大，所以首先要对数组进行离散化，然后根据题意处理询问，找到是否有 $\max{(a[l+1, r-1])<a[r]\le a[l]}$ 即可，对于区间最大值，我们可以用 ST 表来 $\mathcal{O}(\log{n})$ 解决。

Tag : 离散化、ST 表

大富翁¶

一看到这个矩形就应该想到将二维压缩成一维，然后考虑在区间上找到一段尽量长而且满足金额和小于 $S$ 的子区间，假设当前考虑的子区间为 $[l, r]$ ，固定左端点 $l$ ，如果 $[l, r+1]$ 是满足条件的，那么 $r$ 一定不会是答案区间，可以看出右端点 $r$ 满足决策单调性，因此可以用单调栈。

Tag : 状态压缩、单调栈

第三章——图论基础¶

打卡新餐厅¶

一遍 dfs 即可，途中如果到某一点的 $cost$ 已经大于 $m$ 就直接 return 。

Tag : DFS

上课¶

分为两种情况：使用传送门和不使用传送门。

不使用传送门，直接跑一遍最短路算出 $s$ 到 $t$ 的最短路 $dis_1$ 。

使用传送门，就跑两遍最短路，一遍以 $s$ 为起点，求出到 $S$ 的最短路，这个我们可以直接在上一步中的 $dis_1[S]$ 加上路上的边数；另一遍以 $t$ 为起点，求出到 $T$ 的最短路，然后两个最短路加起来得到的 $dis_2$ 就是使用传送门的最短路。

最后比较两个谁小就输出谁。

Tag : 最短路

复习¶

一眼看上去是个裸的 Topo + 贪心，Topo 的时候用个小根堆维护就好了。

然而我假了

这个顺序要求：在满足所有学习限制的前提下，知识点 1 尽量优先复习；在满足所有学习限制且知识点 1 尽量优先复习的前提下，知识点 2 尽量优先复习，…以此类推。

这个要求并不是指答案的字典序最小

我们考虑一组数据

4 2
2 4
3 1

如果按照原先的策略我们得到的答案是 2 3 1 4 ，然而按照要求实际上的答案应该是 3 1 2 4 。

从这个例子中可以看出有时候我们要选择一个当时看上去并不优的解来得到最终的最优解，也就是说这道题并不满足每一步都是选最优的策略，这时候从正面上来考虑一种普适性的策略似乎会很麻烦的样子。

那我们不妨从反面思考。既然要求字典序小的知识点尽量往前排，那么对于优先级低、字典序又很大的知识点我们一定会把它放最后，不如这样，我们按照优先级从低到高考虑，每次把字典序大的放后面，这样其实就是把字典序小的尽量往前放了，然后继续做下去就是将这些字典序小的按照优先级排序了，此时他们需要满足的限制只有优先级，不能再把它往前放了，换句话说，我们每次把字典序大的放后面，不断的做下去直到不能做为止，这样字典序大的除非是优先级高于某个字典序小的否则不可能被放在字典序小的前面。

具体到操作上来说，这种做法是满足贪心的条件的，我们可以建一个反图，然后 Topo 的同时用一个大根堆维护，最后逆序输出答案。

一点启示：

当正面思考感到繁琐、困难时，不妨试着从反面思考。类比数学证明题中通过证明逆否命题的正确性来证明正命题。
建反图 Topo 然后逆序输出答案是在很多存在先后层级顺序、需要满足一些限制的图论中的常见技巧。

Tag : 拓扑排序、贪心

竞技¶

正解似乎是直接暴搜然后加剪枝？不过考虑到两个同学之间可能的结果是 3 种加上 $N$ 的范围只有 10 ，那么暴搜是很自然的思路了。

常用的剪枝技巧：可行性剪枝（排除不可能的状态）、记忆化剪枝（除去重复冗余的状态）

Tag : 搜索、剪枝

第四章——数学基础¶

PvZ¶

容易发现盒子里每一个球的编号 $c$ 一定满足 $ax+by=c$ 的形式，考虑裴蜀定理，必然有 $\gcd(a,b)\mid c$ ，因此统计 $1\sim n$ 中有多少个数是 $\gcd(a,b)$ 的倍数即可，答案是 $\lfloor\frac{n}{\gcd{(a,b)}}\rfloor$ ，如果这个数是奇数，那么小 P 必赢，否则必输。

Tag : 裴蜀定理、gcd

吃萝卜¶

如果一个序列中存在两个数满足他们的乘积是完全平方数，那么这两个数分解后的每一个质数的次数一定都是偶数，于是我们只需筛出 $1e7$ 以内的所有质数，然后对每一个数记录下它对于每个质数的次数的奇偶性，再在当前序列中寻找是否有奇偶性与它完全相同的数即可，这种方案的复杂度是 $\mathcal{O}(n^2)$ ，还是不够优秀。

显然需要优化的部分是查找部分，既然有用的信息只是每个质数的次数的奇偶性，我们不妨将奇数次的指数直接记为 $1$ ，偶数次的指数记为 $0$ ，然后序列中的每一个数都会变成 $p_1^{0/1}p_2^{0/1}\cdots p_n^{0/1}$ ，如果存在一个数每个质数的奇偶性与它完全相同的话，那么他们变形后的数是完全相等的，于是我们只需开一个 $vis$ 数组或者用一个 $map$ 来记录即可。

Tag : 贪心、惟一分解定理、质数筛法

升旗仪式¶

很容易想到要统计满足 $i\times j=x$ 的 $(i,j)$ 的数量，然后一个前缀和加二分查找即可，注意到 $k\le \max(n,m)$ ，因此只需要考虑 $[1,\max(n,m)]$ 的 $x$ ，之后的数一定不可能出现。

不妨设 $n\le m$ ，要统计 $i\times j=x$ 的 $(i,j)$ 相当于求 $x$ 的约数个数，也就是 $\sum_{d\mid{x},d\le n}1$ ，加上统计前缀和的式子就是 $\sum_{i=1}^m\sum_{d\mid{i},d\le n}1$ ，之后就是考虑一个 $d$ 可能对多少个 $i$ 产生贡献，答案显然是 $\lfloor \frac{m}{d}\rfloor$ ，变换求和顺序之后式子就变成了 $\sum_{d=1}^n \lfloor \frac{m}{d}\rfloor$ ，然后整除分块即可，复杂度 $\mathcal{O}(\sqrt{m})$ 。

Tag : 数论分块、求和

巴斯和他的学生¶

等式两边的运算都是列独立的，令 $B_{\star,i}$ 表示 $B$ 的第 $i$ 列，则有 $\forall i\in[1,n],A\times B_{\star,i}=C\odot B_{\star,i}$ ，即 $\forall i\in[1,n],\sum_{k=1}^n A_{j,k}B_{k,i}=B_{j,i}\odot C_{j,i}$ 。

省略第二维的 $i$ ，有 $\forall i\in[1,n],\sum_{k=1}^n A_{j,k}B_{k}=B_{j}\odot C_{j}$

如果 $C_j=0$ 则不管，如果 $C_j=1$ 则相当于把左侧 $A_{j,j}B_j$ 变为 $(A_{j,j}-1)B_j$ ，也就是
$$
\forall j\in[1,n],\sum_{k=1}^n (A_{j,k}-[k=j\land C_j])B_k=0
$$
将 $B_k$ 看做第 $k$ 个向量选不选，相当于从 $n$ 个向量中选若干个，使得他们的异或值为 0 向量，可以在 $\mathcal{O}(\frac{n^3}{\omega})$ 的时间内求出基数 $d_i$ ，答案即为 $\prod_{i=1}^n 2^{n-d_i}$ 。

Tag : 线性代数、矩阵

第五章——动态规划基础¶

多元函数¶

可以发现直接暴力递推进行计算会重复计算很多状态，同时数据范围很小，可以使用记忆化搜索。

Tag: 记忆化搜索

压岁钱¶

这道题需要根据数据范围来选择不同的算法，前 $60\%$ 的数据直接暴搜，后 $40\%$ 的数据 DP ，不过 $100\%$ 的数据应该可以用 meet in the middle 解决。

Tag : 搜索、动态规划

油田¶

分组背包。将第 $i$ 块油田的士兵从小到大排序后得到 $a_{i,1\sim s}$ ，那么在这块油田部署的士兵数量一定是 $2a_{i,x}+1$ ，能战胜的士兵数是前缀和 $a_{i,1\sim x}$ ，相当于第 $i$ 组物品一共有 $s$ 个，选取前 $j$ 个的重量是 $2a_{i,j}+1$ ，价值是前缀和 $a_{i,1\sim j}$ ，然后背包就好了，复杂度 $\mathcal{O}(nms)$ 。

Tag : 分组背包

菠萝蜜¶

价值越高的菠萝蜜一定会优先卖，所以可以将 $p_i$ 从大到小排序，然后发现卖出的菠萝蜜的总价值和菠萝蜜盒的总花费是独立的，而只考虑菠萝蜜盒的选择的话就是一个 0/1 背包问题，我们令 $f[i][j]$ 表示当前考虑到第 $i$ 个菠萝蜜盒，一共可以放入 $j$ 个菠萝蜜的最小花费，那么 $f[i][j]=\min{(f[i-1][j],f[i-1][j-c[i]]+e[i])}$ ，其中第一维可以滚掉，于是我们最后直接枚举放入菠萝蜜的个数，对 $p[1\sim i]-f[i]$ 取 $\min$ 即可，其中 $p[1\sim i]$ 为前缀和。

Tag : 0/1 背包、贪心

第六章——数据结构提高¶

说谎¶

很裸的并查集。但是要注意 $a,b$ 范围很大，需要先进行离散化，然后可能出现先说 $a,b$ 不在一起，后面又在一起的情况，所以还要先处理所有在一起的情况，之后再判断不在一起的说法。

Tag : 并查集

选衣服¶

这道题主要用到了两个套路：

用线段树对一串 01 序列进行排序，每次排序的复杂度是 $\log{n}$
假设有序列 $a_{1\sim n}$ ，打乱它的原有次序（不一定是按数值排序），希望找到新序列的第 $k$ 位是原序列的第多少位，我们可以利用二分，将原序列第 $1\sim mid-1$ 个数变为 $0$ ，其余的数置为 $1$ ，那么以相同的方式打乱次序后，若第 $k$ 位为 $1$ ，说明答案 $\ge \ mid$ ，否则 $< mid$ 。

看到这道题，对于每一个排序操作直接 $sort$ 肯定会超时，如果要减小复杂度的话，必然要从排序的操作入手，我们希望每次排序的复杂度能够做到 $\log{n}$ 的级别，而如果序列是 01 序列的话便可用套路 1 降到 $\mathcal{O}(\log{n})$ ，再看问题，正好可以用套路 2 把序列变为 01 序列，从而我们每次对原序列二分转化为 01 序列之后套一个线段树对 $m$ 次操作排序，然后看排序后的第 $q$ 位是 1 还是 0 即可。

所以这道题应该是一个套路题（

Tag : 套路、线段树

山脉¶

考试的时候想复杂了，写了一个 $\mathcal{O}(n\sqrt{n})$ 并且常数很大的分块暴力，然而忘了 set 的接口最后只能交一个纯暴力解法上去了。

其实这题挺好想的，对于每次的询问，找到小于等于 $b_i$ 的山的数量 $x$ ，如果它们都不在这 $n$ 座山的两端的话，那么答案显然就是 $x+1$ ，而统计这样的 $x$ 就是树状数组的强项了，同时也可以很轻易的解决单次修改的问题。而对于在 $n$ 座山的两端的情况，显然可以直接对两端分别判断一下，也可以在插入树状数组的时候加入 $0$ 和 $n+1$ 两个节点。

Tag : 树状数组

魔法芒果¶

首先考虑暴力求解。每次暴力求出所有合法的边，然后判断两点是否联通，同时判断联通块内的最大值是否合法。

然后考虑用分块离线处理询问。先以边为第一关键字排序分块，再在块内以询问为第一关键字排序，当前块前面的点为第二关键字排序，保证前面的点都是符合当前询问点对于第一关键字的条件的。同时第二关键字都是单调的，所以按照块的顺序处理一下，再对每个询问暴力处理当前块的贡献，由于每次处理涉及撤销操作，因此需要用到并查集。

Tag : 分块、离线处理、并查集

第七章——图论提高¶

挑芒果¶

可以发现奇数和奇数、偶数和偶数的点是不可能出现在同一集合里的，因此可以得知这是一个二分图。

然后考虑求二分图的最大独立集，把所有满足 $\gcd{(i,j)}\cdot \gcd{(i+1,j+1)}=1$ 的点之间连一条边再求解即可。

Tag : 二分图、最大独立集

完全图¶

考虑 Kruskal 算法的步骤，每次加入最小的合法的一条边，记为 $edge(u,v)$ ，然后合并两个集合，设 $u,v$ 所在的集合的大小为 $size[u],size[v]$ ，那么在题述的完全图中，任意一条俩节点分属于这两个集合的边的长度都要大于 $val(u,v)$ ，如果是边权和最小的完全图的话，那么长度就要等于 $val(u,v)+1$ ，于是这两个集合之间的边权和即为 $(val(u,v)+1)\cdot(size[u]\cdot size[v]-1)+val(u,v)$ 。

最后的做法显然就是跑一遍 Kruskal ，每次将答案加上上述边权和即可。

Tag : 最小生成树、Kruskal

探险¶

考试时只想到如果能找出所有的路径组成一张完全图，那么最后的答案就是在这张图的最小生成树上求 LCA ，同时由于 $n$ 很大，建图的时候只需要留下可能会用到的边，但是前面怎样求出这些路径不会。正确的方法是双向宽搜，可以在一定程度上减小复杂度。

Tag : 双向宽搜、LCA、最小生成树

第八章——数学提高¶

挑战者游戏¶

当 $k=1$ 时，显然 $n$ 为奇数的话是先手必胜。

当 $k>1$ 时，如果当前是两堆数量相同的石头，那么无论先手怎么取，后手都可以在另一堆石头里用相同的方式取，从而先手是必输的。因此，FA 只需在一开始就将其分成两堆数量相同的石头让自己成为后手就是必赢的，若 $n$ 为奇数就从中间取 1 个，否则就取 2 个，所以 FA 是必赢的。

Tag : 博弈论

数的研究¶

当 $vi(x)=x$ ，也就是 $x$ 的分解式中不含有指数大于 1 的质因子时，结论显然不成立。

当 $x$ 的分解式中含有指数大于 1 的质因子时，我们尝试找到使得结论成立的 $y,z$ ，观察结论式，不等式两端的数都是 $vi(x)$ 的倍数，右端 $x$ 除以 $vi(x)$ 后只剩下指数大于 1 的质因子的乘积了，而左边除以 $vi(x)$ 后剩下的因子还与 $y,z$ 有关，为了减少未知数的数量，我们希望它只与 $z$ 有关并且显然不会再包含 $vi(x)$ 的质因子了，于是想到令 $y=p_1p_2\cdots p_n$ ，那么 $z=p_{1}p_{2}\cdots p_{n}(p_{i_1}^{a_{i_1}-1}p_{i_2}^{a_{i_2}-1}\cdots p_{i_k}^{a_{i_k}-1}-1)$ （其中 $a_{i_1},a_{i_2},\dots,a_{i_k}>1$ ），此时
$$
\begin{aligned}
\frac{vi(xyz)}{vi(x)}&=vi(p_{i_1}^{a_{i_1}-1}p_{i_2}^{a_{i_2}-1}\cdots p_{i_k}^{a_{i_k}-1}-1)\
&\le p_{i_1}^{a_{i_1}-1}p_{i_2}^{a_{i_2}-1}\cdots p_{i_k}^{a_{i_k}-1}-1\
&< p_{i_1}^{a_{i_1}-1}p_{i_2}^{a_{i_2}-1}\cdots p_{i_k}^{a_{i_k}-1}\
&= \frac{x}{vi(x)}
\end{aligned}
$$
也就是说我们找到了合法的 $y,z$ ，从而当 $x$ 的分解式中含有指数大于 1 的质因子时结论是一定成立的。

于是我们需要将 $x$ 质因数分解即可，考虑到 $x\le 10^{18}$ ，需要使用 Pollard Rho 算法。

Tag : 数论、惟一分解定理、Pollard Rho

喷泉¶

题意即从 $[L,R]$ 中选取 $\le n$ 个数的方案数。

不妨令 $m=R-L+1$ ，即从 $m$ 个数里选取 $\le n$ 个数。直接考虑会很复杂，由于任意一种方案选取的数总能排序后形成一个单调不降序列，因此按照大小顺序来考虑枚举会更好。

假设是选取 $k$ 个数，先从最简单的情况——单调递增序列开始考虑，此时方案数显然是 $\binom{m}{k}$ ，如果是单调不降序列，假设 $m$ 个数分别选取 $x_1,x_2,\dots,x_m$ 个，有 $x_1+x_2+\cdots+x_m=k$ ，并且 $x_i\ge 0$ ，那么就是经典隔板法的应用了，方案数为 $\binom{k-1}{m+k-1}$ ，从而最后的答案为 $\sum_{i=1}^n\binom{m}{i}+\binom{m+i-1}{i-1}$ 。

尝试将式子化简，根据 $\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}$ ，先加上 $\binom{m}{0}$ 再减去 1 ，不断递推约项可以得到 $\binom{n+m}{n}-1$ ，由于模数不大，可以采用 Lucas 定理求解。

Tag : 计数原理、Lucas 定理、排列组合

gcd and prime¶

考虑莫比乌斯反演。

只有当 $\gcd(i,j)=p(p为素数)$ 时才对答案有贡献，因此原式转化为 $\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=p]$ ，等价于 $\sum_{p\in primes}\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=p]$ 。

转化为可以等价代换的形式，$\sum_{p\in primes}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}[\gcd(i,j)=1]$ ，

然后开始莫比乌斯反演，$\sum_{p\in primes}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}\sum_{d\mid\gcd(i,j)}\mu(d)$ ，

改变求和顺序，$\sum_{p\in primes}\sum_{d=1}^{\min{(\lfloor\frac{n}{p}\rfloor,\lfloor\frac{m}{p}\rfloor)}}\mu(d)\lfloor\frac{n}{dp}\rfloor\lfloor\frac{m}{dp}\rfloor$ ，

令 $T=dp$ ，改为枚举 $T$ ，可以发现 $T$ 能取遍 $[1,\min(n, m)]$ ，而 $d\mid T$ 已知，于是有 $\sum_{T=1}^{\min(n,m)}\sum_{p\mid T,p\in primes}\mu(\frac{T}{p})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor$ ，

最后用埃氏筛预处理每个 $T$ 的贡献并且整除分块，再对 $T$ 进行前缀和处理即可。

Tag : 莫比乌斯反演、gcd、数论分块、素性筛

第九章——动态规划提高¶

大禹治水¶

直接求解每个节点遭受洪水的概率比较复杂，但是反过来求解它不爆发洪水的概率则比较简单，等于每条道路不被洪水冲垮同时该节点不爆发洪水的概率的积。

由于这个图是一棵树，考虑换根 DP 。不妨设 1 号节点为根，令 $f_i$ 为在 $i$ 的子树中 $i$ 未遭受洪水的概率，则状态转移方程为 $f[u]=\prod_{v\in son[u]}f[v]+(1-f[v])(1-p)$ ，设 $g_i$ 为 $i$ 未遭受洪水的概率，令 $s=\dfrac{g[u]}{f[v]+(1-f[v])(1-p)}$ ，于是又有状态转移方程 $g[v]=f[v](s+(1-s)(1-p))$ 。

Tag : 概率论、换根 DP

漂亮妹妹¶

考虑数位 DP 。设 $f[i][j][k][l][m]$ 表示第 $i$ 位数，是否存在至少 3 个相邻的相同数字为 $j$ ，上一个数为 $k$ ，相邻的相同数字出现次数为 $l$ ，是否出现 4 和 8 为 $m$ 的方案数，然后仿照 dfs 进行数位 DP 。

Tag : 数位 DP

猫咖¶

很显然是状压 DP ，设 $f[i][j]$ 为考虑前 $i$ 行，其中第 $i$ 行的状态为 $j$ 的方案数然后进行状态转移即可。

Tag : 状压 DP