A. Contest for Robots
为了使第一个机器人的得分比第二个机器人的得分多，一个很直观的想法，就是将某个第一个机器人能够得分的任务但是第二个机器人却不能得分的任务的分值变为无穷大，那么就一定可以满足这个条件。
但是，题目需要在满足第一个机器人得分比较多的条件下，使每个任务点的分值尽可能小。那么，我们可以对上述变化进行改进，不只是单纯的改变某一个任务的分值，而是在只有第一个机器人能够完成的任务点上平分第二个机器人能够得到的最小分值。
综上，此题只需要 $O(n)$ 的时间复杂度求出只有第一个机器人能够完成的任务点数，以及只有第二个机器人能够完成的任务点数（即：第二个机器人能够获得的最小分值，当然，此处不考虑两个机器人都能完成的任务数量）。
不妨假设只有第一个机器人能够完成的任务数量为 $cnt$，只有第二个机器人能够完成的任务的最小分值为 $s$。此时，需要分成两种情况讨论：
- $ s \% cnt == 0$: 此时，$cnt$ 个任务点正好可以平分 $s$ 分，但是题目要求第一个机器人得分严格大于第二个机器人得分，所以需要在该 $cnt$ 个任务点中任选一个或多个，额外增加一点的分值，所以最后需要输出的结果为：$1 + s / cnt$.
- $s \% cnt != 0$: 此时，$cnt$ 个任务点不能恰好平分 $s$ 分，即：其中有部分任务点的分值为：$\lceil s \% cnt \rceil$, 而另一部分任务点的分值为：$\lfloor s \% cnt\rfloor$. 由于分值需要严格大于，所以可以在 $\lfloor s \% cnt \rfloor$ 的这部分任务点中，任选一个或多个任务点的分值 $+1$，所以这种情况下最后的输出也为：$1 + s / cnt$.
- 若 $cnt == 0$，则无论分值的排布如何，都不可能满足题意，这也是唯一无解的情况。
# include <iostream>
using namespace std;
const int N = 110;
int n, a[N], b[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
cin >> b[i];
int cnt, s;
cnt = s = 0;
for (int i = 1; i <= n; i++)
if (a[i] && !b[i])
cnt++;
else if (!a[i] && b[i])
s++;
if (!cnt)
cout << -1 << endl;
else
cout << 1 + s / cnt << endl;
return 0;
}
B. Journey Planning
先来观察一下这个式子：$c_{i + 1} - c_i = b_{c_{i + 1}} - b_{c_i}$，不难发现这个式子具有传递性，即：
$$
c_i - c_j = b_{c_i} - b_{c_j} ...... ① \\
c_j - c_k = b_{c_j} - b_{c_k} ...... ② \\
将上述两式相加可以得到：\\
c_i - c_k = b_{c_i} - b_{c_k} ...... ③
$$
也容易发现，如果存在 $①$ 或 $ ②$ 中的任意一个，再加上 $③$，那么就可以推得另一个。
由此不难发现，题中所给出的观赏各个景点的旅游路径中，两两路径之间，都不可能存在同样的景点，否则，这两条旅游路径就可以合二为一，即：所有满足式子的景点的魅力值相加，就是该条路径的魅力值，以此类推，可以计算出每条路径的魅力值，再取个最大值就是最终的答案。
那么，如何快速判断任意两点是否满足式子？
我们可以再对式子做一个变形：$c_{i + 1} - b_{c_{i + 1}} = c_i - b_{c_i}$
所以，我们可以直接将 $c_i - b_{c_i}$ 作为第一关键字在 $O(nlogn)$ 的时间复杂度下先排个序，那么满足上式的点毕竟会在相邻位置出现。此时，只需要 $O(n)$ 的时间复杂度统计每条路径的魅力值，同时不断更新最大值即可。
# include <iostream>
# include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 2e5 + 5;
int n;
PII F[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++) {
int b;
cin >> b;
F[i] = { i - b, b };
}
sort(F + 1, F + n + 1);
LL res = 0;
for (int i = 1; i <= n; ) {
int j = i;
LL t = 0;
while (j <= n && F[i].first == F[j].first) {
t += F[j].second;
j++;
}
res = max(res, t);
i = j;
}
cout << res << endl;
return 0;
}
C. Remove Adjacent
这题的数据范围只有 $100$，所以很自然的想能否暴力解决。
但是直接暴力似乎又不太可行，因为删了其中某个字符之后，可能会影响到后续字符的删除（依赖于之前某个已被删除的字符）。
举个例子就是：删了字符串中的某个 $b$，但是后续有个 $c$，这个 $c$ 再删除的时候只能依赖于此前删除的 $b$ 才能判定这个 $c$ 可以删除，但是 $b$ 已经被删，所以这个 $c$ 只能保留，这就造成了鲜红的 $Wrong Answer$ 的原因。
那么能否摆脱上述情况的影响？
答案是可以的，只需要在删除的时候，从字典序最大的字符开始删即可，因为删了当前字典序最大的字符之后，不会对后续的任何删除造成影响，即：不会出现上述例子中导致的无法删除的情况。
综上，此题只需要按照字典序的逆序来判断删除字符即可。
唯一需要注意的就是，在判断删除字符的同时，需要跳过中间所有已经删除的字符，即：一个字符串 $acb$，在删除了 $c$ 之后，那么就应该认为 $a$ 与 $b$ 是相邻的。
# include <iostream>
# include <cstring>
# include <algorithm>
using namespace std;
typedef pair<char, int> PCI;
const int N = 110;
int n;
char a[N];
PCI F[N];
bool vis[N];
int main()
{
cin >> n >> a + 1;
for (int i = 1; i <= n; i++)
F[i] = { a[i], i };
sort(F + 1, F + n + 1);
reverse(F + 1, F + n + 1);
for (int i = 1; i <= n; i++)
if (!vis[F[i].second]) {
int pre = F[i].second - 1;
while (vis[pre])
pre--;
int ne = F[i].second + 1;
while (vis[ne])
ne++;
if (pre >= 1 && a[pre] + 1 == F[i].first || ne <= n && a[ne] + 1 == F[i].first) {
vis[F[i].second] = true;
while (pre && (vis[pre] || a[pre] == F[i].first))
vis[pre--] = true;
while (ne <= n && (vis[ne] || a[ne] == F[i].first))
vis[ne++] = true;
}
}
int res = 0;
for (int i = 1; i <= n; i++)
res += vis[i];
cout << res << endl;
return 0;
}
D. Navigation System
沿着道路走一步之后，如果导航的道路需要更新，那么只能说明当前走的这条路径并不在导航预先的规划当中。
那么，如何快速判断这一点，就成为了这个问题的难点。
假设当前需要从 $i -> j$，我们可以分情况来讨论：
- $j$ 不是从 $i$ 到终点的最短路径中的下一个点，此时，走完这一步之后，导航必须更新。
- $j$ 是从 $i$ 到终点的最短路径中的下一个点，此时，又需要一分为二讨论一下：如果 $i$ 到终点的最短路径只有一条，那么导航肯定不用更新；但是，如果最短路径不止一条，那么，导航是否需要更新就取决于当前的导航是否经过 $j$ 这个点，即：答案需要求的最小值在此情况下不需要更新，而最大值需要 $+1$。
经过上述分析，我们需要预先处理出来的信息就是：
- 从终点到所有点的最短路：这只需要在返图上跑一遍最短路，而又由于每条路径的距离都可以当成 $1$，所以这一点只需要写一个简单的 $BFS$ 即可。
- 在返图的以终点为源点的最短路中，某个点能够从哪些的点转移过来：由于上文描述的操作需要支持：$①$ 判断某个点是否在该集合中；$②$ 判断该集合的大小。因此，我们可以直接调用 $STL$ 中的 $set$ 或者 $unordered\_set$ 即可。
至此，此题就能完美解决，至于时间复杂度，由于需要在 $O(n)$ 的 $BFS$ 中套上 $set$ 或者 $unordered\_set$ 的 $insert$ 操作，所以最终时间复杂度大概为 $O(nlogn)$。（本人其实不是很会算时间复杂度，如果有问题请大佬指正
# include <iostream>
# include <cstdio>
# include <cstring>
# include <queue>
# include <unordered_set>
# include <algorithm>
using namespace std;
const int N = 2e5 + 5;
int n, m, k;
int h[N], e[N], ne[N], idx;
int path[N];
unordered_set<int> walk[N];
int dis[N];
void add(int u, int v)
{
e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}
void bfs()
{
memset(dis, 0x3f, sizeof dis);
queue<int> q;
q.push(path[k]);
dis[path[k]] = 0;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (dis[j] > dis[u] + 1) {
dis[j] = dis[u] + 1;
walk[j].insert(u);
q.push(j);
}
else if (dis[j] == dis[u] + 1)
walk[j].insert(u);
}
}
return;
}
int main()
{
scanf("%d %d", &n, &m);
memset(h, -1, sizeof h);
while (m--) {
int u, v;
scanf("%d %d", &u, &v);
add(v, u);
}
scanf("%d", &k);
for (int i = 1; i <= k; i++)
scanf("%d", &path[i]);
bfs();
int min_res, max_res;
min_res = max_res = 0;
for (int i = 1, d = k - 1; i < k; i++, d--) {
if (!walk[path[i]].count(path[i + 1]))
min_res++, max_res++;
else if (walk[path[i]].size() > 1)
max_res++;
}
cout << min_res << ' ' << max_res << endl;
return 0;
}
E. World of Darkraft: Battle for Azathoth
由于题目需要满足某个大小关系，所以我们不如直接将输入的数据排个序，然后再来考虑此问题。
我们先来考虑攻击装备，比如当前的攻击装备为 $i$，那么对于怪物中所有 $防御 < a_i$ 的，都满足了攻击要求，此时，对于其中某一只怪物，所有 $防御属性 > 当前怪物的攻击力$ 的防具，都有资格成为当前攻击装备 $i$ 的配套防具，用于斩杀此怪物，收获奖励。
进一步可以发现，对于当前的攻击装备 $i$，此前的所有攻击装备，即：下标为 $1$ ~ $i - 1$ 的攻击装备，所能杀死的怪物，那么用当前攻击装备 $i$ 也一定能杀死（由于事先按照了攻击力排序）；
同理，对于枚举到的怪物 $j$ 也不需要重新枚举，只需要继续向后判断即可。
那么，在杀死一只怪物之后，由于奖励需要累加到一段区间的防御属性的防具上，因此我们需要一个支持区间加操作的数据结构，而需要查询的内容，就是在当前的攻击装备 $i$ 的攻击力所能满足的 $攻击力 > 怪物 j 的防御力$ 的最大下标 $j$ 枚举完且将怪物的收益累计到 $当前怪物的攻击力$ ~ $ max防御值$ 的区间中（此为左开右闭区间），再查询整个区间的最大值，即为当前攻击装备所能匹配的最佳防具所能达到的最大收益。 很容易可以想到，这一部分可以用线段树来维护。
因此，只需要将防御属性的值域维护成线段树，当然，如果没有相应防御属性的防具，则该点的值为 $-∞$，剩下的点的初始值为买这件防具所需要花的钱的最小值，显然，应该存为相应的负数。
接着，只需要按上文描述，在 $O(nlogn)$ 的时间复杂度排完序，建完线段树，再用双指针从左到右枚举攻击装备和怪物，不断更新收益（每次更新 $O(logn)$ 的时间复杂度），查询答案并更新最大值（只需要 $O(1)$ 查询），最后输出即可。最终时间复杂度 $O(nlogn)$.
# include <iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<PII, int> PIII;
const int N = 2e5 + 5, M = 1e6 + 5;
int n, m, p;
PII a[N];
LL b[M];
PIII k[N];
struct segment_tree {
int l, r;
LL add, max_val;
}T[M << 2];
void update(int p)
{
int lp = p << 1, rp = lp | 1;
T[p].max_val = max(T[lp].max_val, T[rp].max_val);
return;
}
void push_down(int p)
{
if (!T[p].add || T[p].l == T[p].r)
return;
int lp = p << 1, rp = lp | 1;
T[lp].max_val += T[p].add;
T[rp].max_val += T[p].add;
T[lp].add += T[p].add;
T[rp].add += T[p].add;
T[p].add = 0;
return;
}
void build(int p, int l, int r)
{
T[p].l = l, T[p].r = r;
if (l == r) {
T[p].max_val = b[l];
return;
}
int mid = l + r >> 1, lp = p << 1, rp = lp | 1;
build(lp, l, mid);
build(rp, mid + 1, r);
update(p);
return;
}
void change(int p, int l, int r, int c)
{
if (l <= T[p].l && r >= T[p].r) {
T[p].max_val += c;
T[p].add += c;
return;
}
push_down(p);
int mid = T[p].l + T[p].r >> 1, lp = p << 1, rp = lp | 1;
if (l <= mid)
change(lp, l, r, c);
if (r > mid)
change(rp, l, r, c);
update(p);
return;
}
LL query()
{
return T[1].max_val;
}
int main()
{
scanf("%d %d %d", &n, &m, &p);
for (int i = 1; i <= n; i++)
scanf("%d %d", &a[i].first, &a[i].second);
sort(a + 1, a + n + 1);
memset(b, -0x3f, sizeof b);
for (int i = 1; i <= m; i++) {
int p, c;
scanf("%d %d", &p, &c);
b[p] = max(b[p], -1ll * c);
}
build(1, 1, M - 1);
for (int i = 1; i <= p; i++)
scanf("%d %d %d", &k[i].first.first, &k[i].first.second, &k[i].second);
sort(k + 1, k + p + 1);
LL res = -1e18;
for (int i = 1, j = 1; i <= n; i++) {
while (j <= p && a[i].first > k[j].first.first) {
change(1, k[j].first.second + 1, M - 1, k[j].second);
j++;
}
res = max(res, query() - a[i].second);
}
printf("%lld\n", res);
return 0;
}
F. Reachable Strings
由于多种原因，包括通过率吓人，本人蒟蒻实在不会字符串等等，这题就先鸽着，以后等自己变强了再补（前提是我还能变强，且到时候不忘记这个坑
大佬强啊，E题好简洁，我E题写了140多行=。=
$E$ 题我是在赛后参考了榜单上的某份代码，再整理完思路写的hh，一开始看这题我都想不到什么很明确的思路
兄弟，你的题解很棒，我想点赞的，但不小心多点了两下，这个点赞数就变成负的了，非常不好意思，你别在意，这应该是这个bug，我去问问闫总能不能修，非常抱歉！
已修复
我刚刚还在想，第二次写这么长的题解就受那么大打击，然后就看到了这句评论hh。
没事的没事儿，等 y总修复就行了，(๑•̀ㅂ•́)و✧
Thanks♪(･ω･)ﾉ