跟随大神们的脚步进军CF！希望能坚持。。。

【于是我也决定一套一套的刷(屠)了】

• CF 396D - On Sum of Number of Inversions in Permutations

• CF 396B - On Sum of Fractions

结论题。对于一个n，如果p=n+1是质数，那答案就是1/2-1/p。可以用归纳法证明。然后只需要找出离n最近的前后两个质数（利用10^9以内相邻质数不会相差300复杂度可以有保障）即可。

• CF 392D - Three Arrays

题意：给三个长度为n的数组a,b,c。要求最小化i+j+k，使a[1..i],b[1..j],c[1..k]的并集等于a,b,c三个数组的并集。n<=10w。

倒着枚举一个数组的下标，每次要添加一个数k。找到它在另外两个数组中第一次出现的位置x和y。(x,y)作为一个点。然后根据单调性，就是维护一个台阶的形状。。set可以简洁的完成。。

• CF 400E - Inna and Binary Logic

题意：给一个长度为n的序列a[1][1..n],a[i][k]=a[i-1][k] & a[i-1][k+1]。第i个数组含有n-i+1个值。每次修改a[1][x]=y，询问修改后整个a数组的和。

按位搞。只要维护连续1的段。写个treap维护修改即可。

• CF 380C - Sereja and Brackets

题意：给一个长度为100w的括号序列。10w个询问，[l,r]中有多少个'('或')'是合法的。比如())(())中有6个合法的。

先用栈求出每个左括号匹配的右括号的下标i。然后就是询问[l,r]中有多少个i，l≤i≤r。无脑直接上主席树。O(nlogn)。

• CF 379F - New Year Tree

题意：一开始有一颗4个节点的树。每次选一个叶子节点，给它加两个孩子，之后要输出当前树的直径。操作数≤50w。

太弱了看题解才知道只需要维护当前的答案和直径的起点st和终点ed。每次加一个叶子u只需要判断dist(u,st)或dist(u,ed)能更新答案就好。倍增LCA就行。O(nlogn)。

• CF 377D - Developing Game

题意：有n个人，每个人有个能力值vi。他不会和能力值不在[li,ri]范围内的人工作。问你最多能选几个人出来工作，并输出方案。n≤10w,l≤v≤r≤30w

我们考虑先让其中一维有序吧。。比如先按l排序。然后我们发现，如果对于一个方案子集S，一定有vi∈[Lmax,Rmin],Lmax=max{li},Rmin=min{ri},i∈S。

由于我们已经让l有序了，那Lmax一定就是当前的li。然后我想考虑只计算从1枚举到i，此时的最优解，然后想二分之类的做法。比如二分R，使vi∈[li,R]，找前面有多少个j(1≤j≤i)满足li≤vj≤R≤rj，结果获得了意想不到的收获——注意后半边，显然就是求被线段[vj,rj]覆盖次数最多的点。为了vj≥li，还得满足li单调递增。可是vj不一定有序，那只好写个平衡树来维护了，先把前面的vj≥li的线段删掉。求被线段覆盖次数最多的点我们可以用线段树在插进平衡树的同时维护。

每个线段最多只会被插入和删除一次。所以总体复杂度还是O(nlogn)的。

• CF 17E - Palisection

题意：200w个由小写字母组成的字符串，求取出两个不同（位置不同即可）回文子串且这两个回文子串有公共部分的方案数模一个数。

由于有重叠和相交两种情况比较逗，所以我就求 取出任意两个 不同且不重叠不相交 的回文子串 的方案数。

先用manacher是显然的。之后我们只要处理出以i为右端点的回文串个数 和 以j(i≤j≤n)为左端点的回文串个数。然后乘一下了。

运用差分的思想，两个东西都可以O(n)计算出。计算时别忘longlong。

• CF 383C - Propagating tree

题意：一开始一颗20w个点的有根树，一开始点有点权。20w个操作。修改时给出u,x,k，表示在以u为根的子树Tu中，对于所有节点v∈Tu，如果dist(u,v)是偶数，则v的点权+k，否则-k。询问单点点权mod 10^9+7。

很像393C...对子树操作，那我们还是维护dfs序。这回按点的深度的奇偶性把点分成两个点集S奇和S偶。如果u∈S奇，那么对于它的所有后代v∈Tu，如果v∈S奇，那这次修改对v的贡献是+k，反之是-k。u∈S偶的情况同理。两个点集各维护一个树状数组即可。

• CF 187D - BRT Contract

题意：数轴上有一个起点(第0个点）和终点（第n+1个点）。中间有n(≤10w)个点，每个点上有个红绿灯。所有灯的颜色同时改变，一开始是g秒绿灯，然后是r秒红灯，交替进行。10w个询问，在t时刻从起点出发的一辆车，到终点的时刻是多少。到路口如果是红灯需要停下来等待，直到绿灯。

先预处理pre[i]表示从刚好绿灯开始时，从i到n需要多少时间。先把dist都mod (g+r) 一阵转化，问题就变成了求在[i+1,n+1]中最左边的一个范围在[L,R]的数。离散化之后可以用主席树或者线段树。O(nlog^2n) or O(nlogn)。

询问也和上述方法大同小异，使用主席树更加方便。O(nlog^2n)。

两个都用主席树在cf上会TLE QUQ 后来只好把预处理改成线段树才A 0.0

• CF 76A - Gift

显然g增加时，s是递减的。那么枚举g的最大值，按s从小到大排序，求最小生成树。就能求得一组(g,s)，s一定是最优的。新边插进去之后直接插入排序，这样砍掉一个log。O(nm)。可以过。

• CF 226E - Noble Knight's Path

题意：10w个点的树，一开始所有点权都是0。有10w个时刻，第t个时刻可以把一个点的点权设为t（每个点的点权只会被设置一次），也可以询问在a到b的路径上（ab不算），第k个点权不小于x或等于0的点。

先读进来每个点被修改的点权。第t个询问时，二分点，然后判断路径上有多少个点不合法（点权∈[x+1,t]），减一下得到合法的。用主席树（dfs建树）和倍增（求lca）维护即可。注意路径两端不算。

• CF 396C - On Changing Tree

题意：一开始一颗30w个点的有根树，点权均为0。30w个操作。修改时给出u,x,k，表示在以u为根的子树Tu中，对于所有节点v∈Tu，v的点权加上x-k*dist(u,v)。询问单点点权mod 10^9+7。

其实很简单，因为操作都在子树中，所以自然地想到了维护dfs序。对于v∈Tu来说，它要加的delta=x-k*(dep[v]-dep[u])=(x+k*dep[u])-k*dep[v]。前一项是给定的，后一项的-k也是给定的。于是只要用树状数组维护这两个标记即可，时间复杂度O(nlogn)，常数小。

• CF 392C - Yet Another Number Sequence

然后A(i,k)可以由A(i-1,0..k)和A(i-2,0..k)得出。构造矩阵用矩乘加速。时间复杂度O(k^3logn).

• 相关文章