近期CF做题记录：

梗概

主要包括一些近期写的CDE题，大致记录一下，以便之后翻阅复习，也作记录激励自己写题。

内容

【物品冲突】

• 【暴力】Edu104E 很有cf风格的一题，四种类型物品，每种类型物品各选一个，有的物品u和上一种的v间有冲突，问四种物品各选一个的最小花费。

https://codeforces.com/contest/1487/problem/E

冲突数量有限，所以排序后直接暴力即可，本以为会T，其实因为冲突只有2e6，复杂度并不会炸。

【网格挖槽联通】

• 【构造,思维】CF706D 构造，在n*m的网格中有几个位置被挖空，这些位置不会有同边或者同角，问怎么再挖几个空，让所有空槽联通，并且只有一条路，即成为树形

https://codeforces.com/contest/1496/problem/E

在j=3k+2的列上全部挖空，每个这种“走廊”中间刚好隔2，这时候只需要每两个“走廊”挖一条小路即可，如果m%3==1，那么最后空出来的两列在左边有走廊，右边没有，需要特殊讨论！

【网格涂色连线最优解】

• 【差分】CF578D n*n网格填充黑白两种颜色，可以选择把一个k的正方形全部填成白色，问怎么样选这个正方形使得网格中的白色行/列数量最多

https://codeforces.com/contest/1200/problem/D

对每行找出最先出现黑色空缺minn和最后出现黑色空缺maxx，然后想象用一个k*k的正方形去“套住”这条黑线时，哪些是可以选择的左上角，在可以的位置上通过二维差分数组全部加上1，最后看所有位置上最大的数值，就是白色k方块的最佳位置

【已涂色矩阵求满足要求子矩阵数量】

• 【DP】CF567C (这题不看图有点难懂) 有n*m的网格，每个cell有一种颜色(a to z表示26种不同颜色)，问图中有几个子矩形可以组成“国旗”？有三条高度相同的横着的色带的矩形被定义为国旗

https://codeforces.com/contest/118C1/problem/C

用dp写：维护两个数组,$dp_{i,j}$表示以i,j为左下角可以组成几个国旗，$top_{i,j}$表示(i,j)格的颜色往上可以延伸到多长。

先O(nm)预处理出top数组，然后dp的时候，每到一个格子(i,j)，先往上走检查是否有三条高度相同的色带。（注意一开始在这里wa了，因为第三段颜色的长度其实不需要等于第一种颜色的长度，只需要大于等于即可！）如果满足这个条件，那么这里可以形成宽度为1的国旗即$dp_{i,j}$可以等于1，之后再检查和(i,j-1)位置是否可以拼接（三段颜色完全相同),如果可以，那么$dp_{i,j}=dp_{i,j}+dp_{i,j-1}$。答案就是所有dp的和。

【重排序列使极小值最多】

• 【构造,思维】CF671D2 给n个冰球(1e5)，分别有ai的价格（可能相同），要求找到一种排列，使得满足a[i-1]>a[i]<a[i+1]的点尽可能多，输出这种最优的排列。

https://codeforces.com/contest/1419/problem/D2

如果是D1的条件，即ai价格各不相同，那么就是一大一小地输出。但是这题D2是可能相同的，所以我们想：让接近的数字距离尽可能远。所以我们先把ai排序，然后依次把ai填入数组，先填偶数再填奇数。

【n的除数排环使相邻不互质】

• 【构造,数论】CF671E 给一个数字n，列出n的所有大于1的除数，之后把这些除数按一定顺序排成环，要求两个相邻的数字都不互质，还提供一种操作，就是在相邻的两个数字$a_i,a_j$中插入他们$lcm(a_i,a_j)$，问最少进行多少次操作可以使得环满足条件？要求输出初始的环排列及操作次数。除数的数量题目保证不超过2e5

https://codeforces.com/contest/1419/problem/E

