牛客周赛 Round 58 组题总结

大家好，这里是牛客周赛 的组题人。希望大家喜欢这一场的题目~

本场总体偏数学与思维，码量低，特别是 会有一股浓厚的 的感觉（回归牛客数学周赛了）； 难度较高，为竞赛选手设计，非校招难度，可以暂时跳过，思路源于沙老师验题时的看错，从 移植而来。从组题人的角度来总体评价这一场，

• 打卡，我们知道浮点数有误差，但是本题中直接比较不会有问题（为了防止出现问题，标程写的非常严谨，但是最后没有发现问题，可以参考下文图片）；
• 赛前临时加的打卡题，本质时考察循环或者排序，不需要分类讨论；
• 简单博弈，常考，关键点在于看出有人可以为了不输，乱走强行达成 的情况；
• 神秘数学题，卡住了不少人，实际上可以将其转化为进制，但是需要注意 的情况，由于 好数的存在，本题一定有解（理论上讲，本题应该加上一个无解输出 的要求的，需要选手证明这一点）；
• 猜猜题，在算法竞赛中比较常见，如果没见过这种题的校招选手可以学习一下；本题逆推比较好推，正推比较好找规律，简单举例验证可以发现一共只有三种情况；
• 前缀和+二分，也可以用能够维护区间第 大的数据结构来做，例如众所周知的主席树，难度较高，一般在校招中压轴，可以待深入学习后再来补题掌握；本题出题人原意要卡掉主席树（空间），但是由于静态区间第 大有一些神秘数据结构（如小波树，跑本题仅需 ），所以最后还是全部放过；
• 差分约束；题中的 个条件是传统差分约束模板的限制，除此之外，相邻数字间还有一层隐藏的限制，建边后跑 或 均可，如果对此不熟悉的同学可以先学习模板题；出题人原意要构造强力数据，考虑到周赛难度，最后采用随机数据，允许非严格算法通过；与 关联不大，容易被 误导，证明困难，建议收看 视频讲解 。

一些趣闻

感谢本场的各题出题人：

• ：idea by WIDA 、data by bandiaoz；
• ：idea + data by yeVegeTable；
• ：idea by WIDA && bandiaoz、data by bandiaoz；
• ：idea by yeVegeTable && Silencer76 、data by yeVegeTable；
• ：idea by WIDA 、data by bandiaoz；
• ：idea by Svemit 、data by bandiaoz；
• ：idea by 沙烬 && Svemit 、data by bandiaoz；

以上！