CSP-J 游记
啊，有人就会问我：“i 老师，i 老师，你为什么只写了J的游记呢？S的游记在哪里啊？”
啊，我就会回答：“没资格。”
去年考的太渣了，都没脸写游记，这回写一篇罢（
T1
看了一下题，啪一下就慌了啊，很快啊（主要是因为题目有点长，读了大概 5min 才看懂）。
看懂了之后就觉得：“撕，这不会是个暴力吧？”
于是敲出了一个从 \(l\sim r\) 暴力的算法。
结果发现，诶，为啥第三个附件输出的是 230 呢？？？
（我把 233 4567 4657 看成了 233 4567 4567
这个愣是搞了我 5min+，旁边的人都开始写 T2 了，还各种庆祝，心态顿时崩了（calm -= 100）。
自己研究了自己代码很久还没发现问题，甚至考场上我小声的说出了：“收钱协会 T1 样例是不是错了啊。”
最后发现是我眼瞎 (╥╯^╰╥)
写了暴力之后发现 \(r-l\) 最大到 \(1e9\)，于是敲除了一个从 \(r\sim l\) 枚举和一个小剪枝的代码：
#include
using namespace std;
int n, l, r;
int main() {
cin >> n >> l >> r;
int ans = -1;
for (int i = r;i >= l;i--) {
ans = max(ans, i % n);
if (ans == n - 1) break;
}
cout << ans << endl;
return 0;
}
写完就觉得：“T1 稳了稳了，保了个2=”
考后就觉得：“T1 危了危了，不一定2=”
T2
一看题目我就又慌了啊，这 CCF 不讲武德。考前复习的 dp 不给我考，给我考排序？！
再花了 5min- 读完了题，瞬间感觉神清气爽：“这不就是个橙题吗？分分钟切好吧。”
再花了 10min 左右写出了一份时间复杂度爆炸的代码：
#include
#include
#include
using namespace std;
const int maxn = 8010;
int n, q;
int a[maxn];
int a1[maxn];
int main() {
cin >> n >> q;
for (int i = 1;i <= n;i++) {
cin >> a[i];
}
while (q--) {
int opt;
cin >> opt;
if (opt == 1) {
int x, v;
cin >> x >> v;
a[x] = v;
} else if (opt == 2) {
int x;
cin >> x;
for (int i = 1;i <= n;i++) {
a1[i] = a[i];
}
for (int i = 1;i <= n;i++) {
for (int j = i;j >= 2;j--) {
if (a1[j] < a1[j - 1]) {
swap(a1[j], a1[j - 1]);
if (x == j) {
x = j - 1;
}
else if (x == j - 1) {
x = j;
}
}
}
}
cout << x << endl;
}
}
return 0;
}
信心满满的打开了 sort3.in（还是 sort4.in 记不清了），测了一下大数据。
好家伙，算了 3s+ 才出答案，就离谱。
试图关掉同步流卡常失败。
爬回去看题：
诶，题目中 \(14\sim 16\) 和 \(20\sim 22\) 的 \(a_i\) 和 \(v\) 互不相等，可以干 sort 啊！！！
于是写出了和原来分数一样的优化代码：
#include
#include
#include
using namespace std;
const int maxn = 8010;
int n, q;
int a[maxn];
int a1[maxn];
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> q;
for (int i = 1;i <= n;i++) {
cin >> a[i];
}
while (q--) {
int opt;
cin >> opt;
if (opt == 1) {
int x, v;
cin >> x >> v;
a[x] = v;
} else if (opt == 2) {
int x;
cin >> x;
for (int i = 1;i <= n;i++) {
a1[i] = a[i];
}
if (n > 1500) {
sort(a1 + 1, a1 + n + 1);
for (int i = 1;i <= n;i++) {
if (a1[i] == x) {
cout << i << endl;
break;
}
}
} else {
for (int i = 1;i <= n;i++) {
for (int j = i;j >= 2;j--) {
if (a1[j] < a1[j - 1]) {
swap(a1[j], a1[j - 1]);
if (x == j) {
x = j - 1;
}
else if (x == j - 1) {
x = j;
}
}
}
}
cout << x << endl;
}
}
}
return 0;
}
现在不仅只有 AC 和 TLE 了，还有 RE。
Upd: 2021.10.28
好家伙，竟然可以直接 \(\mathcal{O}(n)\) 枚举一下比 \(a_x\) 的值小的元素个数就是 opt = 2 的答案了！
时间复杂度直接降到了 \(\mathcal{O}(nq)\)。。。
硬生生被题目给误导住了，以为就是得用排序才能解决的，结果几个 for 就给解决了。。。
#include
using namespace std;
const int maxn = 8010;
int n, q;
int a[maxn];
int main() {
cin >> n >> q;
for (int i = 1;i <= n;i++) {
cin >> a[i];
}
while (q--) {
int opt;
cin >> opt;
if (opt == 1) {
int x, v;
cin >> x >> v;
a[x] = v;
}
if (opt == 2) {
int x;
cin >> x;
int val = a[x];
int ans = 1;
for (int i = 1;i < x;i++) {
if (a[i] <= val) {
ans++;
}
}
for (int i = x + 1;i <= n;i++) {
if (a[i] < val) {
ans++;
}
}
cout << ans << endl;
}
}
return 0;
}
诶，也不对啊。\(n\times q=8000\times 2\times10^5=1600000000=\text{十六亿}\)
爆了吧，按理来说是错误的，但是洛谷数据点竟然全过了，有一个点卡了 900ms+ 过的（
CCF 的数据肯定更水，痛失 48pts，要不然我就稳 1= 了 /kk
T3
一看题，哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈或或或或或！哦，我亲爱的大模拟！幸好我考前写了 UVA12412，稳了这波，T3 都能 A，保 1= 了。
赛后发现原来就是个萌萌小模拟，考场上想复杂了
花了将近 10min 读完题，20min+ 调完第一份代码。
测一下第一个样例，Pass。
测一下第二个样例，WA。Σ( ° △ °|||)
Debug 了 10min，没找到问题，决定重构（吸取了模拟赛的经验，新建了个文件重写，不覆盖原文件）。
吼吼吼，写出了第二份代码。
测了一下第一个样例，Pass。
测了一下第二个样例，Pass！！！
测了一下第三个样例，WA！！！( ╯-_-)╯┴—┴
使用了一下 Linux 自带的 diff 对拍一下，有区别的行都会显示出来（别人的对拍程序都太麻烦了）。
发现自己判断 IP 地址是否正确写挂了（就是应该输出 ERR 的时候却输出了 OK）。
调了一下就只剩下第 900 多行有一处不相同，结果是忘了开 long long（
改了一下竟然写出了 AC 代码。
考场上懒得算时间复杂度了，估计爆炸（但是考虑到这种专注于考模拟的题不会特别在意效率吧），没管。
#include
#include
#include
using namespace std;
#define int long long
int strtoi(string str) {
int ret = 0;
for (int i = 0;i < (int)str.size();i++) {
ret *= 10;
ret += (str[i] - '0');
}
return ret;
}
int cnt = 0;
struct computer {
string a, b, c, d, e;
int ia, ib, ic, id, ie;
int type; //1: Server 0: Client
bool operator == (const computer& x) const{
if (x.a == a && x.b == b && x.c == c && x.d == d && x.e == e) {
return true;
} else {
return false;
}
}
void clear() {
a = b = c = d = e = "";
ia = ib = ic = id = ie = 0;
type = 0;
}
} info[1010];
int readret = -1;
void read() {
readret = -1;
string opt;
cin >> opt;
if (opt == "Server") info[++cnt].type = 1;
else info[++cnt].type = 0;
string str, a, b, c, d, e;
int pt = 0;
cin >> str;
int amt1 = 0, amt2 = 0;
for (int i = 0;i < (int)str.size();i++) {
if (str[i] == '.') {
if (amt2 != 0) {
readret = 0;
return;
}
amt1++;
}
if (str[i] == ':') {
if (amt1 != 3) {
readret = 0;
return;
}
amt2++;
}
if (str[i] == '.' || str[i] == ':') {
pt++;
} else {
if (pt == 0) a += str[i];
if (pt == 1) b += str[i];
if (pt == 2) c += str[i];
if (pt == 3) d += str[i];
if (pt == 4) e += str[i];
}
}
if (amt1 != 3 || amt2 != 1) readret = 0;
if ((strtoi(a) == 0 && a != "0") || (strtoi(b) == 0 && b != "0") || (strtoi(c) == 0 && c != "0") || (strtoi(d) == 0 && d != "0") || (strtoi(e) == 0 && e != "0")) {
readret = 0;
return;
}
info[cnt].a = a, info[cnt].ia = strtoi(a);
info[cnt].b = b, info[cnt].ib = strtoi(b);
info[cnt].c = c, info[cnt].ic = strtoi(c);
info[cnt].d = d, info[cnt].id = strtoi(d);
info[cnt].e = e, info[cnt].ie = strtoi(e);
if (strtoi(a) != 0 && a[0] == '0') {
readret = 0;
return;
}
if (strtoi(b) != 0 && b[0] == '0') {
readret = 0;
return;
}
if (strtoi(c) != 0 && c[0] == '0') {
readret = 0;
return;
}
if (strtoi(d) != 0 && d[0] == '0') {
readret = 0;
return;
}
if (strtoi(e) != 0 && e[0] == '0') {
readret = 0;
return;
}
return;
}
signed main() {
freopen("network.in", "r", stdin);
freopen("network.out", "w", stdout);
ios::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
while (n--) {
read();
if (info[cnt].ia > 255 || info[cnt].ib > 255 || info[cnt].ic > 255 || info[cnt].id > 255 || info[cnt].ie > 65535 || readret == 0) {
cout << "ERR" << endl;
info[cnt].clear();
continue;
}
if (info[cnt].type == 1) {
bool flag = true;
for (int i = 1;i < cnt;i++) {
if (info[i] == info[cnt] && info[i].type == 1) {
cout << "FAIL" << endl;
info[cnt].clear();
flag = false;
break;
}
}
if (flag) cout << "OK" << endl;
} else {
bool flag = true;
for (int i = 1;i <= cnt;i++) {
if (info[i].type == 1 && info[i] == info[cnt]) {
cout << i << endl;
flag = false;
break;
}
}
if (flag) cout << "FAIL" << endl;
}
}
return 0;
}
T4
没看。
总结：
离谱的很，头回 T1 都稳不了。退了吧。