程序员进阶之算法练习（六）
前言
这次只有四个题目，E题是个奇奇怪怪的数学题，就不去啃这个硬骨头了，我们来分析下A/B/C/D：
- A题是简单的找规律题；
- B题是博弈的入门题；
- C题是简单的模拟题，题目较长；
- D题是贪心，也可以说是构造。
看完题目大意，先思考，再看解析；觉得题目大意不清晰，点击题目链接看原文。
文集：
程序员进阶之算法练习（一）
程序员进阶之算法练习（二）
程序员进阶之算法练习（三）
程序员进阶之算法练习（四）
程序员进阶之算法练习（五）
代码地址
A
题目链接
题目大意：输入n，输出一个字符串。
n = 1：I hate it
n = 2：I hate that I love it
n = 3：I hate that I love that I hate it
代码实现：
int n;
cin >> n;
string ret = "I hate ";
for (int i = 0; i < n - 1; ++i) {
if (i % 2 == 0) {
ret += "that I love ";
}
else {
ret += "that I hate ";
}
}
ret += "it";
cout << ret << endl;
题目解析：
找规律。
把字符串分割成三部分"I hate " + ... + "it"，再根据n构建中间的字符串。
B
题目链接
题目大意：有一个数字游戏：给出一堆整数，轮流进行操作，不能操作者输；
操作是把一个正整数x拆成两个正整数i，j并且i + j = x。
现在有n个整数a[i]，小明希望知道当只有前i个（i=1~n）数字的时候，游戏的胜率情况。
输入：
第一行 n (1 ≤ n ≤ 100 000)
第二行 n个数字，a1, a2, ..., an (1 ≤ a[i] ≤ 1e9),
输出：
n行数据，第i输出假如只有前i个数字的时候，游戏的胜负情况；
如果先手者赢则输出1，如果后手者赢则输出2；
Examples
input
3
1 2 3
output
2
1
1
代码实现：
int n, t = 1; // 1表示先手必败 0表示先手必胜
cin >> n;
for (int i = 0; i < n; ++i) {
int k;
cin >> k;
if (k != 1) {
t = 1 -( t ^ (k % 2));
}
cout << t + 1 << endl;
}
题目解析：
假设，先手必胜为0， 先手必败为1.
那么有
0 + 1 = 0
1 + 0 = 0
0 + 0 = 1
1 + 1 = 1
异或操作符嘛。
具体理解思路就是：
1、当你对一个数x进行拆分时，其实就是拆分必胜和必败的状态；
2、必胜一步可以转为必败，必败一步可以转成必胜；
所以实际上根据奇偶数就可以判断必败或者必胜。
比如说：1是必败，那么2就是必胜，3就是必败，4就是必胜。
C
题目链接
题目大意：
这是一个手机系统本地推送的模拟。
先输入n、q， n为应用数量，q为操作数量。(1 ≤ n, q ≤ 300 000)
接下来q行，每行有两个数字x、y：
- x=1的时候表示id=y的应用产生一条notify；
- x=2的时候表示已读所有id=y的应用；
- x=3的时候表示读取前y个notify；
问每次输入后，剩余的未读数量。
Examples
input
3 4
1 3
1 1
1 2
2 3
output
1
2
3
2
代码实现：
int n, m, ls = 1, k = 0, sum = 0;
cin >> n >> m;
for (int i = 0; i < m; ++i) {
lld x, y;
cin >> x >> y;
if (x == 1) {
a[++k] = y;
++num[y];
++sum;
} else if (x == 2) {
sum -= num[y];
num[y] = 0;
flag[y] = k;
}
else if (x == 3) {
for (; ls <= y; ++ls) {
if (ls > flag[a[ls]]) {
flag[a[ls]] = ls;
--num[a[ls]];
--sum;
}
}
}
cout << sum << endl;
}
题目解析：
题目的难点在于操作2会更新应用所有的通知 以及 操作3读取前y个notify的去重。
观察题目，发现只关注未读的数量，而未读的数量只有操作1能产生。
把操作1形成的数字看成一串数列，num[i]记录id为i的应用目前的未读数量；
对于操作2，只需把num[y]清空，添加flag[y]=k的标志，表示应用y在第k个以前全部已读；
对于操作3，只需向右遍历数字，直到个数大于等于y。
PS：因为没看清题目的操作3，导致误认为是最新的前y个，实际是最初产生的y个，这样导致的难度相差比较多。
D
题目链接
题目大意：
有n只椅子排成一行（从左到右序号1到n），蚁人Scott站在第s只椅子；
蚁人可以从某只椅子跳到其他任何椅子，现在他想经过每一只椅子，最终停在第e只椅子上；（每只椅子只经过一次）
众所周知，蚁人能变大变小；在这里，蚁人只能在椅子上进行变化，且只有两种状态：巨人和小人；
蚁人往椅子左边跳的时候，只能是小人状态；
蚁人往椅子右边跳的时候，只能是巨人状态；
从椅子i跳到椅子j，花费的时间分为三个：
- 起跳时间，小人状态下c[i]，巨人状态下d[i];
- 腾空时间，|x[i] - x[j]|；
- 着陆时间，小人状态下b[i]，巨人状态下a[i]；
问Scott从椅子s到椅子e的最短时间是多少。
数学语言：
n个点，每个点有权值x[i]，a[i], b[i], c[i], d[i]。
每个点都存在一条边到其他点，对于点i到点j边的代价为：
|x[i] - x[j]| + c[i] + b[j] seconds if j < i.
|x[i] - x[j]| + d[i] + a[j] seconds otherwise (j > i).
求从点s到点e，遍历所有点的最短路径。（每个点只走一次）
输入：
第一行 n, s and e (2 ≤ n ≤ 5000, 1 ≤ s, e ≤ n, s ≠ e)
第二行 x1, x2, ..., xn (1 ≤ x[1] < x[2] < ... < x[n] ≤ 1e9).
第三行 a1, a2, ..., an (1 ≤ a1, a2, ..., an ≤ 1e9)
第四行 b1, b2, ..., bn (1 ≤ b1, b2, ..., bn ≤ 1e9)
第五行 c1, c2, ..., cn (1 ≤ c1, c2, ..., cn ≤ 1e9)
第六行 d1, d2, ..., dn (1 ≤ d1, d2, ..., dn ≤ 19)
Example
input
7 4 3
8 11 12 16 17 18 20
17 16 20 2 20 5 13
17 8 8 16 12 15 13
12 4 16 4 15 7 6
8 14 2 11 17 12 8
output
139
样例解释：
路径：4 -> 2 -> 1 -> 6 -> 5 -> 7 -> 3
时间：17 + 24 + 23 + 20 + 33 + 22 = 139.
代码实现：
lld ans = cost(src, dest);
NEXT[src] = dest;
for (lld i = 1; i <= n; ++i) {
if (i == src || i == dest) {
continue;
}
lld MAX = inf, key = 0;
for (lld j = src; j != dest; j = NEXT[j]) {
if (cost(j, i) + cost(i, NEXT[j]) - cost(j, NEXT[j]) < MAX) {
MAX = cost(j, i) + cost(i, NEXT[j]) - cost(j, NEXT[j]);
key = j;
}
}
ans = ans + MAX;
NEXT[i] = NEXT[key];
NEXT[key] = i;
}
cout << ans << endl;
题目解析：
每个点都要走到，且每个点只能走一次，那么把点的遍历路径展开最终路径是一条s到t的直线。
归纳法：
n = 2的时候，直接s到t的路径得到最优解；
n = 3的时候，枚举能插入的位置，可以得到最优解；
...
n = k的时候，在n=k-1形成的s到t链上，枚举能插入的位置，得到最优解。
假设插入的位置是i，那么n=k-1的链会分解成几段：s到i，NEXT[i]到t，i到k，k到NEXT[i]，其中 s到i 、 NEXT[i]到t 的距离不变。
那么当 cost(i, k) + cost(k, NEXT[i]) - cost(i, NEXT[i]) 最小时，i就是插入的最优解。
证明的关键点：当n=k插入的时候，点k不会对s到i、NEXT[i]到t 的路径造成影响。
证明实际存在缺陷，目前还未完善证明，这个做法实则是贪心。
