作为一名完全没有准备的完犊子选手,发挥果然是不尽人意,居然签到没签成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.
Comments | NOTHING