0103abc 的网站

这是一个 240 分的做法，为目前最高得分。 满分做法是非常简单的，直接对整张图做三染色即可满足条件。 具体的，记 $(i,j)$ 位置的颜色为 $(i+j)\bmod 3$，则容易证明选取所有颜色相同的格子一定是满足条件的。然后根据鸽巢原理可知此时出现次数最多的颜色，对应的格子数量一定不少于...

~~P16637 春季限定独立集问题 完全不是数据结构，拉完了~~ 先考虑 $O(n)$ 怎么做。容易想到设 $fi/gi$ 分别表示当前以 $i$ 点为根，独立集中选 / 不选 $i$ 点，独立集大小最大是多少。转移直接显式建树然后 DFS 合并儿子结点的 dp 信息即可。 具体的，有：...

题解怎么没有分治 / semi-启发式合并做法（） 根据 Master Theorem 可以得到下面的结论： $T(n)=T(x)+T(n-x)+O(x)$ 可以得出 $T(n)=O(n^2)$ $T(n)=T(x)+T(n-x)+O(\frac n2)$ 可以得出 $T(n)=O(n\log...

直接 dp 比较困难，考虑套路的用贪心来优化 dp 过程。 设 $f{i,j}$ 表示当前考虑了前 $i$ 个产品，在买车的时候还有 $j$ 个产品没还完钱，最多可以有多少钱用来买车。简单调整可得买产品的过程中先买 $bi$ 更小的产品再买 $bi$ 更大的产品一定不会让答案更差，因此把所有产品按照...

发现要求的答案就是把所有贡献拆成每一对点 $(x,y)$ 和颜色 $c$ 对答案贡献的和，因此答案就是： \prod\limits{i=1}^n(ri-li+1)\sum\limits{x<y\land c\in[lx,rx]\cap[ly...

简单题。注意到两个字符串 $s1,s2$ 都能产生同一个 Morse Code $x$ 当且仅当 $s1=s2$，因此只需要把所有不同的子串可以产生的不同 Morse Code 数量求和就是答案。设 $f_{l,r}$ 表示 $l\sim r$ 一段可以产生多少个不同的 Morse...

这是一个不使用长剖的做法。 注意到一组三元点对 $(i,j,k)$ 是合法的，当且仅当树上存在中心点 $p$，使得 $\text{Dist}(i,j)=\text{Dist}(i,k)=\text{Dist}(j,k)$。 考虑使用递归处理子树 - 合并子树信息的结构来解决问题。设当前 DFS...

直接做是困难的，考虑二分答案，问题变为判定玩家是否可以中 $p$ 次奖。简单调整分析后可以发现对给定的区间 $[L,R]$ 而言 $p$ 合法的充要条件是： $0\le p\le\min\limits{i=L}^R(xi+y_i)$ $\sum\limits{i=L}^R\min(xi,p)\ge...

先特判 $s=1$ 的情况。$s=2$ 和 $s=3$ 的做法类似，后面只讨论 $s=3$。类比 CRT 的做法，记 $\text{LCM}=\operatorname{lcm}(l1,l2,l3),p1=x1\bmod\frac{\tex...

注意（不）到有这样一个结论： 固定 $x1$ 的值，对当前的 $x1$ 枚举所有可能取到的 $a$ 的值（容易证明需要枚举的 $a$ 的数量均摊不超过 $O(\log n)$）。此时考虑快速判定对当前确定的 $x1,a$，是否可以找到一组 $y1,b$...