ZigZagK的博客
[离线+分块+Tarjan缩点+bitset维护传递闭包]The 19th Zhejiang Provincial Collegiate Programming Contest K【Dynamic Reachability】题解
题目概述CF GYM103687K解题报告科技题过于困难。考虑离线,如果我们把询问分成若干个长度为 $BLK$ 的块,那么块中最多涉及到 $BLK$ 条边,$2BLK$ 个点。这样就可以大大减小...
[矩阵乘法+线段树]Codeforces1701F【Points】题解
题目概述CF1701F解题报告对于 $x$ ,设 $[x-d,x-1]$ 上共有 $cnt$ 个点,那么以 $x$ 作为结尾的三元组个数为 ${cnt\choose 2}={1\over 2}(...
[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操作时,也可以...
[DP]Codeforces1499E【Chaotic Merge】题解
题目概述CF1499E解题报告这道题想法不难,但是实现的时候很注重细节。首先我们考虑DP $f_{i,j,0/1}$ 表示第一个字符串取到了 $i$ ,第二个字符串取到了 $j$ ,且最后一个取...
[分块+复杂度分析]Codeforces1491H【Yuezheng Ling and Dynamic Tree】题解
题目概述CF1491H解题报告这么诡异的操作,考虑分块。每个元素记录 $last_i$ 表示 $i$ 往前跳,最后一个没有跳出 $i$ 所在块的位置。查询的时候,先将 $x$ 和 $y$ 跳到 ...
[线段树维护DP]Codeforces1479B【Painting the Array】题解
题目概述CF1479B1 & CF1479B2解题报告在本算法下,B1和B2其实没有很大区别,所以下面仅讨论最小值。定义 $f_{i,0/1,x}$ 表示 $i$ 放了 $0/1$ 颜色,并且另...