这次只有四个题目,E题是个奇奇怪怪的数学题,就不去啃这个硬骨头了,我们来分析下A/B/C/D:
看完题目大意,先思考,再看解析;觉得题目大意不清晰,点击题目链接看原文。
题目大意:输入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构建中间的字符串。
题目大意:一个游戏,每次把一个数字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就是必胜。
题目大意: 题目为模拟手机系统本地推送。
输入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个,这样导致的难度相差比较多。
题目大意: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 的路径造成影响。
证明实际存在缺陷,目前还未完善证明,这个做法实则是贪心。