算法组月赛视频讲解

▶ 点击查看讲解视频

T1：矩形面积

解题思路:

1. $60pts$ 开一个 $100\times100$ 的数组，使用数组标记，记录每个位置被多少个矩形覆盖了，记录被三个矩形覆盖的个数即可。
2. $100pts$ 三个矩形的交集最后一定也是一个矩形，考虑这个矩形的左下角，其横坐标一定是三个矩形左下角横坐标的最大值，其纵坐标一定是三个矩形左下角横坐标的最大值，右上角同理为最小值，知道左下角和右 上角即可计算出矩形的面积，注意判定交集为空的情况。

T2：三倍数

解题思路:

1. 若 $M=10^6$，则答案为 $99$

   $∵ 99|99|99 \le 100|00|00$

2. 若 $M$ 的位数 $|M|$ 满足 $|M|=3n+r,0\le r< 3$，则答案为 $\underbrace{99..99}_{n个9}$

   $∵ 1|1|1,2|2|2,3|3|3,...,\underbrace{99..99}_{n个9}$$|\underbrace{99..99}_{n个9}$$|\underbrace{99..99}_{n个9}$

3. 若 $|M|$ 为 $3$ 的整倍数，则可将其写为 $M_1M_2M_3$ 的形式。若 $M_1<M_2$ 或 $M_1=M_2,M_2\le M_3$，则答案为 $M_1$；否则答案应为 $M_1-1$

需要使用高精度减法从而实现 -1，但无需完整的高精度运算，仅需实现好退位，借位即可。

T3：魔法

解题思路:

$dp[i][j]$：走到第 $i$ 行第 $j$ 列最少要区间翻转几次。

当前点如果是 . ，那么这个点本身不用翻转，翻转次数等于上一个点。

如果当前点是 # ，那么这个点本身需要翻转，如果上一个点也要翻转，那么这个点可以和上一个点在同一个区间里翻转即可。翻转次数也等于上一个点。

如果不是上面两种情况，就为上一个点加 $1$。

T4：“与”路

解题思路:

二进制运算常考虑按位贪心的思路。

先考虑较简单的情况，如有 $2^k>V$，我们将所有 $w_i\&2^k=2^k$ 的边取出，判断此时 $u,v$ 是否联通，若已联通则答案为 $yes$；否则再把 $w_i\&V=V$ 的边取出继续判断是否联通。

正解为从高到低枚举位数 $k$，并设一个 $now$ 表示当前的目标权重。每次枚举先将 $now=now+ 2^k$，如果 $V$ 的当前第 $k$ 位为 $0$，则将所有 $w_i\&now=now$ 的边拿出进行并查集的连通性判断（使用这些边最后按位与的结果一定 $\gt V$），并将 $now$ 恢复。

最后再判断一下所有 $w_i\&V=V$ 的边能否联通即可。

复杂度：$O((m+q)logVlogn)$