[单调栈+扫描线+线段树]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}+...
[主席树求区间mex]Codeforces1436E【Complicated Computations】题解
题目概述CF1436E解题报告呜呜呜，忘了区间mex可以用主席树做了QAQ。开 $n$ 个权值主席树，第 $i$ 棵树记录 $1\sim i$ 中 $x$ 最后一次出现的位置 $pos_x$ 。...
[数学]Codeforces1435E【Solo mid Oracle】题解
题目概述你有一种法术 $a,b,c,d$ ，在 $t$ 时刻使用时将对敌人造成 $a$ 伤害，但是在 $[t+1,t+c]$ 秒时敌人将每秒回复 $b$ 的血量，并且下一次释放时间至少是 $t+...
[扫描线+线段树]Codeforces1435C【Perform Easily】题解
题目概述CF1435C解题报告将 $a$ 排序，令 $B_{i,j}=b_i-a_j$ 。我们可以枚举 $x$ ，然后对于每个 $i$ 我们采用第一个 $\ge x$ 的 $B_{i,j}$ ，...
[计数]Codeforces1428F【Fruit Sequences】题解
题目概述CF1428F解题报告不是很难，但是要考虑的周全一些。对于一块连续的 $1$（假设区间是 $[L,R]$ ），我们枚举 $[L,i](i>L)$ 和 $[j,R](j<R)$...
[贪心+堆]Codeforces1428E【Carrots for Rabbits】题解
题目概述CF1428E解题报告这就是换了皮的贪心+堆套路题，但是我不会QAQ。设 $Count(x,k)$ 表示 $x$ 分成 $k$ 堆的最少时间，显然是分成 $k-x\bmod k$ 个 $...
[思维+最大生成树]Codeforces1408E【Avoid Rainbow Cycles】题解
题目概述CF1408E解题报告呜呜呜，这就是个沙雕题，但是我不会。如果多个集合之间的边组成了环说明就有彩虹路，但是显然我们不可能把一个集合中的所有边建出来。考虑建辅助点，自然而然我们想到对于每个...
