首页 > 其他分享 >2024杭电多校复盘 (1~5)

2024杭电多校复盘 (1~5)

时间:2024-09-16 23:46:44浏览次数:11  
标签:杭电多校 狂欢 题解 线段 一棵树 2024 这题 复杂度 复盘

因为 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

相关文章

  • 2024.9最新:CUDA安装,pytorch库安装
    目录一、CUDA安装1.查看自己电脑适配的CUDA的最高版本2.安装CUDA3.检查环境变量是否配置,安装是否成功二、pytorch库安装1.pytorch库下载2.选择合适的版本3.查看版本一、CUDA安装1.查看自己电脑适配的CUDA的最高版本在命令提示符里输入nvidia-smi表格右上角显示的C......
  • 20240916总结
    不积跬步,无以千里。这两天主要是复习了图的连通性相关的题+听了youwike哥哥讲课。先是复习了缩点,割点,割边,点双,边双,2-SAT,感觉比较需要注意的是割点的那个第一个节点的判断,写题的时候总是容易忘。然后又写了几道练习题。缩点#include<iostream>#include<cstring>usingna......
  • 聪明办法学Python丨202409TASK1学习笔记
        踏入Python编程的世界之初,我便深刻地体会到了这门语言的独特魅力。Python凭借其简洁明了的语法与强大的功能性,迅速吸引了我的注意。相较于C语言等编译型语言,Python的语法更加接近自然语言,这使得即使是初次接触编程的人也能快速上手。Python的设计理念强调代码的可......
  • 2024.9.16
    9点醒了。和gen友面基,请他吃了顿饭,之后绕着学校走了走。想起我小时候从西门来北大玩,在未名湖上溜冰。听说现在不让了,难过。回宿舍,下载农,打了会儿又删了,还是别打这种弱智游戏了。南京在刮台风,唉。和xjc聊,他说他做了个梦,是我跟他讲故事,说会有怪兽把所有退役的OIer吃掉......
  • 2024.9.16 下午 总结(考 DS)
    T1做法1:莫队。(考虑一个数的出现次数变化时的影响。)应该可以直接做,似乎也可以正难则反(见做法2)。做法2:[扫描线](?)。按询问右端点排序。记一下每个位置前面最近的和它权值相同的位置。一种是直接做,分讨。一种是正难则反:算前缀和;算出现次数为\(2\)的数的贡献之和,减去这部分贡献。......
  • 列表与克隆体专题 scratch 20240916_182231
    体验克隆体变量scratch20240916_153936_鲸鱼编程pyhui的技术博客_51CTO博客https://blog.51cto.com/u_13137233/12031738数据的容器列表scratch20240916_155811_鲸鱼编程pyhui的技术博客_51CTO博客https://blog.51cto.com/u_13137233/12031757多组列表共同表达同一数据sc......
  • 多组列表共同表达同一数据 scratch 20240916_170510
    需求如果点击空格就会产生一个克隆体克隆体会随机位置克隆体它会有自己的id同时克隆体会有自己的座标要求我们使用三个列表分别记录他们的id,x,y坐标同时如果点击了某一个克隆体那么就从列表中把它相对应的一组数据删除功能克隆体的id三个列表一个列表存id一个列表......
  • 数据的容器 列表 scratch 20240916_155811
    什么是列表列表是数据的容器创建列表列表添加内容清空内容查找数据根据位置查找数据修改数据删除数据根据下标删除数据遍历所有数据让主角依次把所有的数据都说一遍......
  • 体验克隆体变量 scratch 20240916_153936
    需求本体产生三个克隆体每个克隆体都会说出自己的血量如果鼠标点击这个克隆体角色克隆体的血量就减少同时他说出来的数据也就会变小制作克隆体变量克隆体变量一定要是私有的当本体被克隆时这个私有的变量也会被克隆不过克隆后就各是各的数据了最终代码......
  • 贪吃蛇游戏开发 scratch 20240916_140728
    项目名称贪吃蛇规则只要吃食物就会变长碰到边界就死亡碰到自己的尾巴就会死亡角色贪吃蛇食物障碍物关于图像图像分为矢量图与位图矢量图可以无限放大位图放大后会模糊绘制蛇头要求:使用一个圆形来画蛇头圆形有边框蛇头有两个眼睛蛇头有一根红蛇头使用矢量图来绘......