Loading...
博主已经退役,评论可能会审核很久才能通过。
BZOJ 分析 设 $sum_i$ 表示 $\sum_{j=1}^i[i\text{中有球}]$。显然我们只需要知道所有的 $sum_i$ 就可以知道每个杯子中是否有球了。 考虑到如果询问了 $[i,j]$,那么一旦知道 $sum_{i-1}$ 或 $sum_j$ 中的一个就可以知道另一个。 因此考虑这样一个模型:对于每个区间 $[i,j]$ ,在 $i-1$ 和 $j$ 间连一条边权为 $...
Luogu LOJ 分析 最简单的想法是每个炸弹向能炸到的所有炸弹连一条边,然后统计每个炸弹能到达多少个点。 然而这样子边数是 $O(n^2)$ 级别的。注意到一个炸弹一定是向一段区间连边,那么线段树优化连边即可。 统计的话,注意到每个炸弹能到达的的点一定是一段区间。那么缩点后按拓扑序算一下能到达的最小编号和最大编号就好了。 代码 `// ==========================...
Codeforces Luogu 分析 显然先把最小割树建出来。 首先有一个结论:第一问答案的上界为最小割树上所有边权之和。 下面考虑怎样达到这个上界。 考虑最小割树上的最小边,我们应让它只被经过一次。设它的两个端点为 $a_i,a_{i+1}$ ,则 $a_{1..i-1}$ 中任意两点不经过该边,$a_{i+2..n}$ 中任意两点不经过该边。于是将该边断掉后两边递归处理即可。 代码 /...
AtCoder Luogu 分析 令 $a_{p_i}=i$。注意到要使 $p$ 的字典序最小,则应使 $a$ 的字典序尽量小。 那么题目变为:给定排列 $a_{1..n}$,如果 $|a_i-a_j|\geq k$ 且 $|i-j|=1$ 则可以交换 $a_i,a_j$,求可能排列中字典序最小的。 注意到如果 $a_i,a_j$ 不可能发生交换(也就是说 $|a_i-a_j|<k$)...
Codeforces Luogu 分析 显然一个强连通分量内的所有边都可以无限走,因此可以考虑缩点。 缩点后,每个强连通分量的权值设为内部所有边能得到的蘑菇个数之和,连接强连通分量的边的权值设为边上的蘑菇数,然后 DP 求最长路即可。 考虑怎么求边权为 $w$ 的边无限走能得到的蘑菇数。设这条边走了 $t$ 次后蘑菇变为 $0$,那么 代码 // =====================...
本文被密码保护。如果想知道密码请联系博主。
Luogu 分析 做完这题感觉对 AC 自动机有了新的理解... 注意到 fail 树上某个节点子树中的节点都以该节点对应的字符串为一个后缀(这里建议想一想 fail 的定义),因此我们要查 $X$ 是否作为 $Y$ 的一个后缀出现就相当于查 $Y$ 是否在 fail 树上 $X$ 的子树中。 然而现在要找的是子串而不是后缀。注意到所有前缀的所有后缀包含了所有子串,于是我们只需要把 $Y$...
Luogu LOJ 分析 这个“翻转”操作很容易想到回文。 考虑一个位置怎样才是合法的。可以发现该位置一定满足以下两个条件之一: 回文半径右侧达到 $|S|$ 。 回文半径左侧达到 $1$ ,且右端点合法。 那么只需要用 manacher 求出回文半径,然后从后往前判断就好了。 代码 // =================================== // author: ...
SPOJ Luogu 分析 为了方便,设 两个求和号中的部分利用等比数列求和公式计算即可。 但是 $5$ 在模 $10^9+7$ 意义下没有二次剩余,所以需要扩域。 代码 // =================================== // author: M_sea // website: http://m-sea-blog.com/ // ============...
AtCoder Luogu 分析 首先注意到黑色还是白色并不重要,因为黑白可以互换。因此我们染一棵子树的根节点时可以强制让它为黑色。 那么,当染一棵子树的根节点 $u$ 时,子树中黑点的权值和应为 $X_u$ ,白点的权值和应该尽量小。 这里白点权值和尽量小是贪心的思想,因为权值尽量小是一定能通过一些更改满足条件。 于是可以考虑 DP。设 $f_u$ 表示以 $u$ 为根的子树中白点权值和最...