CSP 游记
CodePenguin · · 个人记录
初赛
前一周一直在机房复习，但是结果不尽人意，许多知识点缺漏仍然很大。虽然在洛谷的初赛模拟中早就轰出 rk14 的逆天成绩，但我还是不放心，毕竟理论上说，我确信我仍然能够出一份卷子让自己不及格。
但是毕竟一周的时间还是过于有限，我终究无法完成复习。最后仍然只是草草背完了所有排序算法和大部分 Linux 命令，语法只复习到了 C++17，C++20 是一个字都没看，刷了两套题而已。
早上把这几天的笔记重看了一下，单选的错题都重做了。然后做了点数学作业，锻炼了一下爆算能力（毕竟待会可是要手模程序的）。
中午瞟了一眼 J 组，没细想，但是感觉不难，甚至自认为能将近 AK，然后就开心地睡觉去了。
下午到考场外面面基，但其实大部分都是熟人。面到了一个学文科的 OIer，是 hzc 的朋友，这种情形无论在哪种竞赛应该都还是很稀有的。
进了考场里面有个小孩子就开始发表一些不当言论，老师也没太管他。
卷子不算难。但是他时不时发出的奇怪声音还是令人害怕，特别是他后面在打蚊子，一惊一乍的。他后面说什么踹死 60 个一中的就能进复赛，更是十分幽默。不过老师直到最后也没有赶走他。或许是怕他禁赛三年闭关修炼然后回来直接进队吧。
值得注意的是，这是我第一次在正赛中有十足地把握做对 linux 命令题。
9A 大作不是很放心，所以改掉了一个。
出来对答案，发现真是 9A 大作。CCF 下大分。
喜提 92 pts，已经超过数学高联复赛。忍俊不禁。
国庆假期
作业很多，写不完，写完还要复习，导致留给 OI 的时间不多了。
三场模拟赛加在一起刚好获得 400 分。可以说每一场的难度都很大，甚至有一场我四个题都不会。题解有的时候也直接看不懂。如何 CSP？
如何 CSP？
月考后
国庆之后就月考。月考总体说得过去，按下不表。
但是国庆期间模拟赛的幽默表现让我真切地感受到，如果再不多加训练，我就将要和 1= 无缘了。
但是练什么？这几场模拟赛之前，上一次集中训练还是在 7 月份（8 月开始在准备数竞的高联）。现在可以说是啥也不会，除了数学，剩下的模块，贪心，dp，图论这些，没有一个能做上位绿的，不是写挂就是根本不会。
这个问题是相当严峻的。于是我做了一个大胆的假设：
今年的 CSP 和去年的难度相似。并且不会有大模拟。
如果真是如此，中位蓝及以上的问题，我自然不用考虑了，我现在要做的，就是把那种下位蓝稳切的实力再找回来。而考虑到这也正是我在暑假集训的几次考试中表现出来的大概水平，这昭示着我所欠缺的只是想题的感觉和写代码的熟练度，或者常说的“手感”，而这要提上去，给我半个月，每天 2~3h 的训练，完全足够了。
于是我开始频繁翘掉晚自习前往机房，我们班再度成为了君主离线制的班级，不过好在这一次有了值日班长，不至于彻底君主离线。
这段时间内训练的细节我就不必写了，文笔本身很次，写出来无非又是大段地以扩写的形式抄袭“屏幕泛微光，键盘触手的微凉”“才曾几何时书生意气，探书海求真理”这类 OI 歌曲。但是确实很经常我是机房里面最后一个走的。
可喜的是，这段时间内，我的题感和码力都有了明显的恢复。最终，在考试的当天早上，在应对完一场数学考试的 vp 并在其中获得 141 的分数之后，我剩余的脑力仍然支撑着我在一个小时内解决 ABC 的两个 E 和一个 F。那一刻，我知道，我真的做到了。
如何 CSP？
就这样 CSP。
CSP
听说 J 组很难。惶恐。
中午睡太迟了，差点迟到，大家都拍完照了，有点幽默。
然后就匆忙进了考场。一看旁边是 lmh 巨佬，赶紧膜拜。
感觉今年一中怎么这么多人。。。
先开题，按照惯例，前 30min 不碰键盘，先浏览一下题目，然后在草稿纸上列下自己本次考试的策略，安排，之后严格执行。
看到 T1，最开始看成 i<j，还想着第一题这么搞一下是不是有玄机，会不会卡我贪心啊，然后发现好像不是这么回事，因为只要不等于都可以打。那这就没事了，直接桶排，然后从小到大扫一遍。秒了秒了。此时的时间是 14:37，因为看错题浪费了一会来证明看错的那个题里面贪心的正确性。
然后看 T2，物理题。看问你最多删几个，那就是最少留几个，一眼看出查到超速的探头对于每一个车来说是一个区间，于是这就成为了一个贪心的板子题。我们只需要求这个区间即可。考虑到精度，显然不能用浮点数，所以我们就考虑用速度平方那个公式来刻画。之后对 a 分讨也不难想，各种上下取整还需要做一下。这个时候是 14:45。
什么，我这就会 200 了？？我考前的论断正确了？
接着是 T3，一眼看出是 dp（总不能一场三个贪心吧）。先考虑常规的设一维，发现不行。然后再加一维，表示当前这个是红的还是蓝的，发现还是不行。此时已经接近 15:00，我果断去 T4，看完题目之后发现有 16 分的大模拟，于是我就在纸上写下了 100+100+100+16 的策略。
策略制定完成，这个时候是 15:01。去上了厕所，遇到 K2CO3，膜拜未遂。
我决定先写个 T1，给自己留个信心，然后一分钟写完， 15:06 就过了大样例。
接着写 T2，写的不快，之后大样例也过不去，一直 WA。后来发现是上下取整有一个地方搞错了。最后在 15:43 在大样例中有了正确性，但是被卡常了。
本着一中机子就是慢的精神，我决定先开 T3，同时也在草稿纸上写下“18:15一定回来给 T2 上快读。”
发现前面的思路不行主要原因或许在于没推性质，上来就试图给出一个的 dp，这是相当冒进和危险的。于是想了想性质，之前的训练中看到一个贪心优化 dp 的 题，这是用贪心确定了每次运垃圾的路线，这道题能不能也用类似的方法来确定每次转移的方向呢？
尝试后就成功了。发现必然用就近的那个相同的来和自己同色，否则会导致更长的一段被直接钦定颜色，这样带来的损失肯定是更大的。既然如此，我们只需要求出每个点的 pre，然后用 pre 的 dp 来转移就好了……吗？
很遗憾在推出这个性质之后我仍然没能成功地用位置+颜色表示出状态转移方程，或许菜就是这样的。那这怎么办啊，加维啊！于是我惊喜的发现，加一维表示它之前的颜色，然后就可以得到一坨非常好玩的转移方程，s 数组表示的是和前一个数相同的数的前缀和，其他的我不详细解释意思，毕竟这也不是题解。
但是或许可以让大家看到我考场上写这题时候的红温：
if(p[i]==i-1&&p[i]>0)
{
f[i][1][1]=max(f[i-1][1][0],f[i-1][1][1])+a[i];
f[i][0][0]=max(f[i-1][0][1],f[i-1][0][0])+a[i];
f[i][1][0]=max(f[i-1][0][1],f[i-1][0][0]);
f[i][0][1]=max(f[i-1][1][0],f[i-1][1][1]);
}
else if(p[i]==i-2&&p[i]>0)
{
f[i][1][1]=max(f[i-1][1][0],f[i-1][1][1]);
f[i][0][0]=max(f[i-1][0][1],f[i-1][0][0]);
f[i][1][0]=max(f[i-1][0][0],f[i-1][0][1]+a[i]);
f[i][0][1]=max(f[i-1][1][1],f[i-1][1][0]+a[i]);
}
else if(p[i]==0)
{
f[i][1][1]=max(f[i-1][1][0],f[i-1][1][1]);
f[i][0][0]=max(f[i-1][0][1],f[i-1][0][0]);
f[i][1][0]=max(f[i-1][0][1],f[i-1][0][0]);
f[i][0][1]=max(f[i-1][1][0],f[i-1][1][1]);
}
else
{
f[i][1][1]=max(f[i-1][1][0],f[i-1][1][1]);
f[i][0][0]=max(f[i-1][0][1],f[i-1][0][0]);
f[i][1][0]=f[p[i]+1][0][1]+s[i-1]-s[p[i]+1]+a[i];
f[i][1][0]=max(f[i][1][0],max(f[i-1][0][1],f[i-1][0][0]));
f[i][0][1]=f[p[i]+1][1][0]+s[i-1]-s[p[i]+1]+a[i];
f[i][0][1]=max(f[i][0][1],max(f[i-1][1][0],f[i-1][1][1]));
}
ans=max(ans,f[i][0][0]);
ans=max(ans,f[i][0][1]);
ans=max(ans,f[i][1][0]);
ans=max(ans,f[i][1][1]);
但是无论如何，编译错误是没有的，运行有一个地方稍微卡了一下，原因是把 p[i]+1 写成 p[i+1] 了，但是改了之后就对了，而且跑的飞快。
此时的时间刚刚来到 16:15，剩下 2.25h 写 T4，这是我从来没有遇到过的局面。
可惜 T4 没有太大突破。在接下来的时间里，我一直在纠结于 A 性质的实现细节，因为我原本的实现方法足以被卡爆，后来才想到可以用线段树维护，这样新加入点就是单点修改或者区间赋值为 null。
可以说想到这一方式为之后的一些发展提供了基础，不久之后就做出了 B 性质，但此时已经 17:03 了，考虑到预估代码长度已经超过了 2.5k，我只能开写，置其他分数于不顾了。
写完 17:40，但是挂了。调完的时候比赛还剩不到半小时，去给 T2 上了快读，之后检查了有没有逆天变量名，有没有 int 没返回，数组开够了没有，然后把所有大样例都测了一遍，可惜 T2 还是 T 了。
时间来到 18:22。我倒数第二次确认了文件名。
18:28。听到监考人员的指令，我再一次确认了文件名。
18:29。为了保证回收的顺利，我关闭了代码框和文件夹。
18:30。结束了。估分 100+[70,100]+100+[32,40]=[302,340]，总体还是令人满意的。猜一手 7 级线 100+100+50+16=266，自认为还算合理。
zzp AK，拜谢。
cch，wjq，wzh 都没有考很高，MA。这种难度的题，其实对于水平较高的人来说真的没什么用，大家都会只能比谁挂分少，而我比他们唯一的优势或许就是性格上比他们稳定，这也就意味着在这种难度我或许的确有一定优势。
但是难度上去了又该如何呢？在接受“能力范围之内可以打满”的好消息的同时，不要忘了一个显然的坏消息：我没有能力。我积累的 trick，以及所谓的“OI思维模式”，终究是比不过他们的。
但无论如何，这个分数是很不错的。
晚上去吃饭，发现和一个教练在同一个店。/jk
之后去打球，被杀穿了，悲。
考后
10-27 早上用刚起床的，没有在几个小时内刚刚被数学考试卷毒打过的脑子想了一下，我去，这个 T4，76pts 是 trivial problem 啊！红温了，昨天怎么没想到。
后面测了，T2 给我放过去了，好耶！T4 比较神奇，B 性质 T 的点全部在前面的那些小的并且没性质的点里面把分补回来了，这让我算挂分有一种让我写电解池镀铜的总反应方程式的美感。
340。牛逼。
最近抽点时间做一下 J 的压轴，然后就可以冲期中考了。考完再在役到 NOIP，再退役，然后期末复习的时候再在役一段时间到省选。
本来今天晚上想做的，但是学化学学到自闭了，就不做了。有时间我润去机房再慢慢写吧。
笑了，这就是三天打鱼两天晒网的，不谈竞赛只谈情怀的，嫌作业都是 trivial problem 不如 OI 写起来爽的闹碳间歇性 OIer 吗。果然是 whk 作业不够多、不够难导致的，他一个年段前五都考不到的人，还有这闲工夫！SARCASM！
Extra：CSP-J vp
vp 了一下 J 组，感觉 T4 没有大家说的那么难。直接依题意模拟，套路地发现每个点可能的前驱构成一个区间直接用单调队列优化一下这个过程，注意一些并不算困难（虽然也不算简单）的讨论即可。
#include<bits/stdc++.h>
using namespace std;
int n,k,q;
int tmp[300005];
vector<int> g[300005];
void lsh()
{
sort(tmp+1,tmp+tmp[0]+1);
tmp[0]=unique(tmp+1,tmp+tmp[0]+1)-tmp-1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<g[i].size();j++)
{
g[i][j]=lower_bound(tmp+1,tmp+tmp[0]+1,g[i][j])-tmp;
}
}
}
int f[103][200005];
inline void upd(int x,int y,int z)
{
//x round, y number, z can give it.
// if z ==-1, it means that more than 2 people can.
// if(x<=7)printf("UPD : %d %d %d\n",x,y,z);
if(f[x][y]==-1)return;
if(f[x][y]==0)f[x][y]=z;
else if(f[x][y]!=z)f[x][y]=-1;
}
int ok[200005],sum;
inline void ist(int x)
{
if(x<0)
{
ok[0]++;
}
else
{
ok[x]++;
sum++;
}
}
inline void dlt(int x)
{
if(x<0)
{
ok[0]--;
}
else
{
ok[x]--;
sum--;
}
}
inline void clr(int i)
{
ok[0]=sum=0;
for(int j=0;j<g[i].size();j++)
{
ok[g[i][j]]--;
}
}
deque<int>Q;
void dp()
{
for(int i=1;i<=n;i++)
{
for(int j=0;j<g[i].size();j++)
{
if(g[i][j]==1)
{
for(int kk=j+1;kk<g[i].size()&&kk-j+1<=k;kk++)
{
upd(1,g[i][kk],i);
}
}
}
}
// printf("ROUND:1\n");
// for(int i=1;i<=10;i++)
// {
// printf("%d ",f[1][i]);
// }
// printf("\n");
for(int r=2;r<=100;r++)
{
// printf("ROUND:%d\n",r);
for(int i=1;i<=n;i++)
{
// printf("%d %d %d\n",i,sum,ok[0]);
for(int j=0;j<g[i].size();j++)
{
while(!Q.empty())
{
int fr=Q.front();
if(j-fr+1>k)
{
Q.pop_front();dlt(f[r-1][g[i][fr]]);
}
else break;
}
// printf("... %d %d %d\n",g[i][j],ok[0],sum);
if(ok[0]>0||sum>1)
{
upd(r,g[i][j],i);
}
else if(sum==1)
{
// printf("IAKIOI : %d\n",f[r-1][g[i][Q.front()]]);
upd(r,g[i][j],i);
}
if(f[r-1][g[i][j]]==0||f[r-1][g[i][j]]==i)continue;
while(!Q.empty())
{
int bk=Q.back();
if(f[r-1][g[i][j]]==-1)
{
Q.pop_back();dlt(f[r-1][g[i][bk]]);
}
else break;
}
Q.push_back(j);
ist(f[r-1][g[i][j]]);
}
while(!Q.empty())
{
int fr=Q.front();
if(1)
{
Q.pop_front();dlt(f[r-1][g[i][fr]]);
}
}
}
// for(int i=1;i<=10;i++)
// {
// printf("%d ",f[r][i]);
// }
// printf("\n");
}
}
void work()
{
scanf("%d%d%d",&n,&k,&q);
memset(f,0,sizeof(f));
memset(tmp,0,sizeof(tmp));
for(int i=1;i<=n;i++)
{
g[i].clear();
int l;scanf("%d",&l);
for(int j=1;j<=l;j++)
{
int x;scanf("%d",&x);
g[i].push_back(x);
// tmp[++tmp[0]]=x;
tmp[x]=1;
}
}
// lsh();
dp();
for(int i=1;i<=q;i++)
{
int r,c;scanf("%d%d",&r,&c);
if(f[r][c]==0)printf("0\n");
else printf("1\n");
}
}
int main()
{
freopen("chain.in","r",stdin);
freopen("chain.out","w",stdout);
int T;cin>>T;
while(T--)work();
return 0;
}不过如你所见，我很擅长把简单的题目复杂化。正如这个题我写了将近 3k 一样。
T1,3,4 写完之后去写了会作业，回来发现 T2 没有在两分钟之内想出来是因为看错题了。唐。
然后随便写了写，就过了。
I AK CSP-J！（（（
官方成绩
S 340. 不多不少。
官方数据测 J 的 vp。第一遍的时候挂成了 395，遭遇卡常。
大怒，申请重测 重新交了一遍，然后波动过去了。
唐。