csp-j2019游记

~~我一pj蒟蒻这点水平还来写游记？~~ 算了，毕竟是第一次，记录一下吧 # noip->csp 话说我跟竞赛是不是天生八字不合啊...... 小学的时候学小奥，等我开始报名比赛，当时似乎所有竞赛都被叫停了，就剩一个~~特别水~~的建模 初一学了OI，到初二准备参加普及组，可是......~~你们都知道~~，因此我就成了一个从未参加过noip的OIer 我真是个~~竞赛杀手~~ &nbsp; # csp-j2019 ## day -34 luogu秋令营pj第一次膜你赛居然让我一个蒟蒻得了$rank1$，算是找回点信心吧..... ## day -29 明天就初赛了我居然还在熬夜补数学？ ## day -28 **csp-j初赛** 本来这几天这天学校是要研学的，所以我们考初赛的就只好呆在学校了~~好像只有3个人这样欸~~ ~~看我都为OI放弃研学了是不是应该让我AK？~~ 中午在家看了看tg的题，复习了一下语法细节和排序相关的内容 &nbsp; 济南是用机试，可能是因为报的人少？ 话说那网页真的好卡...... 不过今年初赛明显的改变就是终于没有那些~~令人厌恶的~~计算机历史了，多了对数学能力的考查 阅读程序也终于不再是只写结果了，虽然变成了全选择但难度我认为没降 其实这样也挺好，减少了考那些对OI没用东西，初赛也能一定程度上反应真实水平了 &nbsp; 晚上还要上物理课..... 自测应该差不多80左右，群里的大佬说应该能过。 看到青岛当天就公布成绩了欸，看到大佬们都80+，90+，心里还是有点慌 ## day -23 提前知道成绩了，85.5，居然比自己估的还高，而且我还是市第五欸 前面的单选错的不多，主要是最后一个补全程序和那些阅读程序太恶心了~~可能也是我太蒻~~ 那些能90+的也太强了吧%%% 开始冲刺复赛...... ## day -11&-10 期中考试，这几天基本没怎么学OI 怎么每年都和期中在同一段时间啊 像我们竞赛氛围不浓的弱省，平时能拿出点时间来学OI就不错了，期中附近自己想学学校、家长也不给这个时间啊 ## day -2 luogu的最后一场膜你居然在工作日下午，话说这是我学OI以来第一次停课 感觉这次FMT没暑假那次有意思，可能更侧重考前答疑吧 晚上终于通过了pj练习场，~~数论题太毒瘤了~~ ## day 0 上午做几道任务列表里的题，下午就去考场了 火车位置竟然还能排错，还要换车厢... 在宾馆刷几道dp，信心-- ## day 1 没去报道，继续刷dp，感觉没啥用了 ~~我和dp真是没缘~~ 午觉醒来感觉更困了，看了看博客里exgcd的板子，但感觉可能用不上......  &nbsp; 进考场，调好编译器，可别人都有题就我电脑上没题是什么鬼？网也关了只能拿优盘考 ~~我们考场居然还有不会文件读写的问监考怎么写freopen~~ 读一遍题，感觉总体不难，至少没有去年摆渡车那种大dp T1，字符串读入和简单处理，长度还是确定的，真是创了pjT1难度的新低 T2，只能算模拟吧，手写一个队列，如果是地铁就把时间和价格入队，是公交就先把过时的优惠卷出队，再依次查找符合条件的价格 我是把用过的优惠卷先不出队（否则容易超时），标记时间和价格为极小值，这样接下来就会被弹出 结果样例2就出问题了，这才发现编译器的调试不能用，一摁F5就error，只能手动输出变量调试了~~我可以把考不好赖在编译器身上吗？~~ 我居然把$continue$都写成了$break$...... 大样例还是没过。不管了直接看T3吧 果然是复杂的dp~~没思路，考完才知道并不太复杂~~ 厕所是个好地方，你总能在那找到灵感思路~~然鹅我并没有~~ 所以骗分： - $t=1$直接输出m - $n=1$和$n,t\leq4$,搜索，感觉过不了，我怎么连复杂度都没估计就开始写了啊~~dfs套dfs？也许我这个程序等量子计算机出世才能跑出样例来吧~~ - $t=2$完全背包，以两天的价格差为价值出考场才想起来输出忘加m了... - 剩下的写了个很扯的dp，连样例都没过 ~~果然我还是死在dp上了~~ 回头看T2，突然发现我只改了用过优惠卷的时间没改价格，改完程序终于过了大样例~~光T2就调了一个多小时~~ 看T4，自以为图论不错但还是只想到奇偶判断就不会写了 写了个爆搜，到1号就判奇偶性 期望得分：$100+100+10+40=250$ 实际得分：$100+100+10+15=225$ 不过为什么考试的时候膜你抄的旋律一直在脑海中回想 &nbsp; 出考场，听大佬们说T3就是完全背包，之后恍然大悟，每一天是独立的，那不就是跑$t-1$个完全背包吗？ 之后T4好像是记录点到1好点的路径奇偶之类的~~反正我不会~~ 听kkk说这是pj最简单的一次~~那为什么我还不会QAQ~~ 晚上吃饭的时候看洛谷上说T3T4都是原题欸，可惜我没做到 两道原题而且还是T3T4这CCF也太过分了吧...... &nbsp; 晚上回去把那道[T3原题](https://www.luogu.org/problem/P2938)写了，才发现这题原来这么简单 其实这道题想不出真是不应该，$T=2$的部分分不就是提示吗。哎还是平时思考的太少（关于比赛的反思下面还会提到） 大佬们说今年pj真的简单了很多，心中也有点慌能不能上1=，毕竟我估的分也不一定能达到 ## day 2 在回去的车上一直用手机看洛谷，各种300+的大佬还在装蒻......   ~~好像一共就留下这么几张模模糊糊的照片~~ &nbsp; 晚上看到洛谷上好多初三高三的发了AFO的帖，希望他们都能在OI中有所获得吧。不过大学还有ACM呢 其实我毕竟才第一年，而且就算考不好也用不着AFO吧。~~心情终于好点了~~ ~~明天就去上课了才发现还有一堆作业等着我~~ ## day 3 继续写游记...... 还有一堆周末辅导班的视频要看...... 看到zcysky发的帖子也是感慨一番 虽然自己只入坑不到一年，但OI已经给我了不少改变 ~~文化课下降？~~ 其实大多数人学OI为的肯定也不只是最后的那个奖吧，能和志同道合的一些人一同奋斗就已经是值得的了，所以享受这个过程吧 ## day 4 游记终于基本写完了，语文不好太费劲了 ~~而且一天天数日期真是太麻烦了~~ ## day 7 牛客输考号查成绩只有$0+100+0+0=100$ 全市连前50%都进不了，~~而且T1为什么会爆零呢？~~ 一下午的好心情顿时没了。。。~~想知道为什么有好心情吗~~ ## day 17 下午出成绩，$100+100+10+15=225$,还是比估的低了点，应该能1=吧 &nbsp; # 反思&总结&题目代码 T2调了一个多小时真是太浪费时间了.... 其实也不是时间规划的问题，因为就算时间比预计的长了也不能放弃T2啊 所以以后写题的时候出了错尽量不要接着就跑到题解区去对照，那样对调试能力的提高真的不大。其实自认为考场上调试能力比代码能力有时候更重要吧，因为一个代码写出来调半天过不了在比赛上是很浪费的~~我太蒻了~~ 而且不算太难的题本地多花点时间调一调，尽量一次AC 还有题解的问题，我感觉自己有时候就是太依赖题解了，即使不看代码好多题的思路还都是题解提供的。这就导致考场上即使比较简单的转换自己也完成不了 有时候自己想一道题稍微有点思路就想去题解区看看是否正确，其实这样虽然能减少一些时间，但对自己的提升真是少了好多。因为即使有的题有了点模糊的思路也不一定能实现出代码。 而且就算是错误的思路也能让自己总结出一些教训（比如往哪些方面思考必定时死胡同）之后避免吧 还是要多思考吧 所以我要立flag了，下次csp之前简单的蓝题和蓝题以下**不看题解不看题解不看题解** &nbsp; T1,cin读入自认为最保险 ```cpp #include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<iomanip> #include<queue> #define LL long long #define R register char s[15]; int main(){ std::freopen("number.in","r",stdin); std::freopen("number.out","w",stdout); std::cin>>s; int ans=0; for(R int i=0;i<8;i++) ans+=(s[i]=='1'); std::printf("%d",ans); return 0; } ``` T2,day 1中说了,t和ti是时间，pr和pri是价格 ```cpp #include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<iomanip> #include<queue> #define LL long long #define R register int n; LL t[100006],pr[100006]; int l=1,r=0; LL ans; int main(){ freopen("transfer.in","r",stdin); freopen("transfer.out","w",stdout); int bus=0,sub=0; std::scanf("%d",&n); for(R int i=1;i<=n;i++){ LL ty,pri,ti;std::scanf("%lld%lld%lld",&ty,&pri,&ti); if(ty){//bus bus++; int flag=1; for(;;l++){//find right time if(l>r){ ans+=pri; flag=0;break; } if(ti-t[l]<=45) break; } if(!flag) continue;flag=1; R int use; for(use=l;;use++){//find right price if(use>r){ ans+=pri; flag=0;break; } if(pr[use]>=pri) break; } if(!flag) continue; t[use]=-99999999;pr[use]=-99999999; } else{//subway sub++; ans+=pri; t[++r]=ti; pr[r]=pri; } // std::printf("%lld l=%d r=%d i=%d n=%d\n",ans,l,r,i,n); } std::printf("%lld",ans); return 0; } ``` T3，~~t遍完全背包考场上为啥就没想到呢？。。。~~ ```cpp #include<cstdio> #include<algorithm> #include<iostream> #include<cmath> #include<iomanip> #include<cstring> #define R register #define EN printf("\n") #define LL long long inline int read(){ int x=0,y=1; char c=std::getchar(); while(c<'0'||c>'9'){if(c=='-') y=-1;c=std::getchar();} while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();} return x*y; } int n,m,t; int w[106],v[106]; int f[10006]; inline void max(int &x,int y){(x<y)&&(x=y);} int main(){ t=read()-1;n=read();m=read(); for(R int i=1;i<=n;i++) v[i]=read(); while(t--){ for(R int i=1;i<=n;i++){w[i]=v[i];v[i]=read();} std::memset(f,0,sizeof f); for(R int i=1;i<=n;i++) for(R int j=0;j<=m;j++) if(j>=w[i]) max(f[j],f[j-w[i]]+v[i]-w[i]); m+=f[m]; } std::printf("%d",m); return 0; } ``` T4,分别存奇偶最短路，注意一号点可能是孤立的，就是没有边与它相连。因此bfs初始要从与一号点相接的点开始 ```cpp #include<cstdio> #include<algorithm> #include<iostream> #include<cmath> #include<queue> #include<cstring> #define R register #define EN printf("\n") #define LL long long inline int read(){ int x=0,y=1; char c=std::getchar(); while(c<'0'||c>'9'){if(c=='-') y=-1;c=std::getchar();} while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();} return x*y; } int n,m,qq; int to[200006],fir[100006],nex[200006],tot; int dis[100006][2]; inline void add(int u,int v){ to[++tot]=v;nex[tot]=fir[u];fir[u]=tot; } std::queue<int>q; inline void bfs(){ std::memset(dis,0x3f,sizeof dis); for(R int i=fir[1];i;i=nex[i]) dis[to[i]][1]=1,q.push(to[i]),q.push(1); while(!q.empty()){ int u=q.front();q.pop(); int w=q.front();q.pop(); for(R int i=fir[u];i;i=nex[i]){ int v=to[i]; if(dis[v][!(w&1)]>w+1){ dis[v][!(w&1)]=w+1; q.push(v);q.push(w+1); } } } } int main(){ n=read();m=read();qq=read(); for(R int i=1;i<=m;i++){ int u=read(),v=read();add(u,v);add(v,u); } bfs(); while(qq--){ int a=read(),lev=read(); if(dis[a][lev&1]<=lev) std::puts("Yes"); else std::puts("No"); } return 0; } ``` &nbsp; ### 最后以zcysky那个帖中的几句话结尾吧 > 愿你们的人生，除了算法竞赛的深度，还有ctf的广度。愿你走遍大江南北，带着一身技术，去做自己喜欢的事。 > 这一次，让我们不计输赢，只谈乐趣。 > code for win × hack for fun √ > 人活着，最重要的还是开心。 放下对输赢的执念，做个黑客吧 &nbsp; ~~大多流水账，毕竟众所周知OIer的语文都不好~~