Day3 B
题意
\((n + 1)\times (m +1)\) 的矩阵，初始全为白色，给定 \(p_{i,j},q_{i,j}\)，分别代表从将第 \(i\) 行最左边 \(j\) 个染黑的概率，和第 \(i\) 列最上边 \(j\) 个染黑的概率，求同色联通块的概率
\(1\leq n,m\leq10^3\)
题解
观察发现，所有黑色块全部联通，只需考虑白色块。
对于白色块，有每个有有唯一的右下角，计数右下角的期望数即为连通块的期望数
Day3 C
题意
给定 \(n,m\)，构造 \(n\times m\) 的 01 矩阵 ，使得每行每列互不相同，且 01 个数各占一半。
\(n,m\leq10^3\)
做法
不妨令 \(n\leq m\)，首先有若 \(n,m\) 同时为奇数时无解，否则，若 \(n\) 为奇数，\(m\) 一定为偶数，将前 \(n-1\) 列用只有一个 0 和只有一个 1 交错填，可以区分所有行，并且满足 01 各一半，然后对于剩下的部分，可以直接列完全相反的一组一组填即可
当 \(n\) 为偶数时，类似于之前的构造，注意一下不一样的情况
Day3 D
题意
给定 \(n\) 个点 \(m\) 条边的有向图，每条边有黑白两种颜色，\(q\) 次询问，每次给定 \(a,b,x\) 求若黑白边长分别为 \(a,b\)，从 \(1\) 到 \(x\) 的最短路径是多长
\(n,q\leq5\times10^4,m\leq10^5,1\leq v-u\leq1000\)
做法
若能维护出每个点的凸包，就可以每次询问快速求解。
对于整点凸包，有结论凸包大小是 \(O(n^{\frac23})\) 的，由此可以直接暴力求解凸包，复杂度为 \(O(m^{\frac53}+q\log n)\)。
Day3 K
题意
给定长为 \(n\) 的数组 \(a\)，每次可以选定一个位置 \(i\) 和一个数 \(x\)，使得 \(a_i=a_i\mod x\) ，求最后全数列 \(GCD\) 的最大值是多少。
\(n\leq10^5\)
做法
每个数 \(x\) 可以变为 \(\lfloor \frac{x+1}{2}\rfloor - 1\)。将 \(a\) 升序排序后，容易发现答案只有可能是 \(a_1,\frac{a_1}{2},\lfloor\frac{a_1+1}{2}\rfloor-1\) 中的一个，逐个验证即可。