ChangKe's Blog

SDOI2016Round1游记

Day 0

我们坐着大巴来到了省城济南。

Day 1

我在考场上睡了5个小时。

Day 2

我在考场上睡了5个小时。
结果爆0了,连参加Round2的机会都没有。还好我不是山东人。
(以上均为口胡)
真实情况:

Day 0

我在家里看着SD的各位神犇发说说求保佑,见一个膜一个。

Day 1

Menci在中午把题发给我,我吓傻了,一道也不会。后来她还告诉我有人AK,感觉心灵受到了震撼。

Day 2

Menci说她可以去Round2了。我又去看各位神犇的游记,见一个膜一个。

后续

Menci把题放到了COGS上,然后混了个管理员权限。然后我才开始正式刷SDOI2016Round1的6道题。
下面才是正文

储值表

第一题就这么坑让不让人活了,考场上被吓倒的话估计直接三个暴力弃疗……所幸不少人做出了明智的决定——放弃法。
但我就是个SX,我并没有用这个方法。这可是新题,没有题解没有标程,周围的人都不知道怎么搞,真真正正的“开荒”。好的是COGS上可以随便看数据,于是就开始对着数据Debug,虽然不是什么光彩的事情,但没办法了。还是太弱,做不到1A。

算法一

直接大暴力算出来所有的数,然后暴力计算,毫无技巧可言。
时间复杂度,因为数据不卡暴力所以有20分。这应该是考场上出现最多的得分了。

算法二

然而我不知道中间那一堆部分分是干嘛的……所以直接来正解。(似乎标算跟我的截然不同?不过很快就是了)
首先我们打一个的储值表。很多题都是一打表就看出规律,这次也不例外:

有什么规律吗?当然。
性质1 如果,那么
证明 显然加上之后,两个数的最高位相同,均为1,异或后抵消,所以最后得到的异或值不变。
性质2 对于任意,有
证明 采用反证法。假设,那么,则有,与题设矛盾,所以不成立。
性质3 对于必取遍中的所有数。
证明 由性质2可知上面这些数都不相同,而这些数字在二进制下都只有不超过位,不可能大于等于,也就是说个数都不超过,显然会取遍所有数。
性质还有很多,你们可以去探索什么的。现在开始讲这题怎么做,核心就是分情况讨论。
我们记表示按照题目要求计算出的结果。为了方便,以下假定
情况1
如果,那么根据性质3,这个正方形内每个小于的数都出现了次,那么直接返回即可,注意用等差数列求和公式化简就好了。
情况2
我们先计算出在二进制下分别有多少位,分别记为。在这种情况下,我们讨论的情况。
这个时候,整个长方形还算是比较“方”的,没有一边长度大于等于另一边的两倍。那么我们可以通过直线把整个矩形分成四部分:
第一部分的四个边界分别是,对这个区域我们用情况1计算。第二部分的四个边界是,这个区域可以看做有行,每行中,每个数都是大于等于的,而且如果我们不考虑它们二进制的最前面一位,那么它们仍会取遍中的所有数,也就是每一行的数都取遍中的所有数,这时还是可以用等差数列求和来求出所有要求的数之和。第三部分的四个边界是,这与第二部分完全一致。第四部分的四个边界是,也就是右下角的小矩形,根据性质1,我们完全可以等价地计算
综上,每次递归总会把问题的规模缩小至少一半。而每次的计算显然都只需要常数时间。
情况3
如果,那么这个图形就会像一个长条一样,我们把它分成两个部分:
第一部分是从左边开始的列,根据性质3,每行的这类数取遍了中的所有数,直接计算即可。第二部分就是剩下的部分,因为这些数的最高位显然都是1,因此当时,我们需要计算,否则先计算,再加上这一部分数的个数乘以,这样才能把最高位都算进来。
综上,每次递归总会把问题的规模缩小至少一半。而每次的计算显然都只需要常数时间。
这三种情况涵盖了所有问题,而递归调用的次数是级别的。因此可以很快出解。
时间复杂度,期望得分100分。值得注意的是这里很多运算有着爆long long的风险,所以要小心哦~
代码上COGS看吧。

数字配对

这题应该不少人现场AC吧。。。那我直接说正解了。
正解是费用流。
首先,我们惊喜地发现,如果把每种数抽象成一个点,可以配对的脸一条边,那么形成的图是一个二分图!
为什么呢?因为,根据质数的性质,这个图不存在任何形式的环。。。然后自己YY一下就证出来了。
因此,我们可以先进行一遍二分图染色来确定每个点是“左侧”的还是“右侧”的。之后建图,建立源和汇,从到所有左侧结点连一条容量为,费用为0的边,从每个右侧结点连一条容量为,费用为0的边,而对于每对可以配对的点,易知它们必有一个在左侧,一个在右侧,所以从左侧点到右侧点连接一条容量为,费用为的边。
然后,站在这个图上按照常规的费用流方法进行增广,当费用超过0或无法增广的时候返回流量即可。因为费用流用的是贪心做法,所以这里可以得到正确结果。但增广时不能以1为增广量,而是保证费用不超过0且不违反流量限制的最大增广量。
然后就去COGS看代码吧。

未完待续