首先有一个结论：只有n是由两个不同质因子组成时，需要一次操作。先$O(n\sqrt{n})$找出n所有的质因子及出现次数，并编号，另外的情况，依照类似如下的排列搭出“骨架”：$1,12,2,23,3,34,4,41$，并把这些数字存进map中防止之后重复，我们发现,可以把所有含有prim[1]的除数都放在$prim_1,prim_1\cdot prim_2$之间，同理可以把所有含有prim[2]的除数放在$prim_2,prim_2\cdot prim_3$之间。我们知道除数的数量不超过2e5,因此直接通过dfs找到所有除数(似乎也可以不用dfs,但是我的方法写dfs比较方便），并且在搜索过程中随便记录它的一个因子i，推入对应的vector[i]中，最后结果就是$1,vec[1],12,2,vec[2],23,3,vec[3],34,4,vec[4],41$

【排列的逆序数】

• 【数学】DBPK2-1004 给数字n，为长度为n的排列初始为$1,2,3,4….n$即字典序最小的排列，m次查询，每次查询让n的排列按字典序后移$x_i$次，并输出移动后的逆序数。

https://www.dingbacode.com/contest/242/problem/1004

研究规律后发现，用一个特殊的进制来表示逆序数的一种排列，比如$1,2,3,4$为0000，$1,2,4,3$为0010，$1,3,2,4$为0100，这个是怎么来的呢？我的这种进制是，第i位上逢i进1！这样一来排列的逆序数即为这个进制数每个位上的数字之和：比如$1,3,4,2$位0110，则逆序数为$1+1=2$。非常神奇

• 【数学,DP】DBPK5-1001 求长度为n的排列的所有逆序对之和对998244353取模的值.

https://www.dingbacode.com/contest/289/problem/1001

结合之前对于逆序数的结论，我推得公式：$dp[i]=i\cdot dp[i-1]+\prod_{i=1}^{i-1}i\cdot\sum_{i=1}^{i-1}i$

【快速计数二进制中的1】【序列多少对ai,aj异或和二进制中1为偶数】

• 【数学】 DPPK5 给序列a，问有多少对ai和aj使得$a_i\oplus a_j$二进制上有偶数个1

https://www.dingbacode.com/contest/289/problem/1002

对于第二个问题，只要求ai二进制中的1和aj二进制中的1数量和为偶数即可。但是如果用除二模二的方法会被卡，(1000ms/1500ms)所以有一种更快的求1数量的方法：这样每次必定能去掉二进制中的一个1！

while(hc){
	cnt+=1;
    hc&=(hc-1);
}

【map<vector,xxx>代替字典树】【分割序列使每段任两个积不是平方数】

• 【数学】 CF708E1 给序列a，不改变顺序分割成几段，要求每段中不能存在ai和aj使得$a_i\cdot a_j=x^2$即不能是

一个平方数。问最少分割成几段。ai范围1e7。

https://codeforces.com/contest/1497/problem/E1

其实这题思路使好想的，在2-sqrt(1e7)之中只有500以内的质因数，ai为最多8个质因数相乘。所以我们拆分每个ai（唯一分解定理）并记录在哪些质数上的次数为奇数。之后用字典树或者这个map统计都行，遇到冲突后清空map并让res++.

【按规则取完石子】

• 【贪心】CF696D 有n堆石子(2e5)，每次操作可以从相邻的两堆石头里各取一个，还支持一种超级操作，在比赛开始前选择相邻的两堆石子进行交换，超级操作只能进行一次，问是否能把石头取完。

https://codeforces.com/contest/1474/problem/D

考虑如果没有超级操作怎么写：贪心地从1到n扫一遍，每次用前面的石头减在后面的石头上，如果前面的多于后面的，则失败。

核心：如果交换了i和i+1，那么1到i-1以及i+2到n是不受影响的，每次交换只要模拟这种两边凑过来只剩下中间的i和i+1的情况。

首先正着反着都扫一遍，处理出b和c两个数组(即从开头到当前节点贪心下来的情况)，如果扫到一个位置发现b[i]>b[i+1],这时说明正着最多只能走到这里了，反过来同理。我们考虑所有可行的位置，交换a[i]和a[i+1],并且让a[i]-=b[i-1],a[i+1]-=c[i+2]（保证b中i-1和c中i+1是有效值），然后看a[i]和a[i+1]是否相等且大于0即可！

【找坐标xy使离所有点距离|xi-xj|+|yi-yj|和最小】

• 【思维】CF703B 给n(1e3)个点的xy坐标(1e9),找到合适的位置建立“博物馆”使得所有点到博物馆的距离（|xi-xj|+|yi-yj|)之和最小，问有多少个这样的点.

