2021年7月训练

七月 27, 2021

202107月训练

CF 1547F

其实我们已经想到了本质是求最长的一段不是全局公约数的子序列长度，而且$O(\sum n)$的提示也容易使人明白需要用类似尺取的方法。但差点意思的是怎么尺取呢？

之前失败的思路，问题在于要考虑的质因数太多，并不能动态维护当前段的所有质因数。所以这时候我们需要估计对于每一个数，其质因数个数的上限——其实就是8个，所以一个一个考虑是足够的。那么问题需要转化，也就是首先所有的数都除掉全局公约数，这样就是求最长的一段$gcd>1$的子序列。

那么我们按照线性筛得到的筛法树的边权（注意严格保存最小质因子），容易得到每个数的因数分解，那么对于每一个数$a_i$,枚举它的所有质因数$p$，然后向左向右扩展，每扩展一个数，就把它的$p$从其质因数集合中消去，这样就可以不断更新最大长度。

算法标签 数论 线性筛 双指针/尺取法

CF 1547G

基本思路是正确的，就是要用SCC来统一处理环。然后1是唯一确定的源点，这个条件很好，使得DFS和Tarjan过程仅从1开始就行。然后从1开始到某点的访问次数，由于只考虑2次以上有限次，所以DFS就可以统计，并不需要DP。最后凡是从1到某个点路径经过SCC（或者自环）的，$ans_i=-1$

算法标签 图论 强连通分量

CF 1391D

这个题其实还是一个奇偶的构造。

首先行数超过4行和行数只有1行的情况很容易处理。那么先考虑两行的情况。这时的偶方阵就是$2 \times 2$的方阵，所以如果有奇数个1，相邻$2\times1$的列的1个数奇偶性应该不同。所以整个矩阵最终效果，就是“奇偶奇偶”的情形，或者”偶奇偶奇”的情形。按照这两种情况扫一遍即可。

那么行数为3的情况怎么样呢？其实这里就是化归，前两行和后两行分别实现$n=2$时奇偶分布，所以是四种情况，同样扫就行。

算法标签 奇偶分析

CF 1550D

这题核心在于一个偏移量的思想。设置$a_i=i+k_i$然后分析$k_i$的性质，来计数。具体思路见题解。

CF 1550F

这个题目很综合，也体现建图和图的处理的一些技巧。

首先怎么考虑每一次$[d-k,d+k]$这个范围的跳跃的构建。其实最朴素的想法是枚举两个节点，连接一条边，边权就是坐标差的绝对值。那么适配这个题目，就再把$d$考虑进去，变成$w=|d-|a_u-a_v||$。所以如果从$s$到$i$经过的若干边，他的边权$w$都不超过$k$，那么就是满足要求的。

考虑到每一次的$k$是变动的，$k$越大，相当于跳跃的约束越小。因此我们就考虑尽可能用$w$的边来构成从$s$到$i$的路径，这样就可以更大化地满足要求苛刻的$k$。于是我们可以考虑求一棵最小生成树。

但是个$n^2$量级的完全图，因此普通的Kruskal和Prim是不行的。我们用一个新算法——$Boruvka$。

Boruvka 算法的一句话思想便是：

“从所有当前的连通块向其他连通块扩展出最小边，直到只剩一个连通块”，其中取最小边的贪心思想是 Kruskal 的主体，而向外扩展又是 Prim 的思想 —— 基于另外两种生成树算法，Boruvka 的正确性显然。

其代码框架如下：

while 连通块个数>1
    for 每个连通块 i
        mn[i] = 连接 i 与其他连通块的最小边
    for 每个连通块 i
        if mn[i] 连接两个不同的连通块
            ans += mn[i]
            Merge( mn[i] 连接的连通块 )
            连通块个数 --

而不同的题目难点就在于快速计算$mn_i$。对于这道题而言，其实$mn_i$就是要找到可以向其他连通块扩展的权值在$[a_i-d,a_i+d]$范围内的最小边。那么我们可以利用set+lower_bound来求这个最小边。

