补题进度：10/13

1001

待填坑

1002(kmp+递推)

题意：

有长度为n(<=50000)的字符串S和长度为m(m<=100)的字符串T，有k(k<=50000)组询问，每个询问(L,R)，表示对于所有的(i,j)(1<=i<=L,R<=j<=n)，将S[1..i]和S[j..n]拼接起来，求这个新的S‘中出现T的次数总和

分析：

我们分析对于一个(i,j)的情况下，那么T的出现有三种情况，一种是整体在[1..i]，第二种是整体在[j..n]，第三种是部分拼接起来

我们先考虑前两种怎么求

只需要将S和T去kmp，记录下匹配成功的位置，pre[i]表示S[i-m+1]..S[i]和T是否匹配成功，suf[i]表示S[i]..S[i+m-1]和T是否匹配成功

我们对pre[i]求个前缀和，对suf[i]求个后缀和，那么pre[i]就表示左分割线在i的时候左边有多少个完整的T，suf[i]表示右分割线在i的时候右边有多少个完整的T

但注意我们的一个询问[L,R]并不是固定分割线L和R，而是左分割线<=L,右分割线>=R

那么就是L左边所有分割线的答案去乘上右边分割线的个数   +    R右边所有分割线的答案去乘上左边分割线的个数

所以只要对pre[i]和suf[i]再去求前缀和以及后缀和

接下来考虑跨区间的问题

因为m很小，所以对于每个询问我们可以枚举一个k，表示左边是T[1..k] 右边是T[k+1..m]

preh[i]表示S[i-k+1]..S[i]和T[1..k]是否匹配成功，sufh[i]表示S[i]..S[i+m-k-1]和T[k+1..m]是否匹配成功

那么答案只要最后加上左边匹配成功的位置数*右边匹配成功的位置数就行了

所以对preh[i]和sufh[i]做一次前缀和与后缀和

时间复杂度O(n+m+k*m)

1003(区间分解质因数)

题意：

为了计算一个东西，需要将[l,r]内所有东西分解质因数，l<=r<=1e12,r-l<=1e6

分析：

类似区间筛

将[1..1e6]内所有的素数p去刷[l,r]内p的倍数，算一算对应数字的p的指数是多少

注意细节：

1、不需要将分解质因数的结果存下来，那样会开很大的数组导致很慢，我们发现为了求因数个数，是可以每次累计求的

2、[l,r]内的数，在被[1,1e6]内的数全部刷完之后，有些数可能不是1，因为它们本身是大素数，所以需要考虑到这些数

3、r-l<=1e6说明区间内数有1e6+1个……这个坑了很久……

1004(分数规划)

题意：

有一个长度为n(<=60000)的数组，数字是<=n的数字，一个区间[l,r]的价值是[l,r]内不同数字个数除以区间长度，求所有区间中价值最小为多少

分析：

一看到最优比率问题就想到分数规划

二分答案mid，看是否有解，即判断是否存在num[l..r]/(r-l+1)<=mid

分母乘到右边，即是否num[l..r]<=r*mid-l*mid+mid

我们从小到大枚举r，去快速寻找价值最小的l

转换一下式子：num[l..r]+l*mid<=r*mid+mid

对于一个确定的r，寻找价值最小的l也就相当于用线段树维护num[l..r]+l*mid的最小值即可

那么r->r+1，会修改哪些信息呢？

我们可以记录下数字a[l]的前一个同颜色的位置pre

那么就相当于给[pre+1..r]这段区间加1

时间复杂度O(logA * nlogn)

1005(取模意义下的最短路)

题意：

有四个点四条边组成了一个环，每条边是长度<=30000的整数，还有一个大整数k(k<=10^8)，我在起点2，最终我也要到达终点2，问所有可行的路径总长度中，长度大于等于k的最短值是多少

分析：

第一眼感觉不能最短路

但是这题其实很套路，我们去考察起点相连的两条边，取两者当中的一个最小值w，那么如果我们可以走出长度x，那么我们就必定可以走出长度x+2*w

我们可以建4*2*w个点，d[i][j]表示从起点走到点i结束，走的长度在模2*w为j的情况下最短路

对于最后的d[i][j]，如果其值>=k，那么就把它和ans取min；如果<k，那么我们就把它一直+2*w，直到>=k，再和ans取min

时间复杂度O(8*w*logw)

1006(手写bitset优化图的dfs)

题意：

