CSP-S 2019 游记

## 考前 考前一段时间晚自习8:00以后就可以去机房，真爽 ~~初赛~~第一轮认证前复习了一下信息学奥赛一本通初赛篇 第一轮认证85分，省排名22，还算满意 然后全心投入~~复赛~~第二轮认证 数位DP，斜率优化DP，扩展中国剩余定理，二次扫描与换根等等等等 这些都是去年没有或很少接触过的 当然还有一些其他知识，也复习了以前学的知识，也做了一些题目 考前也复习了一些模板，LCA，tarjan，tire，主席树等等 数论这块比较有信心，不像去年考前担心数论爆零 ~~初赛~~第一轮认证后，突然想办一场比赛，因为平常做题的时候也积累了一些好的idea，不写出来不舒服 之前也造过数据也出过题目 于是之前写的数据生成器等东西就拿来用了 然后邀请了@Wings来验题 最终，~~复赛~~第二轮认证前一个星期 这场比赛[南康中学2019年CSP-S模拟赛 ](https://www.luogu.org/contest/23712)成功举办 主要参赛者是我校高二OIer 可能由于时间原因，整体得分较低 然后按照教练的吩咐，总共花了大概100分钟吧，把这些题目讲完（所有的部分分都讲了，而与数位DP有关的没讲 讲题的过程，也拉近了我们这些OIer的距离，之前大部分我都是不认识的 ## Day0 和去年一样，先坐公交到赣州然后坐火车到南昌（这火车怎么不是很稳啊 在等火车的时候和szq，znh交流，得知他们是文化课前几、前十几的大佬orz，文化课吊打我 插曲： 天山乌梅一进车厢，所有乘客便都看着他笑 有的叫道，“天山乌梅又降价了！” 他不回答，对厢里喊，“奸商乌梅大礼包好吃不贵，二十元一包，一百元七包，**富含酸性物质**，可以**调节体内碱性环境**（？？？，**富含花青素**（？？？……给家里人带一包，不要那么冷漠无情……来一包，来来来（**强行**”，便排出九包乌梅。 他们又故意的高声嚷道，“你一定赚翻了吧！” “你怎么这样凭空污人清白……” “什么清白？我刚刚亲眼看到你打虚假广告，强卖！” 奸商乌梅便涨红了脸，额上的青筋条条绽出 争辩道，“奸商乌梅不能算强卖……强卖！……奸商的事，能算强卖么？” 接连便是难懂的话，什么“奸商”，什么“最后一趟”之类， 引得众人都哄笑起来：车厢内外充满了快活的空气。 ## Day1 今年用Linux，确实会不习惯 GUIDE还不能调试（垃圾 提前30分钟到考场熟悉环境 试机的时候打了快读和堆dij 8:30之后还没发密码，草稿纸也没... 快8:40才发草稿纸 T1好像是个模拟 看了一下数据范围，肯定不能存全部格雷码 不是模拟 然后想了一会儿发现是分治，也注意到了n=64的情况 不过平常没用过scanf读入ull，于是刚刚打的快读就拿来用了 写完之后没有检查而是直接测样例，然而WA了 麻烦，这该死的GUIDE不能调试，输出中间变量吧 试了几次才发现问题，细节问题... 然后测样例都过了 自己测n=64，k=1的时候也没问题 打算交的时候瞄了一眼警告，什么"between signed and unsigned integer"（其实是这里的锅if(k<(1ll<<63))，k是ull 管他呢，n=64的我都处理了而且自己测的也没问题，直接交 开T2 n方算法好像很好搞，正解应该是O(n)于是开始想正解 想了一个做法，但是有点细节处理不了 于是先开T3 没思路，看看部分分 10分暴力，链与菊花图 链这个贪心扫过去不就秒了吗 自己在草稿纸上手算了一下链的样例，发现和答案对不上？？？ 后来发现数字和结点编号弄反了，，，但是！改过来之后还是不一样？？？ 不会，下一个 菊花图，先试试根结点为1的情况，好像很可做 不过根结点可能不是1，刚刚想的贪心没办法直接用，也很难改，遂放弃 回去T2 上n方DP，打完调试好了之后，开始思考链的O(n)做法，如果思考出来的话可以扩展到树上 but，这转移方程还能怎么优化，好像不行 此时时间已经不多了 继续思考T3 然而手算连样例都过不了 没心思也没空打10分的暴力 回去想T2，无果 最后检查了一下，就下考场了 中午在食堂恰饭（还是自己学校的食堂饭菜更便宜，身在福中不知福 大家都表示今年题目很难，还有黑题 but你谷人均210orz 我太菜了 Day1期望得分100+50+0=150 回来后轻松了好多，模板也没必要再复习了，书也没什么需要看的了 于是便开始~~颓废~~玩耍，和szq打游戏，而znh在学vim，宾馆内外充满了快活的空气 ## Day2 一开始先花了十多分钟看了一边题目 感觉T1是DP，T2贪心，T3树论求重心？又是树 先开T1，这个DP有点绕 有点复杂，先来个搜索再记忆化 打完暴力，小样例能过，先交了 然后上记忆化，but写好之后过不了样例 嗯状态漏了，存主食使用次数的数组也是状态... 这有点难搞，map离散化？时间空间都无法承受 先给数组来个hash离散化，再放map，为了降低冲突率，用了双hash 然而写好之后依旧WA，不知道哪里写挂了 仔细思考了之后发现这样存状态没有意义，没有达到记忆化的目的，因为那些状态都得遍历... 好难，下一题 T2好像可以贪心O(n)，在草稿纸上证明了一下（这个证明是错的 然后发现很可行，T2这么容易就拿高分了？ 先打，边读边算，不用数组了 前两个样例都ok but测第三个样例，，，WA了？？？ 这个样例有点大，不好找错 自己手捏 试了几个后找到了一个反例，之前的证明是错误的，，， but这种情况也不会处理也不好处理 错误的贪心应该也有分，先开下一题 T3 O(n^2)暴力32分可以拿(事实是40分 链和二叉树好像有点麻烦 正解没啥思路，有点像二次扫描与换根？重心不会转移，，， 打暴力吧，还要留时间给T1，T1可不能炸 这个暴力打的比较顺利，枚举删边，求子树大小，暴力找重心 测样例没问题，因为是多组测试数据，也仔细检查了一边有没有清空数组、变量初始化 回去T1 这暴力也不能剪枝，记忆化也行不通 考虑递推？？？难搞 容斥原理？！好像可行 先不考虑某主食使用超过一半的情况 那这样很好求，一边for扫过去就ok 然后考虑不合法的情况 对每种主食，减去其使用超过一半的情况 因为使用超过一半的主食至多一个，所以不用减来加去，加来减去的 求不合法的情况复杂度很高啊，，，不过也没啥优化的思路 先打 然而测样例的时候输出负数？？？ 输出中间变量发现不合法的方案总数很多，显然是有问题的 于是开始艰难查错 后来发现我这不就写的是压了一维状态的01背包吗，这个带i的for循环要放外边，然后逆序更新 再试试 743！ 减去不做菜的情况742！ 调出来了，山重水复疑无路啊 离考试结束只有二十多分钟，谢天谢地，感谢CCF T1得分不至于太低 优化没时间想了，16分还不一定想得出来 先去搞T2 想了一会儿依旧没思路 最后10分钟检查 然后就结束了 期望得分84+？+32 （其实是84+？+40 然后又是漫长的旅途 坐火车的时候和hy聊天，感觉他比较有钻研精神，有潜力 晚上回到家后洗澡、自测 最终洛谷自测100+50+0+84+4+40=278 我觉得应该有省一，不过这分数也不是很理想，D1T2以及D2T2，，， 我还是太菜了 退役喽 # UPDATA 2019/11/19 得到消息，JX选手源程序丢了，要重考 心情复杂，我也不知道我是什么心情