ZigZagK的博客
[莫比乌斯函数+数学]Codeforces1139D【Steps to One】题解
题目概述CF1139D解题报告这是2021天梯赛L3-3的弱化版,吉老师加强版又要杜教筛又要快速乘,懒得写了XD。直接推式子( $1\over n$ 是长度为 $1$ 的情况,需要单独处理):$...
[思维+DP]XXI Opencup GP of Tokyo B【Bit Operation】题解
题目概述CF GYM 102978B解题报告不难发现 $0$ 和 $1$ 执行and和or操作时,相当于把其中一个元素删掉了。而 $00$ 之间或者 $11$ 之间执行and和or操作时,也可以...
[DP]Codeforces1499E【Chaotic Merge】题解
题目概述CF1499E解题报告这道题想法不难,但是实现的时候很注重细节。首先我们考虑DP $f_{i,j,0/1}$ 表示第一个字符串取到了 $i$ ,第二个字符串取到了 $j$ ,且最后一个取...
[分块+复杂度分析]Codeforces1491H【Yuezheng Ling and Dynamic Tree】题解
题目概述CF1491H解题报告这么诡异的操作,考虑分块。每个元素记录 $last_i$ 表示 $i$ 往前跳,最后一个没有跳出 $i$ 所在块的位置。查询的时候,先将 $x$ 和 $y$ 跳到 ...
[Kruskal重构树+树状数组套线段树]EOJ4120【雨(yù)雪霏霏】题解
题目概述EOJ4120解题报告本题难点就在于快速选出海拔 $\le L$ 的连通块,可以利用Kruskal重构树:网格按照海拔从小到大考虑对于 $(x,y)$ ,向相邻海拔低的网格连边,注意连边...
[线段树维护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)$ 。然...
2020 CCPC 长春站 部分题解
F. Strange Memory呜呜呜,想了半天怎么快速处理这个 $i\ \mathbb{xor}\ j$ ,之后发现其实根本没有好的处理方法,只能拆位计算贡献。考虑第 $B$ 位的贡献,那么...