个人刷题单及一句话心得题解(更新随缘)

数 据 结 构 题

点分治

P2634 [国家集训队]聪聪可可就是点分治,把长度对3的取模的剩余的个数取出来然后用1,2余数的合并成0的余数的,答案就是cnt[1]*cnt[2]*2+cnt[0]*cnt[0],至于为什么0的不乘2,因为会重复统计(可能一开始走了左边那个点,然后后面右指针又指到了)(悲)然后gcd搞搞约分就ok了

树链剖分

luogu P3313 [SDOI2014]旅行这个真没什么好讲的了,套路题,就是开多颗线段树维护不同教的信息,然后动态开点减少空间即可AC。点此康代码

LCA

luogu P2680 运输计划一道思维题,本来以为是树剖(确实可以),但实现麻烦,于是就二分答案然后树上差分判断,首先我们舍弃掉时间小于二分值的,因为它不用虫洞也不会对答案造成影响,然后对于剩下的找一个最长的且被剩下任务全包含的道路开虫洞,如果最长的任务行那就行了,否则就不行了,代码好写易懂,但是卡常恶心,必须要$tarjan$求$LCA$,把$log$变为$1$才可以通过。点此康代码

主席树

luogu P3302[SDOI2013]森林比较恶心,一开始还以为是$LCT$的题,但一看到第$k$小就想到了主席树,可以用启发式合并优化合并操作到$logn$,然后查询可以用树上点差分的方式优化到$logn$,但$LCA$细节十分恶心,比如不能用普通的倍增范围,因为有合并操作,然后还要一开始判断一下$x==y$,被卡了好久,维护的东西也较多。点此康代码

luogu P3168 [CQOI2015]任务查询系统这个就比较简单了,相较于$P3302[SDOI2013]森林$,离散化优先级$p$后直接差分开搞,比较套路题,就是获取$k$过程中要开LL。点此康代码

线段树

线段树合并

bzoj P4399 魔法少女LJJ 一看十分不可做的题,断点断边维护还以为要$LCT$,但是数据$c<=7$,还开了$20s$,所以线段树合并轻松水过,但是此题的合并姿势十分奇特,用一般的方法会$WA$,比如manchery学长的此题,具体原因我也不是特别清楚,甚至还因为这个卡了一个礼拜……,然后还有一大坑点是询问连通块权值之积,会爆$LL$,要用小数对数来存就可以了,涨姿势了。点此康代码

分块

P4168 [Violet]蒲公英分块求静态区间众数,怎么说呢,套路题,虽然动态我就不会了,但是也是一种姿势,考虑对于一个区间,只有区间块内的个数最大值和块外的数字在区间内出现的个数会可能成为众数答案,然后就可以轻松维护求解了。

数 学 题

P1829 [国家集训队]Crash的数字表格 / JZPTAB关于莫比乌斯反演中有提到。

算 法 题

CDQ分治(应该算算法吧)

P4169 [Violet]天使玩偶/SJY摆棋子明天更新

DP

斜率优化DP

[CEOI2004]锯木厂选址一道超级水的斜率优化题,因为$n^2$可过,就用sigma化简运算前缀和优化到$n^2$即可。

乱 搞 题

带 模 拟 题

评论

  1. 匿名
    5月前
    2020-7-19 9:41:07

    Orz

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