套题总结
Atcoder Grand Round
单独开了总结贴, 链接 https://www.cnblogs.com/mangoyang/p/9821052.html
HNOI2018
当时作为浙江初三选手去玩的时候挂的很惨, 一年后补完了.
寻宝游戏
考虑把操作序列也写成一个 01 串, 把 \(\text{and}\) 看成 \(1\) ,\(\text{or}\) 看成 \(0\) , 然后结果的某一位为 \(1\) 当且仅当从高位往低位比较, 操作序列的字典序比这一列写下来的 01 串的字典序小, 那么每一位可行的操作字符序列都是一个前缀和一个后缀, 随便维护一下取个交.
转盘
可以大力证明只会走一圈, 然后就变成每次修改求全局一个点下标 + 后缀 \(\max\) 的 \(\min\) , 然后线段树维护单调栈就好了.
毒瘤
把非树边的端点建出虚树会发现不在虚树的边上的点 \(dp\) 值都是不受影响的, 边上的点可以处理出虚树上每个点对其父亲的转移虚树, 枚举一下非树边端点的选取状态, 再 \(dp\) 一遍就好了.
游戏
每个点能到达的点是一个区间, 可以把点缩起来以后暴力扩展每个点的区间, 由于门具有单向的性质, 可以建出一个拓扑图, 按照拓扑序暴力更新复杂度就是对的了.
排列
首先问题可以转化为一棵树每个点必须在父亲之后选, 然后是一个比较厉害的原题, 在转化一步成联通块的问题, 每次找出全局最优值和父亲合并, 推一波式子发现一个联通块比另外一个联通块优的充要条件是平均值较小.
道路
提高组树型 \(dp\) ,\(f[u][x][y]\) 表示当前到了 \(u\) , 有 \(x\) 条没翻修铁路和 \(y\) 条没翻修公路, 然后就... 做完了.
TJOI2018
比较简单的一套题, 暑假的时候花了三天做的
数学计算
有可能不存在逆元, 所以直接线段树在操作序列上维护, 撤销就直接单点修改为 \(1\) .
智力竞赛
二分答案, 转成求 \(DAG\) 上可以相交的最少链覆盖, 传递闭包 + 二分图匹配就好了.
游园会
\(dp\) 套 \(dp\) , 里面的 \(dp\) 差分一下就只有 \(0,1\) 两种取值直接令 \(f[i][j][k]\) 表示当前串与给定串每一个前缀的 \(lcs\) 的差分值集合为 \(S\) , 与限定串匹配到了第 \(j\) 位的方案数, 预处理一下转移即可.
碱基序列
\(dp+hash\) 即可.
异或
树上可持久化字典树裸题
教科书般的亵渎
推个式子发现是个自然幂数和, 插个值就好了.
套题总结
来源: http://www.bubuko.com/infodetail-2992293.html