CSP-J 2021的解决方案。
蒟蒻得分
作为一个学习了一年多，只在入门组的老人，\(T1\)实际上失败了.
\(T1\)是一道简单的数学题，在考场上太复杂了，答案其实是由四个值的最大值决定的。天知道我是怎么想的，我期待得分\(80/100 ~分\)。
\(T2\)是纯暴力，题目保证修改次数不超过\(5000\)，这自然为\(O(n ^ 2)\)修改和\(O(1)\)查询奠定了基础。但是我在考场上使用的方法是\(O(1)\)修改和\(O(n)\)询问，好像通过了，我期望得分\(76/100 ~ pts\)。
\(T3\)是一个大模拟，判断\(ERR\)是真的，令人担忧，已经做了很多特别的判断，所以从现在开始大概花了\(1h\)讨厌这个地址。幸运的是，样本\(3\)给了一个非常好的良心，但它被叫了出来，期望的分数是\(100/100 ~ pts\。
\(T4\)，我旁边的“大哥”开始进攻。脏话飙的厉害(毕竟在小渔村三亚)，心态受到影响。最后最简单的暴力也没有出来，所以我预计得分\(10/100 ~ pts\)。
综上所述，本次\(CSP-J\)的预期总分为\(266/400 ~ pts\)。
题解
T1 分糖果
给定\(L\)和\(R\)的范围，遍历解显然是不现实的，所以考虑一下\(O(1)\)是否可以求解。
再仔细阅读问题后不难发现，对于这个问题，促成答案的是\(L\)和\(R\)除以\(n\)的余数，可以分两种情况来讨论：
当\(R-L \ge n\)时，根据鸽子洞原理，可以得到这个区间内一定有一个数字\(x\)满足\(x \mod n=n-1\)，直接输出\(n-1\)就足够了。
当\(R-L n\)毫无头绪时，再分情况：
如果有一个正整数\(k\)满足$ L kn \le R$(即，\ L \ div n \ ne R \ div n \))，不难发现拿\(kn -1\)颗糖果就能最大化奖励糖果的数量，或者直接输出\(n-1\)。
如果没有正整数\(k\)，让\(k\)为\(kn \le L\)的最大值。此时\(L，R\)的关系为\(kn \ le L \ le R(k ^ 1)n \)，自然冗余越多越大，输出\(R \mod n\)就足够了。
向上代码：
#包含位/stdc。h
使用命名空间标准；
整数n，L，R；
int main(){ 0
scanf('%d%d%d '，n，L，R)；
如果(不适用！=R/n) printf('%d '，n-1)；
else printf('%d '，R % n)；
返回0；
}
T2 插入排序
我在做这道题的时候，没有看到以下修改操作不超过5000次，所以就有了\(O(1)\)修改和\(O(n)\)查询的考场代码。
主要思想是，在这种情况下，对于数组中的一个数字\(a_x\)，它的排序位置取决于它前面的所有数字和它下面的所有数字的总和。
#包含位/stdc。h
#定义MAXN 8100
使用命名空间标准；
int n，Q，a[MAXN]；
int main(){ 0
scanf('%d%d '，n，Q)；
for(int I=1；I=n；I){ 0
scanf('%d '，a[I])；
}
int op，x，v；
while(Q-){ 0
scanf(“% d”，op)；
if(op==1){ 0
scanf('%d%d '，x，v)；
a[x]=v；
} else {
scanf('%d '，x)；
int ans=0；
for(int I=1；I=x；I){ 0
if(a[I]=a[x])ans；
}
for(int I=x 1；I=n；I){ 0
如果(a[I]a[x])ans；
}
printf('%d\n '，ans)；
}
}
retur
n 0;
}
当然，上面的做法会 \(TLE\)，也就希望 \(O2\) 能救救我。
正解来了（\(O(\log n)\) 的修改和 \(O(\log n)\) 的查询）
既然题目给出了排序不会对后面的结果产生影响，那么我们大可不必在 \(a\) 数组中排序，而是可以采用一个 \(vector\) 类型的 \(f\) 数组来存储排序后的序列。
其次，每一次修改都只是单点修改，这就意味着之前的排序结果可以重用，进而降低时间复杂度。具体怎么重用呢这就是接下来的重点了：
对于每一次修改，我们需要：
- 在 \(f[]\) 中找到并删去这个元素。
- 往 \(f[]\) 中推入新的元素，同时维护 \(f[]\) 的单调递增性。
而对于每一次询问 \(a[x]\) 排序后的位置，只需要通过 \(a[x]\) 的值找到其在 \(f[]\) 中的位置，再将其输出就行了。
乍一看，两次操作都是 \(O(n)\) 时间复杂度的啊，哪来的 \(O(\log n)\) 呢
仔细想想，对于每一次操作，我们都要扫一遍整个 \(f[]\) 来查找对应位置，而 \(f[]\) 本身是单调递增的，这就意味着一个新的优化诞生了：二分优化查找过程！
只要每次在 \(f[]\) 中查找对应位置时均用二分优化，无论是修改还是查询，时间复杂度都会降到优秀的 \(O(\log n)\)。
上代码：
#include bits/stdc++.h
#define MAXN 8100
using namespace std;
int n, Q;
struct Node {
int v, id;
bool operator(const Node rhs) const {
if (v == rhs.v) return id rhs.id;
return v rhs.v;
}
} a[MAXN];
vectorNode f;
int main() {
scanf("%d%d", n, Q);
for (int i = 1; i = n; i++) {
scanf("%d", a[i].v);
a[i].id = i;
f.insert(lower_bound(f.begin(), f.end(), a[i]), a[i]);
}
int op, x, v;
while (Q--) {
scanf("%d", op);
if (op == 1) {
scanf("%d%d", x, v);
f.erase(lower_bound(f.begin(), f.end(), a[x]));
a[x].v = v;
f.insert(lower_bound(f.begin(), f.end(), a[x]), a[x]);
} else {
scanf("%d", x);
printf("%d\n", lower_bound(f.begin(), f.end(), a[x]) - f.begin() + 1);
}
}
return 0;
}
T3 网络连接
巨大无比的模拟，判断 \(ERR\) 属实揪心。
因为对 \(STL\) 掌握不熟练，所以考场上索性放弃写 \(map\)。
好了言归正传，判断 \(ERR\)? 时，除了题目中已经给出的情况，还有很多的特判，列举如下：
- \(:\) 的个数少于 \(1\) 个或 \(.\) 的个数少于 \(3\) 个。
- \(:\) 出现在 \(.\) 的前面。
- 不以数字开头。
- \(.\) 或 \(:\) 后面没有数字（体现为以 \(.\) 或 \(:\) 结尾或二者直接相邻）。
- ……
判断完 \(ERR\)，这题也就完成一半了。
因为每一次操作都需要访问之前的服务机，所以我用了一个 \(ser\) 数组来存储对应服务机的下标。
然后就挨个遍历每一台机器，先判断地址是否 \(ERR\)，然后再根据首字母判断机器类型：是服务机则与之前所有服务机比对，有相同则输出 \(FAIL\)，反之输出 \(OK\)；是客户机则与之前所有服务机比对，一旦有相同，立马输出对应服务器在初始序列中的下标并 \(break\)，如果一直没有相同的，则输出 \(FAIL\)。
比对两串字符是否相同就是裸裸的按位比对。
关于两台服务机地址相同则后者 \(FAIL\) 的问题，客户机在连接时也是从前往后遍历的，因此只会连接上第一台出现此地址的服务器，完美地解决了这个问题。
#include bits/stdc++.h
#define MAXN 1100
using namespace std;
int n, ser[MAXN];
char op[MAXN][10], ad[MAXN][30];
bool check(int x) {
int ln = strlen(ad[x] + 1);
int cnt1 = 0, cnt2 = 0;
long long t = 0;
if (!('0' = ad[x][1] ad[x][1] = '9')) return 1;
if (ad[x][ln] == '.' || ad[x][ln] == ':') return 1;
for (int i = 1; i = ln; i++) {
if (ad[x][i] == '.') {
if (ad[x][i - 1] == '.' || ad[x][i - 1] == ':') return 1;
if (cnt2) return 1;
if (ad[x][i + 1] == '0' ('0' = ad[x][i + 2] ad[x][i + 2] = '9')) return 1;
cnt1++;
} else if (ad[x][i] == ':') {
if (ad[x][i - 1] == '.' || ad[x][i - 1] == ':') return 1;
if (ad[x][i + 1] == '0' ('0' = ad[x][i + 2] ad[x][i + 2] = '9')) return 1;
cnt2++;
} else {
t = (t 3) + (t 1) + ad[x][i] - '0';
if (ad[x][i + 1] == '.' || ad[x][i + 1] == ':') {
if (t 255) return 1;
t = 0;
}
}
}
if (cnt2 != 1 || t 65535) return 1;
return 0;
}
bool cmp(char a[], char b[]) {
int lena = strlen(a + 1), lenb = strlen(b + 1);
if (lena != lenb) return 0;
for (int i = 1; i = lena; i++) {
if (a[i] != b[i]) return 0;
}
return 1;
}
int main() {
scanf("%d", n);
for (int i = 1; i = n; i++) {
scanf("%s%s", op[i] + 1, ad[i] + 1);
if (op[i][1] == 'S') ser[++ser[0]] = i;
}
for (int i = 1; i = n; i++) {
if (check(i)) {
printf("ERR\n");
continue;
}
bool fl = 0;
if (op[i][1] == 'S') {
for (int j = 1; j = ser[0] ser[j] i; j++) {
if (cmp(ad[i], ad[ser[j]])) {
fl = 1;
printf("FAIL\n");
break;
}
}
if (!fl) printf("OK\n");
} else {
for (int j = 1; j = ser[0] ser[j] i; j++) {
if (cmp(ad[i], ad[ser[j]])) {
fl = 1;
printf("%d\n", ser[j]);
break;
}
}
if (!fl) printf("FAIL\n");
}
}
return 0;
}
T4 小熊的果篮
最后一道题了，肯定会稍微的有些难度（考完试返程途中才想到正解太淦了）。
直接来讲 \(100pts\) 的思路吧，这题满分解法有很多，起码我现在看到的就有 \(3\) 种了，但我选择的必定是代码最短最好理解的。
因为每一次拿走水果都相当于是从序列里删除一个元素，那么就可以用到链表。
再顺着往下推，推出正解也就不远了。
可以用一个 \(vector\) 容器（令其为 \(b\)）来存储每个块的块头，然后不断更新。具体如何更新呢更新必须满足条件：去掉块头后这个块内仍然有元素。否则跳过（那块都消失了你还管人家干啥）。
最最最后的代码了
#include bits/stdc++.h
#define MAXN 200100
using namespace std;
int n, a[MAXN], l[MAXN], r[MAXN];
vectorint b;
int main() {
scanf("%d", n);
a[0] = a[n + 1] = -1, r[0] = 1, l[n + 1] = n;
for (int i = 1; i = n; i++) {
scanf("%d", a[i]);
if (a[i] != a[i - 1]) b.push_back(i);
l[i] = i - 1, r[i] = i + 1;
}
while (r[0] != n + 1) {
vectorint tmp;
for (int i = 0; i b.size(); i++) {
printf("%d ", b[i]);
int u = l[b[i]], v = r[b[i]];
r[u] = v, l[v] = u;
if (a[b[i]] != a[u] a[b[i]] == a[v]) tmp.push_back(v);
}
puts("");
b = tmp;
}
return 0;
}
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/48882.html