提高模拟赛题解

图

对于一张颜色已知的图，为了最大化图的边数，我们会在不同颜色的点之间连上一条边。

边数为（ $m$ 为颜色总数， $gs[i]$ 是颜色为 $i$ 的点数）: $C(n,2)- \sum_{i=1}^{m}{C(gs[i],2)}$

30分:

枚举每个点选什么颜色，然后计算一下边数。时间复杂度 $O(m*C(n,m))$

明显 $gs[i]$ 平均分最优。

$C(n,2)-(n \ mod \ m) \times C(\lceil \frac{n}{m} \rceil ,2) - (n \ mod \ m) \times C(\lfloor \frac{n}{m} \rfloor ,2)$

60分:

枚举m，然后计算上述式子。时间复杂度 $O(m)$

100分:

发现 $\frac{n}{m}$ 可以除法分块，对于上取整和下取整分开来计算即可。

然后就是除法分块裸题。

位运算

30分:

枚举 $i$ ，然后 $lowbit$ 计算二进制下 $1$ 的个数。

或先预处理出 $F[]$ ， $F[i]$ 表示 $i$ 在二进制下 $1$ 的个数。时间复杂度 $O(n)$

不用 $lowbit$ 计算的话可能被卡。

60分

在30分的基础上分段打表，时间复杂度 $O(\sqrt{n})$ 。

先考虑一下 $L=1$ , $R=2^k$ 的情况。发现答案相当于是有 $k$ 位可以随意选的和加上 $R$ 。

$K$ 位可以随便选，考虑 $DP$ 。

我们可以先枚举二进制中 $1$ 的个数是 $bit$ 。主要是要想到 $\lfloor \frac{x}{bit} \rfloor$ 能怎么分割，发现只要记录一下余数即可，就是余数 $>=bit$ 了就加 $1$ 。然后就是一个很自然的 $DP$ ， $F[i][j][k]$ 表示前 $i$ 位，选了 $j$ 位，余数是 $k$ 的方案数。 $G[i][j][k]$ 表示前 $i$ 位，选了 $j$ 位，余数是k的答案。

            int x=(Pow[i]/bit)%mod,y=Pow[i]%bit;
            if(y+k>=bit)
            {
                Add(f[i+1][j+1][y+k-bit],f[i][j][k]);
                Add(g[i+1][j+1][y+k-bit],g[i][j][k]);
                Add(g[i+1][j+1][y+k-bit],f[i][j][k]*(x+1));
            }
            else{
                Add(f[i+1][j+1][y+k],f[i][j][k]);
                Add(g[i+1][j+1][y+k],g[i][j][k]);
                Add(g[i+1][j+1][y+k],f[i][j][k]*x);                
            }
            Add(f[i+1][j][k],f[i][j][k]);
            Add(g[i+1][j][k],g[i][j][k]);

80分:

如果不是 $2^k$ 的情况的话还要考虑压着限制的情况，可以强制前几位压着限制再做 $DP$ ，复杂度 $logn^5$ 。

100分:

在80分的情况下，发现 $DP$ 是几乎一样的，就是不需要每次都因为强制了一些数就重新 $DP$ ，完全可以和起来一起算。时间复杂度 $logn^4$ 。

树

10分:

先预处理出每个点对的距离。然后枚举点对，计算答案。
时间复杂度 $O(n^3)$

30分:

两种方法

枚举点对，倍增找到分割点，然后分类讨论一下，细节较多，需要预处理的东西也多。时间复杂度 $O(n^2 logn)$
需要稍微转化一下题目，其实就是删掉一条边，求两部分的带权重心值的和。
带权重心有两种做法。一种就是换根DP。另一种就是考虑每条边的贡献，就是 $\sum_{(u,v)\subseteq E}{w_i \times min(size[v],S-size[v])}$ ，这里的 $size[]$ 是指点权和， $S$ 为所有点的点权和， $wi为边权$ 。

50分:

菊花。
有两种情况，

有一个点在中间，那么另一个点就是 $w_i \times val_i$ 最大的点。
按照 $w_i$ 排序，枚举一个点(假设边权为 $W$ )，强制另一点的边权要 $>=W$ ,那么另一个点就是 $(w_i+W)\times val_i$ 最大的点。

70分:

链。
考虑30分的考虑每条边贡献的做法。线段树维护 $w$ 和 $w \times size$ 。然后就可以枚举断哪条边，对两部分求一下 $\sum_{(u,v)\subseteq E}{w_i \times min(size[v],S-size[v])}$ 。就是对于 $2 \times size<=S$ 的求 $\sum_{}w \times size$ ，对于 $2 \times size>S$ 的求 $\sum_{}w \times S-\sum_{}w \times size$ 。

100分:

在70分的情况下，考虑断掉树上的一条边 $(u,v)$ 会怎么样。发现除了 $u$ 到根路径上的边，其余边的 $size[x]$ 都没改变，仍能用70分的做法求。但到根路径上的边 $size[x]$ 变成了 $size[x]-size[v]$ 。 $\sum_{}{w_i \times min(size[x]-size[v],S-size[x])}$ ，分成 $2 \times size[x]<=S-size[v]$ 和 $2 \times size[x]>S-size[v]$ 两部分来求解。用线段树维护 $w$ 和 $w \times 2 \times size$ ，即可。