https://codeforces.com/contest/1486/problem/B

没错这是个b题，但是我确实不会写qaq。把所有点投射到x轴和y轴上的投影记录，排序后找中位数，如果有两个中位数ai和ai+1,那么在这[ai,ai+1]这个区间内的所有坐标都是可行的。同理找到y轴上的中位数，两个区间长度相乘即结果。

这题之所以做不出来，我觉得是总想用算法的角度去写，但是其实这是简单的从二维往一维上的转化的思想。我们把总距离拆分成x轴上的距离和y轴上的距离，这样便转化成了一维直线上的距离之和问题，对于这类问题我们就知道该用中位数了。

【按规则构造树,最多能给多少点涂色】

• 【dp,树】CF652D 给一种树叫RDB，1级的RDB只有一个点，RDB的等级每次往上升级一次时:

如果点u没有孩子，则给它创造一个孩子；如果点u有一个孩子，则给它增加俩孩子；如果点u有三个孩子，则不动它。

每组输入给一个n级的RDB，所有点都是绿色，每次可以选择一个“鸡爪”即一个点连着三个儿子且全部为绿色的子图，把整个“鸡爪”染黄，问最多能染黄多少个点。

https://codeforces.com/contest/1369/problem/D

答：i级的树其实就是两颗i-2级树和一颗i-1级树组成。

因此初步可得到递推式$cnt_i=2\cdot cnt_{i-2}+cnt_{i-1}$，另外还要维护一个top数组，表示i级树的根是否被使用，如果$top_{i-1}$和$top_{i-1}$都为0，则i级树的根和这三个点可以再构成一个鸡爪（最后一张图这样），且$top_i=1$。只需要一开始预处理即可。

【三种木棍选两种构造矩形,使用完木棍总面积最大】

• 【DP】EDU93D 给r,g,b三个数字表示三种类木棍的数量(<=200)之后读入每种木棍的所有木棍。每次可以取两种不同颜色的木棍，以之为长宽构造一个矩形，重复直到木棍用尽，问最大的总面积。

https://codeforces.com/contest/1398/problem/D

用$O(n^3)$的动态规划写，每种木棍从大到小(仔细想一下从小到大也行)排序（因为后面总会有一些用不完的木棍，我们希望能优先使用长的木棍），方法有点类似背包的状态转移。我们用$dp_{i,j,k}$表示用前i个r木棍（全都使用），前j个g木棍，前k个b木棍构造的最大总长度。

我们知道这个dp中有很多状态都是达不到的，比如$dp_{1,0,0}$显然是达不到的状态

并且如果要求$dp_{i,j,k}$,我们不知道他是从$dp{i-1,j-1,k},dp_{i-1,j,k-1},dp_{i,j-1,k-1}$中的哪个拼接上来的。

因此我们用$dp{i,j,k}$往上去推$dp_{i+1,j+1,k}$等等。所以有转移方程：

if(i+1<=c[1]&&j+1<=c[2])
    dp[i+1][j+1][k]=max(dp[i+1][j+1][k],dp[i][j][k]+(ll)a[1][i+1]*a[2][j+1]); 
if(i+1<=c[1]&&k+1<=c[3])
    dp[i+1][j][k+1]=max(dp[i+1][j][k+1],dp[i][j][k]+(ll)a[1][i+1]*a[3][k+1]);
