「Summary」2022-08-08 做题记录

二分图？？？

2022-08-08

$\mathbb{CF613C}$

这个是二分图！？

分类讨论即可，如果没有奇数或有一个奇数，则 $ans = \gcd \{a \}$ ，否则 $ans = 0$ 。

$\mathbb{CF1009G}$

乱贪心被制裁了

一个看起来很对的贪心，从后往前，从小往大贪心，想当然的会认为，当前面的数需要更小的匹配时，可以让后面的数让出来，然而并不是这样，手玩样例就会发现出错。
考虑正着做，还是贪心，如果当前位能够选更小的就选更小的，因为右部点的点集很小，可以状压，统计后缀和，只要后面的数还能选就行。

$\mathbb{CF808F}$

我不会读题

这个和上周的 abc 很相似啊。
将两个相加为质数的点连边跑最小割，奇数的一边连源点，偶数的一边连汇点，特判 $1$ 就行了。

$\mathbb{CF687D}$

写复杂了

这个可以考虑直接二分答案，那么距离相隔大于 $mid$ 的两个点都不可能属于同一个点集，可以染色判定是否为二分图。
考虑第二问，其实一个连通块中的左右两部的点可以互换，则统计联通块个数就行了。其实 $dfs$ 时直接就处理了，结果我脑抽写了个并查集。

$\mathbb{CF741C}$

有意思

瓶颈在于不好处理相邻的 $3$ 个人的食物不同。
其实相当于 $2 \times i$ 和 $2 \times i - 1$ 不同。
连边跑二分图染色就可以了。