DUT"华为杯"第八届大工之星编程挑战赛第一周 题解

第一次周赛就捧杯了..小激动!

T1

类似超级玛丽的手速签到题

T2

依旧语言基础手速题,没看输出格式挂了两发…..

T3

按照题意模拟即可

T4

按照题意模拟即可,,

T5

题目开始变得有点难度了…

输入三个数a,b,c,输出[a,b]这b-a+1个整数中,有多少个整数x满足,x每一位的平方和 × c == x
其中a,b,c都不超过10^9
这题想了挺久的….感觉是个数论题,后来发现反向枚举一下就好了。9位平方和的和是很小的,只有不到800,我们枚举这个看一一可不可行就行了。据说还可以数据按大小分类处理一下。

T6

Zeratul正在打炉石传说的竞技场模式,他的目标是打到12胜。根据炉石传说竞技场模式的规则,Zeratul输掉3场或者赢了12场的时候游戏会立即结束。
Zeratul每场获胜的概率为PP,失败的概率为1P1−P。他现在想知道,自己进行一次炉石竞技场之后的期望胜场是多少。
挺有趣的一题,最开始打算推一个O1的式子,后来放弃了这个可怕的想法,决定老老实实动态规划,然后我就一直没判掉12-3这个情
况。(亏我打了这么多年炉石。一直以为是精度问题….想了挺久的。。

T7

G题就是猜一个性质,如果能飞到目标点后的点,那么一定可以用不超过这个的前飞到目标点,才玩性质之后可以简单的动态规划,但是考场上觉得数据不大,又对动态规划的正确性存疑,直接建图跑最短路草过去了..

T8

Zeratul有n1n10000n(1≤n≤10000)座防御塔,每个防御塔覆盖[L[i],R[i]][L[i],R[i]],且攻击力为A[i](1A[i]1000)A[i](1≤A[i]≤1000)。区间[1,m]1m10000[1,m](1≤m≤10000)上每个整点有一个防御值,是所有能覆盖到这个点的防御塔的攻击力之和。Zeratul可以给防御塔升级k0k109k(0≤k≤109)次,每次升级可以将一个防御塔的攻击力提高1。同一个防御塔可以被多次升级。
现在Zeratul想知道,[1,m][1,m]上所有整点的最小防御值最大是多少。
挺简单一题。。。不知道为什么只有我过了….
就是二分一下答案,然后用线段树维护下就行了。类似从左到右填坑,当前点没填满,就找一个包含当前点的右端点最靠有的端点拼命填坑就行了》。。
据说可以用差分少一个log。我这个线段树版本卡了半天常数…最后强行挂了快读才过…

T9

Kerrigan在编号为11n1n105n(1≤n≤105)的星球都分别部署有一些兵力,每个星球的兵力都可以用一个非负整数来表示。这些军队正在准备进攻Protoss的领地。
现在Zeratul得到了一些关于Kerrigan军事行动的情报。Zeratul得到的情报是下面这个形式的:三个整数LRV(1LRn,0V(2311))L,R,V(1≤L≤R≤n,0≤V≤(231−1)),代表Kerrigan在编号为LL到编号为RR的星球上的兵力的异或VV
现在Zeratul想要知道,他可以从这些情报中确定出多少个星球的具体兵力。如果情报是自相矛盾的,输出-1。
自己还是too young….对于和异或相关的运算还是太不了解了…这个题用带权并查集维护下就行了,边维护,边判断有没有什么矛盾冲突。感觉自己在异或这方面的感觉还是要加强…

T10

这篇题解就因为这道题没搞懂鸽了很久…..

反正sg定理,就是每个子游戏的sg值异或起来,如果是0就先手必败,否则必胜。我们就考虑怎么求每个子游戏的sg值即可。建议去读下2009年的集训队论文。

如果m是偶数,我们从0开始推一下前几个的sg函数值。我们可以发现0是0,1是1,2是2,3是0,4是1,等等等。我们可以发现随着数变大,偶数位的sg值固定为1因为偶数位要么,拆成m个相同的石子堆,m是偶数,异或完是0,或者拆掉一个变成奇数。当前一个奇数为sg值为0时,偶数位必定为1,然后偶数位为1,又会导致奇数为必定为0,因为下一个奇数位只能转移到这个偶数位。

当m为奇数情况的时候稍微有点复杂。

0是0,1是1,2是0,3是1,4是2,5是0,6是2,7是0,8是1,9是0,10是1…我们发现对于奇数位,开始不是0,但从某个临界点后,后面的所有奇数位都是0.因为一旦一个奇数为是0,会使得他的下一位,一个偶数位不为0,那么他的下下位奇数为,就必定是0。那么我们再接着去推偶数位,偶数位,我们每次递归求解x/2就行了,一共logn层,复杂度可以接受。

总结

感觉后面两道题还算有点难度…虽然没做出来QwQ太菜了…….要要加油啊

发表评论