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 。
正解还没看懂。

相关内容

热门资讯

2岁孩子生命最后11天依然努力... 25岁的妈妈将患有罕见病的儿子兜兜送进了长沙的“雏菊之家”安宁病房。她陪伴儿子度过了最后11天,并每...
13岁少年被控杀害5岁男童案 ... 一名13岁少年因妹妹被邻居5岁男童撒沙而心生怨恨,将男童带至桥上推下水致其溺亡。此案引起了媒体的广泛...
全球顶尖科学家加速回流中国 风... 全球顶尖科学家纷纷选择离开美国,转向中国任职。2026年初,莱斯大学90后斯隆奖得主汪淏田全职加盟同...
APEC工商领导人峰会今天聚焦... 11月17日,来自亚太经合组织21个经济体及英国、法国、德国、瑞士等13个域外经济体的2000多位政...
雷军APEC发言 具身智能潜力... 11月17日,小米CEO雷军在2026年APEC工商领导人峰会上表示,具身智能机器人的潜力超过汽车,...
俄罗斯记者惊呼在深圳谁还用现金... 11月17日,今日俄罗斯国际通讯社记者德米特里·加夫里洛夫在接受采访时分享了他的深圳体验。他提到,刚...
雷军:智能机器人产业潜力超汽车... 11月17日,在2026年亚太经合组织工商领导人峰会上,小米CEO雷军介绍了公司在AI、智能制造和机...
保研举报成风,这不只是“坏人变... 保研举报成风,这不只是“坏人变小了” 制度留操作空间。高校保研季举报成风:这不是学生坏,是制度留了太...
广东01年医护女孩为00年闺蜜... 据河南广播电视台小莉帮忙,广东一位01年的女孩,亲自为自己00年的闺蜜接生。她们的缘分有多深?女孩称...
广东网友为迎接APEC会议周有... 11月14日,2026年APEC领导人会议周新闻中心举办了广东省、深圳市专场中外媒体吹风会。这是20...
动车插座在头顶被吐槽像在打吊瓶... 近日,有网友在社交平台发帖分享自己的乘车经历:乘坐D2928次动车组时,发现车厢内的充电插座安装在顶...
万斯称与特朗普无分歧 一致反对... JD·万斯周一表示,他与总统唐纳德·特朗普在伊朗战争问题上完全一致。此前,他曾将共和党在中期选举中的...
痛风人群这4种饮品要少喝 咖啡... 很多尿酸高、痛风人群都知道啤酒、果汁会升高尿酸,那么有没有什么饮料对尿酸“很友好”,甚至还能降低痛风...
医生辟谣左侧睡根本不伤心:正常... 11月17日,经常朝左睡对心脏的影响引发关注。从解剖学角度看,心脏虽然位于胸腔偏左,但它并非孤零零地...
96岁奶奶扒着车窗含泪送孙女返... 近日,湖南,假期快要结束,孙女准备返程。96岁的奶奶扒着车窗,眼里满是不舍。一句有空常回家看看,戳中...
人民日报:从《持械入宋》火爆看... 有能够让行业内外普遍认可的作品出现,是一种新文艺类型成熟的重要标志。正是因为“家里家外”系列、《盛夏...
灵岩寺外围山脊被刀片式铁丝网围... 11月16日,山东济南有网友发视频称,灵岩寺外围山脊被刀片式铁丝网围挡。视频画面中,一名徒友将铁丝网...
地板预留距离业主担心热胀冷缩 ... 陈先生的新房位于湖州德清,他说这段时间正在铺设木地板,去看了一下,结果发现“没有一个地方是对的”,希...
王传福:中国制造不是抢饭碗,而... 中国新能源汽车正积极拓展海外市场。11月17日,在深圳举办的2026年APEC工商领导人峰会上,比亚...
536分捡漏上北大考生被公派瑞... 11月16日晚,来自河南农村的赵同学宣布即将前往瑞士攻读博士学位,并感谢祖国的资助和老师们的帮助。他...