Atcoder Grand Contest 039 B,C,D,E,F

我的提交记录

---

B - Graph Partition

当图中存在奇环的时候显然无解（可以考虑$x,y$x,y之间存在边意味着$x$x与$y$y所属的点集的下标奇偶性不同），否则一定有解。

如果存在划分成$k$k个集合的方案，那么图中必定存在两个点，它们之间的最短路径的边数是$k-1$k−1。设$dis(x,y)$dis(x,y)表示$x,y$x,y之间的最短路的边数，$1+\max_{x,y}\{dis(x,y)\}$1+maxx,y​{dis(x,y)}显然是答案的一个上界。

而这个上界是可以达到的。假设$dis(x,y)$dis(x,y)最大，我们把到$x$x的最短路长度等于$l$l的点分入集合$V_{l+1}$Vl+1​，就可以得到合法的方案。

---

C - Division by Two with Something

题目中的操作相当于删去二进制最低位，然后把删去的位取反放在最高位之前。

对于任意的一个数$X$X，它在$2N$2N次操作之后都必然会变成它本身。所以，倘若$X$X在$d$d次操作之后变成了它本身，那么$X$X在$\gcd(d,2N)$gcd(d,2N)次操作后一定也变回了它本身。所以，$X$X的最小操作次数一定是$2N$2N的约数。

观察发现，对于某一个$d\mid 2N$d∣2N，如果$X$X在$d$d次操作之后变回了本身，那么$X$X一定由$\frac{2N}{d}$d2N​段组成，$\frac{2N}{d}$d2N​是奇数，且$X$X有如下的形式：$AA'AA'\cdots A$AA′AA′⋯A，其中$A$A是一个长度为$d\over 2$2d​的$01$01串，$A'$A′表示$A$A把每一位取反之后得到的结果。

枚举所有的满足$d\mid N$d∣N且$N\over d$dN​是奇数的$d$d，然后计算$2d$2d次操作之后变回本身的数的个数（不要求$d$d是最小操作次数），再通过容斥原理就可以算出$2d$2d为最小操作次数的数的个数。

如何判断一个$AA'AA'\cdots A$AA′AA′⋯A是否小于等于题目给出的$X$X？先比较前$|A|$∣A∣位，如果不相同就可以确定$A,X$A,X的大小关系；否则，由于和$X$X的前$|A|$∣A∣位都相同的$A$A只有一个，可以暴力$O(|X|)$O(∣X∣)判断。拓展到对$AA'AA'\cdots A$AA′AA′⋯A的计数就是：枚举$A$A与$X$X不同的最高位是哪一位，之后的位可以随意取，并特殊判断$X$X的前$|A|$∣A∣位和$A$A完全相同的情况。

---

D - Incenters

对于某一个$\triangle_{ABC}$△ABC​，我们作出$\overset{\Large\frown}{AB},\overset{\Large\frown}{BC},\overset{\Large\frown}{CA}$AB⌢,BC⌢,CA⌢的中点$C',A',B'$C′,A′,B′。则有$\triangle_{ABC}$△ABC​的内心与$\triangle_{A'B'C'}$△A′B′C′​的垂心重合。

证明：

显然$AA',CC',BB'$AA′,CC′,BB′是$\triangle_{ABC}$△ABC​的内角平分线，所以$\gamma={1\over 2}\angle ABC,\alpha = {1\over 2}\angle BCA, \beta=\sigma ={1\over 2}\angle BAC$γ=21​∠ABC,α=21​∠BCA,β=σ=21​∠BAC。

而$\varepsilon = \beta + \gamma + \alpha = {1\over 2}(\angle ABC + \angle BCA +\angle CAB) = 90^\circ$ε=β+γ+α=21​(∠ABC+∠BCA+∠CAB)=90∘，所以$BB'\bot C'A'$BB′⊥C′A′。

同理可证明$CC'\perp A'B',AA'\perp C'B'$CC′⊥A′B′,AA′⊥C′B′。所以$AA',BB',CC'$AA′,BB′,CC′的交点为$\triangle_{A'B'C'}$△A′B′C′​的垂心。

