ZigZagK的博客
[线段树+复杂度分析+差分+树状数组]2021牛客暑期多校训练营7 B【xay loves monotonicity】题解
题目概述xay loves monotonicity解题报告首先我们很自然联想到楼房重建那道题,定义 $Find(p,l,r,i)$​​​ 表示在 $[l,r]$​​​ 的节点 $p$​​​ 前...
[分块+复杂度分析]Codeforces1491H【Yuezheng Ling and Dynamic Tree】题解
题目概述CF1491H解题报告这么诡异的操作,考虑分块。每个元素记录 $last_i$ 表示 $i$ 往前跳,最后一个没有跳出 $i$ 所在块的位置。查询的时候,先将 $x$ 和 $y$ 跳到 ...
2020 CCPC 长春站 部分题解
F. Strange Memory呜呜呜,想了半天怎么快速处理这个 $i\ \mathbb{xor}\ j$ ,之后发现其实根本没有好的处理方法,只能拆位计算贡献。考虑第 $B$ 位的贡献,那么...
[Trie+复杂度分析]2020 ICPC 济南 K【Kth Query】题解
题目概述Kth Query解题报告这道题给了我01 Trie的新思路QAQ。首先我们考虑没有限制的情况,我们对于每个节点 $x$ 维护 $MIN_{x,k}$ 表示 $x$ 子树中第 $k$ 小...
2020 CCPC 威海站 部分题解
比赛链接我是代码工具人,打的都是代码题2333。B. Labyrinth如果终点起点构成的矩阵中没有黑洞,那么答案显然就是曼哈顿距离。否则最优解一定会贴着至少一个黑洞走。把黑洞周围四个点都存下来...
[离线+并查集按秩合并+平衡树启发式合并]Codeforces1417F【Graph and Queries】题解
题目概述CF1417F解题报告超级套路题……任意无向图删边是很麻烦的,所以肯定考虑离线转换成加边然后回退。加边就可以利用并查集来进行合并,考虑用set维护一个块的最大值,并查集合并的时候set启...
[线性筛+除法分块]BZOJ4407【于神之怒加强版】题解
题目概述求 $\sum_{i=1}^{n}\sum_{j=1}^{m}gcd^K(i,j)$ 。解题报告水题吧……先用莫比乌斯函数处理一下:$$ \sum_{d=1}^{n}d^K\sum_{k...
[状压DP+复杂度优化]BZOJ4197(Noi2015)【寿司晚宴】题解
题目概述把 $[2,n]$ 分成两半(不需要全部选),求两边不存在不互质的数的方案数。解题报告如果素数个数少的话可以直接状压 $f_{s,t}$ 表示第一组的素数集合为 $s$ ,第二组的素数集...
数据结构水题选讲(By AwD)部分题解
课件链接Problem A考虑莫队之后在移动指针时怎么维护第 $K$ 大值。带 $log$ 大概会GG。由于答案在 $[1,n+K]$ 范围内,所以可以把值域也分块,这样移动指针就不需要带 $l...
[容斥+三元环]BZOJ5407【girls】题解
题目概述JZ需要从 $n$ 个妹子中挑出 $3$ 个出去浪,但是三个妹子之间不能有冲突,一种方案 $(i,j,k),i<j<k$ 的贡献为:$Ai+Bj+Ck$ ,求所有合法方案的总...