if(j+1<=c[2]&&k+1<=c[3])
    dp[i][j+1][k+1]=max(dp[i][j+1][k+1],dp[i][j][k]+(ll)a[2][j+1]*a[3][k+1]);

想了一下为什么从小到大排序也是可以的：三种类型的木棍，一定有两种木棍是要全部使用的，也就是只有一种木棍可以不用完，而这些不用完的都是最小的那几个。

因为上面的状态转移方程，$dp_{0,0,123}$之类的都是0，从这个点往上dp推出的结果，也就是b类木棍前123个都不使用得到的结果。所以从小到大排序也是可以的。

【旅行商问题,边费用为max(a[j]-a[i],c[i])】

• 【DP】CF712E 有n(1e5)个城市，每个城市有ai和ci两个属性，从城市i到城市j的费用为$max(c_i,a_j-c_i)$,问从任一城市开始经过所有城市再回到该城市所需要的最小费用。

https://codeforces.com/contest/1504/problem/E

我们观察这条式子：$cost(i,j)=max(c_i,a_j-c_i)$,可以知道$c_i$是逃不掉的，因此我们把c全部都先加到结果$res$上，这样每条边的费用就变成了$cost(i,j)=max(0,a_j-(a_i+c_i))$。

我们可以形象地把ai理解成楼房的高度，ci理解成这个楼房的梯子高度，我们在楼房i上时，如果楼房高度和梯子高度之和高于楼房j的高度，则可以免费从i爬到j，否则则需要补上这些高度的差。即从楼高+梯子较高的楼房爬到低的是不需要费用的。

以a为第一关键字，c为第二关键字对房子排序。

因此我们分两部分：

第一部分先从最低的楼层爬到最高的楼层（中间使费用尽量小）。

第二部分只需要把没爬过的楼房从高往低排列，最后走回最低的楼房即可（这部分不需要任何费用）。

int now = ac[1].ft+ac[1].sd;//now是当前房子+梯子的高度
   //之后每步的消耗看作max(0,aj-(ai+ci))
   rep(i,2,n){
       if(ac[i].ft>=now)//通过梯子上去的情况
           res += ac[i].ft-now;
       //不加的这些是达到最高之后访问的
       //如果这个楼可以使now更高，也应该在中间免费经过
       now = max(now,ac[i].ft+ac[i].sd);
   }
   //第二部分经过的楼全部免费

【k个字母构造字符串使(a[i]==a[j]&&a[i+1]==a[j+1])的ij尽可能少】

• 【构造】EDU107D 给两个数字n和k，用字母表的前k个字母构造一个长度为n的字符串，每有一对i!=j使得$a_i=a_j,a_{i+1}=a_{j+1}$，则该串的cost+1,问最小cost的构造为？

https://codeforces.com/contest/1511/problem/D

先考虑如何构造完全无费用地字符串？所有字母地两两组合都能够出现，一共有k*k种组合，这些组合都出现则可以构成长度为$k^2+1$的串（考虑三个字母包含两种组合，四个字母包含3种组合以此类推）.

考虑这种构造:$aabacad,bbcbd,ccd,d$，即对于每个字母，先输出一个它自己，再加上它和排后面的各种字母的组合。

数论

【统计x的所有除数】【求c·lcm(a,b)-d·gcd(a,b)=x​的ab对数】

• 【数论】EDU106D 给$c,d,x$三个1e7内的数，求有多少对$(a,b)$满足$c\cdot lcm(a,b)-d\cdot gcd(a,b)=x$

https://codeforces.com/contest/1499/problem/D

把式子变形，设$a=L\cdot gcd(a,b),b=R\cdot gcd(a,b)$则将式子变形得到$L\cdot R=\frac{\frac{x}{gcd(a,b)}+d\cdot gcd(a,b)}{c}$，观察式子可以发现，x必须是gcd的倍数，因此我们$O(\sqrt{x})$枚举x的所有除数(比赛的时候以为这个是o(x)的),之后右边的值就确定了.