所以只需要算出$\triangle_{A'B'C'}$△A′B′C′​的垂心的期望即可。

令$\triangle_{A'B'C'}$△A′B′C′​的外心为$O$O，重心为$G$G，垂心为$H$H，根据欧拉线我们有$G = {2O+H\over 3}$G=32O+H​（将点看做向量进行的加减乘除），也就是$H = 3G - 2O$H=3G−2O。由于$O=(0,0),G={A'+B'+C'\over 3}$O=(0,0),G=3A′+B′+C′​，只要考虑每一个$A'$A′的贡献就可以得到答案。

时间复杂度$O(n^2)$O(n2)。

---

E - Pairing Points

一个写得很好的博客

首先枚举与$1$1配对的点，然后把$1$1所在的线段删掉（图中虚线标出的），然后考虑那些与$1$1所在的线段有交的线段（图中粗的黑线），发现剩下的的点一定恰好只与这些线段中的一条连通，并且与每一条线段连通的点集一定是两个连续的区间的并。

设$g[a][b][c][d]$g[a][b][c][d]表示把$[a,b]\cup[c,d]$[a,b]∪[c,d]中的点连成一个连通块，并且要求有且仅有一条边的两端在两个区间内。为了辅助转移，再设$f[a][b][c][d] = \sum_{a\le x<b,c<y\le d}g[a][x][y][d]\cdot f[x+1][b][c][y-1]$f[a][b][c][d]=∑a≤x<b,c<y≤d​g[a][x][y][d]⋅f[x+1][b][c][y−1]，表示$[a,b]\cup [c,d]$[a,b]∪[c,d]为若干个合法的连通块“首尾”相邻拼起来的方案数。

考虑$g$g的转移（如下图）：我们枚举跨越两个区间的边$(x,y)$(x,y)，则$[a,x-1]\cup [x+1,b]$[a,x−1]∪[x+1,b]和$[c,y-1]\cup [y+1,d]$[c,y−1]∪[y+1,d]成为了两个互相独立的子问题，并且要求$[a,x-1]\cup [x+1,b]$[a,x−1]∪[x+1,b]划分成若干个合法的连通块，$[c,y-1]\cup [y+1,d]$[c,y−1]∪[y+1,d]划分成若干个合法的连通块：这就是$f[a][b][c][d]$f[a][b][c][d]的定义。所以我们得到

$g[a][b][c][d]=\sum_{a\le x\le b,c\le y\le d} f[a][x-1][x+1][b] \cdot f[c][y-1][y+1][d]$g[a][b][c][d]=a≤x≤b,c≤y≤d∑​f[a][x−1][x+1][b]⋅f[c][y−1][y+1][d]

最后的答案就是$\sum_i f[2][i-1][i+1][2n]$∑i​f[2][i−1][i+1][2n]。

时间复杂度$O(n^6)$O(n6)

---

F - Min Product Sum

考虑题目中给出的权值的组合意义：相当于对于一个确定的矩阵$A$A和一个还没有确定的矩阵$B$B，$A$A的权值等于有多少种往$B$B中填数的方案，使得$B_{i,j}$Bi,j​不大于$A$A中与它在同行或者同列的任何一个数。

而这个填数的条件等价于：对于每一行，$B$B的最大值小于等于$A$A的最小值；对于每一列，$B$B的最大值小于等于$A$A的最小值。

枚举每一列$A$A的最小值$Y_i$Yi​，并要求这一列的$B$B的所有元素都不超过它；枚举每一行$B$B的最大值$X_i$Xi​，并要求这一行的$A$A的元素都不小于它。这与前面的条件仍然是等价的。

对于某一个格子$A_{i,j}$Ai,j​，如果$X_i>Y_j$Xi​>Yj​，就在枚举$X_i$Xi​的时候考虑它的贡献；如果$X_i<Y_j$Xi​<Yj​，就在枚举$Y_j$Yj​的时候考虑它的贡献；如果$X_i=Y_j$Xi​=Yj​，我们规定在枚举$Y_j$Yj​的时候考虑它的贡献。对于某一个格子$B_{i,j}$Bi,j​，如果$X_i\le Y_j$Xi​≤Yj​，就在枚举$X_i$Xi​的时候考虑它的贡献，否则就在枚举$Y_j$Yj​的时候考虑它的贡献。

我们先将行按照$X_i$Xi​排序，列按照$Y_i$Yi​排序。枚举每一个$X_i$Xi​的时候，需要考虑贡献的格子就会有如下的形式（并且右侧的格子每一行要求至少有一个元素取到最大值）：

枚举每一个$Y_i$Yi​的时候，需要考虑的格子有如下的形式（左侧的格子每一列要求至少有一个元素取到最小值）：

发现：

• 枚举每一个$X_i$Xi​的时候，需要考虑的格子的总数量是$m$m；枚举每一个$Y_i$Yi​的时候，需要考虑的格子的总数量是$n$n。
• 枚举每一个$X_i$Xi​的时候，$A$A中需要考虑的格子的数量等于$Y_j$Yj​中满足$Y_j < X_i$Yj​<Xi​的$j$j的数量；枚举每一个$Y_i$Yi​的时候，$A$A中需要考虑的数量等于满足$X_j\le Y_i$Xj​≤Yi​的$j$j的数量。

设$f[t][i][j][0]$f[t][i][j][0]表示$X_1,X_2,\cdots X_i$X1​,X2​,⋯Xi​，$Y_1,Y_2\cdots Y_j$Y1​,Y2​⋯Yj​已经确定，且$X_i< t, Y_j< t$Xi​<t,Yj​<t的方案数；$f[t][i][j][1]$f[t][i][j][1]表示$X_1,X_2,\cdots X_i$X1​,X2​,⋯Xi​，$Y_1,Y_2\cdots Y_j$Y1​,Y2​⋯Yj​已经确定，且$X_i\le t, Y_j < t$Xi​≤t,Yj​<t的方案数。对$f[t][i][j][0]$f[t][i][j][0]，枚举$X_i=t$Xi​=t的行数进行转移；对$f[t][i][j][1]$f[t][i][j][1]，枚举$Y_j=t$Yj​=t的列数进行转移。

总时间复杂度$O(nmk(n+m))$O(nmk(n+m))。