这篇文是在 12/12 写的,但因为隔天还有社会组所以会晚一点发 (?).
 给两个长度 的数列 ,,求有几对 满足 且 与 都是偶数.
 因为加起来是偶数所以奇偶性要一样,就数每一种奇偶性组合有几个就可以算了.
 给一个 矩阵 ,你可以做任意次这两种操作:
 选一个 的子矩阵,将左上和右下角减 1,左下和右上角加 1.
 选一个 的子矩阵,将右上和左下角减 1,左上和右下角加 1.
 求有没有办法让整个矩阵的元素都是 0.
 我看完题目就想到因为做完操作后,总和不会改变,所以所有元素和必须是 0,又看到备注写"你能想到空间复杂度不到 的作法吗"就觉得应该八九不离十了,结果交上去后 WA,想了一下发现同一行和列的和也不会变,所以必须同一行跟列的和都是 0,而且这样肯定能构出解,从左上角开始让格子变 0 就好了.
 pC 椭圆曲线
 100/100
 给 ,,, 和质数 ,求所有的 满足:
 题目给的资讯:当 时要特判. 不是 0 的话,可以令 ,,式子可以整理成
 枚举 就可以得到一个二次方程 ,配方后会变成 .
 当 ,, 时要特判,剩下的状况要开根号,开根号可以预处理.
 就是一个数学阅读测验,我去年全国赛和今年入营考的数学阅读测验都烧鸡,这次终于过了,好开心.
 就是照著题目说的做就可以了,一些特殊状况:
 特判 :直接枚举 ,然后检查.
 ,:一次方程式,可以直接移项.
 ,:显然不会有解.
 :所有 都可以.
 我交上去后 WA 第一个子题,这个子题是 ,我想说可能 的时候模逆元会坏掉之类的,特判就过了,但第三个子题 TLE,把模逆元预处理后过了.
 pD 和尚端汤上塔堂
 100/100
 给数字 和 ,以及一个长度 的数列 ,求全距 的区间数量.
 我以前听到的版本都是和尚端汤上塔没有堂 (?).
 如果固定区间左界的话,右界往越右边移全距会越大,所以枚举左界再二分搜右界就好.我用 sparse table 算全距,听说有人用线段树然后 TLE.
 pE 量子纠缠
 100/100,首杀
 给两张图 和 ,分别有 和 个点, 上的点 记作 , 上的点 记作 ,每个点都有各自的特征,记作 .
 求最大的 使得存在 上的可重复点路径 和 上的可重复点路径 满足:
 .
 ,也就是不能同时往上一步的地方走.
 先做一张有 个点的图 ,上面的点记作 (,),如果有 ,,, 满足 ,,那么就在 和 间连一条无向边(这个关系会是双向的,连一条就好).
 然后问题会变成在 上找一条不往回走的最长路径,如果有环就可以一直绕圈圈,所以这样答案会是无限大.没有环就是找森林里的最长树直径.
 在建图的时候可能会有 条边,如果边数 就可以直接停止.
 pF 闹钟设置
 100/100
 给数字 , 和一个长度 的数列 ,你可以在每个位置 都设置任意个闹钟,并决定每个闹钟什么时候要响,每个闹钟的影响范围是 ,某一个位置 的起床时间是影响到他的所有闹钟中,最早响的时间,而这个时间必须 .求最大的起床时间总和.
 首先就是如果 里最小的 ,这样就一定要有一个包含 的长 的区间,起床时间会是 ,接著会被砍成两半起床时间还不确定的部分,那两半可以分开做事,因为中间已经确定的长度是 ,能影响到其中一半的闹钟一定影响不到另一半.
 看到 就想到应该是某种三维 DP, 范围内的答案,转移就是找到区间里最小那个后枚举闹钟的位置,把区间切两半.
 pG 白银栅栏
 100/100
 给 个点,所有点的 座标都是非负的,你可以决定一个角度 ,然后将所有点以原点为圆心,旋转 ,旋转后必须满足所有点的 座标都仍是非负的,求最小的"最大 座标绝对值".
 题目叙述比较复杂一点,经过一些想像 (?) 后就可以变成这样.
 我看到这题本来以为是旋转卡尺,然后发现我不会平行线距离公式(我知道数学课有教),然后自己导了一个用直角三角形算的算法 (?),应该好好把高一上数学学好的 QQ,高一下和高二上太友善了,高一上有一些超级难的东西,直线与圆超难.
 不过后来发现跟旋转卡尺无关,把题目转化成上面那样后,可以很直觉地发现 对答案是一个单峰函数,所以可以三分搜.决定 后,把每个点的座标转成极座标旋转后再转回来就行了(没错我不会旋转矩阵).传上去后第一个子题过了,第二个 WA,看到只错几笔而已就想应该是误差太大,把精度调高后就过了第二个子题,但后面 TLE,明明复杂度乘一乘也没多大 QQ,心想大概是三分搜次数太多 + 三角函数跟根号常数太大.
 踩几场地雷后想到可以对答案二分搜,每个点转到答案范围之内的角度会是一个区间,取每个点的区间交集,如果不是空的就表示这个角度可以,实作细节:
 假设答案是 .
 枚举点,算出这个点的极作标是 .
 如果 就可以不用管它.
 不是的话它一定有办法转到 座标是 或 .
 把 转到 座标是 需要转的角度 是 .
 ( 其实理论上有两个,因为 acos 的值域是 所以不会坏掉.)
 转到 的会比转到 的角度大,把每个点这两个角度之间的区间交集.
 还有个细节是我是用 算极作标的,因为 atan2 值域是 ,所以如果是负的要加半圈.
 传上去后过了第三个子题,最后一个还是 TLE,我想说没道理啊难到有 的解吗,然后开始压常,把精度调低也没什么用,还多了几个 WA,然后决定开大绝 -  - 时间剪枝,但也没什么用,最后几分钟已经放弃了决定开始乱做,发现我每次都重算极座标,预处理居然就过了,atan2 常数到底多大 @@.
 pH 蚂蚁捷运
 0/100
 给一棵 个点的树,还有 条捷运路线,第 条路线是从节点 到 (双向),在同一条路线上移动不论多远都只要花 ()元,只能透过捷运移动,然后有 个询问,每个询问问从某个点到另一个点的最小花费是多少.
 我好像在不知道哪里看过类似的题目,但这题困难许多.
 本来想说可以建一张图,每个路线都是两个点,一个是入口,另一个是出口,从入口连权重 的边到出口,然后从每个路线上的点连权重 0 的有向边到入口,再从出口连权重 0 的有向边到每个点,这样就会变成单纯的最短路径.
 然后以为可以过前两个子题,但发现第一个子题 但 没有限制,节点数会有 个,所以没办法在线询问也没办法先预处理,第二个子题虽然 但 还是没限制,所以不知道怎么做询问.
 这题灭台了,没有人有分数.
 过程
 为了模拟比赛所以用 Ubuntu 打,题外话:其实在自己电脑以外的地方我比较喜欢用 Ubuntu 比赛,因为别人的 Windows 都会发生怪怪的事 (?),而且 Ubuntu 有内建踩地雷.
 预想的时间分配是先用半个小时读完题目并且对每题都有初步的想法,花 1 小时写掉所有水题,再花 2 小时写完有比较多想法的难题,剩下 1.5 小时处理剩下的题目.
 开场打完 .vimrc,读完题目大概刚好半个小时,对 ADEF 都有几乎完整的想法,pB 只想到全部和必须是 0,不太确定是不是但反正可以 proof by AC,而 C 是小麻烦的数学阅读测验,需要花比较多时间写,在这个时候我还以为 pG 是旋转卡尺裸题,而 pH 只有想到上面那些错误的想法.
 接著开始写,pA 马上过了,pB 错了一次想到正解了,这个时候才过 5 分钟而已.接著想说 DEF 都很简单那就先专心写 pC 吧,写累了再去写后面的.跟 pC 缠斗快一个小时总算过了,接著快乐地去写 DEF,在 120:23 拿到 600 分,剩下来的时间都花在 pG 上.
 发现 pG 不好用旋转卡尺做之后没什么想法,在想会不会有一堆人都 600 分了,然后大家都会 pG 只有我不会.想了一阵子后终于想到是把点旋转,然后可以三分搜角度,缠斗一阵子后终于拿到 32 分,踩地雷踩了一阵子后想到可以对答案二分搜,拿到 69 分了,接著各种压常,还有去想 pH,压到最后 14 分钟已经放弃了,决定去上厕所,上完应该就结束了吧.回来后还有时间,想说再乱压一下,结果就过了,还好我有垂死挣扎 (?).
 结语
 总分 700/800,1 首杀,rank 1
 结束后马上开计分板来看,发现我的担心是错误的 (?),一等线是 658,二等一是 544.没想到我几乎整个后半场都是 rank 1,感觉自己跟去年相比成长满多的,在入营考的时候我还会被数学阅读测验吓到,这次已经可以平静 (?) 地面对了 > <,而且还做出另一个数学题 pG(虽然过程中我把 和 搞反花了很多时间),然后我觉得我应该去学一下直线与圆.
 这次题目的分布跟去年全国赛满像的,前三题有两个水题,一个数学阅读测验,pD 是算裸的资料结构题,EFG 是需要稍微想一下的题目,pH 防破台.
 距离全国赛还剩一个星期,希望那个时候也能像今天一样好好发挥,不要被数学卡死.