Day 0
下午试机，打了一下板子，发现编译都过不了人都傻了，结果是32位机。于是就以为整个机房都是32位机，考试的时候发现自己的机子是64位的，运气真好。试了一下对拍器，看来 库里的gcd没写假 。感觉这次会考 Tarjan缩点，然而并没考，于是又打了一下Tarjan缩scc，随便扔了个数据就不对又傻了，在大佬irc的指点下发现了错，貌似我自己就看出来了。到四点就直接回去被Chery赶回去了。晚上有看了下板子，随机看题，看洛谷关于CSP的讨论之类的，偶然发现初一大佬lrc交了一发我以前模拟赛没做出来的题的题解现在好像还是不会，看来我只配%，呜呜呜。
Day 1
上午睡到9：30，精神还行，起来又看了点题，中午睡完午觉就奔赴考场了。集合后大佬们都在说上午的CSP-J考了四道小模拟，于是下午应该就考四道大模拟。在bs教学楼前晃的时候%%奆佬 PG 。14：10左右进考场，调了一下Dev，听到周围传来阵阵键盘声，于是就加入大队伍开始打板子。差不多打到快读的时候监考老师开始念每年 \(n\) 遍的考试须知。“考试前所有人不能触碰键盘、鼠标等......咳咳，听着就行了” 。
打开题目，还好都是传统题，于是开始腾文件名，看到T3名字是 回文序列 ，还以为又考字符串。但还是平复心情一步一步往下翻，发现开了O2， 这不深吸一口新鲜氧气 。就以现在当做考试开始吧 ，14：30，开始看T1，想错题意还以为暴力都打不了，结果发现有一部分分其实模拟就能过，至于 \(1e5\) 的部分感觉要推点性质才能做。于是又看T2，一堆 \(()*?\) 飞过来，但直觉告诉我这道题很简单，因为显然裸的区间DP。读完题发现 \(O(n^4)\) 区间DP很好想，但貌似不太好写，而且好像有的情况会算重，就又去看一下T3。原来传说中的回文序列不是字符串题 ，题目意思很好理解，但一般遇到这种删头去尾的题就不太有好的思路，看了一眼 \(n\leq10\) 有 \(28\) 分，就决定做到T3的时候想一会儿，不能很快想出来就直接打暴力。T4题目奇怪，没太读懂附加点和题目中的射线，盯着那个图想了一会儿才看懂题目的标号，题目大体意思懂了，但具体的附加点到底是来干啥的还是不懂，语文真菜。所以还是决定顺序开题。
14：40，开始想T1，一开始以为廊桥增多可能会让之前的飞机的顺序发生变化，就不太好做，加上左边一个bs老哥，右边一个bz老哥疯狂突突突 就决定先打个模拟方便之后对拍让他们以为我也会。14：55过了三个样例，就开始分析性质。发现好像廊桥增多的时候原来能飞的飞机现在还是能飞，或许不在一个廊桥了，但所有廊桥下一次能用的时间的集合是包含原来的集合的（回想）好像到这里就正解了。但还是不太会，观察了一波样例，不得不说出题人给的表格很良心 。发现每架飞机都有个廊桥数分界点来决定其是否可以起飞，就想到了按每台飞机来算。于是迅速想到了一个假算法：统计每架飞机到达后之前还有多少架还没飞。一开始没想到是个假算法，于是就激动的敲了个树状数组上去，随便搞个样例就萎了。输出了一下每架飞机的廊桥情况再对比了一下表格，发现这算法假的彻底。已经15：10了，回想起奆佬 PG 说的要在一个半小时内切掉T1T2，要不然T3T4没时间，又听到左右两位老哥突突突，就慌了，顿时压力巨大，感觉要爆零了，就疯狂逼迫自己冷静下来，又看了一下表格，发现表格的轮廓是个美丽的山包，然后脑海中好像有了点灵感，就掏出样例，手动花了一下怎么计算每架飞机需要多少个廊桥才能飞，发现只需要维护一下之前在每个廊桥的飞机最早的起飞时间，每次替换掉廊桥下标最小的一个就行了，这不裸的线段树上二分吗，但害怕算法假了T1就真的无了，就仔细想了想，把第二个样例手动模拟了一下发现没有问题就开始码。15：40码完，调了一会儿，过了大样例后就开始对拍，一堆文件没有差别看起来真爽 。回头又看了一下线段树部分，感觉判断条件好像有点奇怪，就改了一下，也能拍上，考完后想不起来之前怎么写的，就担心对拍写假了，但又记得检查过对拍没问题，就不知道出了什么问题总之考完后很慌 。
T1就让它一直拍着，16：00开始想T2，好家伙，已经一个半小时了 。看着出题人给我的“超级括号序列”的要求，仿佛就像他在用手指着给我说，看！第一条是DP边界，第二条和第三条是DP转移 ，总感觉第二条好像会算重，但还是硬着头皮把 \(O(n^4)\) 的算法码上去，好像也不难写，很快就写完了。样例直接给我输出0，人都傻了，检查了五分钟才发现是 Inc 函数没传引用，加了个寂寞 。但第二个样例还是过不了，自己手玩算法发现写得没问题，算法好像假了，于是就想到了之前想的算重的问题，就放下键盘，开始理性分析。发现好像和之前模拟赛的一道题的思路类似，可以再开一个DP数组，之前的处理两边括号的，新开的处理括号拼接以及中间夹 \(*\) 的情况。过了样例后就开始想怎么优化，很快就发现复杂度瓶颈部分可以再开个DP数组优化掉，就随便码上去，直接过大样例。
16：45左右，开始想T3，由于确实没有什么很直接的思路，就开始手玩样例，发现每次的选择很少，而且很容易减掉很多枝，仔细想了想也没太想到很正确的算法，就直接码了DFS上去，大样例输出来一堆东西，原来是 多测不清空 。
貌似中途的时间有点记错了，反正T3没用这么长 ，17：30开始努力理解T4的意思，反复咬文嚼字后没有效果就开始看样例，通过看样例感觉到一种理解方式，一开始没啥思路就直接放掉了，回去检查了一下T1T2，顺便看了一下T3还有没有什么思路。17：50，又重新看了一下T4，发现如果按我的理解好像有一种可以做的二维DP，但我又怀疑题目理解错了，因为那个思路太好想了，但反复对比了题目和样例，感觉自己的理解很有道理，但现在已经18：05了，感觉时间不够，又害怕算法假了，就决定放掉T4，回来检查比较稳。虽然没有检查出来什么错，T1T2极限数据开了O2都能过，但稳一点终究是好事。
从考场出来，瞬间就闹麻了，先在隔壁考场遇到了大佬ycz，他做出来了T3，我直接开始%，但他T1T2好像都只打了暴力，期望得分略低，但不管怎么说tql。然后又遇到了奆佬 PG ，上来就说花了3个小时调T2，我瞬间懵住，貌似大家都考得不好。在楼梯上问大手子打了多少分，“345”，......，于是我直接开始%，并反思T1为啥想了这么久，导致T3T4这么惨。路上发现大家T1基本就只用了set和priority_queue，独留我一个线段树上二分的瑟瑟发抖。T4大手子还说可以用最小割来打暴力，于是我又对自己的理解产生怀疑......
晚上边吃火锅边看群里大佬们讨论，愈发感觉T1可能会假，当时我害怕极了 ，回家后把代码发给奆佬 PG 拿民间数据测了一下，还好T1T2都没挂，看到奆佬 PG 测了T3暴力，于是我也把我的扔给他测，\(28pts->80pts\) 是我万万没有想到的，应该是民间数据太弱了，虽然我确信我的算法剪枝很强。
Day 2
早上起来又把前三题扔到洛谷上跑民间数据，前两题还是没挂，T3还直接过了，脚造数据，差评! 后面发现大手子T3好像挂分了，以及T4考了个奇怪网络流转对偶图再跑建超源最短路什么的，语文真菜，确信 。
总结
期望得分：\(100pts+100pts+28pts+0pts=228pts\)
这次主要T1想得时间太久导致T3T4没时间想，而其背后的原因是我心理素质不够好，被旁边两位老哥干扰得不行，以及思路还是不够清晰，做题太过着急，写假算法也耽搁了不少时间（最近发现自己想题老是会很快想到一个假算法，这是个改进方向）。
Chery在考完那天晚上说T3最简单，然而我通看题目的时候以为题目难度就是按顺序排的，看来这方面也得多练。
虽然CSP-S相对于NOIP来说不那么重要，但也可以当做是一场NOIP的大模拟赛，更让我发现我和其他选手的差距，还有四个星期，NOIP冲啊！
Author:Sword
Date:2021.10.24
附录
考场代码：
T1:
#include<bits/stdc++.h>
#define inl inline
#define Rep for
#define re(i,x,y,z) for(int i=(x);i!=(y);i=(z))
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define repp(i,x,y,d) for(int i=(x);i<=(y);i+=d)
#define reep(i,x,y) for(int i=(x);i<=(y);i<<=1)
#define per(i,x,y) for(int i=(x);i>=(y);--i)
#define perr(i,x,y,d) for(int i=(x);i>=(y);i-=d)
#define pii pair<int,int>
#define piL pair<int,LL>
#define pLi pair<LL,int>
#define pLL pair<LL,LL>
#define vi vector<int>
#define vL vector<LL>
#define vii vector<pii>
#define viL vector<piL>
#define vLi vector<pLi>
#define vLL vector<pLL>
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define lowbit(x) (x&(-(x)))
using namespace std;
#define getchar() (SB==TB&&(TB=(SB=BB)+fread(BB,1,1<<15,stdin),SB==TB)?EOF:*SB++)
char BB[1<<16],*SB=BB,*TB=BB;
template<typename T>inl void read(T &n){
T w=1;n=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){n=(n<<3)+(n<<1)+(ch&15);ch=getchar();}
n*=w;
}
typedef long long LL;
typedef double db;
template<typename T>inl void chkmx(T &a,T b){(a<b) && (a=b);}
template<typename T>inl void chkmn(T &a,T b){(a>b) && (a=b);}
const int maxn=1e5+5,INF=1e9;
int n,m[2],N,tot;
pii a[2][maxn];
#define lc (id<<1)
#define rc (id<<1|1)
#define mid ((l+r)>>1)
int mn[maxn<<2];
int res[2][maxn];
void Push_Up(int id){mn[id]=min(mn[lc],mn[rc]);}
void Build(int id=1,int l=1,int r=N){
if(l==r) return mn[id]=INF,void();
Build(lc,l,mid),Build(rc,mid+1,r);
Push_Up(id);
}
void Update(int x,int v,int id=1,int l=1,int r=N){
if(l==r) return mn[id]=v,void();
if(x<=mid) Update(x,v,lc,l,mid);
else Update(x,v,rc,mid+1,r);
Push_Up(id);
}
int Query(int v,int id=1,int l=1,int r=N){
if(l==r) return l;
if(mn[lc]<v) return Query(v,lc,l,mid);
else return Query(v,rc,mid+1,r);
}
#undef lc
#undef rc
#undef mid
void Work(){
int now=0;
Build();
rep(i,1,m[0]){
if(mn[1]>a[0][i].fi) ++now,Update(now,a[0][i].se),++res[0][now];
else{
int p=Query(a[0][i].fi);
++res[0][p];
Update(p,a[0][i].se);
}
}
now=0;
Build();
rep(i,1,m[1]){
if(mn[1]>a[1][i].fi) ++now,Update(now,a[1][i].se),++res[1][now];
else{
int p=Query(a[1][i].fi);
++res[1][p];
Update(p,a[1][i].se);
}
}
rep(i,1,n) res[0][i]+=res[0][i-1],res[1][i]+=res[1][i-1];
int ans=0;
rep(i,0,n) chkmx(ans,res[0][i]+res[1][n-i]);
printf("%d\n",ans);
}
int main(){
freopen("airport.in","r",stdin);
freopen("airport.out","w",stdout);
read(n),read(m[0]),read(m[1]);
N=max(n,max(m[0],m[1]));
rep(i,1,m[0]) read(a[0][i].fi),read(a[0][i].se);
rep(i,1,m[1]) read(a[1][i].fi),read(a[1][i].se);
sort(a[0]+1,a[0]+m[0]+1),sort(a[1]+1,a[1]+m[1]+1);
Work();
return 0;
}
T2:
#include<bits/stdc++.h>
#define inl inline
#define Rep for
#define re(i,x,y,z) for(int i=(x);i!=(y);i=(z))
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define repp(i,x,y,d) for(int i=(x);i<=(y);i+=d)
#define reep(i,x,y) for(int i=(x);i<=(y);i<<=1)
#define per(i,x,y) for(int i=(x);i>=(y);--i)
#define perr(i,x,y,d) for(int i=(x);i>=(y);i-=d)
#define pii pair<int,int>
#define piL pair<int,LL>
#define pLi pair<LL,int>
#define pLL pair<LL,LL>
#define vi vector<int>
#define vL vector<LL>
#define vii vector<pii>
#define viL vector<piL>
#define vLi vector<pLi>
#define vLL vector<pLL>
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define lowbit(x) (x&(-(x)))
using namespace std;
#define getchar() (SB==TB&&(TB=(SB=BB)+fread(BB,1,1<<15,stdin),SB==TB)?EOF:*SB++)
char BB[1<<16],*SB=BB,*TB=BB;
template<typename T>inl void read(T &n){
T w=1;n=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){n=(n<<3)+(n<<1)+(ch&15);ch=getchar();}
n*=w;
}
typedef long long LL;
typedef double db;
template<typename T>inl void chkmx(T &a,T b){(a<b) && (a=b);}
template<typename T>inl void chkmn(T &a,T b){(a>b) && (a=b);}
const int MOD=1e9+7;
inl int inc(int a,int b){return a+b>=MOD ? a+b-MOD : a+b;}
inl int mul(int a,int b){return 1LL*a*b%MOD;}
inl void Inc(int &a,int b){((a+=b)>=MOD) && (a-=MOD);}
const int maxn=5e2+5;
int n,K;
bool ok[maxn][maxn];
int f[maxn][maxn],g[maxn][maxn],h[maxn][maxn];
char S[maxn];
inl bool Check(int pos,char ch){return S[pos]==ch || S[pos]=='?';}
int main(){
freopen("bracket.in","r",stdin);
freopen("bracket.out","w",stdout);
scanf("%d%d",&n,&K);
scanf("%s",S+1);
rep(l,1,n) rep(r,l,min(l+K-1,n)){
if(Check(r,'*')) ok[l][r]=1;
else break;
}rep(i,1,n) ok[i][i-1]=1;
rep(len,2,n){
rep(i,1,n-len+1){
int j=i+len-1;
if(Check(i,'(') && Check(j,')')){
if(ok[i+1][j-1]) f[i][j]=1;
Inc(f[i][j],g[i+1][j-1]);
rep(k,i+1,j-1) if(ok[i+1][k]) Inc(f[i][j],g[k+1][j-1]);
per(k,j-1,i+1) if(ok[k][j-1]) Inc(f[i][j],g[i+1][k-1]);
}
g[i][j]=f[i][j];
rep(o,i,j-1) Inc(g[i][j],mul(g[i][o],f[o+1][j]));
rep(o,i,j-1) Inc(g[i][j],mul(g[i][o],h[o+1][j]));
rep(o,i,j-1) if(ok[i][o]) Inc(h[i][j],f[o+1][j]);
}
}printf("%d\n",g[1][n]);
return 0;
}
T3:
#include<bits/stdc++.h>
#define inl inline
#define Rep for
#define re(i,x,y,z) for(int i=(x);i!=(y);i=(z))
#define rep(i,x,y) for(int i=(x);i<=(y);++i)
#define repp(i,x,y,d) for(int i=(x);i<=(y);i+=d)
#define reep(i,x,y) for(int i=(x);i<=(y);i<<=1)
#define per(i,x,y) for(int i=(x);i>=(y);--i)
#define perr(i,x,y,d) for(int i=(x);i>=(y);i-=d)
#define pii pair<int,int>
#define piL pair<int,LL>
#define pLi pair<LL,int>
#define pLL pair<LL,LL>
#define vi vector<int>
#define vL vector<LL>
#define vii vector<pii>
#define viL vector<piL>
#define vLi vector<pLi>
#define vLL vector<pLL>
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define pb pop_back
#define lowbit(x) (x&(-(x)))
using namespace std;
#define getchar() (SB==TB&&(TB=(SB=BB)+fread(BB,1,1<<15,stdin),SB==TB)?EOF:*SB++)
char BB[1<<16],*SB=BB,*TB=BB;
template<typename T>inl void read(T &n){
T w=1;n=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch)){n=(n<<3)+(n<<1)+(ch&15);ch=getchar();}
n*=w;
}
typedef long long LL;
typedef double db;
template<typename T>inl void chkmx(T &a,T b){(a<b) && (a=b);}
template<typename T>inl void chkmn(T &a,T b){(a>b) && (a=b);}
const int maxn=5e5+5;
int T,n;
int a[maxn<<1],t[maxn],pos[maxn<<1];
vi g,h;
bool Work(int l,int r,int x,int y){
if(r-l+1==n){
int nowx=1,nowy=2*n;
Rep(auto p:g){
if(p==nowx) putchar('L'),++nowx;
else putchar('R'),--nowy;
h.eb(a[p]);
}
per(i,(int)h.size()-1,0){
if(a[nowx]==h[i]) putchar('L'),++nowx;
else putchar('R'),--nowy;
}puts("");
return 1;
}
if(l+1<=x-1 && pos[l]==x-1){
g.eb(l);
if(Work(l+1,r,x-1,y)) return 1;
g.pb();
}if(l+1<=x && y+1<=r && pos[l]==y+1){
g.eb(l);
if(Work(l+1,r,x,y+1)) return 1;
g.pb();
}if(l<=x-1 && y<=r-1 && pos[r]==x-1){
g.eb(r);
if(Work(l,r-1,x-1,y)) return 1;
g.pb();
}if(y+1<=r-1 && pos[r]==y+1){
g.eb(r);
if(Work(l,r-1,x,y+1)) return 1;
g.pb();
}return 0;
}
int main(){
freopen("palin.in","r",stdin);
freopen("palin.out","w",stdout);
read(T);
while(T--){
read(n),g.clear(),h.clear();
rep(i,1,n) t[i]=0;
rep(i,1,n<<1){
read(a[i]);
if(t[a[i]]) pos[i]=t[a[i]],pos[t[a[i]]]=i;
else t[a[i]]=i;
}g.eb(1);
if(!Work(2,n<<1,pos[1],pos[1])){
g.pb();
g.eb(n<<1);
if(!Work(1,(n<<1)-1,pos[n<<1],pos[n<<1])) puts("-1");
}
}
return 0;
}
T4:没打
方便给未来的自己看看现在的奇葩写法。
Update 10.31
官方成绩：$$100pts+100pts+60pts+0pts=260pts$$
T3离正解差几个 return 。没想到T4的最小割暴力如此好想......
标签：ch,int,rep,vector,2021,pair,游记,CSP,define From： https://www.cnblogs.com/Sword-K/p/16840879.html