3/11 考试总结
创始人
2024-06-01 18:48:10
0

时间安排

7:30–7:50 读题,T1 是个利用随机性的题目,T2 dp,T3 不知道是啥。
7:50–8:30 T1,对于随机有个结论时最值突变不超过 log ,于是可以处理出所有 log 个区间然后统计答案,但这暴力做是个 3log 铁定过不去。
8:30–8:50 T2,对于部分分可以无脑容斥,以及状压 dp 什么的。
8:50–10:30 T1,写完暴力然后码。有 3log ,然后用线段树二分之类的可以去一个 3log ,再加上分讨就是 2log ,然后测大样例跑了 1s 多,自己随机造个数据要跑 10s 。卡卡常仍旧是过不去。
10:30–11:50 卡了卡T1,写T2部分分。

回顾反思

T1:
用到随机性质,我知道最值突变只有 log 次,但是不知道对应区间长度也是 log 次,于是直接暴力,稍微减减肢就是对的。
赛后问了问同学怎么观察出来的, wxq 说打表打出来的,而且他说他用正确性换时间,写的没有正确性但是随机就是能过。
这个结论积累一下。一个证明是,考虑笛卡尔树,随机时树高 log ,于是每个点贡献和累加再均摊,每个点子树大小平均就是 log 。
还是要学会多打打表,尤其时这种涉及一定随机乱搞性质的题目。
本场比赛在这道题上实在时太莽撞了,一直急着考虑能不能把 2log 卡进时限。几乎没有去看其他题,以至于 t3 送的插头 dp 的 50 分没有拿到。
在高分不能保证的时候还是要多去看看部分分。

T2:
两种做法通过值域分治拼起来,这两种做法在部分分上有所体现,自己也都能想到。
但是合并的方式比较神奇,还没太看懂。

T3:
首先是这场比赛一直在莽 T1 几乎没怎么思考这道题。
50 插头 dp 是送的。
然后对于多组询问,容易想到预处理前缀后缀拼起来。
至于更高的分数,则考虑不对一般的横平竖直的行列 dp ,观察到斜线的长度不满,对斜线 dp 。
正解还没看懂。

相关内容

热门资讯

安卓8录制系统声音,安卓8系统... 你有没有想过,用安卓手机录个视频,还能把系统里的声音也一起录下来?这听起来是不是很酷?想象你正在玩一...
安卓系统体感游戏,引领健康娱乐... 哎呀呀,你有没有想过,在沙发上就能动起来,和游戏里的角色一起跳跳蹦蹦?现在,这不再是梦想啦!随着科技...
安卓原生系统 如何刷,从入门到... 你有没有想过,你的手机里装的那个花里胡哨的系统,其实它有个超级酷的亲戚——安卓原生系统!想象没有那些...
鸿蒙怎样还原安卓系统,操作指南... 亲爱的手机控们,你们有没有想过,有一天你的华为手机从安卓变成了鸿蒙,然后你又想把它变回安卓呢?这可不...
如何关闭安卓盲人系统,安卓手机... 亲爱的手机用户们,你们有没有遇到过这种情况:手机屏幕突然变得“聪明”起来,不管你点哪里,它都“念念有...
安卓系统怎么装win,深度解析... 你有没有想过,你的安卓手机也能变身成为Windows系统的超级战士呢?没错,就是那个我们日常办公、学...
车载安卓系统进底层,车载安卓系... 你有没有想过,你的爱车其实也可以像智能手机一样,拥有一个智能的大脑呢?没错,就是那个我们熟悉的安卓系...
安卓系统版本英文缩写,Expl... 你有没有发现,你的安卓手机每次更新系统时,都会出现一些让人眼花缭乱的英文缩写?比如,Lollipop...
在车上安装安卓系统,打造个性化... 亲爱的车主朋友们,你们的车载系统是不是已经有点儿“老态龙钟”了呢?别急,今天我要给大家带来一个超级实...
鸿合安卓系统使用,引领智能教育... 你有没有遇到过这样的情况:一台看起来高大上的鸿合教学一体电脑,竟然只能显示安卓系统,电脑桌面却成了“...
安卓12系统是否成熟,成熟度与... 最近手机界可是热闹非凡呢!安卓12系统正式发布了,小伙伴们是不是已经跃跃欲试,想要一探究竟呢?今天,...
安卓系统剧机软件,打造沉浸式观... 你有没有想过,家里的老电视也能变身成智能剧机呢?没错,就是那种可以安装安卓系统软件的智能电视!今天,...
全站仪安卓系统,引领现代测量技... 你有没有想过,全站仪这个看似高冷的专业设备,竟然也能和安卓系统来个甜蜜的邂逅呢?没错,现在就让我带你...
安卓系统设置预装软件,揭秘安卓... 你有没有发现,新买的安卓手机里总有一些你不认识的应用?别急,今天就来给你揭秘这些神秘的小家伙,教你如...
安卓系统乱象怎么解决,全面解析... 你有没有发现,用安卓手机的时候,有时候会遇到一些让人头疼的小麻烦?比如APP版本号乱七八糟,更新速度...
安卓系统壁纸app苹果,海量美... 你有没有发现,手机里的壁纸可是我们个性的小秘密呢?今天,就让我带你一起探索安卓系统和苹果系统上那些让...
安卓系统如何充值etc,北京E... 亲爱的车主朋友们,你们是不是也在为ETC充值的事情烦恼呢?别急,今天就来教你们如何用安卓手机轻松搞定...
小米4系统安卓下载,畅享安卓8... 亲爱的手机控们,你是否曾为拥有一部性能卓越、价格亲民的智能手机而心动?小米4,这款曾经风靡一时的国产...
安卓港版系统怎么升级,轻松掌握... 你那安卓港版手机是不是已经有点儿“老态龙钟”了?别急,今天就来给你支个招,让你的手机焕发青春活力! ...
黑莓手机安卓系统吗,从Blac... 亲爱的手机控们,今天咱们来聊聊一个曾经风靡一时的品牌——黑莓。你可能听说过它,也可能对它有所了解,但...