2020届集训队选拔赛题解

发布于 2021-03-15  145 次阅读



作为一名完全没有准备的完犊子选手,发挥果然是不尽人意,居然签到没签成emmmm而且从出赛场开始被嘲讽到现在了我都快ptsd了,感谢大家的厚爱,十分感谢呜呜呜呜呜

A我才是签到题

没错,就是这道签到题嘤嘤嘤
拿到就有思路,并查集+01背包,把有关系的商品进行合并后就是普通的01背包。唯一的问题就是路径压缩不完全,在访问祖先的时候应当直接用find,而不是father数组。

此处由于拉题拉错了,空了一题。


C小b想要知道

算思维题吧,a^b=n可以变为a=n^b。设a<b,那么n与b最高位1的位置必须一致,否则a就会比b大。b的取值就是n-1-2^x+1,x为n最高位1的位置。怎么获取x呢?可以利用右移运算,非常好写。


DThebest的数学题

唯一分解定理的运用,长见识了。

唯一分解定理:任一正整数(≥2)都可以被分解成一系列的质数相乘,且这样的分解唯一。

有什么用呢?分解后,我们可以知道这个数中每一个质数因子的数量有几个,比如2有x个,3有y个,5有z个。。。根据乘法原理,这个数的因子数量就是(x+1)(y+1)(z+1)。。。
为什么要加1?因为每一种质因子都可以一个也不选。
分解质因子有一种O(logn)的算法,可递归实现。


E排序

传说中被疯狂暗示快去写但无动于衷的题。当时确实有思路的,但是线段树区间修改没用过。。。

作为一名完全没有准备的完犊子选手,发挥果然是不尽人意——uli

首先注意,元素只有0或1。线段树正常存区间和,即是区间中1的数量。1的数量定了,区间的长度定了,0的数量也就定了。之后要做什么?排序?不不不,排什么序,排序有什么好排的。升序就是先塞0,再塞1,降序就反一下。

或许,对于一种数据结构来说,它就该做它该做的事。——uli

至于最后怎么输出?该怎么输出就怎么输出。


F会长认证签到题

题面给的是数的长度(其实不用)已经在暗示大整数思想了。(那你为什么当时没做出来?)

一个数字的每一位都能拆成10^n乘上一个数,再将拆出来的数加在一起就是本来的数。那么利用同余模定理,这个数取模就等于把他拆开取模再相加。

唯一要注意的就是最后要对三个取模的结果相乘再去模。

模就完事了。——uli


G暴力ac题

状压dp(什么状怎么压如何d哪里p?)

dp[i][j]表示第i行的第j种状态时的方案数。把每一行的状态压缩成一个十进制数,剩下就是考虑如何状态转移了。


H温暖人心

二分题,当时看着就挺简单的。(那你为什么当时没做出来?)二分最高等级,check金币是否足够来缩窄范围。亲测范围到inf时间都绰绰有余(log之力)只不过,二分范围比较头疼。。。

(二分)思路很简单,细节是魔鬼。——Knuth


I小YY闯地牢

此处省略一千字脏话

“取log后就是一般的最短路了。”《一般的最短路》虽然从思想上来说是没有太出格。。。

显然,组合数算出来的话是会爆的。更别说乘了。

巧妙的是,我们对组合数C^b_a取log,就能够把它从乘变为加。

在这里我也想让大家自己思考(体验绝望),所以我也说取log后就是 一 般 的 最 短 路 了。

猫猫能有什么坏心眼呢?

思考,最短路不能用乘法的根本原因与如何解决。


J大毒瘤

确实是道毒瘤dp嗷(出题人表示他dp稀烂)

官方题解谜语人,看了一头雾水。

这题是可以用二维写的,但是也可以压成一维滚动数组。

f[i]表示在i高度时的生命值,那么将能量块一块块放进去,如果高度大于d了,那么就逃出去了。如果没有,那么当前高度+能量块高度这个状态下的生命值就能够从当前高度或是当前高度+能量块高度的状态下转移。如果逃不出去,那么f[0]就是逃不出去情况下最长的存活时间。

我承认我又省略了一些细节,故意的。应该能自己想到,只要大胆一点。


K签到题又双叒叕来了

这个也算是签到吧?线段树模板题。唯一需要想的就是要乘-1该如何解决。一开始我想在线段树上做手脚,后来发现这样肯定不对。

或许,对于一种数据结构来说,它就该做它该做的事。——uli

然后我想到建两棵树,一棵正一棵负。由于一个区间的正负性由左区间就能决定了,所以这样说不定能行 ,但是我很懒所以一时不想写。

然后就想到正解了,之前说正负性由左区间决定,这是对的。所以我们要做的只是在建树的时候判断一下就解决了。


Q.E.D.


夢に僕らで帆を張って 来るべき日のために夜を越え。