感觉APIO过后整个人的竞技水平就低了呢（擦好不爽

感觉自己是个傻逼

update:16.06.30

BestCoder Round #83

1002.zxa and wifi

$O(nklogn)$ 的线段树优化DP做法（BZOJ原题）

然而转移范围可以将右端无限延长，然后一开始先预处理出后缀最优值，成功甩掉一个log，$O(nk)$

1003. zxa and leaf

裸树DP（需要特判都是叶子且都有标记的情况）

1004. zxa and xor

分位考虑，考虑每一位上的增量（因为先加后xor）得到询问区间，然后弄31棵个动态开点线段树就可以了

Codeforces Round #349 (Div. 1)

B. World Tour

求出两点之间的最短路，然后找到最远次远第三远的点($[c-d]$)，每个点再求出最远路径、次远路径（两种，c不一样和d不一样）三条路径($[b-c-d]$)，最后枚举 $a$ 和 $b$

C. Codeword

给一个字符串 $S$，每次要么换字符串，要么询问长度为 $L$ 且存在一个子序列为 $S$ 的字符串数，$S$ 的总长小于 $10^5$

知道了L和n就能算出答案，$\sum_i\frac{26^{i}}{25^{n-L-i}}C(n-i-L,L-1)$，然后就发现L知道了可以 $O(n)$ 推出所有n的值，然后由于字符总长度限制，不同的L最多只有 $\sqrt{n}$ 个然后就能搞了

E. Forensic Examination

给主串和一堆模版串，每次提出主串一个子串和一段模版串，询问子串在这一段模版串中的哪一个模版串出现最多次

全部串弄个SAM，SAM上的每个节点用合并线段树的姿势求出每个节点在ParentTree中的子树的各个子串出现次数，询问时倍增找出主串的节点，然后做遍区间最大值查询

或者建完SA或建完SAM搞个dfs序，这样的话询问就变成一个区间了，然后莫队搞，但是复杂度较高

2016"百度之星" - 初赛（Astar Round 2A）

D Game

设 $F(i,j)$ 表示这段区间内最多能删除多少数，$G(i,j,d)$ 表示区间能否全删且删除两端时的公差为第d个

BD String

直接递归即可

2016"百度之星" - 初赛（Astar Round 2B）

区间的价值

找右边第一个比它大（小）的数，然后枚举左端点，右端点不断移动，然后由于答案是单调的就可以乱搞了

刷题计划

最小乘积思想加上背包即可

瞬间移动

$\sum C(n-2,a)C(m-2,a)$

货物运输

二分答案，然后对于那些距离超过二分值的线段来说，满足要求的传送站是一个45度倾斜的正方形（假如把传送站看作平面上一个点的话）然后就是矩阵求并，并判断并集是否有合法解

区间交

枚举K区间交的左端点，用线段树求出右端点，就可以提取出一堆极大K区间交

中位数计数

因为互不相同的限制，直接枚举中位数然后将原序列搞成正负1然后就相当去求一段和为0的区间

2016"百度之星" - 初赛（Astar Round 3）

D++游戏

直接照搬D游戏，但是多了连续个数的限制

那么我们就对 $G$ 多加一维 $G(i,j,d,l)$ 表示区间能否全删且删除两端时的公差为第d个且连续长度为l

啊还要最短步数，这个就相当于第二关键字啦，新建数组即可

K个联通块

给无向图，选出能使所有点联通的边集个数

求出一个联通块的联通方案数，然后做背包

一个联通块的联通方案数可以容斥求，总方案数减去不联通方案数，后者枚举第一个点所处联通块然后这个联通块的联通方案数乘上补集的总方案数累积起来减掉就好了

拍照

将相同方向的船视为固定，然后将船映射到河岸上，那么就会有两个大区间，问题也就变成移动区间求最大并了

然后对于区间A的一部分而言，它能和区间B的一段处于同一位置（某个时间内）于是我们可以扫一遍出答案

XOR 游戏

将数列分成 $K$ 份，每一份长度最多为 $L$，每一份的价值为xor和，每种方案的价值为每一份的最小值，求方案最大价值

二分答案，但是一行内转移还是 $O(n^2)$ 的，那么将状态扔到二进制Trie上就能快速转移了

△带可选字符的多字符串匹配

△矩阵方程的解

CodeChef May Lunchtime 2016

ASTRING: Akhil and String

求字符串中长度为 $K$ 的最小字典序子序列

每次找最靠左的且比右边字符大的字符删掉，没找到的话就删掉最右

AHWORK: Akhil And Homework

给6种01串 "0,1,01,10,00,11" 并排成一段，求删除多少个串才能使拼接之后的长串为回文串

将一开始的长串做出来，然后区间DP，但是我们不能把处在同一个串的字符拆开，于是加个状态储存两端拿不拿，转移再仔细讨论一下即可