因为 6 7 8 三场是我们验的题,我基本没补题,9 10 两场也没认真打,所以只复盘了前5场。
第一场
先开01,先想到的是sam做法,结果写到一半发现,这题内存只给了64M,sam开不下,于是转行SA,过了,但是很勉强。
看了题解才发现哈希直接秒了,怪不得这题过的人这么多。
02 星星,就是个 n^2 的背包,但是队友算错复杂度了哈哈,以为边数是n^3。
03 是个平衡树小练习,感觉没啥好讲的。不过题解用了线段树合并,比我的splay少个log。我经常把这种值域合并的题当成平衡树启发式合并小练习,不过一般线段树合并就够了。
04 zxn说完题,我惊了一下,这不就是线段树分治+可撤销并查集的板子吗,上学期还专门写了博客来着,分析了可撤销并查集tag的标记方式。然后粘过来只改了两行就过了。
05 队友给出了一个非常重要的思路,那就是如果总数是偶数且字符串不能平分,那么每个人获胜概率都是一半,虽然总是Alice先拿,不过既然是随机的,那么Alice和Bob的字符串就是对称的。
06 赛时没思路,赛后补的,发现这么简单。非空子序列的立方和,直接转化为:选三个序列,恰好相同的方案数。比如某个子序列出现了5次,我们把集合复制三份,每个集合中选一个,方案数就是5³。设 \(f[i][j][k]\) 表示 \(s[i]=s[j]=s[k]\) 的三个位置作为三个相同串的末尾,方案数,用 \(w[i][j][k]\) 表示三维前缀和,转移方程就一句话:\(f[i][j][k]=w[i-1][j-1][k-1]+1\),加 1 表示子序列只选这一个字符,前一个位置的前缀和就是把前面选三个相同序列的所有情况都加上 i j k 三个位置。有另一个写法,就是把序列为空当做一种情况,只选 i j k 单个字符就是从空序列的基础上拓展一个字符,设初值 \(f[0][0][0]=1\),状态方程改为 \(f[i][j][k]=w[i-1][j-1][k-1]\) ,麻烦的地方在于 \(f[0][0][0]\) 要计到前缀和里。
07 竞赛图三元环计数,曾经和队友在群里讨论过,绝杀。所以说这场俩题撞枪口。求竞赛图三元环数量,只需要求出所有点的入度,答案是\((_2^n)-\sum\limits_{i=1}^n(^{d_i}_2)\)。度数用三维排序做,CDQ分治解决。
08 签到,不是我开的。
12 是矩形并的期望面积,把矩形边界离散化一下,整行整列切割,二维前缀和求出每个小方块儿的覆盖次数,贡献可以单独算。牛客里后来出了一道类似版本,不过那题是矩阵交,且不能为空。
第二场
01 和队友手玩了一下,发现了规律,感觉没什么好说的。
02 是这场过的最难的一道,但是好像我没参与。。。
03 是这场我们队名次高的重要原因(university排名16),点开题目一看,三阶魔方,一下子想起来川大校赛模拟二阶魔方,当时二阶魔方就写了有好久,这题改成了三阶,还有个角贴错了颜色,更难模拟了啊感觉。本来我已经打算开始写了,zxn看了看题目,问我是不是真的不用模拟,他突然脑子亮灯泡了,说只需要判断八个角颜色的顺序就行了,如果是贴错了两个角,那么原本顺时针的颜色顺序一定会变成逆时针,好家伙!直接很快就写完了,不过第一发WA掉了,原因竟然是因为我代码里只写了六个角,属实有点唐了。。。
06 小武写的,我没参与,不过看代码长度,这题不算难。
07 字符串签到,希望题目能描述得再清点。。。理解错题意WA了一发。
08 是个很有意思的题,每个点都会分裂,且会分裂m次!简单地猜下结论就会发现,如果确定了一条链作为直径链,那么第一次分裂后所有点度数就不超过3了,度数为2的点会分成两个2,度数为3的点会分出一个3两个2。我的思路是在树形dp时用 \(f[i]\) 表示选择的链有 i 个 3,最多能有多少个2。一开始怎么也想不到优于n^2的做法,后来突然大胆起来,我猜能一条链能组出不同的3的个数平均不超过根号,这个跟去年济南B的思路很像,只需要用unordered_map记录能够取到的dp值,而为什么平均不到根号呢,其实我没有理性证明,只是个猜想,因为想要有不同的3的个数,就必须让这些点的度数不同,而度数越大,说明这个点的分叉越多,平均下来链长就会变短,大概在根号时复杂度拉满。虽然不知道对不对,不过我还是上手写了。可最后找最大值却把我难住了,我们要找最大值的模数,而我只会用矩阵快速幂算出每个情况取模后的值。
zxn突然发现根本不用矩阵快速幂,而是用高中数列的知识就够求了,设度数为 2 的点数量为 A,3 为 B,每一轮 B 不变,\(A_i=2A_{i-1}+2B\),写成等比数列:\(A_i+2B=2(A_{i-1}+2B)\)。直接就能通过初值算结果。当m比较小的时候,可以直接求出所有值,都到不了模数,当m比较大的时候,-2B 这一个常数项就显得非常小,我们只需要比较 \(A+2B\) 的值。
看了题解才发现自己唐了,树形dp写的太复杂了点。在m小的时候,每个点分裂m次的长度直接可求,算直径不就行了;m大的时候,把 \(A+2B\) 作为第一关键字,\(-2B\) 作为第二关键字求直径。其实题解有个更简练的式子,就是把度数为 d 的点最终分裂的点数直接算出来了。
10 11 俩题都是小武做的,我没看,不过都是签到难度。
12 我们队卡了两个小时一点突破口没有找到,有点过于坐牢了。赛后群里竟然把洛谷原题链接发出来了,好家伙,于是直接去补了洛谷上的题。
记录n个点的和哈希,哈希值就是在d张图中并查集祖先的val和,如果两个点在d张图中均连通,那么他们每张图中祖先相同,和哈希也相同,统计多少对点哈希值相同,就是哈希值出现次数的平方和。用启发式合并,两个并查集合并时,更新size小的那个连通块的所有点,更新它们的哈希值。
一交,WA了,后来才知道是哈希冲突的原因,虽然不知道是怎么冲突的,碰撞率我也不太会算,不过把p改成自然溢出就好了,然后val值用随机,不要固定base,很容易被卡。
随机一个ull范围(1.8e19)的写法:
mt19937_64 rng(random_device{}());
val[i] = rng();
第三场
01 是个跟因子相关的dp,结论很好找,不过我是把所有因子用vector存下来了,有点卡,事实上枚举因子就能做。
02 一个线段树合并+dp,题目风格很像DSU,不过赛时没做出来,题解也看不懂,摆烂了。
03 通过率11%,一开始我看到这题,很是不解啊,这不是签到难度吗,通过率这么低,是我理解错题了?跟队友讨论了下,马上就想去写。然后被叫住了,原来这题最复杂的地方在于看到醉汉在初始位置的那些人,目击在初始位置时间的奇偶性决定了最早出发时间。不过队友提供了一种按时间将前缀1和其他数分开记录的写法,细节很多,我现在不怎么回忆得起来了,反正就是set判左右,判奇偶,写得相当艰难且麻烦,不过最后关头还是把它过掉了,可喜可贺。
07 线段树pushup小练习,本来想上手写,zxn提醒我只需要维护差分数列就行了,我恍然大悟,直接简单了一大半。
08 小武写的,我没看。
11 又是一道细节题,zxn上去狂敲代码,有数不清的变量名,还都有用。WA了好久找我一起调,也没调出来。最后,是哪里错了,竟然是答案爆了int。
12 是签到。
唉,这场打的很魔幻,几句话就讲完了,题也没补。
第四场
Claris场,代码乱搞拉满。
05 和 09 是签到,不需要说。
然后是 07 和 04,两个随机数据题。
07 数列循环移动,并自取max,求出每次移动后的数列和。因为数据是随机的,我猜取最大的根号个数,循环移动后覆盖的位置会很多,实时确实如此,留下的位置虽然有的很长,但是总和大概是n根号级的,再暴力求每一个留下的位置是什么即可。拿最大的数去覆盖,有一个区间加的操作(时间上区间加),可以差分维护。
03 的随机化更是个重量级。
找出k个长度为质数的子段,使子段和的min值最大。现在都不知道自己代码在随机数据下的复杂度,是使劲卡卡过去的,6s的题卡了又卡到了5s过了。
先二分一个答案h,然后线段树维护后缀,二分找第一个是质数且后缀大于h的位置,有点神仙。。。题解是用的set,不知道和线段树有什么区别,不过肯定比我们的代码快。
然后12又是俩队友写的,我看都没看。
唉感觉这两场都没什么好讲的,过题比较少。
做完 03 和 12 就没时间看 06 了,一开始想的是这个题爆搜剪枝,反正m只有50,不过 4^50 有点太大了。
群里有人说dp,jiangly也亲自讨论起了复杂度,虽然这题我们没补(我没有hdu交题账号,一点补题欲望都没),不过想了想好像已经会了。dp记录自己的位置,敌人的位置,敌人的血量,枚举时多一个m,这个复杂度可过。和队友讨论了下dp和记忆化搜索的区别,结论是没有区别,不过我们没想到状态怎么设置,也就是没想到直接记录自己和敌人位置就行了,不需要关心操作序列长什么样,这样可以压缩掉大量的状态。
第五场
02 是个小分类讨论,好像情况挺多的,忘了。
04 比较有意思,首先是 \(lcm(i,j)<=x\) 这个耐人寻味的式子,本以为是数学,但是小武在做 05,没空来帮忙,后来我猜想了下,是不是 n 以内的 i j,lcm 小于 n 的数量会比较少,模拟了一下,发现只有百万级。题解里说了大概是 nlog^2 ,不过其实目测也只有单个 log。
于是我想到了一个线段树合并的做法,权值线段树记录每个值 x 的出现次数。首先将 i j 的贡献合并到 LCA 处,枚举 ij 也比较有讲究,为了保证 lcm 小于 n,我先枚举gcd,再枚举 \(x=\frac i{gcd},y = \frac j{gcd}\),x·y·gcd 就是 lcm,虽然还需要判断 xy 是否互质,不过总体复杂度也是俩log的,线段树合并也是俩 log 的,我以为已经做完了。
结果给线段树开空间的时候意识到不对劲了,这个空间复杂度是俩 log 的,但这题只给 256M,丸辣。
但是这题也不能就这么放弃啊,算了下空间的极限,我尝试性地去开了132倍空间,乞求数据比较弱,然后一直不断地减小常数,因为线段树合并的写法配上俩log的算法,常数是有点大,这题的评测状态也在 TLE 和 MLE 之间不断盘旋。
最后,4s的题,3968ms跑过去了,我只能说很6。赛后想了想,这题数据卡满还是挺难的。
正解是什么呢,我们注意到,这题我们用权值线段树来统计小于 x 的值,但是为啥这题只问小于 x,而不是问 l 到 r 之间呢(不对。。我错了,改成 l 到 r 之间也能做)。题解是将询问按 x 离线排序,然后一个一个值往树上加,而将树上dfn序形成的区间用一个线段树来维护。挺妙的,这就省去了线段树合并空间上的log。本来以为题目改成 l 到 r 的话需要套莫队的,又想了想好像不用,就把每个询问拆成 r 和 l-1 两个询问,最后答案做个差就行了。
05 好像卡掉了虚树的做法,小武用虚树搞的,赛后反思了下好像只需要用并查集加个小优化就行了,而且不需要建虚树,吃完饭回来就补了,我没仔细想。
06 打了个小表猜结论,规律是发现了,不过赛时没考虑证明,吃饭的时候把证明给补上了。如果三个数都是1那就必败,归纳完发现三个数都是奇数直接必败,奇偶不同则必胜,但是三个数都是偶数还没发现规律。思考了一下发现,因为要先吃掉一个数,然后再劈开另一个数,那么劈开之后不能是两个奇数,否则三个数奇偶不同了,所以劈开也只能是偶数,那就相当于什么,就是两个两个绑定,操作的粒度都是偶数,三个数都除以二的答案也是一样的。所以输入的三个数都是偶数的话,一直让它们除以2,看最后是三个奇数还是奇偶不同。经过牛客那次比赛后,懂了一个更快的写法,就是判断三个数lowbit是否相同。
08 猫咪们狂欢,一道有好多种建图方法的流题。
最好想的是zxn提出来的,如果选了一条边,那么就不能选另一棵树上同一个点的相邻边,两边的边可以分成左右两个阵营,且阵营内部不存在冲突,因此可以直接套用最大权独立集:将所有可以狂欢的边连向源汇点,流量设为狂欢值,当然那些狂欢不了的边就不用理睬了,加上冲突边后跑最小割,最大独立集为可以狂欢的总权值减去最小割。
这个建图方式是有复杂度缺陷的,因为 n 取值是1000,如果两棵树都是菊花图,那么第一棵树的每一条边都和另一棵树的所有边冲突,因此二分图中间的边数达到了惊人的n^2,也就是1e6条边,何况这题还是多测,n 总和 10000,最大权独立集的做法显然不是正解。
那么题解是怎么建图的呢?题解转化为了一个最大权闭合子图的模型。
首先让所有猫咪走到第一棵树上(最大权闭合子图经典套路,然后开始考虑移动的代价),算出此时的总和 sum1。对于任何一只狂欢猫,如果它要蹦跶到第二棵树上,那么第一棵树与它相邻的所有边失去狂欢值(需要是邻点有狂欢猫的边),因此开 k 个负权的点表示一只狂欢猫从第一棵树跳到第二棵树这一事件。首先处理第二棵树,如果第二棵树上一条边两个点都跳来了狂欢猫,那么加上这条边的边权,将这条边设成一个正权的点,如果同时选那两只猫的点,那么就可以获得这个正边权的点。怎么在最大权闭合子图模型里描述选了两个点就可以选另一个点呢?我们可以反过来理解为选了另一个点就必须选这两个点,因为闭合子图边的关系是必须而不是可以,因此这个正权的点连向那两只猫。第一棵树上的边也有问题,一条边两边的狂欢猫都跳走了,那么这条边权值被减了两次,我们补偿一个正权点,表示同时跳走这两只猫,就可以额外多获得这条边的权值,建图和第二棵树上的边一样,你会发现甚至是对称的。根据最大权闭合子图的计算公式,我们设正权点总权值和为 sum2,最小割为 maxflow,答案就是 sum1+sum2-maxflow,sum1 是第一棵树所有狂欢边的和,sum2 是第一棵树加第两棵树所有狂欢边的和,为啥建边是对称的但是第一棵树与第二棵树却不对称了呢,因为狂欢猫的那些点负权值是和第一棵树有关的。
这样以来,边数,点数都是 O(n) 的,只能说很妙。
11 和 13 感觉都有点签,最后讲一下 10。
10 其实是一道歪榜题,因为题面太长没人想去读,和牛客第6场那道挖掘机状况很像。
一开始我在想每个点维护根号个祖先的和,但是将某点权值置为零的修改操作会导致修改一大堆的值,至于那些攒一部分再修改的方法,都想过了,但因为修改和询问操作是叠在一起的,且询问操作也需要修改,所以放弃了根号算法,以为这题挺难的。
结果zxn突然发现,好像这题是个水题,因为每个点的庄稼只会被收割完一次,那么我们倍增找到第一个没被收割完的点,向下收割就可以了,当时距离比赛只有20分钟了,我二话不说开始敲起了倍增代码,然后又讨论起了置零操作会不会干扰倍增的寻找过程,讨论后的处理方式是打个标记,当准备收这个点的庄稼的时候突然发现这个点已经被蝗虫吃掉了,就继续找下一个点。
敲代码敲到一半问题又来了,下一个点怎么找?
每个点有许多儿子,我怎么知道哪个儿子连向的是询问的起点呢?正当我准备写个 dfn 序加 vector 上二分时,zxn跟我说,如果当前点只有一个儿子,就可以直接下去,如果有多个儿子,那么我们从起点再重新倍增一次。这个想法我觉得很天才也很对,虽然复杂度不知道,不过我先写了。
在距比赛结束5分钟的时候,我写完了代码,测一发样例没过,我没慌,我觉得我代码错误不多,然后仔细审阅了一番,发现了一个小错误,改完之后样例第一组过了,第二组没过,又发现是多测没清空 vector。
过样例了,看时间 59 了,直接交,然后直接过了,非常蓟县,16:59:34,20分钟带思考带敲代码带debug,脑子要炸掉了,看到AC了之后马上歇了下来。
本来以为拿了个顽强拼搏,结果一看提交记录还有最后十秒过题的,甚至是同一个题,自愧不如哈哈。
标签:杭电多校,狂欢,题解,线段,一棵树,2024,这题,复杂度,复盘 From: https://www.cnblogs.com/maple276/p/18416765