这次比赛从4月30号晚上就开始了，晚上读了几道题，发现有一些题是之前写过的，于是果断找了一个没人过的题拿了个一血（不过被GNU C++坑的WA了两发）。
后来就断网了，只能把读了的题都写了，但是没法提交。第二天早上7点起床，交了几道就出门了，下午回来又写，断断续续的终于AK了。
A.Little Dima and Equation
签到题。只要想到换一种方式枚举就是一道非常水的题目了。
题目大意：找出所有的$10^9$以内的数$x$，满足：
$x = b·s(x)^a + c$
其中$s(x)$定义为$x$的各位数之和。
某次CF原题……由于$x$大小为$10^9$，所以$s(x$)不超过$81$，枚举$s(x)$之后判定即可。
B.Levko and Strings
这是一道明显的dp题。
题目大意：给出一个字符串s，找出所有的字符串T，使得满足s[i..j] < T[i..j]的(i,j)对数为k，求出这样的字符串t的数量。
对于字符串T的每一位i，都有三种情况：大于s[i]，等于s[i],小于s[i]。
T中每有一T[i]大于s[i]，显然，它会带来的(i,j)对数为$(i-t)*(n-i+1)$；其中，t是i之前第一个满足s[t] != T[t]的数。
我们设计状态f[i][j]表示考虑前i位中的字符，他们提供的对数为j时的方案数。
若T[i] <= s[i]，则有
|
|
若T[i] >= s[i]，则需枚举在i之前满足s等于T的长度t，则有：
|
|
之所以要减去f[i - t - 1][j - t × (n - i + 1)]，是为了要保证T[i - t]不等于s[i - t]。
根据调和级数的性质，时间复杂度为$O(n^2 \log n)$
C.Subsegments
STL乱搞
题目大意：给出长为$n$的序列$A$， 对$A$的每一个长为$k$的子区间，求在其中只出现$1$次且最大的数。
每一个子区间转化为下一个子区间时，仅有两端的数字会发生变化，右边加了一个数，左边减了一个数。我们用一个map维护当前区间中所有数字的个数，这样可以$O(\log n)$的实现区间的转移。
此外，再维护一个大根堆，每有一个数字的个数变为1就将它加入堆中，之后输出堆顶元素。
涉及到从堆中删除元素的操作通过对每一个数字记录它的修改时间来实现。
D.Palindrome Degree
Manacher算法
题目大意：定义k回文串：s是回文串，且s的前半段和后半段都是k-1回文串，则s称为k回文串。对给出的字符串s，求它所有的前缀的k之和。
如果学过Manacher算法，这道题就变得非常简单。
Manacher算法通过在字符串s中添加’#’字符，可以在O(n)的时间复杂度下求出以字符串s的每一位为中间点的最长回文串的长度。
如果我们知道了这个，那么对s的每一个前缀，我们只需要判断以这个前缀的中间位置为回文串中点的回文串长度是否大于等于当前前缀，如不是，则当前前缀的k值为0，否则当前前缀的k值为当前前缀的前半段的k值加1。
此外，这道题还可以通过hash来做，这需要我们找到一个好的hash函数。
E.Little Bishops
dp
题目大意：给出n×n的棋盘，在其中放一些象(国际象棋中的象)，象可以斜着移动并吃掉位于这条路径上的其他象。问在其中放k个象，使他们互相不能攻击到的方案数。
最初看到数据范围想到的是搜索。不过这道题和N皇后问题相比，少了不同行不同列的限制，这就导致答案可能会非常多。
后来发现将棋盘旋转45度后就变成了不同行不同列的问题了。这样就可以通过dp来解决它了。
行数为奇数和偶数是互相不影响的，所以应该分两个dp来做。
设dp[i][j]为前i行放了j个象的方案数。
- 如果当前行不放象，那么
dp[i][j] = dp[i-1][j]。 - 如果当前行放象，则
dp[i][j] = dp[i-1][j-1] × (len-j+1)。 - len为当前行的格子总数。
注意行的长度是先增大后减小的，为了使dp成立，需要先将长度排序。
F.Y
树形dp
题目大意：给出一棵树，找出所有的集合{a,b,c}满足不存在一条简单路径同时覆盖a，b，c。
这道题在Ruclion刷树形dp时见到过……
如果我们知道所有的可以被一条简单路径覆盖的集合数目，那么ans = C(n,3) - sum。现在我们的目标就是求sum。
考虑以i为根的子树，如果i是位于路径中间的点，那么通过枚举i的子树和i上面的一坨，可求出i对sum的贡献。累加和即可。
G.Editor
很巧妙的在线查询问题。
题目大意：对一个编辑器，有5种中操作：
I x 表示在光标所处位置之后插入一个数x
D 表示删除光标所处位置的数字
Q k 表示询问k之前的前缀和的最大值(k <= 当前光标)
L 光标左移
R 光标右移
对每个询问，输出ans
通过链表存储，由于询问都是小于等于当前光标位置的，所以我们只需维护当前光标之前的前缀和最大值即可。
对于I操作，插入并维护前缀和最值。
对于D操作，删除，此时位于光标之前的前缀和最值并不发生改变。
对于L操作，左移光标，此时位于光标之前的前缀和最值也不发生改变。
对于R操作，右移光标，并更新前缀和及最值。
H.Sum
数学题。
题目大意：定义S(k)为满足sum(x[i]) = n (1 <= i <=k， x[i] > 0)的有序对(x1,x2,…,xk)的数目。求sum(S(i)) (1 <= i <= n)
通过隔板法，S(k) = C(n-1,k) 故要求的就是sum(C(n-1, i)) = 2^(n-1)
根据费马小定理，若k，p互质，则k^(p-1) % p 等于 1。
因此2^(n-1) % MOD = 2^((n-1) % (MOD-1)) % MOD。在n-1模MOD-1之后，可用快速幂计算。
I.Exam
如果想通的话，也是非常简单的题。
题目大意：定义f[x]为满足a × b | n的有序对(a,b)的个数。求sum(f[i]) (1 <= i <= n)
初看这题并没有什么思路。不过后来发现我们没必要求出每个f[i]。
对于a × b | n这个条件，我们可以看作有序对abc = n。那么我们要求的就是所有的有序对满足
a × b × c <= n
若a，b，c相等，这样的有序对共有pow(n, 1/3)
若a，b，c中有两个相等，通过枚举相等的那个数i(i<= sqqrt(n))可得到的方案数有n/i × 3个。(若n/i >= i，则需去掉n/i与i相等的情况)。
若a，b，c均不相等，不妨设a < b < c，通过枚举a(a <= pow(n, 1/3)),b(b <= sqrt(n/a))
可得到的方案数为(n / a / b - b) × 6.
J.Zombie’s Treasure Chest
部分贪心。
题目大意：有两种物品，每种物品的体积和价值已知，给容量为N的背包，求背包能装下的最大价值。
由于背包很大，所以直接做完全背包是不行的。
如果某种物品的体积大于1000，则可以在10^6的时间复杂度内枚举它的个数，从而求出最优解。
如果两种物品的体积均小于1000，则先留出容量为v1*v2体积的背包，剩余的贪心求解，之后将贪心剩下的和预留的容量进行完全背包即可。
事实上，在贪心完后，可以直接枚举某种物品的数量求最优解了。