程序员进阶之算法练习（六）
前言
这次只有四个题目，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个数字，轮流进行操作，不能操作者输，输出结果。
代码实现：
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)
每行有两个数字x、y；
x=1的时候表示id=y的应用产生一条notify；
x=2的时候表示已读所有id=y的应用；
x=3的时候表示读取前y个notify；
问每次输入后，剩余的未读数量。
代码实现：
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形成的数字看成一串数列，numi记录id为i的应用目前的未读数量；
对于操作2，只需把numy清空，添加flagy=k的标志，表示应用y在第k个以前全部已读；
对于操作3，只需向右遍历数字，直到个数大于等于y。
PS：因为没看清题目的操作3，导致误认为是最新的前y个，实际是最初产生的y个，这样导致的难度相差比较多。
D
题目大意：n个点，每个点有权值xi，ai, bi, ci, di。
每个点都存在一条边到其他点，代价为：
|xi - xj| + ci + bj seconds if j < i.
|xi - xj| + di + aj seconds otherwise (j > i).
求从点s，到点t，遍历所有点的最短路径。（每个点只走一次）
代码实现：
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，NEXTi到t，i到k，k到NEXTi，其中 s到i 、 NEXTi到t 的距离不变。
那么当 cost(i, k) + cost(k, NEXTi) - cost(i, NEXTi) 最小时，i就是插入的最优解。
证明的关键点：当n=k插入的时候，点k不会对s到i、NEXTi到t 的路径造成影响。
证明实际存在缺陷，目前还未完善证明，这个做法实则是贪心。