联合省选 SC 游记
MoCaRabbit · · 生活·游记
这份游记现在才敢交审。
The start.
The dream.
The ending.
给我我无限自卑的比赛。
Day ?
打了 n 场，全挂惨了。
有次打了个 20。
猎奇挂分王。
Day -5~0
Day 1
考场旁边坐的是 JDScript0117。
开场不想干猎奇期望，去想 T3。
什么牛福题。
想了会暴力，老实了，做 T1。
现在已经过了 1h。
T1 好像是个树形背包，先打。
这啥，为什么编译过后过个几十秒才能运行 exe，烦死了。
然后打了 1h，好像打出来了个三次方算法？
好像背包可以用 NTT 优化到
也可以撤销背包，但我貌似是不会的。
然后我就没有想到将上面两个结合一下，暴力多项式除法，于是直接死了。
于是开卡，加了个只枚举值不为 0 的位置。
然后最后一个大样例跑了 2.5s，考虑学校机子比较慢，再加上实在不想卡了。
把 T3 暴力打了，以为 T2 就是大构造题，不敢去开，结果你告诉我 T2 就是一个简单 DP？
[64,100]+0+12
被这个杀毒软件恶心到了。
听说了 BID 旁边坐了 _O_vO。
Day 2
在场外在 BID 的带领下见到了 _O_vO 和 getaway_car 两位大神。
得知了左边坐的是 lucasincyber。
两道交互，一个大数据结构。
T1 什么题，好像可以
是分治吗？
对着题做了 1h 发现需要
然后我就沿着分治的道路越走越远，以为是递归单边。
走了 1.5h，走的很欢愉。
搞得脑子崩溃，看到旁边的 JDScript0117 一直在写代码。
然后发现做不出来，又发现好像可以查询前后缀。
这可以压到
然后随便乱搞了一下，写出了下面这坨奇异搞笑的玩意。
#include<bits/stdc++.h>
#include <vector>
void init(int, int);
std::vector<int> perm(int);
int query(int, int);
using namespace std;
void init(int c,int t){
}
vector<int>p,R;
int l[100010],r[100010];
std::vector<int> perm(int n){
r[0]=n;
p.resize(n),R.resize(n);
for(int i=0;i<n;i++) p[i]=R[i]=0;
int pos0=0;
for(int i=1;i<n;i++){
r[i]=query(i,n-1);
if(!r[i]) break;
pos0=i;
}
l[n-1]=n;
for(int i=n-2;i>=pos0;i--) l[i]=query(0,i);
set<int>s;
for(int i=0;i<n;i++) s.insert(i);
R[pos0]=1;
s.erase(0);
for(int i=pos0+1;i<n;i++) if(l[i]!=l[i-1]) p[i]=l[i-1],R[i]=1,s.erase(p[i]);
for(int i=pos0-1;i>=0;i--) if(r[i]!=r[i+1]) p[i]=r[i+1],R[i]=1,s.erase(p[i]);
if(pos0<=n/2){
for(int i=pos0+1;i<n;i++){
if(R[i]) continue;
int t=*s.begin();
if(t==l[i]) t=*next(s.begin());
s.erase(t);
p[i]=t;
}
for(int i=pos0-1;i>=0;i--){
if(R[i]) continue;
int t=*s.begin();
if(t==r[i]) t=*next(s.begin());
s.erase(t);
p[i]=t;
}
}
else{
for(int i=pos0-1;i>=0;i--){
if(R[i]) continue;
int t=*s.begin();
if(t==r[i]) t=*next(s.begin());
s.erase(t);
p[i]=t;
}
for(int i=pos0+1;i<n;i++){
if(R[i]) continue;
int t=*s.begin();
if(t==l[i]) t=*next(s.begin());
s.erase(t);
p[i]=t;
}
}
// for(int i=0;i<n;i++) cout<<p[i]<<" ";
// cout<<"\n";
return p;
}这个思路是哪边数少往哪边填。
此时我已经被这个题搞得很烦了，这份代码过了大样例，于是就直接交了，把对拍忘的那是一干二净。
还有 1h 去打 T2，T3。
T3 读了 15min 的题，读不懂啊，这个空集怎么比大小。
T2 读了题，准备搞个乱搞上去骗点分。
于是优化乱搞，还是没过第 2 个还是第 3 个大样例。
然后似了，似的很欢愉。
我出场认为我是 100+?+0。
Day ?
复现了代码，perm qoj 25，似了。
Day ?+1
下发了成绩，64+0+12+25+0+0=101，没下 100 分。
找寻者代码搞到，交洛谷，怎么一遍过了？？？
为什么 D1T1 指数级和三次方都过了。
为什么大家都有 200 分？
懵了。
绝望了。
Day ？？
APIO 没上，等候补。
Day ？？？
NOIp 分数太低了，没有 D 类去。
Day ？？？？
APIO 候补上了，倒数第二名。
Day ？？？？？（2026/5/9）
APIO T2 Sub #3，和 perm 一个压法，我没有压成 30 次，而是查询了 31 次。
Day ？？？？？？
发现自己离 D 类好像只差一个 std::list 的常数。
我已经在 CSP-J2024，NOIp2025，省选 2026，APIO2026 中国区中被常数区分爆了哈哈哈哈哈哈哈哈哈。
为什么我要心血来潮，在正赛考场上用 std::list 写单调队列哈哈哈哈哈哈哈哈哈。
我之前用 std::deque 写队列被卡空间常数，现在轮到我用 std::list 写单调队列被卡时间常数了哈哈哈哈哈哈哈哈哈。
命运啊，哈哈哈哈哈哈哈哈哈。
Day ？？？？？？？（2026/6/12）
补全了绝望而糟糕的省选游记。
还是不想面对我是个普及组小朋友的现实呢？
明年再战，我要进省队！！！
明年再战，我要进省队！！！
明年再战，我要进省队！！！