主页
搜索
最近更新
数据统计
赞助我们
系统公告
1
/
1
请查看完所有公告
CSP 2022 游记
最后更新于 2025-06-15 20:53:27
作者
konyakest
分类
个人记录
复制 Markdown
查看原文
更新内容
### 统计 共计1923词（typora显示） ### Day -?? 初赛日 一大早看见了zxy、zkx、ycy、zjs等熟悉的面孔 8:30考试，8:00就进了考场 由于姓氏优势，来到了离出入口最近的考场 照例先上个厕所 话说 j 组考牛顿迭代？ 提前交了卷，发现zkx、ycy也在讨论 >ycy：那道判断题算出来是448，题目是449，所以它是错的 > >zkx：是的 > >算出四百五十多认为自己算错后选择了对的我：... 下午 感觉csp-s和csp-j难度差不多 耗尽了所有的做题时间 ccf不讲wood，出了膜负数、归并kth（一直用nth_element的我表示很淦 《关于宇宙射线破坏基数排序》  ### Day random[-??+1,-?-1] 摆烂 发现有向图联通是强联通 子串包括空串 …… 爆了好多分 ### Day -? - 出分力 - csp-j 81 - csp-s 74 > ~~山不在高，有仙则名；分不在多，能过就行；斯是瞎蒙，惟吾rp高~~ - 打模板 > 图论: > > dsu，换根dp，树上背包，最小生成树，spfa，dijkstra，tarjan > > dp: > > 背包，单调队列 > > 字符串: > > kmp，trie > > 数学: > > 矩阵优化递推，快速幂，高斯消元，排列组合 > > 数论: > > 筛法，bsgs，excrt > > 数据结构: > > st表，线段树，树状数组，莫队 - 摆烂 ### Day -1 - 教练强调了注意事项 - [经过qtc验证，``freopen`` 后 ``ios`` 不会炸](https://www.luogu.com.cn/discuss/519186) - 发现新的 rp++ 方式：``unsigned long long rp=-1;`` - 还剩 > 图论: > > dsu，树上背包，tarjan > > 字符串: > > kmp > > 数学: > > 排列组合 > > 数论: > > 筛法，excrt > > 数据结构: > > 莫队 没打，摆烂 ### Day 0 #### J - 目标：三百多pts，如果比去年简单就AK （赛后：确实比去年简单，但AK无望了） 早上醒来不知道为什么想学中缀转前缀 于是bdfs学了（但搜索时搜成了中缀转后缀，于是实际上学了中转后） > emmm...**感觉没什么卵用**（记住这句话，后面要考的） > > ——[CSP-J/S2020游记 @SpadeA261](https://www.luogu.com.cn/blog/SpadeA261/csp-js2020-you-ji) 大约8:00进考场 开始打线段树，打了一半有人提醒我坐错位置了  来到正确位置，发现上面有另一个人的东西，但没人——他也坐错了  一直等那个人出现，让他把东西移开 此时已经剩5min，于是打了头文件后静待开题 - T1 直接暴力计算pow，溢出时输出NO，并且特判1 - T2 看标题，还以为是字符串，结果是数学 一开始想枚举因数，但复杂度惊人 于是拿起草稿纸推式子，过程很顺畅 发现要sqrt，联系[这道题](https://www.luogu.com.cn/problem/P8255)想到sqrtl 但是不放心sqrtl精度，于是大概这样验证了一下： ```c++ #define int long long for(int i=1;i<=1e9;i++){ if((int)sqrtl(i*i)==i); else cout<<"wa",exit(0); } ``` 验证通过，于是放心用了 T1+T2半个多h AC - T3 看题目乐 于是大概背了一遍早上学的 （直到我调试输出时，我才知道早上学的是转后缀，不是前缀） 转成后缀后发现不好处理，于是又转为了前缀（伪代码） ```cpp string trans(string& s){ if(s.back()是0/1) return s; char c=s.back(); s.pop_back(); string s1=trans(s),s2=trans(s); return c+s2+s1; } ``` 然后处理 小插曲：写最终处理前缀式时（solve函数中），写了 ```cpp bool solve(bool flag){//1:not duanlu 0:duanlu if(ss[pos]=='|'){ pos++; if(!flag) return solve(0)||solve(0); ... } ... } ``` 出了奇妙的锅 百思不得其解 后来才反应过来，c++短路了  改成 ```cpp bool f1=solve(0),f2=solve(0); return f1||f2; ``` 后对了   ~~第一次讨厌c++优化~~ 愉快AC前三个大样例，第四个大样例1.2s 开O2后重试，仍然是1.2s 感觉不可思议：$O(n)$ 跑 $10^6$ 1.2s ? 看了一下，发现转前缀复杂度不对 于是改为了建表达式树转前缀 ~~于是有了中缀->后缀->表达式树->前缀->求解的离谱代码~~ 不到0.1s过样例4 - T4 我太菜了，想了半天只想到 $O(600*600n)$ 的dp （赛后：好像能过） 怕 $n=500$ 时T，于是改写部分分 > 他们给的部分分实在太多了 $a,b \le 100$ 时和 $k=0$ 时足足有75分 于是打了并通过了全部样例（全比赛最水的大样例） ```cpp if(k==0) case2::solve(); else if(check()) case1::solve(); else cout<<rand()%(n+k)+1; ``` ~~自测时没有rand到分，希望CCF评测时可以出现奇迹！~~ 检查时，发现T1是1e9算溢出，而我写的INT_MAX。。。 又一次检查时，发现是严格大于算溢出，而我写的大于等于。。。 。。。 最后不到10min和考试结束依次检查时没事干，开了几把扫雷，都输了 一怒之下开了蒟蒻模式：   - 自己估分：100+100+100+75=375 #### S - 目标：120pts 到达考点先背了kmp~~（这次真的没用）~~ 两点多进考场，~~没有坐错座位~~ 先打线段树（push_up、push_down实现没写） 看了看还有时间，于是查找头文件把pbds_tree的typedef写了（不会背pbds定义的单词的我） 看了看还有时间，于是把树状数组写了 看了看还有时间，于是把[二维偏序](https://baizongyu314.blog.luogu.org/er-wei-pian-xu-mu-ban)写了 还剩四五行没写完就开考了 解压题目后坚持写完才开题 - T1 想了20min，没想出来，跳过 - T2 很好想到维护几个区间最值： > - 最大数 > - 最小数 > - 最大负数 > - 最小正数 > - 是否有0 想到ST表，但没有经受住旁边线段树的诱惑 测了一下，前两个样例过了，后两个样例WA了 好在经过半个小时的不懈努力，发现了问题： > 最小正数初值（如果没有正数返回）为LLONG_MAX，与另一个数乘时溢出了 特判后，终于全过大样例 （长舒一口气，继续） - T3 对于我这种蒟蒻来说，T3T4就是暴力的乐园 正解压根没想 不过题意很明确，模拟很方便 用set存图，就能快速删边、加边了 想到了unordered_set和gp_hash_table，但是害怕会出现和deque数组那样尴尬的事情，就没用 撸完发现样例WA了 发现自己删点理解错了，略加改动就过了应该过的样例 - T4 感觉选的点都在链上，于是想到把链薅下来DP（$O(kqn)$） 但是写好后发现k=3时爆了 仔细想想，发现k=3时可能不在链上 于是感觉自己T4寄了 - T1 打T1暴力 打了 $O(n^4)$ dp 和 $k=0$ 时的暴搜 打完发现暴搜复杂度没有保证，可能会寄，但是想不到其他方法了 ```cpp if(n<=20) case1::solve(); else if(k==0) case2::solve(); else cout<<"I am too ruo to solve this situation"; ``` - 估分：[40,55]+100+40+[24,44]=[208,239] ### Day 1 **注：以下score和rank均为预估** 自测 J：（小图灵，luogu均为）100+100+100+75=375，小图灵预估``SX.rank(*this)==3`` S：（INFOJ，luogu均为）55+100+40+28=233 ### Day ？（today） - 小图灵S预估出来了，55+100+40+24=219，预估``SX.rank(*this)==7``
正在渲染内容...
点赞
0
收藏
0
