2019.9 月赛题解

Xiejiadong edited 4 月,3 周前

花絮

# Tag Idea Developer Tester
A 博弈 cs2017 Xiejiadong Kilo_5723 10175101214
B 贪心 Xiejiadong Xiejiadong 10175101214 oxx1108 Grunt
C 签到 Weaver_zhu Weaver_zhu 10175101214 oxx1108
D 数学 Kilo_5723 Kilo_5723 10175101214 Grunt
E DP Grunt Grunt 10175101214 Xiejiadong

Problem A

First Solved:ustczml

本题的模型是一个平等博弈的游戏。

题目中的 DAG 可以通过 SG 函数 求出先手必胜还是后手必胜。

把所有后手必胜的局面列举出来,发现后手必胜的 的二进制表达里只有偶数位可能为

可以证明,所有符合这种性质的 都能找到后手必胜的策略,而不符合这种性质的 都有先手必胜的策略。因此,每个 的奇数二进制位是否都为 就是答案。

Comments

10175101214 : 这题博弈和我以往做的不太一样,挺有意思的。

Problem B

First Solved:suzukaze

因为题目保证了不包含数字 ,很显然的,要求最小的最大,我们一定会尽可能的把数位先分均匀。

较小的位数一定是 ,我们可以直接算出位数为 的个数和位数为 的个数。

最小的数一定产生在位数为 的数中,于是我们会贪心地把大的数字分给他们。

分配的方案一定是,按照数字从大到小,依次分给当前可能最小的数。

当前可能最小的数的数量是会发生变化的,因为一旦当前所在位所分配的数字不同,就一定会产生大小的差异,也就是说,当前可能最小的数一定会越来越小。

还可以发现的是,最小的数,一定是一个数字从大到小的非降数字构成的,也就是相同的数字只可能在同一段出现(这个从上面贪心的策略可以得到)。

于是对于最小值,我们模拟贪心的过程,每一个数字一次性放入,对于取模的结果,可以预处理得到。

Comments

Xiejiadong : 我和验题人都没有考虑到大力预处理暴力就能过的问题。所以变成了纯·签到题。如果加上在线修改,就能卡掉他们了吧。

Problem C

First Solved:ReTleWa

因为受到的伤害是固定的,所以问题不在于哪个时机 Cuber QQ 打出最后一击,而是是否能在每次外界攻击前配合之前的攻击打死小兵,我们只需要在这次攻击结算前一秒打出最后一击就行了。

而要求第一下最晚,就恰好是从 (也就是这次攻击结算前一秒) 恰好一直连续攻击 次配合外界攻击击杀小兵,显然这样是可行的又是最好的方案。注意需要过滤掉超过 的攻击,或者干脆加一个时间为 ,伤害为 的攻击。

然后就是从小到大枚举每次攻击前一秒,看看是否可以给出最后一击,然后更新答案。注意时间可能相等,需要一次处理完所有 相同的攻击,也要注意随之而来的爆 int 问题。

Comments

oxx1108 : 感觉这题的坑,挖的有些许生硬。

Xiejiadong : 这题的题面进行了无数次的修正,希望最终版本没问题吧。

Problem D

First Solved:SuperSodaSea

我们只关心鸭子是否分布在一个半圆中,所以鸭子离圆心的距离不重要。我们可以假设鸭子都落在圆周上。

如果所有的鸭子分布在同一个半圆中,那么让鸭子面朝圆心,所有的鸭子一定都在某一只鸭子的右手边。

令所有鸭子都在第 只鸭子的右手边是事件 ,则 发生的概率是 。那么, 只鸭子分布在其中任何一只鸭子的右手边的概率是不是

答案是肯定的。可以证明 () 不会同时发生(因为 只鸭子不会同时分布在 的右手边,如果 的右手边, 就一定在 的左手边)。对于 个不会同时发生的事件,它们之中任何一个发生的的概率就是每一个发生的概率之和,也就是说, 只鸭子分布在其中任何一只鸭子的右手边的概率是

