ZigZagK的博客
[Splay维护序列]Codeforces GYM103145F【Permutation】题解
题目概述CF GYM103145F解题报告其实两个反转操作是独立的,我们可以用两棵Splay来维护位置的序列(A树)以及数值的序列(B树)。每次询问位置 $i$ 的时候,我们先找到 $i$ 位置...
[思维]Codeforces1527B【Palindrome Game】题解
题目概述CF1527B解题报告我来翻译题解啦!由于不是回文串的时候才能进行操作2,所以我们可以认为操作2是执行一次“啥都不干”。如果 $s$ 是回文串(B1):如果 $n$ 是偶数:Bob必胜,...
[思维+DP]XXI Opencup GP of Tokyo B【Bit Operation】题解
题目概述CF GYM 102978B解题报告不难发现 $0$ 和 $1$ 执行and和or操作时,相当于把其中一个元素删掉了。而 $00$ 之间或者 $11$ 之间执行and和or操作时,也可以...
[几何+思维]Codeforces1477C【Nezzar and Nice Beatmap】题解
题目概述CF1477C解题报告呜呜呜,几何学太差了,根本不会。三角形大边对大角,所以最小边一定是锐角。随便选一个点开始走,每次选距离最远的,那么夹角一定是锐角。示例程序#include<c...
[思维+二分+ST表]2020-2021 ACM-ICPC Brazil Subregional Programming Contest M【Machine Gun】题解
题目概述CF GYM 102861M解题报告首先要仔细读题,题目保证了覆盖的点的个数总和不超过 $10^6$ ,因此只需要想办法快速找到被覆盖的点就行了。如果按照题目里的说法很难快速查找,因此我...
[思维+DP]Codeforces1446C【Xor Tree】题解
题目概述CF1446C解题报告画下Trie树,不难发现如果一个节点 $0$ 子树中只有一个元素,$1$ 子树中只有一个元素,那么这两个元素就会形成重边。由于题目要求形成一棵树,因此重边必须有且只...
[思维]Codeforces1442B【Identify the Operations】题解
题目概述CF1442B解题报告定义一个新数组 $A_i$ 表示 $b_i$ 在 $\{a_n\}$ 中的下标,然后将 $\{a_n\}$ 递增排序,问题转化为在 $\{a_n\}$ 中选出 $A...
[思维+最短路]Codeforces1442C【Graph Transpositions】题解
题目概述CF1442解题报告首先有个基础想法:$dis_{i,j}$ 表示走到 $i$ ,反转了 $j$ 次的最短路,那么答案就是 $\min\{dis_{n,j}+2^j-1\}$ 。但是反转...
[思维+最大生成树]Codeforces1408E【Avoid Rainbow Cycles】题解
题目概述CF1408E解题报告呜呜呜,这就是个沙雕题,但是我不会。如果多个集合之间的边组成了环说明就有彩虹路,但是显然我们不可能把一个集合中的所有边建出来。考虑建辅助点,自然而然我们想到对于每个...
[思维+构造+倍增+exgcd]Codeforces1427E【Xum】题解
题目概述CF1427E解题报告神仙构造题,我又来翻译题解啦QAQ!如果 $(x,y)=1$ ,根据裴蜀定理,一定能求出两个正整数 $a$ 和 $b$ 使得 $ax-by=1$ ,而且如果 $ax...