A．BZOJ1293: [SCOI2009]生日礼物
题意
求一个最小的区间使得包含所有的颜色（并不一定只出现一次） 。n<=100W
题解
这题我刚开始做的时候只想到了我们限制一定出现所有颜色，然后取长度最小。也就是说我们一开始把所有颜色的最左边的放入堆中，然后用 max-min 更新 ans，然后再取出最靠左的，把它这种颜色的下一个位置加入堆中，然后不断更新答案。然后在考试的时候发现 Tunix 选手提供了另一种想法：我们二分这个长度（显然是满足单调性的） ，然后剩下就是如何判定一个长度为 mid 的区间是否能包含所有颜色。我们发现这样是可以 O（n）判定的。不断地往队尾加入一个最近的元素，然后看看队尾-队首是否超过了 mid，是的话队首出队。直到队尾-队首<=mid,然后判断是否包含了所有颜色， 只有有一次满足
就返回 1。否则最后返回 0。
Orz Tunix
B．BZOJ1485: [HNOI2009]有趣的数列
题意
我们称一个长度为 2n 的数列是有趣的， 当且仅当该数列满足以下三个条件：
(1)它是从 1 到 2n 共 2n 个整数的一个排列{ai}；
(2)所有的奇数项满足 a1<a3<…<a2n-1，所有的偶数项满足 a2<a4<…<a2n；
(3)任意相邻的两项 a2i-1 与 a2i(1≤i≤n)满足奇数项小于偶数项，即：a2i-1<a2i。
现在的任务是：对于给定的 n，请求出有多少个不同的长度为 2n 的有趣的数列。因为最后的答案可能很大，所以只要求输出答案 mod P 的值。
n≤1000000 且 P≤1000000000
题解
此题一股浓浓的数学趣味。 我们首先要将题目换一种描述方式，或者转化一下， 否则直接统计这样的排列数目几乎是不可能的。我们考虑到因为奇数位和偶数位的其实是单增的，那我们是不是就可以考虑把 1-n 按顺序填到奇数或者偶数位上，这样我们就满足了第一个条件，也就是说我们只要确定每个数是放在奇数位还是偶数位就可以了（因为先后顺序已经确定） 。 ；但是第二个条件应该怎么满足呢？我们只要在往每一位填数的时候加上限制：任意时刻偶数位放的数必须不多于奇数位放的数。然后我们发现任意一个时刻的状态就只与当前奇数位放了多少个数以及偶数位放了多少个数有关了，因此就可以 DP 了。
50 分算法
令 dp[i][j][k]表示前 i 个数，在奇数位上放了 j 个，偶数位上放了 k 个的方案数， 并且 j<=k。 然后我们考虑放第 i+1 个数，当 j=k 的时候只能放到奇数位上，否则都可以放。显然这是个 2 维的 DP。O（n^2）可以拿到 50 分。
100 分算法
既然是数学题那我们考虑数学算法。我们不妨将整个放数的过程画到一张网格图上，起点为（0,0）每次往奇数位上放一个数就连一条（x，y）到（x+1，y+1）的折线，往偶数位上放一个数就连一条（x，y）到（x+1，y-1）的折线。这样我们的限制其实就可以换个方式
性质 1 其实就是表示终点是（2*n，0） 。而性质 2 表示这条折线任何时刻都不能穿越 x 轴！
对 Catalan 数比较熟悉的选手现在估计已经开始写程序了。但为了详细点我们继续推导下去：这个方案数应该怎么统计呢？
如果不考虑穿越 x 轴的限制，方案数是 C(2*n，n),然后我们去掉不合法的方案数就可以得到合法的方案数。不合法的方案数一定在某个时刻第一次到达了（x，-1） ，那么我们把这之后的折线翻转方向，终点变成了（2*n，-2） 。然后我们可以证明不合法的与从（0,0）到（2*n，-2）的一条
折线是一一对应的（应该很好想，自己想想吧） 。然后那我们就用 C（2*n，n）-C（2*n，n-1）就是 ans。化简之后其实是 C（2*n，n）/（n+1） 。
这样就结束的话这道题就是一道纯数学题了。但我们是搞信息学竞赛的，不能光搞数学。接下来才要用到信息学的方法。
求 C（2*n，n）/（n+1）mod P，P 不一定是质数。
P 是质数的话用逆元随便搞搞就可以。但这里 P 不一定是质数。
其实也可以搞。
如果不取模？你会怎么写？高精乘+高精除？
我们介绍另一种方法我们直接对每个数分解质因数，然后在每个素数的幂上加加减减，最后乘起来就是 ans。因为 ans 肯定是整数所以不会出现某个质数的幂为负。 （其实这个做法是我当时不会写高精除才学的方法 QAQ）
然后取模这样搞也可以。但是复杂度是 O（n√n）的。能不能过我也布吉岛（因为我没写过，如果这样写过了请受我一拜）
其实一个数 x 的质因数由它的一个质因数 p 和 x/p 的质因数来组成。那么我们从大到小处理每个数对质因数的贡献，那么对于 x 就只用操作 p 然后把剩下的任务交给 x/p 就可以了！求一个质因数用线性筛就可以啦！这样复杂度是 O（n）的，可以通过全部测试数据。
C．BZOJ2500: 幸福的道路
题意
给出一棵带正权树，首先你需要求出一个序列 a[1……n]，其中 a[i]表示从 i 点出发的最长链。然后请问最大的 ans，满足存在一个长度为 ans 的区间，这个区间里最大值和最小值之差不超过 m。n<=100W
题解
a 数组的求法就不说了，noip 难度的问题。然后求一个最长的区间使得最大-最小<=m。
80 分算法
我们二分这个 ans，然后用 rmq O（n）判定一下就可以了。
100 分算法
哈哈！其实这种问题一般都和单调队列有关！因为固定右端点，左端点其实是单增的，所以我们就可以直接上单调队列了。维护的方法可以自己 yy 一下，也可以到我的博客看做法（建议自行 yy）
（其实我是按 code length 排的题目）
D.BZOJ 3653: 谈笑风生
题目
给出一棵 n 个边权均为 1 的树，再给出 Q 个询问（p，k） 。表示
询问三元组（a，b，c）的数目，其中 a=p，a 和 b 都是 c 的祖
先，a 和 b 的距离不超过 k。n，Q<=30W a,b,c 互不相同。
题解
20 分算法
暴力枚举 b 然后 dfs 出 c 来即可。 （不用写 LCA。 。 。 ）
70 分做法
稍微思考一下，如果 b 是 a 的祖先，那么我们直接用 b 的个数*(s[a]-1)就得到了这一部分的 ans。这一部分可以 O（1）计算。
否则，那么 b 是 a 的儿子，我们要计算的是 sigma（s[b]-1）满足 dist（b，a）<=k。其实 dist 可以改成（dep[b]-dep[a]）
与子树有关的问题肯定首先考虑 dfs 序啦！然后问题就变成了这样一个问题：
每次询问一个区间里某一维值属于某个区间的另一维的值的和。说起来有点儿绕。 。 。
那么树套树就可以啦！70 分到手！
100 分做法
我们其实可以以 dep[i]为权值建立权值线段树，然后在 dfs 序上可持久化。这样问题就转化成了多次询问一个区间的数的和了。O（nlogn）搞定。
这题的关键在于以 dep[i]为权值建立主席树，这样我们就消掉了区间限制这一维（因为直接前缀和减一下就可以了，之前是需要用一个线段树来查询就会多一个 log） 。然后变成一个二维
问题就成了我们所熟知的了。
评论 (0)
