Day8~ Test

正睿OI

---

---

Day1

A

$Solution$
　　考虑两个数异或怎么会得到1：$0\oplus0=0，0\oplus1=1，1\oplus1=0$，也就是同一位的两个1会抵消成0。那么令$bit[x]$表示$x$的二进制1的个数，如果计算只奇偶性，$bit[x\oplus y]\%2=(bit[x]+bit[y])\%2$。因为如果有变成0的1也一定是两个一起变成0。那么如果令$p_0$表示区间$[l,r]$中$bit[i]$为偶数的$i$的个数，$p_1$表示区间中$bit[i]$为奇数的$i$的个数，该区间的答案为$p_0\times p_1$。
　　计算$p_0$，可以数位DP。$p_0[l,r]=p_0[r]-p_0[l-1]$，考虑$[0,m]$中的$p_0$怎么求。对于一个偶数$x$，$bit[x]$一定与$bit[x+1]$奇偶性相反。于是我们这样分组：$01,23,45\ldots$奇偶性是这样的：$偶奇,奇偶,奇偶,偶奇\ldots$可得：

$$p_0[0,m]=\begin{cases}\frac{m+1}{2},& m为奇数\\\frac{m}{2}+\left[bit[m]是奇数\right],& m为偶数\end{cases}$$
　　对于区间的处理，$O(n^2)$：把端点离散化，这样把所有区间分成了若干段小区间，每段区间是若干段小区间的并。这样每有一段区间，直接去找属于它的区间即可。如图：。
　　$O(n\log n)$：建一棵值域$1\sim2^{32}-1$的线段树，动态开点（能覆盖大区间就直接覆盖，否则递归新建左/右区间节点）。

B

$Solution$
　　

C

$Solution$
　　

Day2

A

$Solution$
　　计算覆盖的格子，如果不考虑交叉，单独算主对角线(向右斜的统称主对角线了)与副对角线(所有向左斜的)的话很容易。那先算出这个的答案。
　　考虑主次对角线交叉的部分，我们枚举每条次对角线，看它与哪些主对角线有交点，这是一个区间，那么好像可以二分。
　　而如果以x=y这条对角线为边界的话，确实可以二分两次来确定这个区间。
　　但是交点是指在格点上相交。这相当于两条直线的交点有整数解。但是可以发现每相邻两条副对角线，它们在格点上有交点的主对角线是正好互斥的。
　　再观察下，然后可以分奇偶性，求前缀和就行了。

　　但是不需要二分，因为我们可以O(1)计算出区间位置，然后前缀和。
　　分奇偶性的话前缀和从i-2转移就行了。把坐标系旋转45°找规律会更方便些。

B

$Solution$
　　有一个只有一条边有权值的部分分，对于某种位置分布情况，我们肯定是在这条边两侧尽量配对。
　　这样扩展到每一条边，如果它两边能配对，我们应尽量让两边的配对，多走这条边的路，即$dis$一定会增加。
　　那么我们可以对每一条边计算其贡献。$O(m^2)$枚举它一边男女生人数就可以得到所有情况。设它某一边连通块点数为$x$，则边$now$的贡献为：

$$w_{now}\times\sum_{i=0}^m\sum_{j=1}^m(\min(i,m-j)+\min(m-i,j))C_m^iC_m^jx^i(n-x)^{m-j}x^j(n-x)^{m-i}$$
　　把前面只与$i,j$有关的放到前面，枚举边： $$\sum_{i=0}^m\sum_{j=0}^m(\min(i,m-j)+\min(m-i,j))C_m^iC_m^j\sum_{edge}w_{edge}x^{i+j}(n-x)^{2m-(i+j)}$$
　　这样就只与$i+j$有关了，预处理所有边在$i+j$的贡献。复杂度$O(nm)$。

C

$Solution$
　　

Day3

A

$Solution$
　　

B

$Solution$
　　一个环删掉一段，剩下的一段也是连续的。它当中不含有相邻的相同字符。如果原串中存在相邻的相同字符，则在这里把环切开，最后会把环切若干段，合法的剩下的段显然是某一段的一部分。
　　然后判断在合法的段中是否有长$x$的合法长度（若存在，则删$n-x$个是可以的），即长$x$首尾字母不同的段。而再删一段后首尾字母相同就是一段前后缀相同。判断前后缀是否相同可以直接用KMP/Hash。如果有长为$l$的相同前后缀长度，则$n-l+1$位置是非法的。拆环为链每次只删后缀就是正确的了。
　　如果不存在相邻的相同字符，把整个串求一遍就行了。

C

$Solution$
　　

Day4

A

$Solution$
　　

B

$Solution$
　　$sp[x]=sum[x]-sum[lson]-sum[rson]$

C

$Solution$
　　

$$m=1:x^2+x^3+\cdots=x^2(1+x+x^2+\cdots)=\frac{x^2}{1-x}\\m>1:F[m-1](x)^2+F[m-1](x)^3+\cdots=\frac{F[m-1](x)^2}{1-F[m-1](x)}$$
　　
　　$f_i(j)=\sum_kf_{i-1}(k)\times[f_{i-1}(j-k)+f_i(j-k)]$
　　$f_i(z)=f_i*f_{i-1}+f_{i-1}^2$

Day5

A

$Solution$
　　

B

$Solution$
　　

C

$Solution$
　　

Day6

A

$Solution$
　　

B

$Solution$
　　

C

$Solution$
　　

Day7

A

$Solution$
　　

B

$Solution$
　　

C

$Solution$
　　

Day8

A

$Solution$
　　

B

$Solution$
　　

C

$Solution$
　　

Day9

A

$Solution$
　　

B

$Solution$
　　

C

$Solution$
　　

Day10

A

$Solution$
　　

B

$Solution$
　　

C

$Solution$