2021CSP-J/S复赛游记
Day -10
开始不上晚自习回来练OI。
Day -1
早上第三节课下出校门，吃了午饭之后过了一会儿坐车去盐城。
大概3:30到了盐城，然后等盐中同学放学等到6:00从盐城出发去南京，大概10:30才到清沐酒店。路上要难受死了
然后就早早睡了。早早：指11:30
Day 0
J组
早上6:30起床，吃早饭之后直接走到考场。
大概8:00进了考场实验楼真的远，然后打了一个快读和dij的模板。8:25出题。
看到T1直接2min切掉，实在是CCF传统艺能：T1直接送。
然后8:29开T2，发现貌似T2像去年T2一样一眼看起来比较不可做，先放了。顺序开T3，题面又臭又长，就又顺序开T4。T4暴力应该是可以直接30分，正解的话大概是链表吧，想到这就先上了个厕所。
回来直接开T3，T3细节是真的多，码了好久之后开始对拍，前面两个点拍过了。最后一个大样例好多没过，不得不说这次CCF是真的良心，大样例给的很好。好多细节比如：存a,b,c,d,e的时候要开longlong题目里面也给了，还有直接两个.相邻，数不足5个等等。
然后再9:58的时候大样例过了，一个多小时AC T3的我是屑。
T4貌似比T2可做一点，就先写T4了，打了链表发现并没有什么用，白白浪费了30分钟时间来到10:30。这时候就有点慌了，因为T2和T4都可以说还没有开动。
然后决定放弃T4去T2，T2看了一下每个数的排名就是他前面<=目前数的个数和后面<这个数的个数和+1。（因为这个插入排序的伪代码如果两个数相等，那么在序列里面越排在前面的越靠前。）所以直接用lx[x]和rx[x]维护一下上面说的两个就行了。时间复杂度大概是O(n^2),n=8000应该是可以过的。
大概是11:00了，又复查了一下前3题就开始专门搞T4了。然而整场考试都没有搞出来，写了一个大概是<O(n^2)（极限数据下就是O(N^2)）的暴力代码交掉走人。
花絮：刚出场后面人和我说他随随便便AK了，然后我问他T3开没开longlong。他当场傻掉（。然后就改口说是350~400。（不过还是比我强。）真·不开longlong见祖宗。
J组考完之后心态不太好，原来是准备AK来的。
估计分数：
洛谷民间数据：
实际分数：
S组
中午到饭店大概是12:50了，吃完饭1:05回到酒店。1:20就出发了……
2:00试机，试机又打了一个快读和dij模板（虽然我觉得S不可能考dij的。）2:30发题目。
T1貌似比较可做，T2,T3貌似应该能打个暴力，T4直接没想，题目都看不懂。
然后就开始肝T1，T1的优先队列做法貌似比较显然，把给国内和国际i个最多能停多少飞机用优先队列预处理出来。中间调了好多好多次，最后做法是用一个小根堆来处理结束时间，再用一个小根堆来处理目前空闲的车道。对于目前的飞机，如果他到的时间与目前飞机道空闲下来最小的时间迟，那么就把他加到这个飞机道里面。否则如果小于，但是目前的飞机道比n小，就再加一个道。如果目前飞机道已经等于n就不能再开辟了。然后就把开辟的第一个车道的能停靠的飞机数作为国内飞机1个跑道的最大价值，前2个的和作为两个的最大价值……以此类推。然后枚举i求出mc[i]+md[n-i]的最大值就行了。
4:26 T1结束，然后就开始肝T3，因为T3貌似可做一点。然后就打了一个28分的模拟，T2暴力写了半天发现check不会写，0分滚蛋了。
T4直接输出我的幸运数字13
然后出来之后直接开回盐城，大概10:30到一个亲戚家住了一晚。
估计得分：
洛谷民间数据：
实际得分：
Day 1
早上6:00从盐城出发回家，在路上写的这篇游记（写这句话的时候是2021.10.24 8点整）。
贴一下我几个AC代码（J组目前还没有程序，J1,J2,J4比较简单就打了，J3太复杂懒得打，就等J组程序公布之后再贴吧）（如果打脸了没AC就自动Orz）
J1:
#include<bits/stdc++.h>
using namespace std;
int k,l,r;
int main(){
cin>>k>>l>>r;
if(l==r){
cout<<l%k<<endl;
return 0;
}
if(r-l>=k-1){
cout<<k-1<<endl;
return 0;
}
int lmod=l%k,rmod=r%k;
if(rmod<lmod){
cout<<k-1<<endl;
return 0;
}
else{
cout<<rmod<<endl;
}
return 0;
}J2:
#include<bits/stdc++.h>
using namespace std;
#define N 100001
int lx[N],rx[N],a[N],n,x,v,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
for(int j=1;j<i;j++)
if(a[j]<=a[i])
lx[i]++;
for(int j=i+1;j<=n;j++)
if(a[j]<a[i])
rx[i]++;
}
for(int j=1;j<=m;j++){
int opt;
cin>>opt;
if(opt==1){
cin>>x>>v;
for(int i=1;i<x;i++)
if(a[x]<a[i]&&v>=a[i]) rx[i]--;
else if(a[x]>=a[i]&&v<a[i]) rx[i]++;
for(int i=x+1;i<=n;i++)
if(a[x]<=a[i]&&v>a[i]) lx[i]--;
else if(a[x]>a[i]&&v<=a[i]) lx[i]++;
lx[x]=rx[x]=0;
for(int i=1;i<x;i++)
if(a[i]<=v)
lx[x]++;
for(int i=x+1;i<=n;i++)
if(a[i]<v)
rx[x]++;
a[x]=v;
}
else{
cin>>x;
cout<<lx[x]+rx[x]+1<<endl;
}
}
return 0;
}J3:
#include<bits/stdc++.h>
using namespace std;
#define N 10001
string opt[N],ad[N];
map<string,long long>S;
long long n,a[N];
long long check(string s){
long long c[5],cnt=0;
memset(c,0,sizeof(c));
s=s+'.';
if(s[0]=='.') return 0;
for(long long i=0;i<s.size();i++){
if(i==s.size()-1) break;
if((s[i]=='.'||s[i]==':')&&(s[i+1]=='.'||s[i+1]==':')) return 0;
if(c[cnt]==0&&s[i]=='0'&&s[i+1]>='0'&&s[i+1]<='9') return 0;
if((s[i]=='.'&&cnt==3)||(s[i]==':'&&cnt!=3)) return 0;
if((!(s[i]>='0'&&s[i]<='9'))&&s[i]!='.'&&s[i]!=':') return 0;
if(cnt>4) return 0;
if(s[i]>='0'&&s[i]<='9'){
c[cnt]=c[cnt]*10+s[i]-'0';
continue;
}
if(s[i]=='.'&&(cnt<=2||cnt==4)) cnt++;
if(s[i]==':'&&cnt==3) cnt++;
if(cnt>4) return 0;
}
for(long long i=0;i<=3;i++)
if(c[i]<0||c[i]>255)
return 0;
if(c[4]<0||c[4]>65535) return 0;
if(cnt!=4) return 0;
return 1;
}
int main(){
cin>>n;
for(long long i=1;i<=n;i++){
cin>>opt[i]>>ad[i];
if(opt[i][0]=='S'){
if(check(ad[i])==0){a[i]=-3;continue;}
if(S[ad[i]]!=0) {a[i]=-2;continue;}
S[ad[i]]=i;a[i]=-1;
}
else{
if(check(ad[i])==0){a[i]=-3;continue;}
if(S[ad[i]]==0) {a[i]=-2;continue;}
a[i]=S[ad[i]];
}
}
for(long long i=1;i<=n;i++){
if(a[i]==-3) printf("ERR\n");
else if(a[i]==-2) printf("FAIL\n");
else if(a[i]==-1) printf("OK\n");
else printf("%lld\n",a[i]);
}
fclose(stdin);fclose(stdout);
return 0;
}S1:
#include<bits/stdc++.h>
using namespace std;
#define N 100001
#define MP make_pair
#define F first
#define S second
#define PII pair<int,int>
priority_queue<PII,vector<PII >,greater<PII > >q;
priority_queue<int,vector<int>,greater<int> >g;
int c[N],d[N],s1,s2,n,m1,m2,cnt1,cnt2;
int mc[N],md[N];
struct node{
int x,y;
}a[N],b[N];
void dfs2(){
memset(d,0,sizeof(d));
memset(md,0,sizeof(md));
while(!q.empty()) q.pop();
while(!g.empty()) g.pop();
q.push(MP(b[1].y,1));
cnt2=1;d[1]=1;
for(int i=2;i<=m2;i++){
while(!q.empty()&&b[i].x>=q.top().F){
PII u=q.top();
q.pop();
g.push(u.S);
}
if(g.empty()&&cnt2<n){
d[++cnt2]=1;
q.push(MP(b[i].y,cnt2));
}
else if(!g.empty()){
int tmp=g.top();
g.pop();
d[tmp]++;
q.push(MP(b[i].y,tmp));
}
}
for(int i=1;i<=n;i++)
md[i]=md[i-1]+d[i];
}
void dfs1(){
memset(c,0,sizeof(c));
memset(mc,0,sizeof(mc));
while(!q.empty()) q.pop();
while(!g.empty()) g.pop();
q.push(MP(a[1].y,1));
cnt1=1;c[1]=1;
for(int i=2;i<=m1;i++){
while(!q.empty()&&a[i].x>=q.top().F){
PII u=q.top();
q.pop();
g.push(u.S);
}
if(g.empty()&&cnt1<n){
c[++cnt1]=1;
q.push(MP(a[i].y,cnt1));
}
else if(!g.empty()){
int tmp=g.top();
g.pop();
c[tmp]++;
q.push(MP(a[i].y,tmp));
}
}
for(int i=1;i<=n;i++)
mc[i]=mc[i-1]+c[i];
}
int cmp(node a,node b){
return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
int main(){
cin>>n>>m1>>m2;
for(int i=1;i<=m1;i++) cin>>a[i].x>>a[i].y;
for(int i=1;i<=m2;i++) cin>>b[i].x>>b[i].y;
sort(a+1,a+m1+1,cmp);sort(b+1,b+m2+1,cmp);
dfs1();dfs2();
int ans=0;
for(int i=0;i<=n;i++)
ans=max(ans,mc[i]+md[n-i]);
cout<<ans<<endl;
fclose(stdin);fclose(stdout);
return 0;
}总的来说感觉J组370,S组128的话还是挺不错的，祈祷别挂分。
Update on 2021.10.30
突然出分，官网直接炸了。大概加载了15分钟出了S组，挂了16分之我是sb。然后又过了大概15分钟J组出来了，370没挂分还挺好。
大概在JS的话，J组1=稳了，S组2=应该有，1=比较悬（换句话说，几乎没有可能）。总的来说还挺不错（反正初中生参加不了NOIP……无能狂怒）。
Update on 2021.11.3
JS突然给初中生参加NOIP了，S组80以上应该就可以了。
续命，备战NOIP，2021.11.20。