ZigZagK的博客
ICPC2020沈阳区域赛现场赛游记
Day [-n,-2]考前天天gym VP,感觉状态神神鬼鬼的,我的发挥比较看题目。某天晚上梦见飞机坠机了,可能是某种预兆(迫真)。Day -1本来还想考前最后一场VP,结果队长睡过头了,所以就...
[仙人掌DP]BZOJ4316【小C的独立集】题解
题目概述图论小王子小C经常虐菜,特别是在图论方面,经常把小D虐得很惨很惨。这不,小C让小D去求一个无向图的最大独立集,通俗地讲就是:在无向图中选出若干个点,这些点互相没有边连接,并使取出的点尽量...
[仙人掌+圆方树]BZOJ2125【最短路】题解
题目概述给一个 $n$ 个点 $m$ 条边的连通无向图,满足每条边最多属于一个环,有 $Q$ 组询问,每次询问两点之间的最短路径。解题报告不难想到建出圆方树,然后将距离转化为圆方树上的距离。给定...
[Splay维护序列]Codeforces GYM103145F【Permutation】题解
题目概述CF GYM103145F解题报告其实两个反转操作是独立的,我们可以用两棵Splay来维护位置的序列(A树)以及数值的序列(B树)。每次询问位置 $i$ 的时候,我们先找到 $i$ 位置...
[思维]Codeforces1527B【Palindrome Game】题解
题目概述CF1527B解题报告我来翻译题解啦!由于不是回文串的时候才能进行操作2,所以我们可以认为操作2是执行一次“啥都不干”。如果 $s$ 是回文串(B1):如果 $n$ 是偶数:Bob必胜,...
[贪心+DP]Codeforces GYM103049A【Atomic Energy】题解
题目概述CF GYM103049A解题报告物品体积小,背包容量大的题,我们可以采用大范围贪心,小范围DP的办法。
[莫比乌斯函数+数学]Codeforces1139D【Steps to One】题解
题目概述CF1139D解题报告这是2021天梯赛L3-3的弱化版,吉老师加强版又要杜教筛又要快速乘,懒得写了XD。直接推式子( $1\over n$ 是长度为 $1$ 的情况,需要单独处理):$...
[思维+DP]XXI Opencup GP of Tokyo B【Bit Operation】题解
题目概述CF GYM 102978B解题报告不难发现 $0$ 和 $1$ 执行and和or操作时,相当于把其中一个元素删掉了。而 $00$ 之间或者 $11$ 之间执行and和or操作时,也可以...