据说是比较水的题目？然而我似乎被NOIP题框住了。。
维护小鸟能到达的范围。因为是每次只能上下，所以根据横坐标的差值可以得到纵坐标的变化区间。 一开始是，然后依次扩大，并与可以通过障碍物的区间取交。 注意：可以通过障碍物的区间并不是每个点都可以到达，只有纵坐标值奇偶性和横坐标相同的时候才可以。但是区间之内的点不会造成影响，只有区间端点才会造成影响(区间长度的时候，一定存在合法的点)。所以每次要判断一下得到的区间是否合法。 当区间为空集的时候立即退出，因为后面的操作还会再把区间扩大，可能就又合法了。
做到题目的弱化或者强化版不要被之前的思路限制住，要找到原来的做法套在当前题目上多了什么，少了什么。
1 | //Code by Lucida |
问题就是在个数字中选出的倍数个，使得这些数字的值为给定值，询问方案数目。
直接DP是很显然的：表示算到了第个数字，取的数字值为，取了的个数的方案数目。
方程为
发现卡空间，可以直接把这个方程用背包的方法原地转移。
发现TLE，那就把排个序，每次只需要处理个数字，总复杂度。
看到Claris大神给了另一个DP：
方程相应为
这样确实就需要用那种神奇的方法了……这个神奇的方法确实很厉害，应该能在别的地方用到，但我还是觉得对这道题来说我的方法好一些。
如果给定一个的条件，要对这个条件思考一下能不能用来优化。另一个例子就是SDOI的那道虚树DP。 的题目排序之后就可以让的值域单调，也许能有些用处。
1 |
|
题意是每个点至多经过一次，“没有重复经过同一个点两次以上的简单路径”感觉怪怪的。
这是一张竞赛图 这样的问题肯定是要缩点DP的，问题是如何构造路径。
两点之间有且只有一条有向边 结论来了：强连通的竞赛图一定有蛤密顿回路
首先要证明任意竞赛图都有蛤密顿路径，因为需要用来构造蛤密顿回路 ，结论成立 设，结论成立，需要证明在时结论也成立 对于原有的路径 如果存在，那么存在。 否则， 如果有或者，那么存在。 假设上面的情况都不符合，那么有，，中间的点无论怎么连边都会有一个转折点，就符合了第一种情况，所以假设不成立。 所以结论成立。
关于一些扩展内容
有了蛤密顿路，来构造蛤密顿回路，主要思路是扩展已有的环 对于蛤密顿路径的前个点组成的环，现在要加入得到 (实现的时候把环拆开，维护断点，设为首尾)
1 | int ce=he;Add(he,pts); |
这样先SCC，然后对于每个SCC都构造蛤密顿回路。 缩点之后，SCC之间的连边也一定是竞赛图的形式，如果有两条有向边，就成了一个SCC。也就是说，如果对于两个SCC，存在边，那就一定不存在，且一定有，存在边。 然后缩点图上进行DP，最后构造答案输出即可。
1 | //Code by Lucida |
显然， 所以问题就是在这些数字中选出尽量多的数使得和为的倍数，在最多的情况下字典序最大。 我又想DP了，233...似乎跟Bird的思维过程惊人相似。。好吧 因为对于任何数字，有，所以肯定至少可以取到个。而且这样肯定也是最优的。 剩下的数字排个序就是答案要求的数了。。 然后询问在前缀和里面二分就好了(然而这个二分我还费了好大的劲才转过弯来。。)
std::partial_sum的等价代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15template <class InputIterator, class OutputIterator>
OutputIterator partial_sum (InputIterator first, InputIterator last,
OutputIterator result)
{
if (first!=last) {
typename iterator_traits<InputIterator>::value_type val = *first;
*result = val;
while (++first!=last) {
val = val + *first; // or: val = binary_op(val,*first)
*++result = val;
}
++result;
}
return result;
}
没错，中间值是用输入数据的类型计算的！！不要问我怎么知道的！！
1 | //Code by Lucida |
搜到了波兰人的题解！！还有视频！！
1 | 1: 1 |
打表发现，50来项之后就有，而，所以差值要，只能是一个偶数项和它的前一项，也就是。 这些只能让集合增加一个的数字，即，所以数组在之后是连续变化，每次增加。 所以把小范围的答案算出来存进，也把存起来； 大范围的在中二分找到最后一个小于的，也就是说在预处理的这些项之外，要找到第对数字。然后再算一下就可以得到答案了。 比较好理解，但我太jiruo，想了很长时间。
1 | //Code by Lucida |
第一步转化是最重要的：把所有的图形都转化为纵向的几部分，然后分11种情况转移即可
细节不算很多，而且样例给的比较良心
唯一想写一下的是的第2种转移。
大体是这样的形式:
这个转移做到对我这种juruo还是比较有难度的。。
想了很长时间都不对，只好看Fuxey神的题解，虽然没有看懂，但得到了一个很好的思路：数形结合
于是用几何画板画出来。
(最后面划的那几下是表明以此类推。。)
然后就很清晰了，只要维护每一竖列的最大值，就可以更新了。
涉及到不等关系的各种东西，如果想不明白，就画图，画几个连续变化的图感受一下。
1 | //Code by Lucida |
给定序和序，求同时满足的期望树高 首先重标号，把序变成的形式 序上的一个区间对应着树的一层，相当于在序上切几下，构成满足序的树
可以发现，序上相邻的两个点的关系是不会影响其它点之间的关系的，所以就只需要看每对相邻点对答案的贡献即可。记点在序中的对应位置为
和要么是同一层，要么在的上一层
如果在的上一层则有两种情况
否则也有两种情况
讨论
是上层的最后一个点，是下层的第一个点，且是的子节点
那么之前的点的深度都，之后的所有比深的点与的LCA必然是，即对于与，之间没有和深度相同的点。
当然，这两个条件对于相等的Case #1同时适用，所以对答案的贡献是。
2.，则
假设，只能是Case #1。而Case #1中在序中也一定相邻，所以不符合最值使用ST表查询，用二分查找来寻找最后一个比大的数字，复杂度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81//Code by Lucida
typedef long long int64;
template <class T> inline bool chkmx(T &a,const T &b){return a<b?a=b,1:0;}
template <class T> inline bool chkmn(T &a,const T &b){return a>b?a=b,1:0;}
const int MAXN=2e5+11,LOG=20,INF=0x1f1f1f1f;
using std::max;
using std::min;
namespace _SparseTable_
{
struct Node
{
int mx,mn;
Node(){mx=-INF,mn=INF;}Node(int mx,int mn):mx(mx),mn(mn){}
Node &operator =(int x){mx=mn=x;return *this;}
}f[MAXN][LOG];
Node operator +(Node a,Node b){return Node(max(a.mx,b.mx),min(a.mn,b.mn));}
int log_2[MAXN];
void ST(int a[],int n)
{
log_2[0]=-1;
for(int i=1;i<=n;++i)
{
f[i][0]=a[i];
log_2[i]=log_2[i>>1]+1;
}
for(int j=1;j<=log_2[n];++j)
for(int i=1;i+(1<<j)-1<=n;++i)
f[i][j]=f[i][j-1]+f[i+(1<<j>>1)][j-1];
}
Node RMQ(int l,int r)
{
if(l>r) return Node();
int lo=log_2[r-l+1];
return f[l][lo]+f[r-(1<<lo)+1][lo];
}
int Find(int x,int l,int r)
{
int L=l-1,R=r;
while(L!=R)
{
int Mid=(L+R+1)>>1;
if(RMQ(Mid,r).mx>x) L=Mid;
else R=Mid-1;
}
return L==l-1?-1:L;
}
}using namespace _SparseTable_;
int main()
{
static int ref[MAXN],dfs[MAXN],bfs[MAXN];
int n;get(n);
for(int i=1;i<=n;++i) get(dfs[i]);
for(int i=1;i<=n;++i) get(bfs[i]);
double Ans;
if(n==1)
Ans=1;
else
{
Ans=2;
for(int i=1;i<=n;++i) ref[bfs[i]]=i;
for(int i=1;i<=n;++i) dfs[i]=ref[dfs[i]],bfs[i]=i;
for(int i=1;i<=n;++i) ref[dfs[i]]=i;
ST(dfs,n);
for(int i=2;i<n;++i)
{
int a=i,b=i+1;
if(ref[a]>ref[b])
Ans+=1;
else if(ref[a]+1==ref[b] && RMQ(1,ref[a]).mx<=a && RMQ(ref[b],Find(b,ref[b],n)).mn>a)
Ans+=0.5;
}
}
//putd(Ans-0.001),putchar('\n');
putd(Ans),putchar('\n');
//putd(Ans+0.001),putchar('\n');
return 0;
}
是上层的最后一个点，是下层的第一个点，且是的子节点
条件的另一种判断方法：
序中之后的所有点，在序中组成恰好连续的一段，那么也完全可以不受的影响。
首先这个结论是正确的，然后假设存在不连续的一段且可以不受的影响，则有
看了一节课不明白
以后再研究吧。
见黄学长的提交here
根据一些类似的分析可以得到下面三个约束条件
把差分一下得到数组，可以把以上三个条件重新写出来
前两个很好处理,现在看第三个 如果取值为，那么都是一层的。这个条件不需要任何前提就可以满足，所以不用管。 如果取值为，那就看这些变量里有没有被限制为的，如果有，其它的只能为，否则，其它的都是 被限制为的只会有一个，因为和的深度相差最多为，中间一段连续的序的深度变化也至多为。
1 | //Code by Lucida |
去年在考场上精心写了一个暴力，得了5分 究其原因，是因为：
当时还根本没听说过超哥线段树这种技巧
树链剖分之后，一条链上的点到根节点距离的前缀和是递增的，就可以看做是坐标，可以上超哥线段树了。 对于这个操作，把链拆成两半 对于到这一段，其增加的值为，相当于在线段树上添加一条直线 对于另一段，增加的值为，相当于在线段树上添加一条直线 对于区间查询，对于查询时途径的节点都算一下直线在处的取值，用来更新答案。
1 | //Code by Lucida |
一道题，说明我斜率优化和CDQ分治都学的一知半解。所以会写的很详细。
用来对拍
1 | namespace KISS |
考虑在序列上，无限制的情况。 看起来很斜率优化。 设，优于当且仅当 即 给定，所以递增，可以化为 维护一个下凸壳。 并不是递增的，所以不能用单调队列，需要用单调栈+二分。
1 | namespace NakedOptOnChain |
加上了路径限制。一开始的想法显然就是在单调栈中二分到第一个可以取到的位置，然后再二分查找最优位置，当时觉得应该不行，但也没想出反例。写出来之后WA，发现反例如下
所以这样是不行的。。
而CDQ分治恰好可以对区间的两半分别做一些操作而不影响答案，于是就CDQ分治
第一维，按照可以到最靠左的点排序；第二维，分治区间
在统计答案的时候，两个指针都从右向左走，维护满足距离限制的凸壳
回溯的时候按照标号的大小顺序归并
1 | namespace DCOnChain |
这一步做法就非常妙了。 在树上要满足距离限制，也可以借鉴CDQ分治的思路，把用来更新的点和被更新的点隔离开，就可以分别进行一些操作 对树点分治，每层找重心，找到重心之后先把重心的父节点对应的子树DC，然后用从重心的父节点开始，沿着父指针一直走到当前层之外，用这条链上满足距离限制的点更新重心的答案，然后把重心也加进这条链。取出剩下的子树中的所有节点，再按照序列上的做法用那条链更新剩下的节点。
1 | namespace DCOnTree |
这是第二次做到考算法新推广的题 第一次是用替罪羊思想维护动态点分治 做不出来甚至看不懂题解说明这种算法本身就学的不扎实 以后再碰到这种情况也应该像这样写出退化版问题的程序，可以加深对原算法和推广的算法的理解
1 | //Code by Lucida |
超神线段树，又叫超哥线段树，又叫李超线段树 在线段树的节点上存储直线，当添加新的直线的时候按照交点讨论选择将一条线压到子区间 首先，如果一条直线被另一条完全覆盖，可以直接把被覆盖的扔掉(但其实不需要单独讨论) 然后对于两条直线，设在点处取值较大的直线为，另一条为。 如果两线段的交点在区间中点左侧，把压到左半区间 否则将压到右半区间 查询的时候，在覆盖该点的所有线段树节点存储的直线中取一个最大值即可。
1 | //Code by Lucida |