[思维+构造+倍增+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$ 个，现在的问题就转化为有多少种方案，使得...