所以求得最小边后，就用vector维护的并查集来合并（小并入大）维护连通块，同时在新图上连接无向边。

运行完Boruvka算法后，再从$s$出发DFS遍历整个MST，求得它到其他点路径上的权值最大值。最后处理询问时只需要考虑这个权值最大值是不是比k来的小就行了。

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

算法标签 最小生成树 启发式合并 图论建图

CF 1550E

这道题核心在于模拟匹配。

从Frozen_Guardian的博客上学到了关于这种状压的一些真知灼见。

状压$dp$就是全排列问题的一种优化，所以状压$dp$可以解决的问题，全排列暴力枚举肯定也是可以解决的。所以先将问题简化，假设本题放开全排列该如何去做？

我们要全排列什么？其实相当于从左到右依次放置待判定长度的相同字母子串。所以问题的关键就在于判别不同排列时能不能恰好匹配？所以这里就借助了序列自动机的概念。我们记$nnext[i][j]$表示从字符串第$i$个字符开始，其最早完全匹配第$j$种字符的待判定长度的字串时，下一个位置是多少？那么计算就是从后往前计算，如果借助？和已有的字母能够新增出一个完全的匹配，那么就赋值，否则照搬$nnext[i+1][j]$。

再考虑$dp$的转移，很容易想到$dp[mask]$就是已经使用字母的状态，这个dp值的含义是完成状态内这些字母的匹配后，最小的下一个位置（相当于一个$end$指针）。所以说我们其实并不关心从左到右到底是如何安排的，只需要按照$nnext$来辅助转移就可以了。

所以最后的判定标准就是如果$dp[2^k-1]$在$n-1$范围内，就是可以的。主函数二分答案即可。

算法标签 二分答案 序列自动机 状压DP

Nowcoder Summer 2

J Product of GCDs

给定一个集合，求其所有大小为$k$的子集的$gcd$之积

基本思路在赛场上就讨论的很清楚了，事后看题解也大致是这个思路。但赛场上没写出来的原因，是欧拉函数不会求。

把所有的数按照所含的质因子分类，朴素来说就是每一个质数开一个桶，把凡是含有这个质因子的数往这个桶里装，然后这个桶不断的处理该质因子的若干次幂的情况，相当于每一次把桶里所有数除一遍这个质数，然后删掉不再含有该质因子的数，每一次操作后对桶的大小做一个组合数的快速幂：

$ans \gets prime^{C_{size}^k}$

这个组合数数值很大，难以存储，又考虑这个组合数在指数的位置上，所以先求出$\varphi(p)$,然后用公式$C_n^k=C_{n-1}^{k}+C_{n-1}^{k-1}$来递推取模得到所需的组合数，对一组数据复杂度为$O(nk)$

此外关于实现，其实朴素想法中的“桶”是不需要用STL的什么容器来实现的。只需要每次枚举质数和质数的幂次即可。因为用了容器，反而会多出来一些复杂度。

算法标签 欧拉函数 组合数

G League of Legends

将$n$条线段分成$k$组，每组线段求一个交，求最大化所有交之和。

其实这个分组问题很容易想到的是用DP解法。那么DP解法我们不能枚举分组情况，从经验而言，一般是考虑连续的一系列线段构成最后一组这样子。那么怎么做才能使这样的DP成立呢？

首先我们把线段分成两类：一类线段可以包含其他的线段。那么如果把这个线段和其所包含的线段安排在一组，则不会对答案有新的贡献，要么把它单独分组，贡献其长度。另一类线段就是相互之间均不能包含，但可以有相交的部分。我们考虑把这些线段按左端点从小到大排序，那么右端点一定是单调不降的。这个时候，我们分析贪心，在这些线段中分组，一定是把连续的线段分成一组。因为通过画图可以知道，如果把排序后两条不相邻$i$,$j$的线段分成一组，那么我们取$k,i <k<j$，就会发现无论是$(i,k)$一组还是$(k,j)$一组，对答案的贡献都比$(i,j)$一组来的多。当然这里还有一个显然的事情就是一个组的线段越多，相交部分肯定倾向于越少。

