退役前的一句话题解

asuldb · 2019-10-07 17:03:33 · 个人记录

由于太懒了，没什么意思的题就写一句话题解了

10.07

zroi #1118

分别对\sum a,\sum b开状态开不下，考虑到a_i\leq b_i，所以任意时刻都有\sum a\leq \sum b，所以设dp_{i,j}表示选到了第i个数满足\sum a\leq j\leq \sum b的最小代价，显然有转移dp_{i,j}=\min_{k=j-b_i}^{j-a_i}dp_{i-1,k}+c_i，单调队列优化转移即可

zroi#1116

两个数异或起来只有两个1，考虑枚举这两个1分别在哪里，即对于c=2^i+2^j(i\neq j)，求有多少对a_i\bigoplus b_j=c，拆一下式子变成了(a_i\bigoplus 2^i)\bigoplus (b_j\bigoplus 2^j)=0,i\neq j，于是我们能将每一个a,b搞成\log个数，得到了两个n\log n长的数列，求一下这两个数列有多少对相等的数对即可。考虑i\neq j的限制，发现对于原数列一对相等的数，在每一个数位都会被计算一次，于是还要减掉原数列里相等的数对个数乘上数位个数。

通过玄妙的挂链hash能做到O(n\log n)。写两个\log基本都被卡了，比如说不会hash的我。

zroi#1110

分析一下不难发现对于所有“添”连边得到的图一定是仙人掌（因为保证三线不共点，所以一条边不会出现在两个简单环里）

众所周知，给仙人掌染色最多只需要三种颜色。当且仅当存在奇环的时候，需要用到的颜色数是3。我们发现当且仅当有不少于三种斜率的时候一定会存在奇环(三种斜率一定会构成一个三角形，而三角形是一个三元环)，于是判断一下是否存在三种或以上不同斜率即可；

zroi#1111

不难发现只需要按\frac{t_i}{p_i}从小到大排序之后顺着选过去；修改用线段树维护一下即可。

zroi#1120

用一个树上差分能够维护出每一条边被经过的次数，如果选定了根我们贪心的选择经过次数最大的那条边作为重儿子即可。所以随便先定一个根，大力换根即可。由于换根的时候可能会把原来的重儿子换成根，所以对于每个点要维护最大儿子和次大儿子。

zroi#1113

x,y满足x异或y在二进制下有奇数个1当且仅当cnt(x)\bigoplus cnt(y)=1，cnt(x)表示x二进制下1的个数。这个结论非常简单，因为cnt(x\bigoplus y)=cnt(x)+cnt(y)-2\times cnt(x\&y)，又因为运算在模2意义下所以后面那个2\times cnt(x\&y)相当于没有。于是维护当前区间并内有奇数、偶数个1的数分别有多少个即可。

我们把所有区间视为左闭右开的形式，把所有区间的端点拿下来排序建线段树。相邻两个端点之间用数位dp算有奇数个1的数的个数，用线段树维护区间并即可。

zroi#1127

对于所有1到n的排列p，使i向p_i连边，问期望环的个数

答案即\frac{\sum_{i=1}^n\begin{bmatrix}n\\i\end{bmatrix}i}{n!}，设f_n=\sum_{i=1}^n\begin{bmatrix}n\\i\end{bmatrix}i，则有

不过好像有更简单的方法说明答案就是\sum_{i=1}^n\frac{1}{i}

zroi#1126

求一下差分数组，记差分数组中所有小于-k的与-k的差为A，大于k的与k的差为B，答案就是\max(A,B)

证明比较简单，设A<B，我们使用A的代价把所有小于-k的都调整到-k,使得差分数组只剩下大于k的，在用B-A的代价把这些调整到K即可；由于差分数组的和为0，这样的调整方案是一定存在的。

10.08

uoj#66

显然当长度为2^i的时候最优策略就是一直折半，答案就是2^i-1；

对于更一般的情况，感性理解一下分成一些2的次幂一定是最优的

zroi#1132

首先先把必须连的边都连上，如果出环就是-1；再暴力一下两个点i,j，看看i,j是否能连边，用这些边和必须连的边跑一棵生成树，输出这些边即可。

uoj#67

树是一个n个点n-1条边的无向连通图，也就是说删除一个点后必须剩下n-2条边，且图联通就能保证是一棵树

所以我们删的点必须是度数为m-(n-1-1)=m-n+2的非割点，tarjan求一下即可。

「NOI2015」荷马史诗

发现如果满足n\%(k-1)=1的话就是一个k叉的哈夫曼树，开一个小根堆，暴力拿出重量前k小的合并成一堆即可。又要求最大深度最小，所以额外记一个最大深度作为第二关键字。

当n\%(k-1)\neq 1时，我们需要确定一个第一次的合并量i，使得(n-i+1)\%(k-1)=1，显然这个第一次合并量越小越好，我们枚举这个i，先把这i个合并起来；之后再按照n\%(k-1)=1的方式合并

CF1169C

我们发现答案就是最大的修改量，于是二分一下这个最大修改量，这样每个数能形成的取值就是一个区间。问题变成了能否给每个数一个取值使得序列单调不降，直接贪心即可。

LGP4755

傻题，讨论一下最大值，无脑分治即可

[POI2005]SAM-Toy Cars

贪心，感性理解一下我们应该放回去的是下一次出现最晚的那一个，于是用大根堆维护一下。一个坑点是堆中的元素的下一次出现时间必须动态更新，并不需要可删堆，由于新插入的下一次出现时间一定更大，所以直接插入即可。

CF1174E

只会一个无脑做法。我们发现在序列里多次添加同一个数并不会使得前缀\gcd的变化次数，所以这题和UR1的外星人非常相似。

