程序员进阶之算法练习（十五）
前言
有朋友推荐一个新的算法练习网站leetcode，说北美的公司招人都是400题起步，国内公司招聘也经常用到，上海的尤其多。 很有意思，可以花点时间做做leetcode，看看题目质量。 这次更新的仍然是CodeForces的Contest710。
正文
A
题目链接 题目大意 一个8*8的棋盘，输入一个点表示国际象棋中的king的位置，求king能行动的格子数量；
输入两个字符，表示列和行。 列是'a'到'h'，行是1到8。
Example
input
e4
output
8
题目解析 题目较简单，看如何实现比较方便。 列-'a'得到索引x； 行-'1'得到索引y； 特判当king在边界的时候和同时在两个边界的时候。
B
题目链接 题目大意 输入n个x轴上的点，输出和n个点距离最近的点，如果有多个点，输出最左边的那个点。 n (1 ≤ n ≤ 3 * 1e5) x[i] ( - 1e9 ≤ x[i] ≤ 1e9)
Example
input
4 1 2 3 4
output
2
** 题目解析** 对点排序，易知最后的点在最中间。
对于在[A, B]中的点x，易知x到A和B的距离是固定； 那么对于[A, B, C]的最优解，必然是在B； 同上，在[A,B,C,D]中，点x到A和D的距离是固定的，同时与x到[B, C]的最优解的重叠。 类推，得到答案就是排序完最中间靠左边的点。
C
题目链接 题目大意 输入一个奇数n，输出一个n*n的矩阵，矩阵内数字从1到n*n。 矩阵的要求是行、列、对角线的和都是奇数。 n (1 ≤ n ≤ 49)
Examples
input
1
output
1
input
3
output
2 1 4 3 5 7 6 9 8
题目解析 我们把1到n*n的数字抽象成0，1.（根据奇偶性） 我们来看 n=3的时候 010 111 010
问题是当n=5的时候，如何构造？ 已知，n=3的矩阵，那么只要保证n=3外面的矩阵行列和都是偶数就行。 1 010 1
0 010 0 1 111 1 0 010 0
1 010 1
那么题目可以变成这样一圈圈的去构造； 并且为了方便，从中心开始构造最为简单。
E
题目链接 题目大意 构造n个'a'字符，x为insert/delete 'a'一次的代价，y为复制粘贴一次的代价。 n, x and y (1 ≤ n ≤ 107, 1 ≤ x, y ≤ 109).
Examples
input
8 1 1
output
4
input
8 1 10
output
8
题目解析： 动态规划。 dp[i] 表示构造i个字符的最优解。 对应三种可能，三个状态转移。 dp[i] = min(dp[i], dp[i + 1] + x); 删除 dp[i + 1] = min(dp[i + 1], dp[i] + x); 增加 dp[i * 2] = min(dp[i * 2], dp[i] + y); 双倍
1 2 4 8 16 13 26 52 删除3次，double 6次 1 2 4 6 12 13 25 52 增加3次，double 6次
F
题目链接 题目大意 m个操作。 操作1，把一个字符串s放入集合D，每次插入不同； 操作2，把一个字符串s从集合D删除，保证有值； 操作3，询问一个字符串x在集合中子串的数量。 m (1 ≤ m ≤ 3·1e5)
Examples
input
5 1 abc 3 abcabc 2 abc 1 aba 3 abababc
output
2 2
题目解析： 题目有一个很重要的性质：每次插入不同。 于是可以插入建一个自动机，删除建一个自动机，相减即可。
查找函数再引入一个dp值，如果访问一次，就记录当前值。这样每个点就只访问一次 build函数，dp值=-1 比较关键 这里的字典树要引入一个flag来标志是否真的有孩子。（build之后，及时字典树没有孩子，ch指针也会指向fail指针）死循环了几次 插入和更新，在引入一个flag，有更新之后再重新build
如果题目数据更强：（队友提供的神优化） 再引入logN的优化，建logN个自动机，分别存放1、2、4、8等个自动机。
总结
A、B是简单题，C是构（脑）造（洞）题，E是动态规划，F是AC自动机。 新年快乐~