有n(<=500)个点的稠密图，m(m<=250000)次修改，每次修改将原图中不超过10条边进行取反（原本连上的就断开，原本断开的就连上），对于每次修改之后，都要求出图的强连通分量

分析：

我们先来算一算暴力的复杂度：因为是稠密图，我们用邻接矩阵来存，那么对图2次dfs的复杂度就是n^2，总的复杂度就是62500*25000=1.5*10^9，无法接受

我们可以考虑用bitset来优化

我们可以开一个bitset表示当前未访问过的点的集合，另一个bitset表示某个点u的相邻点的集合，将两个bitset and一下，那么我们去跑那些为1的位置

这样总的复杂度就除以了64，变成了3*10^7，就行了

但是用stl里的bitset有个问题，它不支持取出所有为1的位，你还是只能一个一个去枚举，这会导致复杂度并没有降下来，解决方法是自己手写一个bitset(%%%%csy)

1007(拓扑排序+dfs找环)

题意：

有一个左边n个点，右边n个点(n<=300000)的二分图，左边的每个点都向右边的两个点连出两条有权值的边，对于一个完美匹配，匹配的价值是所有匹配边边权的乘积，求所有完美匹配的价值和

分析：

很容易发现如果右边某个点度数是1，那么完美匹配的这条边就固定了，同时它对应的左边那个点度数也就变成1了，那么它剩下的那个边也是固定的了

所以我们可以先拓扑排序把这些固定的匹配给筛出来

那么还剩下来左边m个点，每个点度数都是2，右边剩下m个点，度数都>1

又因为左边度数一共2m，所以右边必然也是每个点度数都是2

那么就分成了连通块，我们发现可以分别去处理这些连通块，最后答案相乘

对于一个连通块，它一定会形成一个环，而且是偶环（奇环不存在于二分图），那就相当于这个连通块的完美匹配有两种方式，一种是取1 3 5 7 9边，另一种是取2 4 6 8 10边，只要去dfs找出这个环，算出两种方式各自的乘积就行了

1008(MST+并查集)

题意：

n(<=100000)组成一个数，有m个修改(a,b,c,d,w)表示将树上a->b的点、树上c->d的点，以及它们彼此之间都连上权值为w的边，最后求最小生成树

分析：

类似Kruskal算法，我们按w排序，然后去用并查集维护是否出现环

很明显对于一个询问，我们只需要把a,b均走到它们的lca，将路中相邻的点在并查集中连边即可，cd也是一样的道理，最后将两者的lca在并查集中合并就行了

但是问题上我们不能对于每个询问都去将路径上所有点都走慢

我们发现有很多链之前都已经走过了，我们可以再开一个并查集，f[i]表示树上连续链当中，i往上最高能走到f[i]

时间复杂度O(mlogm)

1009(构造)

水题略过，容易构造出模数为2的答案

1010(DP)

待填坑

1011(模拟)

略

1012(递推)

题意：

有长度为n的a数组和长度为m的b数组,n,m<=2000，问a和b的所有共同子序列中有多少个是摆动数列

分析：

很容易写出一个递推，f[i][j]表示a的前i个，b的前j个，以a[i],b[j]为结尾的，最后的上升/下降趋势为k的结果

f[i][j][k]=Σf[i‘][j‘][1-k] (a[i‘]==b[j‘],a[i‘]<a[i]或者a[i‘]>a[i])

这样是O(n^4)的，并不可行

我们发现这个递推式子其实是求[1..i-1][1..j-1][1..a[i]-1]的前缀和，这个维数挺高的……

但我们发现因为i是单增的，所以第一维可以直接省掉，a[j][num]表示当前i下，最后一个位置是b[1]..b[j-1]，并且数字大小<=num的f值的前缀和

这样可以用一个二维树状数组来维护

时间复杂度是O(n^2log^2n)的，恰好可以卡过去

不过有更优秀的方法

我们在从小到大枚举j的过程中，我们可以根据b[j]和a[i]的大小关系来决定这个j作为前一个波峰/波谷的答案，用一个cnt0和cnt1来将所有b[j]!=a[i]位置的贡献加起来就行了（贡献就是对应的前缀和）

对于b[j]=a[i]的位置，就可以直接根据cnt0和cnt1来O(1)更新递推的答案

所有j枚举完了，要记得将这次的f值也要放入前缀和当中

这样复杂度就是O(n^2)的了

1013

待填坑

2017多校Round4(hdu6067~hdu6079)