T1 区间 [贪心]
Description
给定 \(n\) 个正整数区间，从左往右进行 \(n - 1\) 次操作，每次可以将相邻两个区间取交集或并集。
要求至少有 \(m\) 次取交集操作。
求操作后最大的区间长度。
Solution
考虑三个集合 \(A，B，C\)，显然 \(card(A\cap B\cup C)\) 一定不劣于 \(card(A\cup B\cap C)\)，
因此我们贪心地把 \(m\) 次交集操作放在前面，后面全部取并集即可。
T2 旅行 [图论]
Description
给定 \(n\) 个节点，\(m\) 条边的有向图，可以任选一个点，遍历尽量多的点，并最终回到这个点，中途可以经过起点。遍历的点的数量被称为指数。
至多新增一条边，只能是原图边的反向边，但可以和原边相同。求新增边后指数的最大值，新增哪些边的反向边能达到这个最大值。
\(n\le 2\times 10^3\)，\(m\le 4\times 10^4\)。
Solution
根据数据范围，我们可以 \(O(nm)\) 预处理出每个点可以到达哪些点。
接着枚举每一条边 \((u,v)\)，假设要添加它的反向边，那么我们再枚举中心点 \(k\)，计算有多少个 \(k\) 使得 \(u\) 可以到达 \(k\) 且 \(k\) 可以到达 \(v\)。
取最大值即可。
T3 棋盘染色 [组合数学]
Description
给定一个 \(2\times N\) 的棋盘，将棋盘染成三种颜色红、绿、蓝。
一个棋盘是漂亮的，当且仅当：
- 任意两个相邻的格子颜色不同；
- 任意一个 \(2\times 2\) 的网格里，每一种颜色都至少出现了一次。
求有多少个漂亮的棋盘恰好有 \(R\) 个红色格子，\(G\) 个绿色格子和 \(B\) 个蓝色格子。对 \(10^9+7\) 取模。