总结

今天是大年初三！结果我们就回到学校啦！因为要省选了！想念我的文化课！

今天的模拟题是新的，brand new。难度适中，做起来不难受，至少很顺？或许是这样的。又一年了啊……好奇妙。

题解

先上链接：link 。

怎么说呢，今天的题目感觉做的时候没有太沉下气，可能需要几天调整一下状态吧。

今天涉及的知识点有一些，计算几何，trie 树，CDQ 分治 / 整体二分（或许是），然后是分治，虚树。

A

就是平面内会有一些东西，每个东西有一个存在的时间。有一段时间不动的圆，有一段时间匀速移动，头尾会暂停一段时间的圆，还有与这个动圆相匹配的它的一个圆移动覆盖的图形。这个图形和对应圆同时存在或消失。

然后分为两个难度，动圆和框架一体或者看成两个东西。然后求有多少对会相交（相切）。这个就计算几何 + 大模拟。不卡精度，所以可以乱搞（）。然后就画一画容易发现每种可以转化成更简单的情况，然后搞一下就好了，虽然判断两个是的，但是我函数用了递归之类的……反正看起来常数很大。

我写了 2h，看起来还是手生了啊……

P.S. 说到这里，吐槽一下我们这个 OJ，最开始所有数据都挂了……A 题数据出锅，B、C 测试点配置出问题……然后最后重测的时候我 A 题又测了个 Format Error，没有找到测试数据。这是什么 bug……。

B

虽然是博弈论，实际上一点也不博弈。就是一个奇数长度的数列。要你枚举拿掉的一个数，剩下的数分成若干个二元组，然后每个组的权值是两个数的异或和，然后这种分法的权值就是所有组的权值的最大值，要求这个最大值最小。

首先思考暴力，就是从高位枚举到低位，如果这一位为 0,1 的分别都是偶数个，那这位就可以是 0，然后继续递归。如果不是怎么办？我们就可以直接 Trie 树上搜，找到最小的那个异或和，其它的又是偶数，分组一定小于这个。

然后这里就感觉很像整体二分了，考虑去同时处理所有情况。那么一定会分成一坨偶数和奇数，去掉偶数里面一个就变成奇数的情况了，这个时候答案就是其它的最小值，维护最小值，次小值就行啦。然后就看奇数个，会发现变成两个偶数，那么算一下那边偶数的贡献，累计起来，继续往下就行啦！感觉很容易想到喵。

C

这也是一道很有趣的题目。考试的时候如果在努把力就能拿到 30 pts！继续加油能更高！这个题也有许多有纪念意义的小技巧！先说题意。就是一个排列，建成一个树，每个位置的父亲就是前面第一个比它大的位置，然后没有就是 0。每次对位置区间加，然后查询树上一个祖先到子孙的这条链上的和。容易发现每个操作能拆成两个，然后考虑对一个前缀修改对后面一个查询的位置的贡献。如果小于等于前缀，从根到这个点就是深度倍数的修改值，否则就是和那个 lca 的深度倍数的修改值。前一种情况很好处理，然后小技巧来啦，暴力是的，显然没有什么用，然后这种每个查询是由时间在它前面的一些修改影响的我们就可以考虑分治（或许就是 CDQ 分治吧），然后这些修改满足结合律（是不是有一点群论线段树的味道了嘻嘻）。然后就分成两半，统计完内部的贡献然后考虑这一边的贡献。对于这道题，发现建立虚树上面统计就可以了。

这道题恶心的是什么呢？代码其实很好写，最简单的是，然后你会发现，过不去。因此合并区间需要用归并排序，求 lca 需要的时间复杂度。在曾师这边 OJ 稍微卡一下常 5s 内能过，但是梁师那边 4s，通过我一堆卡常，然后加火车头，再加多次提交，终于 3998 ms 卡过去了（）。std 跑得好快啊，看不太懂。

后记

祝大家春节快乐呀！新的一年越来越好哦！