NOIP 2023 游记
NOIP 2023 游记
N日功力，结汇与此。
题目过于可怕，感觉该次比赛分数线可能比 CSPS 高。
DAY -5 2023/11/12
听同班同学 LZL 描述 NOIP （可能会出黑题、去年的喵了个喵），感觉异常可怕。虽然我以 CSPS 150 分的高分挤进初中前十，但 NOIP 能不能过，还是个巨大的问号。为此，我于该天在洛谷写了一堆（看上去没什么卵意义的）题目，水了几乎一天的谷，并未好好复习下周本应准备的 whk 。
DAY -3~-2 2023/11/14-15
这两天 whk 期中考试，听LZL说LRZ巨佬已于几天前翘课请假，备战 NOIP ，感到非常不可思议。
DAY -1 2023/11/16
whk 被我考寄了，估计连年前三十都没有。 回来加紧复习 NOIP ，却感觉自己脑海里一片空白，该会考的线段树、最小生成树、KMP（这些还好都不于这次出现）要学的一个没有学。
尝试祈求 ZYH（她居然会玩 Python ）的庇护，试着加她 QQ（其实也没什么事，就是很好奇），却很明显失败。唉，RP大减、大减。
熬到午夜十二点，睡了。
DAY 0 2023/11/17
翘课。大早上起来打了一会 MC，然后被家长带着去高铁站汇合（总算认住了SYN , ZXR , LJH等神犇）。上午坐车做了 4 个小时，在车上写了两道题，浅浅的读了徐西岭《整型溢出》，然后就是摆。
高铁 1:40 到达，在等公交时，还看见一大批外校学生。他们看上去队伍庞大，加上我们学校的教练和他们教练看上去关系不错，给我一种莫名的恐惧。
我们到上饶，吃了一顿盖浇饭后，被安排住到 NOI 官网上江西省推荐的住宿地点（什么饶派数字文创酒店），价格较高，环境也好。我和巨佬 LRZ 分在同一间。尝试提交了车上离线写的两道题，但是只 A 过了一题，剩下一题莫名其妙的挂了（我太蒟了）。然后开始疯狂写题，大概写了很久吧，不过仅仅写了一些简单的地痞、广搜。
晚上 7:30 吃完外卖后，就开摆了，先是玩了会东方，但居然被琪露诺搞得生不如死，再是开了个新档玩 MC ，顺便在后台下载一些和信息学有关的东西。这时LZR却说要去其他房间什么“面基”，大概 10 分钟后回来。结果“一去不复返”，我没了他的热点，进入了断网模式。
LRZ 回来后，终于才发现了酒店密码是八个八（可能是从别的房间的人里学来的），这就逆天好吧。
DAY 0.5 2023/11/17 11:00-2023/11/18 凌晨
打模板！
我想赶紧学一下线段树，怕会考，如果考到了的话就药剂，可LRZ提醒我，现在学的话考场上也背不出来，说完他就去敲图论中的最短路、缩点、割点等一系列图论模板了。可怜的我，只能再敲一遍 spfa 、并查集、线性筛等模板，这期间他还给我看了一下 cf 上的一场比赛，可惜打不了。
时间来到凌晨，我打卡看到是中吉。然后以一道红题矩阵加法开启今天的第一道题，没想到，第一遍就A过了。
LRZ 定了两个闹钟，一个是 6:00 的，一个是 6:30 的，计划是先以 6:00 做预备，然后 6:30 再做正式的起床，然后去写 A+B Problem. 就这样定了。在 0:30 的时候，我们睡了。
Day 1 2023/11/18
我醒来时，我们学校的教练在敲门， LRZ 过去开，教练进来后告诉我们已经 6:50 了，要于 7:15 进入酒店餐厅吃早餐。我大惊，看来两闹钟没起效，匆忙起床收东西，现在没时间写 A+B Problem 来增强信心了。
餐厅里汇集了从四面八方来的学生和陪同他们的教练。他们各自汇拢在一起，有一批还在讨论什么可持久化并查集，这使我感到竞争非常非常的激烈。早餐后，叫了个滴去考场，在门外等着。
我在考场外收拾自己的东西，听见他们都在祈祷什么总司令、CCF 的脚，螈题什么的，太强了。我也是这样期盼的。
过检查进考场后，换了个“暴力出奇迹”的 NOI LINUX 自带壁纸（右击桌面，点那个什么 background 即可选择其他壁纸），玩了几把贪吃蛇（在 code::block 中的菜单里有个什么 game，专供蒟蒻食用），用 geany 敲了一下快读和快速幂（看到有人在敲 namespace FastIO，恐怖如斯）。
但是在 8:30 开考时，点击网页那个下载链接，所有机子都 404 ，没有人能够正常下载比赛题目，在我的视野内，所有人都恐慌至极。这里是 NOIP，不是 CSPJ，时间的紧迫早已在其他选手的游记中暴露无遗。在 8:35 时，监考老师汇报了真实情况（机子出了亿点点问题），并提示我们重启电脑，并在磁盘上不会保留先前写入的任何内容。这下，有一些人没什么反应，反正一定会有加时，而有些人——可能是敲 namespace FastIO 的大佬则感觉到了不公，直接“啊”起来。8:40 时，电脑重启完成，同时桌面上多了一个 zip 格式的压缩包——即今年题目。所有选手获得了 15 分钟的加时，考试结束时间延长为 13:15。没人为多出来的 5 分钟而感到欣喜，也没人为失去的 namespace FastIO 而感到惋惜，大家一致进入了敲代码的模式，可本蒟蒻却从头开始，花了 15 分钟读了一遍 pdf ，现在看来就是浪费时间。
T1 词典
看完 pdf 后，发现有人 T1 代码已经写满了屏幕，有的人已经在写 T2，有人在看 T3，意识到自己必须赶紧开 T1。于是写了个含 sort 的代码，甚至不知算法是否正确，就过了大样例。
#include<bits/stdc++.h>
#define I using
#define AK namespace
#define NOIP std
I AK NOIP;
inline int rd(){
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getchar())x=((x<<3)+(x<<1)+(ch^48));
return x*f;
}const int maxn=3005;
struct str{int idx;string a;}s[maxn];
bool cmp(str a,str b){return a.a<b.a;}
bitset<maxn>ans;
char s1[maxn],s2[maxn];
signed main(){
freopen("dict.in","r",stdin);
freopen("dict.out","w",stdout);
int n=rd(),l=rd();
if(n==1){cout<<"1\n";return 0;}
for(int i=1;i<=n;++i)cin>>s[i].a,s[i].idx=i;
sort(s+1,s+n+1,cmp);
//for(int i=1;i<=n;++i)cout<<s[i].a<<' '<<s[i].idx<<'\n';
strcpy(s1,s[1].a.c_str());
ans[s[1].idx]=1;
for(int i=2;i<=n;i++){
strcpy(s2,s[i].a.c_str());
sort(s2,s2+l);
ans[s[i].idx]=(strcmp(s1,s2)>0);
}for(int i=1;i<=n;i++)cout<<ans[i];
cout<<'\n';
return 0;
}两次 sort，我有点担心会爆，但大样例从头 clock 到尾 clock ，平均差700000（我以此猜测是不是以微秒为单位），估计能过。我放心了。
（但是有人说，CCF 这次可能会带着自己的心意，去卡 sort 。）
T2 三值逻辑
看起来十分甚至九分的简单，我怀着这种心态开了 T2。
9:20，我也不知道自己在干什么，迷迷糊糊开了两个数组，一个 sink 用来存储“汇”，一个 f 用来存储赋值语句中与汇的关系（正向反向），如果汇为 0，则恰巧表示 T , F 或 U.存储这些玩意就耗费了我近一个小时，中途还出现了一些奇妙的情况，如最后一个点的汇突然指向一个超出 n 的数，或第 0 个点突然出现了属于自己的汇。
存完了，然后就不知道该干啥了，忙活了半小时后，发现可以按照顺序，取汇的汇的汇的汇的汇……来判断是否存在“汇环”，有存在的话，如果引起矛盾，环上的点全部设为 U 。但是第二个样例始终过不去。我最后放弃想正解了，直接 dfs，中途也不是很顺利，在 lyr(递归层数标记)>n 时把 cnt 写成了 ncnt，结果一直没有输出。这告诉我，即便是深搜，也不是很好写。
开完后面两题后，我回来看 T2，发现第 3，4 个点很好写，v 可能的取值只有 TFU，那么意味着所有点的汇都是 0，很好写。于是我又写了这些点的代码，期望多得到 20 分，然后再也没管这一题。
（后来民间数据测试结果告诉我，第 66 行的 debug(n) 没删，痛失 20 分！！！因提交时调试代码未删净而彻底的寄掉了！！！）
#include<bits/stdc++.h>
#define I using
#define AK namespace
#define NOIP std
I AK NOIP;
inline int rd(){
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getchar())x=((x<<3)+(x<<1)+(ch^48));
return x*f;
}const int maxn=1e5+5;
int f[maxn],sink[maxn];
bool vis[maxn];
int opt1[maxn],opt2[maxn],opt3[maxn],cnt,m;
//vector<int>src[maxn];
void debug(int n){
cout<<'\n';
for(int i=1;i<=n;++i)cout<<f[i]<<' ';
cout<<'\n';
for(int i=1;i<=n;++i)cout<<sink[i]<<' ';
cout<<'\n';
}int seq[maxn],a[maxn],n,ans;
void dfs(int lyr){
if(lyr>n){
int cntu=0;
for(int i=1;i<=n;i++)a[i]=seq[i];
for(int i=1;i<=cnt;i++){
if(opt1[i]==4)a[opt2[i]]=a[opt3[i]];
else if(opt1[i]==5)a[opt2[i]]=(a[opt3[i]]==2?2:a[opt3[i]]^1);
else a[opt2[i]]=opt1[i];
}for(int i=1;i<=n;i++){
if(a[i]!=seq[i])return;
cntu+=(a[i]==2);
}ans=min(ans,cntu);
return;
}for(int i=0;i<3;i++)seq[lyr]=i,dfs(lyr+1);
}signed main(){
freopen("tribool.in","r",stdin);
freopen("tribool.out","w",stdout);
int ptnum=rd(),datanum=rd();
while(datanum--){
n=rd(),ans=1e8;m=rd(),cnt=0;
memset(f,0,sizeof(f));
for(int i=1;i<=n;i++)sink[i]=i;
for(int i=1;i<=m;++i){
cnt++;
char ch=getchar();
if(ch=='T'||ch=='F'||ch=='U'){
int k=rd();
f[k]=(ch=='T'?0:ch=='F'?1:2);
opt1[cnt]=f[k],opt2[cnt]=k;
sink[k]=0;
}else{
int x=rd(),y=rd();
if(f[y]<2)f[x]=f[y]^(ch=='-');
else f[x]=2;
sink[x]=sink[y];
opt1[cnt]=(ch=='-')+4;
opt2[cnt]=x,opt3[cnt]=y;
}
}//for(int i=1;i<=cnt;i++)cout<<opt1[i]<<opt2[i]<<opt3[i]<<'\n';
if(ptnum<3){dfs(1);
cout<<ans<<'\n';}
else{
debug(n); //错误出在这里，忘记删了
ans=0;
for(int i=1;i<=n;i++)ans+=(f[i]==2);
cout<<ans<<'\n';
}
}cout<<'\n';
return 0;
}T3 双序列拓展
这是啥？好吃吗？可以嚼的动吗？
为了避免你扔硬币蒙混过关？这是什么意思？
拿着黑笔和蓝笔，在考场上研究规律，显然本蒟蒻没有能力推出它们，只好退而求其次，寻 CCF 的部分分。即便如此，我也只写出了第一个点，第二个点我只祈求 CCF 的第二个点是 nm=2，而非 n=m=2（因为自己菜，写不出），这样就能得 10 分，多得 5 分。
其他的我连深搜都写不出来，如果我能写出来，那么其他巨佬一定也能写出来，甚至有更好的解法。
在windows环境下还来了个 CE（在 void solve 函数里面写了个 return 0），但愿 linux 不要让我 ce ，笔记考场上这段代码还是能正常运行的。
#include<bits/stdc++.h>
#define I using
#define AK namespace
#define NOIP std
I AK NOIP;
const int maxn=500005;
int c,n,m,q;
int x[maxn],y[maxn];
string ans;
inline int rd(){
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getchar())x=((x<<3)+(x<<1)+(ch^48));
return x*f;
}void solve(){
if(c==1){ans+=(x[1]==y[1]?"0":"1");return;}
if(n==2&&m==1){ans+=((x[1]-y[1])*(x[2]-y[1])<=0?"0":"1");return;}
if(n==1&&m==2){ans+=((x[1]-y[1])*(x[1]-y[2])<=0?"0":"1");return;}
if(x[1]==y[1]){ans+="0";return 0;} //错误出在这里，return 0
if(c>=8&&c<=14){
}
}signed main(){
freopen("expand.in","r",stdin);
freopen("expand.out","w",stdout);
c=rd(),n=rd(),m=rd(),q=rd();
for(int i=1;i<=n;++i)x[i]=rd();
for(int i=1;i<=m;++i)y[i]=rd();
solve();
while(q--){
int kx=rd(),ky=rd(),k1,k2;
for(int i=1;i<=kx;i++)k1=rd(),k2=rd(),x[k1]=k2;
for(int i=1;i<=ky;i++)k1=rd(),k2=rd(),y[k1]=k2;
solve();
}cout<<ans<<'\n';
return 0;
}T4 天天爱打卡
突然想起了 NOIP2016 的天天爱跑步？不过好像和这题挨不上一点边。
开这题时，已经是 12:20，本来想思考一下动规的状态转移方程的，但时间不允许。深搜，启动！！！void dfs(int lyr,int now,int nl)
深搜写的很快，lyr 表示层数(Layer 的缩写)，now 表示当前连续的跑步天数，nl 表示当前的能量。在 lyr>n 时取nl最大值。写完后发现一个细节问题，截止时间为 x 的天数可能不止一个，而我是用一维数组存储对应关系。哎，接下来的事情我也改变不了，就看今年 CCF 的出数据工具是用手还是用脚了。
#include<bits/stdc++.h>
#define I using
#define AK namespace
#define NOIP std
#define hbx unordered_map //很明显，一开始我想hbx，但感觉不如一维数组
I AK NOIP;
const int maxn=100005;
int n,m,k,d;
struct tz{int x,y,v;}t[maxn];
bool cmp(tz a,tz b){return a.x<b.x;}
int tr[maxn]={0};
int seq[maxn],ans=0;
inline int rd(){
int x=0,f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
for(;isdigit(ch);ch=getchar())x=((x<<3)+(x<<1)+(ch^48));
return x*f;
}void dfs(int lyr,int now,int nl){
//cout<<'\n'<<lyr<<' '<<now<<' '<<nl;
if(lyr>n){
//for(int i=1;i<=n;i++)cout<<seq[i]<<' ';
ans=max(ans,nl);
return;
}if(now<k){
seq[lyr]=1;
if(tr[lyr]!=0&&t[tr[lyr]].y<=now+1)dfs(lyr+1,now+1,nl+t[tr[lyr]].v-d);
else dfs(lyr+1,now+1,nl-d);
}seq[lyr]=0,dfs(lyr+1,0,nl);
}signed main(){
freopen("run.in","r",stdin);
freopen("run.out","w",stdout);
int ptnum=rd(),datanum=rd();
while(datanum--){
memset(t,0,sizeof(t));
memset(tr,0,sizeof(tr));
memset(seq,0,sizeof(seq));
ans=-0x520ccf;
n=rd(),m=rd(),k=rd(),d=rd();
for(int i=1;i<=m;i++)t[i].x=rd(),t[i].y=rd(),t[i].v=rd();
sort(t+1,t+m+1,cmp);
for(int i=1;i<=m;i++)tr[t[i].x]=i;
dfs(1,0,0);cout<<ans<<'\n';
}
}结尾
我粗略的检查了一下 T1 和所有题的 freopen，然后还打算玩盘贪吃蛇，但在监考老师的巡视中，“自信”的交了代码，拿着士力架的包装袋和未食用的八宝粥，沉重的离开了考场。
估分：100+20+5+8=133
于是乎，寄了。
同行四人中，一个九年级的，一个高一的，两个高二的，都估计拿到了超过 160 的分数。面对 T2 脑残挂的 20 分，我只留下无尽的感慨。
题目过于可怕，感觉该次比赛分数线可能比 CSPS 高。