于是我们就有了DP方程：

$dp[i][j]=max_{k<i}\{dp[k][j-1]+R[k+1]\}-L[i],R[k+1] \geq L[i]$

其中，$dp[i][j]$表示把第二类线段的前$i$条线段分成$j$组的最优情况。

那么这个方程我们可以用单调队列优化。

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

算法标签 递推与动规 贪心 单调队列

数论知识回顾

欧拉函数

基本定义：对于一个正整数$n$,$\varphi(n)$代表比$n$小的且与$n$互质的正整数的个数。

计算性质：

$\varphi(n)=\begin{cases} n-1,&\text{n is a prime}\\ (p-1)p^{k-1},& n=p^k,\text{p is a prime}\\ \varphi(s)\cdot \varphi(t),&\text{n=st and (s,t)=1}\\ \varphi(k) ,&n=2k,\text{k is an odd} \end{cases}$

定义式：

$\varphi(n)=n \cdot \prod_{i=1}^k (1-\frac{1}{p_i})$

其中，$p_i$是$n$的质因子。

判断质数的方法：Miller Rabin

大整数质因数分解（探寻其质因子） Pollard Rho

特殊情况的组合数取模 Lucas

$C_n^m \equiv C_{n/p}^{m/p}\cdot C_{n \;mod\;p}^{m\;mod\;p}\;(mod \;p),\text{p is a prime}$

单调队列优化DP

题目比如参考上面的G题

这个题的特点是左端点是单调不降的，右端点也是单调不降的。因此我们的单调队列里存下标值，比较的条件是$dp[k][…]+R[k+1]$,限制的条件是$R[k+1] \geq L[i]$,假设当前正在考虑第$i$条线段。

这个单调队列不适合用STL，原因是它两端都要删除添加，还是用数组手写比较方便。

从队首到队尾，dp+R这个值单调递减，同时下标是单调递增的。原因：分同样多的组，当我们可用的线段更多时，方案数更丰富，因此可以得到更好的答案。

二重循环第一重是考虑第几条线段，第二重是考虑分几组。而且需要注意的是，分几组要从大到小来，因为处理完第$i$条线段的信息时，第$i$条线段对应的dp+R也会更新到这一系列队列中，对于同样是$i$而分更多组的计算造成干扰（避免后效性）。

队列操作：每一次先在队首剔除掉虽然dp+R很大，但不满足$R[k+1]\geq L[i]$的元素，然后算出当前的$dp$值，再在队尾更新，把原本队尾dp+R更小的剔除掉。因为这些决策点下标又小，又不利于贡献后面的答案。

Vector的简易写法和for的C++0x用法

vector<int> a;
a.resize(n);  //使得其大小为n，访问[0,n-1]
vector<int> a(n); //大小为n的vector，访问同上
vector<int> a(1,7);//一个元素，值为7
for(auto x : comp)   //x为comp容器的遍历器，下面直接访问x如何
{
    xxx
}
for(int i:{-d,d})//数值范围内遍历
//如果是vector<vector <xxx> > Q；这样的二维vector情形，则考虑
for(const vector<int> &comp : comps) {  //不过遇事不决用auto 就可以了

代码能力

1、vector的size是unsigned int类型。

2、STL Vector可能有重分配地址,*it 遍历器可能失效.

计算几何学习

见手写笔记

编码细节

1、unsigned long long 用printf输出时控制符为$\%llu$

2、最小值的预命令形式

1	#define min(a,b) (a)<(b) ? (a) : (b)

3、Windows 命令行屏幕输出文字： echo+文字内容（不用引号）

4、LL的溢出，考虑用(__int128)或者慢速乘来解决。如

LL mul(LL a,LL b)
{
    return (__int128)a*b%P;
}

此外，还要注意乘除的顺序，必要的时候先除后乘。

两个int相乘在long long的范围内判定，简单明确的写法是1LL*i*j>N这类。

5、取模简化运算：预命令

1	#define Mod1(x) (x>=MOD)&&(x-=MOD)

查看评论