ZigZagK的博客
[扫描线+双标记线段树]2020 ICPC EC-final G【Prof. Pang's sequence】题解
题目概述Prof. Pang's sequence解题报告首先根据经典套路,我们记录 $pre_i$ 表示 $i$ 上次的出现位置,这样的话对于一个左端点 $L$ ,只有 $pre_i<L...
[FWT+高维前缀和]2020 ICPC 沈阳 M【United in Stormwind】题解
题目概述United in Stormwind解题报告太久没做过这种题了,其实非常套路。题目里给出了 $n$ 个 $01$ 串,把两个串异或就可以得到两个串不同位置的集合。首先我们可以利用FWT...
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如果终点起点构成的矩阵中没有黑洞,那么答案显然就是曼哈顿距离。否则最优解一定会贴着至少一个黑洞走。把黑洞周围四个点都存下来...
[思维+二分+ST表]2020-2021 ACM-ICPC Brazil Subregional Programming Contest M【Machine Gun】题解
题目概述CF GYM 102861M解题报告首先要仔细读题,题目保证了覆盖的点的个数总和不超过 $10^6$ ,因此只需要想办法快速找到被覆盖的点就行了。如果按照题目里的说法很难快速查找,因此我...
[单调栈+扫描线+线段树]2020 ICPC 小米 网络选拔赛热身赛 H【Equivalent Prefixes】题解
题目概述Equivalent Prefixes解题报告首先我们用单调栈维护出 $[LA_{i},RA_i]$ 表示 $a_i$ 的控制区间( $a_i$ 最小的区间),还有 $[LB_i,RB_...
[离散+线段树分治+并查集按秩合并]2020 ICPC 小米 网络选拔赛热身赛 E【Explorer】题解
题目概述有 $m$ 条边,每条双向边 $(x_i,y_i)$ 只有人数在 $[l_i,r_i]$ 时才能通过,如果人数 $x$ 能够从 $1$ 到 $n$ 则可行,求可行的 $x$ 的数量。解题...
[树状数组]2020 ICPC 小米 网络选拔赛热身赛 B【Beauty Values】题解
题目概述求数列 $\{a_n\}$ 所有子区间不同数个数的和。解题报告套路题,令 $nxt_i$ 表示 $a_i$ 下一个和 $a_i$ 相同的位置。对于一个 $R$ ,如果 $1\le i\l...
[计数+DP]2020 CCPC 秦皇岛站 H【Holy Sequence】题解
题目概述一个合法的整数数列 $\{a_n\}$ 需要满足:$1\le a_i\le n$ 。令 $p_i=\max\{a_k|1\le k\le i\}$ ,则 $p_i\le p_{i-1}+...