ZigZagK的博客
[思维+最短路]Codeforces1442C【Graph Transpositions】题解
题目概述CF1442解题报告首先有个基础想法:$dis_{i,j}$ 表示走到 $i$ ,反转了 $j$ 次的最短路,那么答案就是 $\min\{dis_{n,j}+2^j-1\}$ 。但是反转...
[主席树求区间mex]Codeforces1436E【Complicated Computations】题解
题目概述CF1436E解题报告呜呜呜,忘了区间mex可以用主席树做了QAQ。开 $n$ 个权值主席树,第 $i$ 棵树记录 $1\sim i$ 中 $x$ 最后一次出现的位置 $pos_x$ 。...
[数学]Codeforces1435E【Solo mid Oracle】题解
题目概述你有一种法术 $a,b,c,d$ ,在 $t$ 时刻使用时将对敌人造成 $a$ 伤害,但是在 $[t+1,t+c]$ 秒时敌人将每秒回复 $b$ 的血量,并且下一次释放时间至少是 $t+...
[扫描线+线段树]Codeforces1435C【Perform Easily】题解
题目概述CF1435C解题报告将 $a$ 排序,令 $B_{i,j}=b_i-a_j$ 。我们可以枚举 $x$ ,然后对于每个 $i$ 我们采用第一个 $\ge x$ 的 $B_{i,j}$ ,...
[计数]Codeforces1428F【Fruit Sequences】题解
题目概述CF1428F解题报告不是很难,但是要考虑的周全一些。对于一块连续的 $1$(假设区间是 $[L,R]$ ),我们枚举 $[L,i](i>L)$ 和 $[j,R](j<R)$...
[贪心+堆]Codeforces1428E【Carrots for Rabbits】题解
题目概述CF1428E解题报告这就是换了皮的贪心+堆套路题,但是我不会QAQ。设 $Count(x,k)$ 表示 $x$ 分成 $k$ 堆的最少时间,显然是分成 $k-x\bmod k$ 个 $...
[思维+最大生成树]Codeforces1408E【Avoid Rainbow Cycles】题解
题目概述CF1408E解题报告呜呜呜,这就是个沙雕题,但是我不会。如果多个集合之间的边组成了环说明就有彩虹路,但是显然我们不可能把一个集合中的所有边建出来。考虑建辅助点,自然而然我们想到对于每个...
[思维+构造+倍增+exgcd]Codeforces1427E【Xum】题解
题目概述CF1427E解题报告神仙构造题,我又来翻译题解啦QAQ!如果 $(x,y)=1$ ,根据裴蜀定理,一定能求出两个正整数 $a$ 和 $b$ 使得 $ax-by=1$ ,而且如果 $ax...
[离线+并查集按秩合并+平衡树启发式合并]Codeforces1417F【Graph and Queries】题解
题目概述CF1417F解题报告超级套路题……任意无向图删边是很麻烦的,所以肯定考虑离线转换成加边然后回退。加边就可以利用并查集来进行合并,考虑用set维护一个块的最大值,并查集合并的时候set启...
[构造]Codeforces1427D【Unshuffling a Deck】题解
题目概述CF1427D解题报告题目中疯狂暗示你做 $n$ 次,往这方面考虑就行了。假如我们现在已经有了连续的 $1,2,3,\cdots,k$ ,我们想要把 $k+1$ 加到 $k$ 后面一个,...