ZigZagK的博客
[构造]Codeforces1028E【Restore Array】题解
题目概述有一个序列 $\{a_n\}$ ,令 $\{b_i=a_i\ mod\ a_{i\ mod\ n+1}\}$ ,现在给出 $\{b_n\}$ ,求出一组可行的 $\{a_n\}$ 。解题...
[计数]Codeforces1028D【Order book】题解
题目概述有 $n$ 次操作,每次操作可以:1.加入一个A/B类型值为 $p$ 的元素(保证 $p$ 互不相同)。2.删去值为 $p$ 的元素,保证之前出现过。同时保证每次所有加入的A类型的元素均...
[two-pointer+线段树]BZOJ4653(Noi2016)【区间】题解
题目概述有 $n$ 个区间,求取 $m$ 个区间使得交不为空时的最小 $max\{len\}-min\{len\}$ 。解题报告我不会做题啦……很显然区间越多交越小而且解也不会优,所以可以按照长...
[DP]Codeforces1013E【Hills】题解
题目概述$x$ 轴上按顺序有 $n$ 座山,每座山有海拔 $h_i$ ,如果一座山比周围两个山高就可以建房子。可以花费 $1$ 的代价把山铲去 $1$ 的海拔,问建 $1\sim\lceil{n...
[思维+并查集]Codeforces1013D【Chemical table】题解
题目概述如果存在 $(r_1,c_1),(r_2,c_2),(r_2,c_1),r_1\not=r_2,c_1\not=c_2$ 那么就可以不消耗费用添加 $(r_2,c_2)$ 。现在 $n\...
Codeforces Contest & Virtual Participation合集
场次编号完成状态题解Codeforces Round #721 (Div. 2)1527QwQBEducational Codeforces Round 10614995/7ECodeforce...
[期望DP+高斯消元+复杂度分析]Codeforces963E【Circles of Waiting】题解
题目概述从原点出发,每次往上下左右走都有一定的概率,问第一次走到离原点距离超过 $R$ 的点的期望步数。解题报告很显然可以期望DP,令距离超过 $R$ 但最接近原点的一圈的 $f_{x,y}=0...
[计数]Codeforces963C【Cutting Rectangle】题解
题目概述有 $n$ 种小矩形,第 $i$ 种小矩形长为 $w_i$ 宽为 $h_i$ ,有 $c_i$ 个,问有多少种 $(A,B)$ 使得存在一种切割方案将其切割为所有小矩形。解题报告神仙计数...
[离线+AC自动机+复杂度分析]Codeforces963D【Frequency of String】题解
题目概述有一个文本串,现在有 $m$ 个模板串(互不相同),问文本串中长度最小的子串使得模板串出现了 $k_i$ 次。解题报告$m$ 个模板串互不相同奥妙重重,令 $M=\sum Length(...
[几何+计数]Codeforces1025F【Disjoint Triangles】题解
题目概述有 $n$ 个点,选出 $6$ 个点使得能够组成两个不相交的三角形,求方案数。解题报告几何神题,可以证明两个不相交的三角形之间恰好有两条切线(画了几个好像没什么毛病,反正我不会证明),所...