2020-2021:teams:farmer_john:2sozx:educational_codeforces_round_87_rated_for_div_2
A
- 题意:小水题。
- 题解:水水水。
B
- 题意:给定一个由$123$组成的字符串，求最短的包含$123$的子串。
- 题解:记录每个位置的后继是啥，然后枚举开头是哪个数字，然后往后搜就行。
C
- 题意:给定一个正$2n$边形，求覆盖这个正多边形的最小正方形。
- 题解:$n$是偶数的时候很简单，画个图只需要补全就可以。$n$是奇数的时候考虑猜答案，显然一定会有两个点在对角线上，然后可以枚举其余的点在正方形边长上时的正方形边长，取最大值即可。
D
- 题意:数据结构，插入和删除第$k$小。
- 题解:树状数组。
E
- 题意:$n$个点$m$条边的图，有$n_1, n_2, n_3$ 个 $1,2,3$，将他们放到每个点上，要求每条边相连的两个点权值相差绝对值$1$，问是否有解，如果有解则输出。$(1 \le n \le 5000, 0 \le m \le 10^5, n_1 + n_2 + n_3 = n)$
- 题解:$1$和$3$不能有边，因此可以合并为一类，转化为二分图染色+背包判断。因为要输出方案，所以背包dp的时候记录一下当前的染色是否要翻转，最后从 $1$ 到 $n$ 扫一遍输出值即可。
F
- 题意:
- 题解:
G
- 题意:摸了
- 题解:也摸了
2020-2021/teams/farmer_john/2sozx/educational_codeforces_round_87_rated_for_div_2.txt · 最后更改: 2020/06/01 12:01 由 2sozx