因此, 只鸭子分布在同一个半圆中的概率就是

更多解法,可以查阅知乎。

Comments

Grunt : 这题知乎上有答案。

Kilo_5723 : 当时是看到了 只鸭子的题目,发现可以推广,就拿过来了。

Xiejiadong : 能自己完整做出来的人,估计不是很多吧。

Problem E

First Solved:Fuck_you_asshole
解法 1 :

by 10175101214

Part One

考虑在每次插入一个数后维护若干桶( Bucket )。

每个桶记录一下信息:

当前值 :表示这个桶已经确定的前 位二进制位,桶里面的所有元素前 位二进制位的与的结果 需要满足 的前 位二进制位, 的前 位二进制位)。

剩下需要考虑的位置 :由于前 位已经确定,所以剩下还需要考虑( )位。

每个桶支持操作:

计算最大的可能值 :由于前 位已经确定,最大可能值为剩下 位全为 ,即

Part Two 案例分析

考虑插入

1、插入 :直接插入

curval:0
j:31
flag=false
num:9
    10

2、插入 :由于桶中元素已经满了,所以需要将桶分裂成 个桶:其 分别为: 分别为 。表示含义枚举下一个 填在哪里,若下一个 填为第 位,则答案变成 ,此时所有位都确定(因为下一位填在第 位意味着第 位都不可能填),后面的桶类似。现在考虑将 重新分配成 个新的桶中:由于 的二进制是 ,所以对 的桶有贡献,所以插入在这两个桶中,类似 放入 的桶, 放入 的桶中(注意:若插入过程新桶也满了,如例子中 的桶,则递归这个过程)。(此时

3、插入 (此时

Part Three 复杂度证明

1、插入过程:如果插入一个数桶没有满则直接插入,若需要桶分裂,假设分离了 的桶,则所以 的桶都无需继续考虑,因为 ,而每一次的分裂需要确定的二进制位数至少减少 ,将原来桶中的 个数重新分配需要 的复杂度,而重新分配过程中最多继续分裂一个桶,所以插入一个数最多分裂 个桶,所以插入复杂度为

2、查询过程:动态维护 ,查询

解法二

与解法一大同小异,但是时间复杂度相差一个

首先考虑离线的版本:

可以用广为人知的 SOS DP解决。

具体做法是将去重后的插入按操作顺序存为数组 。用类似SOS DP的做法, 存的是一个大小为 的小顶堆, 表示满足 的最小的

对于每个询问,从高到低逐位确定答案的那一位是否可以为 , 当前 当且仅当 的最大值小于本查询的时间 tag 时可以取到。

再考虑一个暴力的做法:

维护一个数组 , 对于每个不重复的插入 , 枚举所有满足 , 令 。查询同样是从高到低逐位确定答案, 当前 当且仅当 时可以取到,这样可以做到动态插入和查询,但显然复杂度过高。

考虑如何优化暴力的复杂度:

观察到冗余的操作主要在于 时, 再增加是没有意义的。于是可以在枚举子集的过程中直接 break 掉。

最后的问题是按什么样的顺序枚举子集,这个可以参照SOS DP的方法。

具体可以参考上图中的枚举顺序。

最后我们得到了一个化离线为在线的神奇做法, 时间复杂度为

恭喜 cy1999 Manari Gzhu_ConanYu 冠亚季军。

Comments

hhu17电信张宇杰

A怎么打表啊?蒟蒻表示只会链上的SG函数,不会树上的

Xiejiadong

SG 函数,本身的定义不就是在 DAG 上的吗?

山海亦可平

A题“发现后手必胜的 n 的二进制表达里只有偶数位可能为 1。”,这个可以加上证明吗,菜鸡列出后手必胜了也没有发现

Xiejiadong

这个打表以后,很容易发现的规律吧。

山海亦可平

好吧,我也是最后几分钟打的表,也没看多久,早知道多找找规律了QAQ

wjt404

请问D题最后让输出的是什么?求出的逆元为什么不行呢?

wjt404

已解决

你当前正在回复 博客/题目
存在问题!