BJOI2018 - Click Here
5/5
吐槽
题答就不做了…
二进制和染色两题的体验极差…
BZOJ5291
Solutions考虑如何处理询问。
区间问题不好处理，因此转换成求单点的贡献。设$A_{i,j}$表示$j$位置能够覆盖长度为$i$的区间个数，那么询问的答案为$\sum_{i=L}^R \sum_{j=1}^n A_{i,j} v_j$
注意到$A_{i,j}$只与该位置能包含的区间数以及长度为$i$的区间最大覆盖数有关。因此设$a_i=min(i,n-i-1)$，则有$A_{i,j}=min(a_i,a_j)$
现在所求的答案为$\sum_{i=L}^R \sum_{j=1}^n min(a_i,a_j) \cdot v_j$。显然对于不同的$i$答案互相独立，因此只用求出$\sum_{i=1}^x \sum_{j=1}^n min(a_i,a_j) \cdot v_j$就好了。
考虑除去$min$。
注意到$a_i$是两个一次函数的合成，因此所求和式可以转换成求$\sum_{i=1}^x \sum_{j=1}^n min(i,a_j) \cdot v_j$
现在对$1$到$n$分类讨论。根据$i$和$a_j$的大小关系可以将$1$到$n$分成三块。
设$s_x=\sum_{i=1}^x i$
当$i \leq a_j$恒成立时，所求和式等价于$\sum_{i=1}^x \sum_j i \cdot v_j=s_x\sum_j v_j$
当$i \leq a_j$不恒成立时，所求和式为
因此只需要维护$\sum v_j , \, \sum a_jv_j, \, \sum(s_{a_j} - a_j^2)v_j$就好了。
时间复杂度$O(m \log n)$，常数大概在10左右，需要卡卡常…
CODE
BZOJ5291 - Click Here
BZOJ5292
Solutions考虑DP求解。
令$f(i)$表示剩余$i$血量的期望治疗量，$p_i$表示攻击到英雄$i$次的概率。显然有$f(0) = 0, \, p_i = \dbinom{k}{i} (\frac{1}{m+1})^i (\frac{m}{m+1})^{k-i}$
当$i < n$时，$f(i) = 1+\frac{1}{m+1}\sum_j p_{i+1-j}f(j) + \frac{m}{m+1} \sum_j p_{i-j}f(j)$
当$i=n$时，$f(i) = 1 + \sum_j p_{i-j}f(j)$
可以高斯消元求$f$，时间复杂度$O(Tn^3)$无法接受。
注意到每一个$i$最多只与$i+1$相关，因此由高到低消元就能消成上三角矩阵。
时间复杂度$O(Tn^2)$
CODE
BZOJ5292 - Click Here
BZOJ5293
Solutions签到题…
对每个节点求出到根的路径的$k$次方和，询问直接差分一下就好了…
CODE
BZOJ5293 - Click Here
BZOJ5294
Solutions这题细节极多…体验极差…
先考虑合法子串的性质。
注意到$2^i$对$3$取模是$0,1$往复循环的。因此如果子串含有偶数个1，必定满足条件。若子串含有奇数个1，那么可以利用同样的方法构造出余1的结果。现在考虑0带来的影响，若要使得最后调整为3的倍数，需要将余2的1移动到余1的位置，而这个操作必须至少存在2个0。
因此合法子串的性质是，含有偶数个1或含有奇数个1且0与1的个数均大于1。
个数大于1这个限制不好处理，考虑求不合法情况。即求满足含有奇数个1且0个数小于等于1或者含有1个1且0个数大于等于2的子串。
然后这东西显然可以线段树维护。在合并两个区间时，只需要考虑跨过边界的子串数。因此维护第一个0/1的位置，第二个0/1的位置，倒数第一个0/1的位置，倒数第二个0/1的位置就能计算合并贡献。
时间复杂度$O(m \log n)$
CODE
BZOJ5294 - Click Here
BZOJ5295
Solutions情况较多的结论题…体验极差*2…
令所有点的颜色集合相同，这样就变成了二分图染色。因此若图中存在奇环则不合法。
然后从$n=m-1$开始，逐渐加边讨论。
当$n=m-1$时显然YES，因为连通图变成了一棵树；当$n=m$时显然YES，图中只有一个偶环。
现在考虑$n=m+1$的情况。
首先注意到对于一个偶环，可以通过构造钦定某个点的颜色。因此如果两个偶环没交的话，答案为NO。
若两个偶环有交且非交部分长度>2，则可以通过同样的构造使得颜色冲突，答案为NO。
若两个偶环有交且非交部分长度=2。当相交长度>2时，则能看做是两偶环的并集与另一个偶环的相交问题，这样就转换成上一种情况，答案为NO；当相交长度=2时，不管怎么调整都会有存在非交部分长度=2的情况，此时因为长度的限制，无法钦定某个点的颜色，答案为YES。
当$n>m+1$时，可以看做是$n=m+1$加上若干条边的情况，利用上诉的推导可知答案为NO。
因此合法的连通图条件为，偶环个数不大于1或者偶环个数为2且其中一个环大小为4且含有2条公共边，跑一边DFS找出偶环判断即可。
时间复杂度$O(n)$
CODE
BZOJ5295 - Click Here