先对于每一个数求一下把这个数放在第一个前缀\gcd的最大变化次数。之后设dp_i表示当前前缀\gcd为i的序列有多少种，我们发现从i向i的约数j转移的时候，会有\left \lfloor \frac{n}{j} \right \rfloor-\left \lfloor \frac{n}{i} \right \rfloor个数变得没有作用，所以我们乘上一个排列数让这些数排列进去

更详细的题解还是看看神仙写的吧。更高论的做法好像需要在dp过程中存下2和3的次幂，过于高论就不会了。

10.09

[ioi2013]robots

答案就是行动次数最多的机器人的行动次数，二分这个行动次数mid

先所有物品按照重量排序，把这些物品依次加入一个以体积为序的大根堆里，每个有重量限制的机器人贪心地选择质量小于其限制的体积前mid大的物品；剩下的物品就只有了体积限制，让有体积限制的机器人贪心选就可以了。

[NOIP2005]篝火晚会

难点在于读题，就是瞎推几下把目标环推出来，之后把初始的环摁在上面匹配就好了。初始环要从两个方向都匹配一遍，否则会WA80

bzoj2375

把所有操作倒过来，这样就不用考虑当前操作对一个已经染过染色的格子的影响了，知道我们使得一个格子被遍历常数次就能做到O(n+m)的复杂度，所以只需要使用并查集维护已经染好颜色的格子就行了

[SCOI2014]方伯伯的玉米田

链接里就是题解

10.10

uoj#175

链接里就是题解

zroi#1134

发现这个x+1,x+2...x+c-1都出现但x和x+c不出现不是很好限制，考虑容斥一下，求连续c-1个出现-2\times连续c个出现+连续c+1个出现即可。

考虑离线，把所有询问按照右端点排序，维护当前每种值最靠右的位置，同时维护值域上所有长度为1到c+1的区间的最小值。每更新一个数，可能影响到的区间就有c^2个，我们直接暴力这些区间，并去树状数组上修改这个区间对应的最小值。查询的时候直接查询有多少个长度为c的区间最小值不小于l即可。据慎老师分析，复杂度只有O(nc^2+(n+m)\log n)

[NOI2005]聪聪与可可

猫哥的走位有点迷，于是先搞个预处理id[i][j]表示猫在i，鼠在j的时候下一步猫的走位；不难发现因为期望的线性性，我们可以直接搞一个dp_{i,j}表示猫在i，鼠在j的时候期望走几步，直接记搜转移即可

CF860E

把题意转化一下大概就是求f_i=\sum_{j}[dep_j\leq dep_i]dep_{LCA(i,j)}，考虑先求出所有点和i的LCA的深度和，再减掉深度比i大的。显然深度大于点i的点一定在深度和i相等的点的子树中，于是我们直接对深度相同的点建虚树，把虚树上每个叶子的点权设为子树大小减1，问题转化成了对于每一个叶子求其他叶子和它形成的LCA的深度乘叶子的点权，在虚树下瞎搞一波就行了

10.11

LGP4713

发现这个最低扣成0导致不是无法直接算贡献，于是2^k枚举一下哪几个部分大零蛋，其余部分照常算，扣成负数也不要紧；显然这样不会使得最优答案变小或一个更大的较小的答案变大。里面套一个dp_{i,j,k}表示用完第i个句子，填了j行，第j行填了k个字的最小扣分。大力转移就好了。

uoj#48

显然这个次大公约数就是\gcd除以最小质因子，注意到和a_1取\gcd之后一定是a_1的约数，所以我们将a_1质因数分解，搜出其所有约数，搜的时候就能方便的得到所有约数的最小质因子了

[JXOI2018]数列

吉老师的小清新dp，搞了好久搞出一个不一样的做法，题解在链接里

晚上打了场牛客，成功让我知道vector<int> d[maxn]有多慢，由于卡B卡不过去搞了很久，之后还一边写题一边和瞎颓，导致没有时间去rush一个E，成功4题滚粗+罚时爆炸

10.12

CF594D

显然是个垃圾题，维护一下每一个质因子最后一次出现的位置，大力离线+树状数组即可

[JLOI2015]战争调度

显然是个简单题，大力状压每个点到根的路径上的状态，设dp_{i,s,j}表示i点到根的路径上的状态为s，子树内部有j个农民参战了，贡献直接在叶子节点算好，往上只需要把左右儿子合并一下即可。注意到后两维的状态的乘积始终是2^n，合并成一维就好了，所以空间复杂度是O(2^{2n})，再分析一波发现每一层节点对时间复杂度的贡献相同，所以时间复杂度是O(n2^{2n})，所以难点在于对时间复杂度的分析。

[NOIP2011]观光公交

比较玄幻的贪心，注意到我们要最小化的东西是\sum b_it_i-\sum A_i，b_i是在站点i下车的人数，t_i是到达站点i的时间,\sum A_i是个定值不用管他。于是最小化\sum b_it_i即可。

考虑到我们在某一段道路上用一个加速器会使得后面所有的t_i都减小1，所以看起来我们好像是应该在尽量靠前的地方使用加速器。但是注意到有一些车等人的情况，我们发现我们对于一条道路用了加速器，结果后面的某处车停下来等人了，于是并没有使得车等人站点更靠后的站点的到达时间减小。

于是我们分一下段，使得同一段内都是人在等车，每一条道路的价值是同一段里位置更靠后的站点的b_i的和，贪心地选出价值最大的一条道路使得这条道路的d_i减一即可。之后继续分段，做k次之后就是答案了，复杂度是O(nk)的，loj上有数据加强版看起来非常牛逼的样子。