ZigZagK的博客
[线段树维护DP]Codeforces1479B【Painting the Array】题解
题目概述CF1479B1 & CF1479B2解题报告在本算法下,B1和B2其实没有很大区别,所以下面仅讨论最小值。定义 $f_{i,0/1,x}$ 表示 $i$ 放了 $0/1$ 颜色,并且另...
[二分]Codeforces1479A【Searching Local Minimum】题解
题目概述CF1479A解题报告如果 $a_i<a_{i+1}$ 则称 $i$ 为上点,否则称 $i$ 为下点。首先如果 $1$ 是上点,或者 $n-1$ 是下点,那么 $1$ 或 $n-1...
[几何+思维]Codeforces1477C【Nezzar and Nice Beatmap】题解
题目概述CF1477C解题报告呜呜呜,几何学太差了,根本不会。三角形大边对大角,所以最小边一定是锐角。随便选一个点开始走,每次选距离最远的,那么夹角一定是锐角。示例程序#include<c...
[拓扑]Codeforces1476E【Pattern Matching】题解
题目概述CF1476E解题报告如果用模式串来匹配给出的串,复杂度显然炸了。但是我们发现,字符串长度很短,所以如果用给出的串来匹配模式串(枚举哪些位置改成_),复杂度就只有 $O(2^4)$ 。然...
[贪心]Codeforces1464B【Grime Zoo】题解
题目概述CF1464B解题报告我太菜了,这种题的思路其实挺经典的。考虑相邻两个?之间的情况,假设他们之间有 $s_0$ 个 $0$ 和 $s_1$ 个 $1$ :第一个放 $0$ 第二个放 $1...
[DP]Codeforces1453F【Even Harder】题解
题目概述CF1453F解题报告考虑路径计数 $cnt_i=\sum_{j=1}^{i-1}[j+a_j\ge i]cnt_j$ ,如果想要 $cnt_n=1$ ,那么一定不存在一个 $cnt_i...
[背包+构造]Codeforces1444D【Rectangular Polyline】题解
题目概述CF1444D解题报告这题演我啊,我看三个 $1000$ 以为有什么高级的分半算法,结果写背包能过QAQ。首先显然 $h\not=v$ 时无解,然后我们需要把水平线段和竖直线段都拆成两半...
[思维+DP]Codeforces1446C【Xor Tree】题解
题目概述CF1446C解题报告画下Trie树,不难发现如果一个节点 $0$ 子树中只有一个元素,$1$ 子树中只有一个元素,那么这两个元素就会形成重边。由于题目要求形成一棵树,因此重边必须有且只...
[并查集按秩合并]Codeforces1444C【Team-Building】题解
题目概述CF1444C解题报告首先我们对于每个相同颜色的块,求出是否存在奇环,如果存在那么这种颜色显然不能选。排除了不能选的颜色之后,我们发现只有有边相连的两种颜色才有可能违法,因此会违法的颜色...
[思维]Codeforces1442B【Identify the Operations】题解
题目概述CF1442B解题报告定义一个新数组 $A_i$ 表示 $b_i$ 在 $\{a_n\}$ 中的下标,然后将 $\{a_n\}$ 递增排序,问题转化为在 $\{a_n\}$ 中选出 $A...