P2375 [NOI2014]动物园 我竟然会做NOI的题目辣(≧▽≦)/（看的题解 总而言之，这是一道简单的KMP问题。题面简直是给没学过KMP的人看的（比如我）。 我们发现，这个所谓的 num 数组和 nxt 有异曲同工之妙。但是我们对于不能重合这一块有一点问号。那我们先不管重不重合，先给他记录成重合的。 于是在标记 nxt 时同时也可以把 num 标记。原理是，nxt ...

P2476-记忆化搜索 DP? 我们看看，这个状态似乎有亿点点多。我们看看数据范围，数量不超过5，颜色数不超过15. 15维DP显然不靠谱。 那么我们就思考一下……状态个数？发现记忆化搜索可ac： 1234567891011121314151617181920212223242526272829303132#include<iostream>#include<cs...

P2490 [SDOI2011]黑白棋 题意 一个 \(1*n\) 的棋盘上，A 可以移动白色棋子，B 可以移动黑色的棋子，其中白色不能往左，黑色不能往右。他们每次操作可以移动 1 到 \(d\) 个棋子。 每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。 思路 显然可以将题意转化为一种 K-Nim 游戏，即在 \(\frac...

P3203 弹飞绵羊-分块 观察数据范围，发现可以分块。只需要处理每个点跳出所在块后的位置和次数即可。目的是为了加速查询并降低修改复杂度。 对于修改，重构整个块内信息即可。 时间复杂度正确的一批 具体实现也挺简单。注意重构时从后往前贡献即可。 1234567891011121314151617181920212223242526272829303132333435363738394...

P2491 消防/P1099 树网的核 双倍经验，双倍快乐。 题意 在一个树上选择一段总长度不超过\(s\)的链使所有点到该链距离的最大值最小。 输出这个最小的值。 做法 Define:以下\(s\)指链或链长。 证明一下\(s\)一定处于直径上。假设它不在直径上，一定存在直径的其中一个端点到\(s\)的距离大于现在所处支链的最大距离。所以\(s\)不在直径上一定不优。 ...

平面图 平面图就是所有点的连边可以在平面上不相交的图。这一点可以大概理解成拓扑图的性质，即每连一条边就会将某个区域进行分割——很明显，如果两个点分别处在两个不可达的区域，它们要连边显然是要穿过其他边的。 平面图定理 边数大于点数的三倍减六的图一定不是平面图。即设n为点数，m为边数，有 \[m<=n*3-6\] 关于平面图的其他定理和上定理的证明我不会不过我有大佬博客就不乱搬了...

P3214 [HNOI2011]卡农 题意 在集合 \(\{1,2,\cdots,n\}\) 中选出 \(m\) 个非空子集满足： 不存在完全相同的两个集合； 每个元素在所有集合中出现次数之和为偶数。 思路 考虑转移，利用容斥方法进行 Dp。设 \(f_i\) 表示选了 \(i\) 个集合满足条件的方案数： 首先，如果确定了前 \(i-1\) 个集合，那么为了满...

P3643 [APIO2016]划艇 题意 一个合法序列可表示为一个长度为 \(n\) 的序列，其中第 \(i\) 个数可以为 0 或 \([l_i,r_i]\) 中一个整数，且满足所有不为零的数组成的子序列严格上升。求合法序列方案数。\(n\leq 500,l_i\leq r_i\leq 10^9\)。 思路 朴素动态规划做法为，设 \(f_{ij}\) 表示第 \(i\)...

P4074 [WC2013]糖果公园 树上带修莫队 题意：树上每个点有一种糖果，求\(\sum_c\sum_{i=1}^{cnt_c}v_c*w_i\) 其中c为糖果种类，\(cnt_c\)其为出现次数。 思路 离线树上带修莫队。 先进行树上分块。分块内的询问按照出发点、终止点、询问id优先级依次递减排序。 对于树上莫队，其实就是在欧拉序上莫队。因为欧拉序的性质，即每个节点子树...

P3312 数表 题意 求出 \[ \sum_{i=1}^n\sum_{j=1}^m\sigma(\gcd(i,j))[\sigma(\gcd(i,j))\le a] \] 其中 \(\sigma\) 表示约数和。 思路/推导 考虑没有 \(a\) 的限制的情况。 \[ \begin{aligned} ans&=\sum_{d=1}^{\min(n,m)}\sigm...