A - Too Many Requests
题意
给定正整数 \(N\) 和 \(M\)。
输出 \(N\) 行，对于第 \(i\) 行：
- 如果 \(i\leq M\) ，则输出
OK - 否则输出
Too Many Requests
代码
void solve()
{int n, m;cin >> n >> m;for(int i = 1; i <= n; i++)if(i <= m)cout << "OK\n";elsecout << "Too Many Requests\n";
}
B - N - 1
题意
给定一个长度为 \(N\) 的整数序列 \(A=(A_1,A_2,\ldots,A_N)\) 以及一个整数 \(M\)。
判断是否可以删除 \(A\) 中的某个整数，使得剩余的 \((N-1)\) 个整数之和正好为 \(M\) 。
思路
枚举删除哪个数字，然后判断剩下的数字总和是否为 \(M\) 即可。
或者先求出所有数字的总和 \(S\)，为了删除一个整数使得总和为 \(M\)，那么要删除的整数数值一定是 \(S - M\)，然后判断数组内是否存在这个数值即可。
代码
void solve()
{int n, m, a[105];cin >> n >> m;int sum = 0; // 总和for(int i = 1; i <= n; i++){cin >> a[i];sum += a[i];}for(int i = 1; i <= n; i++){if(sum - a[i] == m){cout << "Yes";return;}}cout << "No";
}
C - Odd One Subsequence
题意
给定一个长度为 \(N\) 的整数序列 \(A=(A_1,A_2,\ldots,A_N)\)。
求满足 \(1\leq i \lt j \lt k\leq N\) 且满足以下条件的整数三元组 \((i,j,k)\) 的数量：
- \(A_i,A_j,A_k\) 中恰好包含两个不同的值。即 \(A_i,A_j,A_k\) 中有两个相等，其余一个不同。
思路
已知 \(A_i, A_j, A_k\) 中存在两种不同值，因此这三个数字只会呈现出 \(\texttt{ABB, BAB, AAB}\) 这三种不同的形式。
考虑枚举三元组中最后一个下标位置 \(k\)，然后进行分类讨论：
- 如果三元组呈现 \(\texttt{ABB, BAB}\) 这样的形式，也就是说最后一个数字与前两个数字当中的某个数字相同。记此时在 \(k\) 位置之前已经出现了 \(x\) 个不同位置的值与 \(A_k\) 相同，那也就说明有 \((k-1)-x\) 个位置的值是与 \(A_k\) 不同的。只需要在值相同的位置里任意挑选一个，在值不相同的位置里也任意挑选一个位置，那么这两个位置就可以与 \(A_k\) 组成答案三元组，答案数量为 \(x \times [(k-1) - x]\)。
- 对于 \(x\)，可以借助计数数组简单地维护出来。
- 如果三元组呈现 \(\texttt{AAB}\) 这样的形式，也就是说前两个数是相同的。记此时在 \(k\) 位置之前已经出现了 \(y\) 对不同的二元组 \((i, j)\) 满足 \(A_i = A_j\)，那么这些二元组照理来说都可以和 \(A_k\) 组成答案三元组。但问题在于如果这 \(y\) 对二元组的数值与 \(A_k\) 也相同，那么可能会出现三数数值均相同的情况，这不符合题意。所以这里需要把前面所有与 \(A_k\) 值也相同的二元组数量从 \(y\) 中减去。在上一步中我们已经得到 \(x\) 用于表示前面值与 \(A_k\) 相同的位置数量，那么只需要从中任选两个位置均可以组成对应的二元组，即 \(C_x^2 = \frac{x(x-1)}{2}\)，那么答案数量为 \(y - \frac{x(x-1)}{2}\)。
- 对于 \(y\)，在按顺序处理每个 \(A_k\) 时，由于 \(x\) 表示的就是前面有多少个与 \(A_k\) 值相同的位置，那么这 \(x\) 个位置与当前位置 \(k\) 均能够组成值相同的二元组，此时可以把 \(y\) 定义成一个变量，每次往里头加上当前的 \(x\) 即可。
时间复杂度 \(O(N)\)。
代码
long long cnt[200005];void solve()
{int n;cin >> n;long long ans = 0; // 答案long long sum = 0; // 前面有多少个二元组 (i, j) 两个数字相同for(int i = 1; i <= n; i++){int x;cin >> x;// AB[B] BA[B]ans += cnt[x] * ((i - 1) - cnt[x]);// AA[B]ans += sum - cnt[x] * (cnt[x] - 1) / 2;sum += cnt[x]; // 当前数字 x 可以和前面任意一个 x 组成相同数值的二元组cnt[x]++;}cout << ans;
}
D - On AtCoder Conference
题意
有一个周长为 \(M\) 的池塘，池塘边有一间小屋和 \(N\) 个人。
对于一个实数 \(x\) \((0\leq x \lt M)\) ，我们将点 \(x\) 定义为从小屋出发顺时针方向上经过 \(x\) 所到达的位置。
第 \(i\) 个人位于点 \(A_i\) 。 可能会有多个人站在同一个位置。
另外，给定一个不大于 \(N\) 的整数 \(C\)。对于 \(i=0,1,\ldots,M-1\) ，定义 \(X_i\) 如下：
- 高桥会从点 \((i+0.5)\) 开始并朝着顺时针方向移动。
- 只要高桥遇到的总人数小于 \(C\)，他就会朝着顺时针方向一直移动，直到他遇到的总人数达到 \(C\) 人为止。
- 只要他走到了某个人所在的点上，就可以当作他遇到了这个人。
- 如果同一个点上存在多个人，那么只要高桥走到了这个点上，这里的所有人就都可以算作是高桥遇到的人。
- \(X_i\) 即表示高桥在停止移动之前遇到的总人数。
- 由于最后停止的位置可能有多个人存在，因此 \(X_i\) 可能会大于 \(C\)。
求对于 \(i=0,1,\ldots,M-1\) 的 \(X_i\) 总和，即 \(\displaystyle\sum_{i=0}^{M-1} X_i\)。
思路
对所有人的位置 \(A_i\) 先进行排序，然后为了方便在环上进行维护，可以先借助化环为链的技巧，让 \(A_{i+N} := A_i\) \((1 \le i \le N)\)。
首先可以发现，对于两个位置分别为 \(A_i, A_{i+1}\) 的人（明显他们两个是相邻的），从其所在位置之间的所有起点出发，最终答案肯定是一致的，我们只需要计算一次即可。
但即使如此，如果我们每次暴力地以每个人所在位置作为起点去计算答案，这样的时间复杂度也还是 \(O(NC)\) 的。
发现现在每个人的位置 \(A_i\) 已经有序，那么随着我们枚举的起点 \(A_i \sim A_{i+1}\) 朝着顺时针方向慢慢移动，最终所停留的终点位置一定也是会随着慢慢朝顺时针方向移动的，因此这一步我们可以借助双指针进行优化，每次把上一段模拟得到的终点记录下来，处理下一段答案时直接接着继续用即可。
记 \(p\) 表示从 \(A_i \sim A_{i+1}\) 之间的位置出发，直到遇到至少 \(C\) 人后，最终停留的位置下标（即 \(A_p\)，因为停下来的位置一定和某个人所在位置重合）。只要 \(i+1 \sim p\) 之间的人数不足 \(C\) 人，或者人数已经达到，但是最后一个位置有多个人重合（a[p] == a[p+1]），那就让下标 \(p\) 一直向后移动即可。这里要注意，万一所有人的初始位置均相同，不要让 \(p\) 移动超过一圈，保证 \(p - i \le N\) 条件在最终仍然成立即可。
移动完成后，那么从 \(A_i \sim A_{i+1}\) 之间的任意位置出发，最终答案均为 \(p - i\)，求出 \(A_i \sim A_{i+1}\) 之间有多少个不同起点后，令其与 \(p - i\) 相乘后直接计入最终答案即可。这里要注意特判 \(A_1\) 与 \(A_N\) 之间这一段。
时间复杂度取决于排序的 \(O(N\log N)\)。
代码
typedef long long ll;int n, c;
ll m;
ll a[1000005];void solve()
{cin >> n >> m >> c;for(int i = 1; i <= n; i++)cin >> a[i];sort(a + 1, a + n + 1);for(int i = 1; i <= n; i++)a[i + n] = a[i]; // 化环为链ll ans = 0;int p = 1; // p 用于表示从 a[i]+0.5 开始往后走，遇到的第 c 个人的位置（如果有重合则取最后一个人）for(int i = 1; i <= n; i++) // 每次处理 a[i]~a[i+1] 这一段，保证覆盖整个环{// 处理起点在 a[i] ~ a[i+1] 之间的所有 0.5 位置的答案，可以直接假设起点为 a[i] + 0.5// 此时 a[i+1] 可以看作是第一个遇到的人// p-(i+1)+1 = p-i 表示遇到的人数// 如果人数不足，或者人数足够但最后一个位置有多个人重合，则让 p 指针不断向后移动while(p - i < c || p - i < n && a[p + 1] == a[p])p++;ll cnt = a[i + 1] - a[i]; // a[i] ~ a[i+1] 之间的起点数量if(i == n) // 注意特判第一个点与最后一个点间的这一段cnt = a[1] + (m - a[n]);ans += cnt * (p - i); // 每个起点的答案都是 p-i}cout << ans;
}
E - Hit and Away
题意
给定一张包含 \(N\) 个点和 \(M\) 条边的简单连通无向图 \(G\)。经过每条边需要的时间都是 \(1\)。
每个点要么是安全的，要么是危险的，该状态由一个长度为 \(N\) 的字符串 \(S\) 给出，该字符串仅包含 S 和 D。其中，当第 \(i\) 个字符为 S 时，说明点 \(i\) 时安全的，反之则表示点 \(i\) 是危险的。保证至少存在 \(2\) 个安全点和 \(1\) 个危险点。
对于每个危险点 \(v\) ，请找到以下值：
从某个安全点出发，经过 \(v\) 点，然后再走到一个与起点不同的安全点上，所需要的最短时间。
思路
可以把“\(\text{安全点1} \rightarrow \text{危险点} \rightarrow \text{安全点2}\)”这一过程拆分为“\(\text{安全点1} \rightarrow \text{危险点}\)”加上“\(\text{安全点2} \rightarrow \text{危险点}\)”。
接下来便可以从所有的安全点出发，对整张图进行搜索。
对于每个危险点，我们需要保证两步的时间和越小越好，那么也就相当于对于每个危险点，需要求出从任意安全点出发到达该危险点的最短路以及次短路长度，并且还要保证最短路与次短路的起点不能是同一个安全点。
考虑最短路，但在搜索的同时带上“来源点”这一属性，开 dis1 以及 dis2 两个数组，分别用于表示从任意安全点出发到达每个点的最短路以及次短路长度。为了保证次短路的来源与最短路不同，还需要再开一个 from 数组，用于表示取到最短路时的来源是哪个点，便于在求次短路时对来源进行判断。
最后由于整张图的边权均为 \(1\)，直接考虑 SPFA 即可，第一次搜到某个点即为最短路，第二次搜到即为次短路（需保证来源不同）。
时间复杂度 \(O(N+M)\)。
代码
struct point
{int pos, dis, src;// 当前点 与起点的距离 源点
};int n, m;
vector<int> G[200005];
char str[200005];queue<point> q;int dis1[200005], from[200005];
// dis1[i], from[i] 表示从任意起点到达 i 的最短路，及其来源的起点编号
int dis2[200005];
// dis2[i] 表示从任意起点到达 i 的次短路，保证来源与最短路的来源不同void solve()
{cin >> n >> m;for(int i = 1; i <= m; i++){int u, v;cin >> u >> v;G[u].push_back(v);G[v].push_back(u);}cin >> (str + 1);for(int i = 1; i <= n; i++){dis1[i] = dis2[i] = 1e9;if(str[i] == 'S'){dis1[i] = 0;from[i] = i;q.push(point{i, 0, i});}}while(!q.empty()){point x = q.front();q.pop();for(int &v : G[x.pos]){// x.pos -> vif(dis1[v] == 1e9) // 不存在最短路{dis1[v] = x.dis + 1;from[v] = x.src;q.push(point{v, x.dis + 1, x.src});}else if(dis2[v] == 1e9 && from[v] != x.src) // 不存在次短路，且此时来源与最短路不同{dis2[v] = x.dis + 1;q.push(point{v, x.dis + 1, x.src});}}}for(int i = 1; i <= n; i++)if(str[i] == 'D')cout << dis1[i] + dis2[i] << "\n";
}
F - Shortest Path Query
题意
给定一张 \(3 \times N\) 的网格图，以二维字符数组 \(\{S\}\) 给定，其中 \(S_{i, j}\) 表示第 \(i\) 行第 \(j\) 列的网格状态。
如果 \(S_{i,j}\) 为 #，则表示单元格 \((i,j)\) 是墙壁，不可通过；如果为 . 则表示是空地，可以通过。
给定 \(Q\) 次查询，您应该按顺序处理这些查询。
每个查询都会给出整数 \(r\) 和 \(c\) ，您应该翻转单元格 \((r,c)\) 的状态（如果是墙壁则变成空地，如果是空地则变成墙壁），然后输出以下问题的答案：
每次可以向相邻的上、下、左、右四个方向进行移动，问从单元格 \((1,1)\) 移动到单元格 \((3,N)\) 所需要的最小移动次数，或判断单元格 \((3,N)\) 不可到达。
思路
首先因为网格图只有三行，所以过程中不可能出现往左移动的情况，只需要专注于向右移动即可。
考虑合并过程中的移动步骤。如果我们要从单元格 \((x, a)\) 移动到 \((y, b)\)，再从 \((y, b+1)\) 移动到 \((z, c)\)，那么我们只需要知道 \((x, a)\) 到 \((y, b)\) 的最短路长度以及 \((y, b+1)\) 移动到 \((z, c)\) 的最短路长度，在两者之和的基础上再 \(+1\)（表示 \(b\) 列移动到 \(b+1\) 列这一步），便可以得到从 \((x,a)\) 移动到 \((z, c)\) 的最短路长度。
也就是说，两个列区间 \([a, b]\) 和 \([b+1, c]\) 的答案是能够进行合并的，我们可以借助线段树来辅助进行维护。
对于线段树上的每个结点，除了记录该结点对应的列区间 \([l, r]\) 以外，再开一个数组 dis[i][j] 表示从左端点的 \(i\) 行移动到右端点的 \(j\) 行的最短路长度（即从 \((i, l)\) 移动到 \((j, r)\) 的最短路）。
初始化时，对于叶子结点而言，如果当前这一列的第 \(i\) 行到第 \(j\) 行之间不存在障碍物，则 dis[i][j] 表示两行之间的距离 \(|i-j|\)；如果存在障碍物，可设置为 \(\infty\)。
然后考虑答案上传，与上面的例子相同，对于列区间为 \([l, r]\) 的结点，由于其左端点与左儿子左端点相同，右端点与右儿子右端点相同，因此只需要枚举将左右儿子合并，跨越区间中点时是经过哪一列的，便可以借助类似 Floyd 的方法从两个儿子的答案中维护出父结点的答案，即：
最终答案就是列区间为 \([1, n]\) 的结点（也就是根结点），其左侧第一列到右侧第三列的最短路长度，即 dis[1][3]。
整道题只需要用到单点修改的线段树。
时间复杂度 \(O((N+Q)\log N)\)。
代码
const int INF = 0x3f3f3f3f;#define ls (p << 1)
#define rs (p << 1 | 1)int n;
int mp[4][200005]; // 0/1 表示有无障碍物 1 表示有struct node
{int l, r;int dis[4][4];// dis[i][j] 表示 mp[l][i] -> mp[r][j] 的最短路
};
node tr[200005 << 2];// 子结点标记上传
void push_up(int p)
{memset(tr[p].dis, INF, sizeof tr[p].dis);for(int i = 1; i <= 3; i++)for(int j = 1; j <= 3; j++)for(int k = 1; k <= 3; k++)tr[p].dis[i][j] = min(tr[p].dis[i][j], tr[ls].dis[i][k] + tr[rs].dis[k][j] + 1);
}// 判断 c 这一列的 x, y 两行间是否存在障碍物
bool check(int c, int x, int y)
{if(x > y)swap(x, y);for(int i = x; i <= y; i++)if(mp[i][c] == 1) // x 到 y 行内存在障碍物return false;return true;
}// 更新叶子结点 p 的 dis，对应原图的 c 列
void update_leaf(int p, int c)
{// 这里的 dis[i][j] 表示 i, j 这两列间是否存在障碍物// 无障碍物即为 abs(i - j)// 有则不连通 视作 INFfor(int i = 1; i <= 3; i++)for(int j = i; j <= 3; j++){if(check(c, i, j))tr[p].dis[i][j] = tr[p].dis[j][i] = abs(i - j);elsetr[p].dis[i][j] = tr[p].dis[j][i] = INF;}
}// 建树
void build(int l, int r, int p = 1)
{tr[p].l = l;tr[p].r = r;if(l == r){update_leaf(p, l); // 更新叶子return;}int mid = l + r >> 1;build(l, mid, ls);build(mid+1, r, rs);push_up(p);
}// 单点更新
void update(int pos, int p = 1)
{if(tr[p].l == tr[p].r){update_leaf(p, tr[p].l); // 更新新的叶子信息return;}if(pos <= tr[ls].r)update(pos, ls);elseupdate(pos, rs);push_up(p);
}void solve()
{cin >> n;for(int i = 1; i <= 3; i++)for(int j = 1; j <= n; j++){char c;cin >> c;if(c == '#')mp[i][j] = 1;}build(1, n);int q;cin >> q;while(q--){int x, y;cin >> x >> y;mp[x][y] ^= 1;update(y); // 单点更新 y 这一列if(tr[1].dis[1][3] == INF) // 直接取叶子结点 dis 作为 [1, n] 区间的答案cout << -1 << "\n";elsecout << tr[1].dis[1][3] << "\n";}
}