集训期间完成8道，补题5道。
比赛链接：http://vjudge.net/contest/121106#overview
A - Article Decryption(KMP + DP)
题意：
给定几种单词，问给定的文本串有几种翻译方式。
分析：
KMP预处理出每个单词在文本串中的匹配情况，然后$dp$一下即可。
最初KMP写错了一个地方，竟然完全没有发现，一直以为是细节出错，wa了4发！
代码：
|
|
B - Special Fish(KM)
题意：
给定$n$条鱼的价值及他们之间的攻击和被攻击关系，一个条鱼仅可以攻击和被攻击一次，攻击产生的价值为两条鱼的异或，问产生的最大结果？
分析：
看了样例才知道题目问的是什么= =
裸KM
代码：
|
|
C - Bear and Bowling 4(斜率优化dp)
题意：
给定序列，求一个子序列，若子序列中有$k$个元素，值分别为$s_i,s_2,…s_{i + k}$，那么结果为$\sum_{j = i}^{i + k} (j - i + 1) * s_j$，问能够得到的序列的最大值。
分析：
容易想到状态$dp[i][j]:= 第i+1个元素到第j个元素之间的序列得到的值$
设$pre[i]:=前i个元素的和，val[i] := \sum_{j = 1} ^{i} j \times s[j]$，
那么$dp[i][j] = val[j] - val[i] - i \times (pre[j] - pre[i]);$
若$dp[i][j] > dp[k][j], i > k$
即$ val[j] - val[i] - i \times (pre[j] - pre[i]) > val[j] - val[k] - k \times (pre[j] - pre[k])$
$$grad(i,k)={(val[i] - i \times pre[i]) - (val[k] - k \times pre[k]) \over{i - k}} < -pre[j]$$
这样就转化成一个很斜率的式子了，
即当$i > k且grad(i,k)<-pre[j]$时，$i优于k$
令$i>j>k，grad(i, j )< grad(j, k)$，此时$j$均非最优，故可以舍弃。
最后由于$pre[j]$不单调，所以不必维护$head$，直接每次在单调队列上进行二分即可。
最后注意一下$long long$
代码：
|
|
D - Treasure Hunt(线段交)
题意：
$100 \times 100$的正方形围墙内有$n(n \le 30)$端点在围墙边上的墙。给定终点，问从正方形外部走到终点要经过最少多少堵墙，穿过墙时只能走中点？
分析：
$n$只有30，显然枚举入口。仔细分析我们可以发现只能走墙中点这个信息并没有什么用，因为只要是经过这堵墙，必然要穿过去，实际走的即是直线。
那么我们在枚举入口的时候只需枚举端点，然后求连接起点与终点的线段与其他所有线段的交点个数最小值即可~
顺便复习一下线段交 http://blog.csdn.net/yukizzz/article/details/50816072
代码：
|
|
E - Network(LCA + 并查集)
题意：
给定无向图，给定若干询问，每个询问加入一条边，问加入该边后图中桥的数目。
分析：
首先想是缩点，缩点之后形成的是棵树，树边均为桥，每加一条新边，就把他们所在集合并起来。这样就在树上形成了一个环，环中所有边都不再是桥。找环中的边的过程实际就是找最近公共祖先的过程，向上爬的过程中遇到的所有边都不再是桥。
集合并起来很自然的想到用并查集搞，而缩点过程我们也可以在tarjan求桥的同时求用并查集搞。对于每个询问在两个点向上爬的时候判断该点是否与父节点在同一集合中，若不是，说明连边为桥，删去，并将该点与其父节点并起来。
QAQ在缩点的时候我们用深度最低的点来代表他所处在的强连通分量中，利用这点就可以在求LCA时集合合并的同时让结点向上一步一步的跳。
代码：
|
|
I- Intellectual Inquiry【dp，构造】
题意：
给定字符串，要求用字母表前$k$个字母组成长度为$n$的字符串，并添加在已知字符串后面，使得不同子序列个数最多，求个数。
分析：
设$dp[i]:=前i个元素组成的子序列个数$，则有$dp[i] = dp[i - 1] * 2 - 重复序列个数$.
如何求得重复序列呢？首先对于每个$i$，我们都保证$dp$值中不存在重复序列，那么对于第$i$个元素，只需考虑$s[i]$对于序列的影响即可。而这重复部分即为$s[i]$上一个位置$last[s[i] - ‘a’ ]$之前的所有元素与$s[i]$形成的序列，即重复序列个数=$dp[last[s[i]-‘a’]-1]$。
为使最后得到的$dp$值最大，我们要尽量减小$dp[last[s[i]-‘a’]-1]$，而显然$dp$值是单调上升的，构造时每次选取last值最小的即可~~每次得到的$dp$都是最大的，这样累加起来最后得到的而$dp[n+m]$也一定是最大的。
代码：
|
|
J - Dividing Kingdom II(带权并查集，二分图)
题意：
给定$m$条边，若干询问，每次选择编号在$[l,r]$之间的边，将图分成两部分，问如何分才能使得端点在同一部分的最长边最小。
分析：
为使在端点在同一部分的最长边长度最小，我们可以将所有边从大到小排个序，然后每次都贪心的将两条边的端点放在两部分，这样便形成了一个二分图，不停加边直到不能形成二分图，即一条边的端点在同一部分，当前边就是最大值。使用带权并查集判断二分图。
代码：
|
|
K - Can you answer these queries?(线段树)
题意：
给定序列，将给定区间所有数开方，若干询问，询问区间和。
分析：
这题的关键是即便最大的数开方7次也变成了1，之后无论怎么开方都为1，这样在区间更新的时候判断下区间是否全为1即可。再套个线段树求区间和。
分析题目数据范围及性质！
注意这题一大坑点：$l,r$大小未知！
代码：
|
|
L - Assign the task(DFS+线段树)
题意：
给你一棵有$N$个节点的树，有$M$次操作。
$T\ x\ y$ 表示把$x$点权值修改为$y$，其所有子节点都会变成$y$。$C\ x$ 查询$x$的权值。
####分析：
求出DFS序，找到每个节点第一次被标记和最后一次被标记的区间，建立线段树，成段更新+单节点查询即可。
这题暴力好像也能过，每次查询一个结点，就访问向上访问他的祖先，找到最后一次修改的结点即为答案。
代码：
|
|
M - Vases and Flowers(线段树)
题意：
有$n$个花瓶，标号$0到n-1$，每次输入$k,A,B$，有两种操作：
- $k=1,$ 从标号为$A$的花瓶开始顺序放$B$朵花，若花瓶非空，则跳过。问初始放花的花瓶和最后一个放花的花瓶的序号。可以不放完。
- $k=2$，标号为$A到B$的花瓶清空。问清空了多少个原本非空的花瓶。
分析：
线段树记录区间空花瓶的个数。
最初想法是：每次都更新到tree[i].cnt == tree[i].r - tree[i].l + 1即该区间内花瓶皆空，$ls，rs$必为这些区间的端点，比较一下即可。但是对于特殊情况，每次都要更新到叶节点，就变成了暴力。。。。
换个思路，我们可以先计算出$A$之前所有空花瓶的个数$cnt$，那么第$cnt+1$个空花瓶即为$ls$，同理第$cnt + B$即为$rs$，找第$cnt$个花瓶就利用线段树查询时递归的性质。
操作二直接区间更新，用一个全局变量记录区间内空花瓶个数。
代码：
|
|
N - 覆盖的面积(扫描线+线段树)
题意：
给定平面上若干矩形,求出被这些矩形覆盖过至少两次的区域的面积.
分析：
矩阵面积交问题，扫描线+ 线段树。
关键思想就是将矩阵上下边拆成两条线段，给每条线段一个标记，标记为上边还是下边，排序+离散化之后，从下往上扫描。题目中说的是被覆盖两次或以上的矩形，那么我们就对每个区间记录区间内被覆盖的长度，以及覆盖两次或以上的线段的长度，每扫到一个边就更新一次，最后将区间内覆盖两次或以上的边长乘上距下一条线段的高度差加到答案中，扫到最后一条边即可。
具体看代码理解。
代码：
|
|
坐标那里一定要注意，以区间$[0,5]$为例，他的左右结点分别为$[0,2],[3,5]$，如果我们直接用左右端点来表示线段的话，线段$[2,3]$即无法表示，所以在线段树中我们采用$[l, r -1]$来表示端点为$[l,r]$的线段。
- 矩阵面积并问题，即可直接用我们线段树中的$len$进行求解。
- 矩阵周长并，即传说中的轮廓线，求法也类似，可以横着扫一遍再竖着扫一遍，也可以给线段树每个节点增加一个变量$num$，记录该区间内有多少条线段，$ls和rs$来表示当前节点左右端点是否被覆盖(用于去重)，那么该竖直方向的长度即为$num 2 高度差$，水平方向直接求扫描线经过一条线段的长度差即可。线段树辅助——扫描线法计算矩形周长并（轮廓线）
其中$push_up()$的操作1234567891011121314151617void push_up(int i){if(tree[i].cnt){tree[i].len = (X[tree[i].r + 1] - X[tree[i].l];tree[i].ls = tree[i].rs = 1;tree[i].num = 1;}else if(tree[i].l == tree[i].r){tree[i].len = 0;tree[i].num = tree[i].rs = tree[i].ls = 0;}else{tree[i].len = tree[i << 1].len + tree[i << 1 | 1].len;tree[i].ls = tree[i << 1].ls;tree[i].rs = tree[i << 1 | 1].rs;tree[i].num = tree[i << 1].num + tree[i << 1 | 1].num;tree[i].num -= (tree[i << 1].rs && tree[i << 1 | 1].ls); //减去重叠覆盖的部分}}
O - Airport
& P - Radar (DLX重复覆盖问题)
题意：
给定$n$个城市的坐标，要在城市中建$k$个飞机场，使城市距离最近的飞机场的最长距离最小，求这个最小距离。
分析：
最小化最大值，显然二分最大距离。然后我们将距离在范围内的两个城市建边，看能否选出$k$个城市，使得覆盖了所有城市。
将点之间的关系转化成01矩阵的覆盖问题，重复覆盖，建好边套个$DLX$即可。
看了鸟神博客，这里可以直接将所有距离保存在一个数组中，排序并去重，二分下标即可。这样快了很多很多！
P题和这题一个套路，更裸一些。
跳舞链好强大，可惜只会用模板，这个讲的还挺清晰
代码：
|
|
|
|