河南2023青少年程序设计能力认证游记
2023.1.18 WC闭幕式当天
收到了省内计算机学会开办省赛的通知 （完了eeee作业又双叒叕写不完了）
\(Day~ -8 至0\)
先去了一天高中部，第一次见程序学长，和他vp了一场cf，中午一起去高二的寝室休息，见了好多高中的其他学科竞赛生（高二信竞只剩一个人了qwq）
下午看了一下数论分块，感觉自己码力并不好，稍复杂一些的式子就不好调出来了，
当天收到了初中部物理数学竞赛上课的通知……
没办法，去京广校区上了两天数学物理竞赛课，感觉还是省赛重要呃，给前班主任和现班主任请了假，然后跑到高中部去了
接着vp cf的比赛…… 然后就是主要开始做往年csps和noip的题……之前几乎都没写过呃，
光csps2020的T3函数调用和学长一起折腾了两三个小时呃，
但是纯靠自己把摆渡车和一道容斥+dp几乎写了出来，感觉还不错……希望省赛出dp也会吧（
(但是年前年后20天都没写学校课内作业……开学测试要挂)
考前一天晚上收拾了准考证和一些资料，
指导了一下同桌比赛时的注意事项（打电话而已）
想到次日可以见还未谋面的zyb等同学以及学校的同学，十分激动。
\(Day~1\) 比赛日
考点离家很近，走路估计不到半个小时就能到，开车只用十分钟
六点五十多起了床，吃好饭，确认东西拿好就出发了，上午普及8:30开始到12:00结束，所以七点半就进考场了，四楼一个机房，计算机windows7，远古cpu。
由于进场比较早，罚 干坐了30min
8:15开始允许动机子，装了一下MinGW，配置了一下环境，
8:30准时发题，
花了十分钟读完题，
T1模拟，T2前缀和，T3搜一下吧或许，T4看着有点神奇，每个点的特殊性质都写在题目上
一个小时左右过了前三题大样例。
然后去想T4，
分析40min后发现难点在于处理马走日，
于是去想。
大意是一个询问：平面直角坐标系上从一点到另一点，只能跳马，求最小步数，坐标范围正负1e8；每个点1s，1000组询问
直接搜不行，
于是考虑打表找规律。
凭借十分糊涂的脑子，
一个简单的 \(\mathcal{O}(n^2)\) 就可以搞定的打表程序，我却当时不知为何写了个复杂度应该不低于 \(\mathcal{O}(n^4)\) 的打表程序，
又在使用的机器老旧cpu的鼎力加持下，
20*20的数据都要跑半分钟……再大都是指数级时间增长，
但是硬是没想到可以写 \(\mathcal{O}(n^2)\) 的打表。。。。
要命的是折腾了一个多小时我几乎找不到什么有用的规律。
十一点决定先把T4其他特殊性质分写了，
于是花了十几分钟打完了一个硕大的分类讨论，
不出意外，第一个样例都没过（因为涉及到马走日），但是后面俩都过了。
11:30了，由于之前没多少比赛经验，决定先检查一下。
查了一下前三道，确保文件读写没问题且大样例都能过，然后先交了前三题上去，
然后感觉T4的马走日正解难以想出，于是手造数据去hack我的分类讨论，
成功改掉一个bug
比赛结束前交上去了。
出了考场，并不高兴……普及组是冲着满分来的呃，但是T4花了两个多小时也没切……
估分 100+100+100+[10,60] = [310,360]
希望前三题别挂
（对了……一上午没见一个认识的同学）
回了家，吃碗饺子和一些牛肉，躺了一会儿，跟同桌打了个电话，
他说他感觉把前三题写了，但是T2因为没有学过时间复杂度（是的，他们学的确实比较晚且慢且少，新的学期线下了，加油吧awa），不知道 \(n\leq 10^5\) 的时候会超时，
而且T3大样例比较水，他觉得T3不一定能得分呃
下午提高组14:00开始18:00结束，为了不罚坐，一点三十多才进场，13:45开始动机子，吸取上午经验，不想用记事本了（没有括号补全），装了个devcpp，设置了一下编译选项，准备开始考试。
两点整准时发试题，题目比较简洁大概十多分钟就通读了一遍，
T1有个一眼的70分贪心，每次选 \(h\) 最大的飞龙进行单独攻击即可，攻击轮数就是答案，
T2是dp吗？ 如果是的话应该是线性dp呃
T3感觉是神奇的位运算，有点后悔考前没有学线性代数，然后学异或线性基，说不定就用上了（考后发现正解其实是01trie），估计就会30分暴力
T4一个图论和数据结构吧，不确定，但感觉用得上lca求距离
14:23写好了T1的 \(\mathcal{O}(hlogn)\) 的70分大根堆暴力，过了大样例，
吸取了冬令营死磕第一题导致t3痛失28分的经验，先写T2
很明显的线性dp，由于 \(n\leq 3\) ，前五十分只需直接硬 \(\mathcal{O}(m)\) 的动态规划就能过，
于是花了半个小时调好，过了前两个样例，
发现第三个样例里 \(m\leq 10^9\) ，又由于机关的数量 \(k\leq 5*10^5\) ,
可以离散化一波，然后直接 \(\mathcal{O}(k)\) 跑。
写了半个多小时离散化，
前两个样例都没问题，但是第三个过不去，
没办法，写了个数据生成器，和非离散化代码对拍，
大概花了10min写好，拍出来了错误
改后发现还有问题……
继续拍。。。。。
然后发现离散化方式会导致dp的时候转移出问题……
于是想其他的离散化方式，
此时时间3:20左右，而且已经拿了T1 70分，所以内心比较轻松，
想出一个3倍常数的离散化方式，打了出来，大概20min调好，
跟非离散化代码拍了几百组，
一直没出问题，
但是第三个样例过不去……
深呼吸
干脆先试了试第四个样例
？？？
第四个样例居然过了……
立马找到错误了，
我只考虑了 \(n=3\) 的情况……反而没处理 \(n=1\) 。。。呃呃呃
心情愉悦，先去了个厕所，
回来吃了个巧克力球
然后把错误改了，第三个样例就过了，
注释掉调试输出，然后看T3
先15min打了个二进制枚举暴力，时间复杂度 \(\mathcal{O}(2^{n}n)\) ，
轻松过掉30分样例，感觉估计没啥问题，开T4
前25分暴力显然的lca一波即可，
花了20min码了100多行 \(\mathcal{O}((n+m)q*logn)\) 的程序，然后跑样例……
QAQ 跑不过去，手画了样例的图，感觉没问题，
突然想起来了关于第一种操作的定义……赶快看了一眼，
淦
读错题了……我以为成修改 \(f\) 到 \(g\) 路径上的节点了。。。
实际是编号 \(f\) 到 \(g\) 的节点eeee
然后发现如果这样的话可以 \(\mathcal{O}(mq*logn)\) 能把另外25分也拿了，
一下就过了 \(n,m,q\leq 2000\) 的样例。
此时近17:00了，
计划了一下，决定去写T1剩下30分……
考虑是最优化问题，且答案显然具有单调性，
how about binary search?
答案值域应该为 \(0\) 至 \(10^9\)，
那咋写check函数捏
想了一个想法，然后第三个样例假了，
又检查10min，发现改一下应该就没问题了，
改后跑过了第三个样例，估计没啥问题了。
然后检查了一下后面的题，
还剩40min，决定写一下T3的爆搜+剪枝，骗些分
当 \(n\leq 15\) 时，枚举，
否则跑dfs
自己写了个数据生成器，
然后试了试，跑得很慢……
加了几个剪枝，有一定提升，但是大部分情况还会超时呃呃呃
比赛还剩15min结束，
斟酌了一下，设了个阈值，暴力卡时，
输出最优答案。
随着手表两声滴滴，一天的比赛结束了。
这是我这半年多第一次参加对标我的程度的比赛，
能获得这次参赛机会十分激动。
按照工作人员要求，下了楼，
发现我们机房是第一个下楼的呃
下午四高高一的同学和程序学长也来了，
于是站在机考院的院子里等着程序学长。
碰到了几个穿着四中校服的同学呃。。。。
但是不认识qwq
不久后看见程序学长下来了，旁边跟着一位同学，或许是高一的吧。
程序十分激动地给我说：“诶呀！我T2理解错题意了，第三个样例一直过不去，考完试cwl给我说了一句我就明白了！”
/lh eeeee……我也是最初只写了 \(n=3\) 的dp……但是后来成功发现了错误，qwq
希望多一些 \(n=3\) 的点吧！
出了门看见了爸爸妈妈，在路边站了一会儿，和学长讨论了一下题目。
他把T1切了，和我差不多的二分答案做法，
T2能对 \(n=3\) 的点，
T3 T4 暴力拉满。
我的话估计 100+100+[30,???]+50=280+？？？
程序先回家过周末了。
转头，见了王老师，他旁边是几位看起来和我差不多大的同学，
穿着红色棉袄的zyb站在我前面.
这是第一次见到在线上认识的zyb同学，我向他问了好，
他旁边是zxh同学，省实验初一的dalao （日常被单调队列）
他们也刚刚出考场，我们向王老师说了提高组考题的情况，
他们好像都把前两题切了，
但是zyb似乎和程序学长一样只写了 \(n=3\) 的点……额，应该问题不大
他还向我们介绍了他的T3图论思路（是的，他从位运算联想到了一道图论题/zj）
然后又介绍了他写的T4 不含 \(e\) 操作的线段树20分
%%%%%%%
我都没有去仔细想T4剩下的分，更没有精力想数据结构了……（我对数据结构了解甚少）
但是其他人似乎也没写
我们又讨论了普及T4的马走日，发现大家都不会写，但是zyb口糊了个贪心的思路，听起来有点靠谱呃。
由于街上比较冷，回了家。
\(Day~2\)至\(5\)
一寒假OI呀！该补补文化课了，开学还有个考试呢，回家后先给班主任打了电话，她很支持我学OI，也同意我先不用管20天左右的寒假作业，转头复习。
开学要考八下物理前三章，
但是我没报辅导班呃
也没咋自学，qwq 妈妈十分担心，
于是比赛结束当天就开始看物理书，看完知识点就看书上的问题、习题
考虑到学校培优课讲过初中力学，没有很害怕。
第二天有完整的一天用来复习，于是多睡了睡觉
早上感觉注意力不集中，半天看了一点。。。。
学校次日开学，下午到校，到校即考试，次日先考生物物理，后天考剩下6科。
考试两天好评
遂复习生物，看生物书。但是是不是回去关注前一天比赛的消息。还看见zyb的普及T4贪心思路过了一道类似的题（那是一道HN的省选题……luogu上的贪心蓝题，放到普及T4感觉真的不合适诶），
看了别人的游记，
发现提高组时，左边坐的是 @Franz_Liszt hhhhhhh
之前在luogu上经常看到他发言呃
总之注意力还难以从OI中转过来
次日睡醒就是开学日了，
上午看了会儿物理生物，
收拾了物品，打了一个大包袱，里面是住校用的被子床单等。
十二点四十离了家，到学校往宿舍搬东西，
惊喜的发现，宿舍没开门，
6。
于是把物品放到宿舍楼梯间。
到了班里见了几个月未见的同学们，
开了两个小时的开学典礼。
先考生物。
大题有个空不太确定，其他或许全（对）？
吃完晚饭再考物理
或许满分吗，但是晚自习和同学们交流后发现一个受力分析图少画了摩擦力/ll
晚自习重点复习了语文，最后五分钟翻了历史书的目录和最后几章
回到宿舍，铺好床，sleeeeeeeeeeeeeep，ZZZZZZZZZZZZZzzzzzzzzzz
第二天起床~
早上直接到考场，先语文，考完感觉废了，但是也轻松了
然后数学，考完感觉ak了
历史，考完也觉得好像还行
中午吃饭，whj突然给我说历史小短文要写两张图
？？？
%&$(&%())
10分啊10分……没理解清题意，感觉爆炸
回班后问了卜神苏栈，他们都写的俩图……吐血
中午睡觉ZZZZZZZZzzzz
下午先英语，完形填空感觉阴间，有个空完全不能理解……（2这个数字在中文里有什么特殊寓意吗，“祸不单行”）
小语篇似乎也最后一个不确定，感觉英语要完。
稳住心态，赶快上个厕所，复习道法。
道法考完了，感觉意外的不难……但是有几道大题不确定行不行qwq
随后是最后一科地理
选择仔仔细细写完，希望没问题吧额鹅鹅鹅
剩的时间很多，检查了几遍。
交卷后，轻松了些。
晚上查数学寒假作业（xs，我们三个数学课代表没一个人写完）
和同学们交流后觉得考的不算好，尤其是历史的十分短文啊。/kk
十分担心提高组第一题，害怕二分边界没处理好，
也担心第二题离散化常数大而爆内存qwq
万一挂惨的话怎么办？
睡觉
第二天上午对了数学答案，不出意外地又要气死，
“5-3=3“ —— jmc 2023/2/7
个位数减法算错hhhhhh
老师说函数图像不画交点要扣两分，所以97？（虽说交点在这个题没啥用）
英语对答案，完型竟然全对呃，小语篇最后一个果然戳了。
道法选择全对，但是大题估计不超过96，最低92吧
物理估计98……是的，还有个地方多保留了一位小数呃
其他科后来慢慢也对改了。
等着省赛出成绩，但是没有出呃
机房一直没有人qwq
周四中午，又拿班主任电脑查了一下，
诶嘿
出成绩了诶
普及355 提高295
提高的T3暴力剪枝卡时竟然过了15分
提高一等线似乎140多吧（不确定呃）
跟我同届的除了我还获得了普及组1个1=， 4个2=， 1个3=
同天晚上whk考试出成绩
呃？总分753/820，语文竟然96，还可以呃
但是为啥总分这么低
？
历史78/100？为啥捏
数学100/100？为啥捏
物理95/100？为啥捏
生物99/100？为啥捏
地理94，道法95，英语96算正常呃
总分比年级第一低了1分QAQ
我和卜神并列呃，她历史92……
嘿嘿，周五机房开门了，
见了好几个月没见的袁老师。
我给同学们讲了一下普及组第一题和第二题70分做法。
然后回班了。
大概就是这样
寒假最后一段时间的信息竞赛相关呃
祝大家新的学期高兴顺利~