有了$L\cdot R$的值，然后设$zyz[L\cdot R]$为y的所有质因子数量,先用类似埃式筛的方法筛出每个数字的有多少种不同的质因子。那么这种情况下$(L,R)$有$2^(zyz[L\cdot R])$对。

哦对，关于统计x所有除数的方法：非常基础，但是我忘掉了

rep(i,1,sqr){
    if(x%i==0){
        vec.push_back(i);
        if(i*i!=x) vec.push_back(x/i);
    }
}

【给一序列,可插入2*ai-aj,问能否得到k】

• 【数论,裴蜀定理】CF698D 给一个序列a，长度2e5，每次操作可以选定序列中的任意两个数字x,y.可以把2x-y插入序列中，问能不能通过这种操作拼凑出k（1e18）。

https://codeforces.com/problemset/problem/1477/A

裴蜀定理：有非0数a和b，则一定有ax+by=gcd(a,b)一定有整数解.(也是exgcd的前置)

我们把$new = 2a-b$拆分为$new = a+(a-b)$ ，设$a=c+(c-d)$，那么递归可以得到$new = c+(c-d)+(a-b)$,后面也可以再来一堆(x-y),所以我们把问题转化成了：

是否能用$\sum a_i-a_j=k-a_x$。（i,j随便取）。再结合之前的裴蜀定理，我们先算出所有$a_i-a_{i-1}$的gcd，再枚举$a_x$，看$k-a_x$能否被gcd整除即可，复杂度$O(n)$.

【查询l,r区间最少要拆分成几段使子串各元素互质】

• 【数论,倍增】CF717D 给1e5长的序列(ai也是1e5范围)进行1e5次询问，每次给l和r，问最少需要把l到r这一区间的序列拆分成几段子串，才能使每段的LCM=这段元素的积.

https://codeforces.com/contest/1516/problem/D

很久没有写倍增了，因此这题记录的详细一点。

首先可以确定，要满足LCM=这段元素的积，即这段元素的所有数字必须两两互质。我们用质数筛筛出1到1e5的质数推入质数表中，然后对每个数字进行质因数分解，我们需要维护两个数组：

• pre[x]表示质数x上一次出现的位置(因为是倒着找的，所以pre[x]一定是比当前位置往后的)
• rb[i]表示i位置往右边数，最近是哪个数字和他不互质

我们知道如果要找到当前位置i的下一段，即直接跳转到rb[i]即可。我们倒着做一次循环：

if(a[i]%prm[j]==0){
    while(a[i]%prm[j]==0) a[i]/=prm[j];
    rb[i] = min(rb[i],pre[prm[j]]);
    pre[prm[j]] = i;
}

即一个数字有多个质因子组成时，需要找到这些质因子x中pre[x]最小的赋值给rb[i];其次因为在当前位置i上找到了新的包含质数prm[j]的位置，所以也需要更新pre[prm[j]]。

我们知道rb[i]是i位置经过一次跳转后到达的位置，使用倍增法，我们需要对i位置找出跳转2,4,8,16….次的位置，放在bz[i],[j]中，表示位置i经过$2^j$次跳转后到达的位置。

rep(i,1,n) bz[i][0] = rb[i];
bz[n+1][0] = n+1;
rep(j,1,20){
    bz[n+1][j] = n+1;
    rep(i,1,n){
        bz[i][j] = bz[bz[i][j-1]][j-1];
    }
}   

这样一来，我们读入l时，从大往小检测2的倍数，弱没有超过r则执行这次跳跃，并且统计结果。

cin>>l>>r;
int cnt = 1;
repb(j,20,0){//从大往小找
    if(bz[l][j]<=r){//如果执行2^j次跳跃不会越界,则执行
        cnt+=(1<<j);
        l = bz[l][j];
    }
}

这题还有一些边界需要赋初值，比如rb[n+1]=n+1,所有pre[x]=n+1,以及bz[n+1],[0]=n+1。