做题笔记 2023.2
CF808G Anthem of Berland 展开目录
数据范围明示 dp。首先在模式串上跑 kmp,预处理失配指针,dp 时遇到问号就暴力枚举字符集中每个字母,复杂度为
我们也可以允许匹配过程随时中止,然后钦定问号为期望的字符,这样可能会求出一些错误答案,但错误答案只会比正确答案小,所以不影响,在完成匹配时要更新所有 border 的答案,这样做正确性不是那么显然,复杂度优化至
CF702F T-Shirts 展开目录
买衣服的过程很复杂,考虑把人丢到数据结构内,按顺序枚举每件衣服进行修改。
相当于要维护这样的操作:对于所有
在平衡树上,我们可以拿出
总复杂度为
CF1100F Ivan ans Burgers 展开目录
前缀线性基模版题,可以
具体的,对每个前缀维护一个线性基,线性基内每一位记录一个 pos 表示此处的数在序列上的位置,每次插入,我们从大到小遍历线性基的每一位,如果当前数能插到这个地方且 pos 比原 pos 大,就交换两个数,并将原数异或当前数,拿着原数继续往下遍历。
我们达到的效果是,优先使得较大的位 pos 尽量大。
每次查询找到
LG8511 [Ynoi Easy Round 2021] TEST_68 展开目录
考虑找到全局异或和最大的两个点,那么除了这两个点到根路径上的点之外,所有点的答案都是这个最大值。
对于两条到根路径上的点,暴力计算答案即可,这部分每个点只会被插入 01trie 内
总复杂度为
LG6072『MdOI R1』Path 展开目录
由于一条路径的权值为路径上边权的异或和,我们维护每个点到根路径上边权的异或和,那么异或两个点就可以得到两点之间路径的权值。
另外,两条不交路径一定可以会被某个点分开,一条在该点的子树内,一条在子树外,考虑枚举每个点,计算子树内的两数最大异或和加上子树外的最大异或和,最后取最大值即可。
那么用上一题的方法就做完了本题的一半。
对于子树内,我们可以用 dsu on tree 做到
当然,注意到除了两条到根路径上的点之外,所有点子树外的答案都相同,为了让子树内答案更大,显然这个子树越大越好,那么我们只需要暴力计算两条路径上点所有儿子子树内的答案即可,每个点依然只会被插入 01trie
CF464D World of Darkraft - 2 展开目录
期望妙妙题。
每件装备相同且独立,考虑对每件装备单独计算答案。
注意到一件装备被升到
然后是常规的期望 dp。注意期望 dp 倒着做更简单。
CF464E The Classic Problem 展开目录
很早以前的模拟赛题。
主席树维护高精度即可,需要支持的操作有:比大小,单点修改 / 区间覆盖,找到某个位置之前的第一个 0。
主席树上也可以直接打 lazytag,但是 pushdown 的时候要新建结点,这样做的复杂度没有任何问题。
比大小和找 0 都可以通过维护哈希值解决,哈希用于判断两个区间是否相等以及一个区间是否全是 1,实现有少量细节,不多赘述。
这题可以直接用题目要求的大质数取模作为哈希,这样还不用特意去求值。
LG5826 子序列自动机展开目录
子序列自动机是个很平凡的东西,就是贪心的匹配靠前的字符,子序列自动机维护每个位置之后每个字符第一次出现的位置即可。
LG6239 [JXOI2012] 奇怪的道路展开目录
首先我们要求每个点只能向前连边。
设
刷表转移,枚举第
细节比较多。
神奇纸牌展开目录
转化后的一句话题意:
这类连通性计数问题通常和斯特林数 / 斯特林反演有关。
考虑容斥,设
因为连通块是无序的,所以会出现第二类斯特林数。接下来可以递推求解,也可以使用斯特林反演。
形式和二项式反演不能说非常相似只能说一模一样。目前还没有系统学过斯特林数相关的内容,而且多项式的技能树才刚开始点,要学的东西还不少。
打扫笛卡尔展开目录
转化后的一句话题意:定义树上一个点的权值为
设
即,考虑枚举左子树点数。边界是
发现和式内的部分是对称的,所以可以重新整理:
我们最后要求的是
剩下的内容就是拆开组合数和阶乘,变变形,前缀和优化转移,复杂度线性。
CF1785C Monsters (hard version) 展开目录
对于一个不降的序列
具体来说,设
可以用值域线段树(维护
CF715E Complete the Permutation 展开目录
很有意思的一道题。
简单来说,我们知道将一个长度为
这样的话,对于一个残缺的序列,我们会连出若干完整的环和若干残缺的环。对于一个残缺的环,在这个特殊的模型中,也就是一条链,我们发现其一定等价于一个孤立点或单独的一条边。我们将完整的环去除,将链缩成孤立点和边,图中就只剩下了:
- 孤立点,且左右两侧个数必然相等
- 从左向右的连边(简称 AB 边)
- 从右向左的连边(简称 BA 边)
不难发现,AB 边和 BA 边是绝对不会出现在一个环内的,我们先让孤立点和若干 BA 边(还有一些 BA 边自己拼成了环)组合形成 AB 边,然后让所有 AB 边组合,按这个顺序计数即可。
upd on 2023.3.28:这种二分图连边方式其实不太方便,如果使用的话一定注意,左向右连的边一定位置相同,右向左连的边一定值相同,思考的时候可以认为右边的点是完全不区分的(用连入的边确定位置,连出的边确定值)(那和
有啥区别 /fad)。
CF1681F Unique Occurrences 展开目录
考虑单独计算每种颜色的贡献。
某种颜色的边需要经过恰好一次,那么我们删去树上所有这种颜色的边,一条边的贡献就是树上两个相邻连通块大小的乘积。
线段树分治即可。除此之外还可以建虚树 dp 或直接在原树上换根 dp。
LG2664 树上游戏展开目录
对于这种数颜色问题,我们考虑计算每种颜色所作出的贡献。
大规模路径问题,考虑点分治。计算子树内结点对分治中心的贡献是平凡的,问题在于我们如何计算跨越分治中心的路径对一个端点的贡献。
对于每种颜色
Topcoder 13444 CountTables 展开目录
斯特林反演模版题。
我们钦定行的限制被满足,然后对列的限制进行容斥。注意这里为什么会出现斯特林数,因为「列」这个结构自带顺序,所以我们只需要进行等价类的划分,然后按照天然的顺序构造双射即可。
GYM100517C Comb Avoiding Trees 展开目录
满二叉树计数有一种奇妙的方法,即按照先序遍历顺序 dp,由于满二叉树的性质,从一个点到下一个点,只可能是走向左儿子或者退回上一个走向左儿子的点走向右儿子。
这道题用这种方式就可以做到
值得一提的是本题还能够做到线性单点求值,具体来说,我们的 dp 方程可以视作一个括号序列 / 格路计数模型,然后容斥即可。
CF765F Souvenirs / CF1793F Rebrending 展开目录
区间一维最近点对的模版题。
考虑对前
按照上面的思路,有两种实现方法,一种是先只考虑
LG2597 [ZJOI2012] 灾难展开目录
支配树模版题。这题的题解质量真的是够低的。
首先,给定起点
在支配树上,每个点的父亲是距离自己最近的支配点(不难发现不会有两个支配点到自己的距离相同),这里距离定义为最短距离或者什么别的东西都行,所有祖先是自己所有的支配点,子树内是被自己支配的点。
求支配树,我们考虑按照拓扑序,即每次找到入度为 0 的点,将其加入支配树,其父亲应该是所有入边起点在支配树中的 lca,这里求 lca 其实是对这些点的支配点集合取了个交,由于要支配树是由上到下逐步构造的,求 lca 最方便的方法是直接倍增,复杂度为
LG5513 [CEOI2013] Board 展开目录
初看这道题我的思路是用类似 The Classic Problem 的方法,通过线段树快速维护高精度二进制数,当然本题并不需要这么复杂。
由于我们是先进行了若干次修改,然后在进行查询,我们没有必要动态的维护高精度数,具体来说,每次进行加减饭我们并不进行进位 / 借位,当前位无论是
这样复杂度是线性的。
本作品采用 知识共享署名 - 非商业性使用 - 相同方式共享 4.0 国际许可协议 进行许可。