ZigZagK的博客
[思维+构造+倍增+exgcd]Codeforces1427E【Xum】题解
题目概述CF1427E解题报告神仙构造题,我又来翻译题解啦QAQ!如果 $(x,y)=1$ ,根据裴蜀定理,一定能求出两个正整数 $a$ 和 $b$ 使得 $ax-by=1$ ,而且如果 $ax...
[并查集]洛谷6786【GCDs & LCMs】题解
题目概述洛谷6786解题报告假设 $(b_i,b_j)=A,b_i=BA,b_j=CA(C>B)$ ,然后推式子:$$ BA+CA+A={BA\cdot CA\over A}\\ BA+C...
[离线+并查集按秩合并+平衡树启发式合并]Codeforces1417F【Graph and Queries】题解
题目概述CF1417F解题报告超级套路题……任意无向图删边是很麻烦的,所以肯定考虑离线转换成加边然后回退。加边就可以利用并查集来进行合并,考虑用set维护一个块的最大值,并查集合并的时候set启...
[离散+DFS+计数]AtCoder Regular Contest 104E【Random LIS】题解
题目概述AtCoder Regular Contest 104E解题报告这题还是挺可做的。我们发现 $n$ 小的一批,因此考虑离散。我们没必要对于每个 $i$ 都枚举 $1\to A_i$ ,对...
[容斥+计数]HHKB Programming Contest 2020 D【Squares】题解
题目概述HHKB Programming Contest 2020 D解题报告其实不难,就是烦的一批,考试的时候写复杂了然后调不出来。首先补集转化,我们求相交的数量,然后总数量减去相交的数量。为...
[构造]Codeforces1427D【Unshuffling a Deck】题解
题目概述CF1427D解题报告题目中疯狂暗示你做 $n$ 次,往这方面考虑就行了。假如我们现在已经有了连续的 $1,2,3,\cdots,k$ ,我们想要把 $k+1$ 加到 $k$ 后面一个,...
[DP]Codeforces1427C【The Hard Work of Paparazzi】题解
题目概述CF1427C解题报告我又被傻子题干翻了😭,首先 $O(n^2)$ DP非常好想,需要优化。由于保证了 $t_i<t_{i+1}$ ,所以当 $j+2(r-1)\le i$ 时,$...
[思维+贪心+最短路]Codeforces1407E【Egor in the Republic of Dagestan】题解
题目概述CF1407E解题报告这题好妙啊……如果正着做,那么一个城市的颜色决定了好多边,但是倒着做的话,一条边决定了一座城市的颜色,明显好考虑了很多。从 $n$ 出发做最短路,记录 $dis_{...
[思维+区间DP]AtCoder Regular Contest 104F【Visibility Sequence】题解
题目概述AtCoder Regular Contest 104F解题报告我又来翻译题解了😭。我们在最前面加上一个 $+\infty$ ,然后把 $P$ 中的 $-1$ 改成 $0$ ,那么不难发...
[计数+背包]AtCoder Regular Contest 104D【Multiset Mean】题解
题目概述AtCoder Regular Contest 104D解题报告对于每个 $x$ ,我们认为第 $i$ 个物品大小为 $x-i$ ,共有 $K$ 个,现在的问题就转化为有多少种方案,使得...