较高难度dp题目选做

发表于 2023-03-18

1.CF559E Gerald and Path

题目大意：

有条线段，每条线段给定其中一端的位置及长度，求所有线段覆盖的最大长度。

难度：Normal，*3000

大概就是要想着先对一端排序，然后每次钦定当前线段的方向然后去dp。

设计一个表示前条线段，最右端覆盖到位置时覆盖的最长长度。

转移的时候如果当前向右放就比较好处理，因为再往右没有被覆盖过的了，全是新的贡献。设当前线段固定的端点的位置是，则。

但是向左放的时候可能会出问题，因为他可能会覆盖到之间没有被覆盖过的部分。（前面的都太短了，而这个特别的长）

借个图：

所以为了避免这种情况，我们可以枚举一个，强制钦定的线段都往右放。

令表示当前这条线段往左放后左端点的位置，表示中所有线段的右端点的最大值，则有，正确性可以被感性理解。

2.CF1305G Kuroni and Antihype

剧透别看后面的白字 $\color{white}\text{~~逛洛谷看到有人在要MST的牛逼题就想到了这个~~}$

题目大意：

现在有个人，并且给出他们的年龄。两个人是朋友，当且仅当两个人年龄的按位与结果为。

现在，有一个传销组织，每个人有两种操作：

1、主动加入传销组织，这样的话，传销组织不会给你钱；

2、邀请自己的一个朋友加入传销组织，这样的话，传销组织会奖励你数值等于你的年龄的钱。（当然，执行该操作的人必须已经进入传销组织了）

每个人只可以进入传销组织一次。

现在，请你输出，如果个人通力合作，传销组织支付给这个人的钱数之和最大是多少。

难度：Normal+，*3500

妙！难点就一句话，上面的白字。

每个点只能加进这个组织一次，就像一棵树每个节点最多一个父节点一样，难度就在于怎么去构造这个MST。

设，且初始这个人已经加入了组织。如果将每个点在过程中选择的点与它之间连一条边，会得到一棵树。此时将和之间的边权设为，那么答案就是最大的边权减去总点权，就是最大生成树。

由于只有两个点与起来为才会有边，所以加法相当于是或。

这就可以推出一个能过的的做法了。从大到小枚举当前考虑到的边权（kruskal基操），然后枚举的一个子集，将和连起来。

此题还有的做法，留给读者自行思考。（用哪个啥B开头的MST算法）

3.CF1188D Make Equal

题目大意：

给出个数字，每次操作可以给其中一个数加上的非负整数次幂。求最少的操作次数，使得这个数相等。

难度：Hard-，*3100

我不会做，降智。

一个显然的（对我来说并不显然）的转化是要变为求的类型。（让按照从小到大排序）

下面让变为。（我怎么想不到啊）

从小到大决策当前这个的第位，有个相关的量：

这一位是不是
中有多少个数这一位是（接下来会产生进位）
前面为的进位对这一位产生的贡献

前两个好处理，就是第三个不好处理。

如果 bitmask 枚举前面那些数，那么复杂度就爆炸了（），显然过不去。

又是一个对我来说不显然的结论，就是对于最低的位来说，对第位产生进位的一定是那些中对取模后从大到小排序的一个前缀。证明显然。

令表示考虑了最低的位，上一位有个进位时的答案。

可以发现我们不关心这个数到底是多少，只关心的数量和进位的数量

令为中这一位数中的总数，为前个数这一位的总数。

上次进位，这一位是，有个。
上次进位，这一位是，有个。
上次未进位，这一位是，个。
上次未进位，这一位是，个。

这一位取，则进位，这一位是。

这一位取，则进位，这一位是1。

没了。有就是这玩意和基数排序很像，这么写可以减小常数。

4.CF739E Gosha is hunting

题目大意：

你要抓神奇宝贝！
现在一共有只神奇宝贝。
你有个『宝贝球』和个『超级球』。
『宝贝球』抓到第只神奇宝贝的概率是，『超级球』抓到的概率则是。
不能往同一只神奇宝贝上使用超过一个同种的『球』，但是可以往同一只上既使用『宝贝球』又使用『超级球』（都抓到算一个）。
请合理分配每个球抓谁，使得你抓到神奇宝贝的总个数期望最大，并输出这个值。

。

我可以出到。

难度：Easy—，*3000

就这也配*3000？？？

裸的wqs二分，套一次可以做到过原题，套两次就可以做到过。

那就简单写一下什么是wqs二分。

原题没有代价只有次数限制，现在我们想办法取消这个次数限制。

如果直接取消那么肯定是全部用掉最优，所以我们对每次用就加上一个代价。

然后二分这个代价，直到贪心（或者dp）后得到使用的次数和限制相同且答案最大。

5.CF1463F Max Correct Set

题目大意：

规定一组正整数。当且仅当满足以下条件时该组正整数成立：

如果并且，那么并且

对于给定的数值，你需要找到成立数组的最大长度。

难度：Normal+，*3100

神奇的思维题，和我之前做过的一道MO题好像？？？

结论是可以有个长度为的循环节。钦定，然后令表示考虑到了第位，最后位的 mask 位时的答案。（这样我们只用存位而不是位了，是个trick）

证明挺难的，可以参考 7KByte大爷的或者 feecle6418大爷的。

6.CF1616H Keep XOR Low

题目大意：

给你个整数和一个整数。

你需要求出的一个子集，满足中任意两个不同的元素，满足 $a_i~~{\rm xor}~~a_j\le x$。

求选取的方案数，对取模的结果。

难度：Normal+（可能我不熟悉这类题），*3000

一眼异或，鉴定为 01-trie。设计表示考虑到以为根的子树中，两两异或都的方案数。

这么dp会寄掉，应为当这一位是的时候它的两个子树间互相还有限制。

怎么办？大胆点，令表示在和中选若干个数，两两异或都的方案数。

看起来这个玩意很扯淡，但是是可行的。（记当前考虑到第层）

若的第位为，那么的左儿子和的左儿子的子树内的数异或起来一定不会大于了，的右儿子和的右儿子同理。所以现在我们只需要考虑的左儿子和的右儿子，以及的左儿子和的右儿子之间的限制，直接把两个值乘一下就行了。

若的第位为，那么的左儿子和的右儿子不能同时选数，的右儿子和的左儿子同理。所以把这两个dp值加一下，再加上单独在某个儿子里选数的方案就可以了。

7.[AGC024F] Simple Subsequence Problem

题目大意：

有一个 01 串集合，其中每个串的长度都不超过，你要求出至少是中个串的子序列的最长串，如果有多解，输出字典序最小的那组解。

由于可能很大，因此我们是这样描述的：

你将得到个 01 串，第个串的长度为。
第个字符串的第个字符，代表数字的、长度为的二进制表示是否出现在中。

。

难度：Hard（？），difficulty 3544

这是我的子序列自动机入门题。

题目相当于对于每个串，对其所有子序列的值+1，问你最后所有可能的01串的值的最大值是多少。

我们不可以枚举每个串的所有子序列，所以这之后就要用到一个叫做子序列自动机的玩意。

考虑如何贪心的去确定一个01串是不是另外一个01串的子序列。假设当前匹配串的开头是，那么我们要在模式串中找到开头第一个去和他对应。

所以我们就可以模拟这个过程，令为当前已经匹配好的串，为模式串剩余的部分，然后可以发现每种状态有两种出路（把模式串的开头匹配掉和从头开始第一个和开头不同的字符匹配掉）。

由于，所以我们就可以记录和，然后dp的时候枚举的长度，就可以方便的转移了（这样做可以直接省掉两个开头互相匹配的情况，十分方便）

参考代码

8.[AGC016F] Games on DAG

题目大意：

给定一个个点条边的DAG，对于每条边都满足，号点各一个石头，每次可以沿DAG上的边移动一颗石头，不能移动则输，求所有个边的子集中，只保留这个子集先手必胜的方案个数

难度：Normal（？）,difficulty 3754

我的博弈论入门题

这题本质上就是要求SG(1) 和 SG(2) 不相同，然后可以转化为减去相同的情况。

SG(i) 的定义：它的所有邻居的SG()的mex

所以我们就可以每次枚举新的SG()值为0的点，要求满足他们之间不能互相连边，之前枚举的所有不是0的点至少要向这些点中的一个点连边，这些点向不是0的点的连边没有要求

然后就是1号点和2号点要么同时在不是0的点，要么同时是新的0。

这是个子集枚举，复杂度

9.CF1149D Abandoning Roads

题目大意：

一张个点条边的无向图，只有两种边权（），对于每个，求图中所有的最小生成树中，从到距离的最小值。

难度：Hard++++，*3000

溜去看题解了。

你告诉我这只有3000？？？

这复杂度是人能想出来的？？？？

由于是在所有最小生成树中，所以有这么一个性质：一条连续的全为的路径肯定会出现在至少一棵MST中。

就有了这么一个结论：如果把原图中所有重边删掉，会剩下一些联通块。一条路径可能在最小生成树上，当且仅当它没有离开一个联通块后再回到原来那个联通块中。

然后就是令表示考虑已经走了状压后集合为的连通块，当前走到时最短路径的长度。转移用最短路转移。

这个方法时的，铁定过不去。

但是现在还有这么一个结论：我们不用考虑所有大小的连通块，因为这种连通块我们就算不把它压进去，它光是靠dijkstra就可以把它排除不会再进来了。（出去再回来至少要，而内部光靠就可以做到，更优）

结束了。妙死了啊！时间复杂度，如果用01bfs代替dijksta可以砍掉这个。

10.APC001F XOR Tree

题目大意：

给你一棵有个节点的树，节点编号从到，
树边编号从到。第条边连接节点和，其权值为。

你可以对树执行任意次操作，每次操作选取一条链和一个非负整数，将链上的边的权值与异或成为该边的新权值。

问最少需要多少次操作，使得所有边的权值都为0。

难度：easy-，difficulty 2865

就这也能黑题？洛谷恶评严重。

一个套路是将比边权下放到点权，令每个点的点权为它周围一圈边的权值的异或和。

现在如果对一条到的路径做异或，那么就相当于对点和的权值做异或，最终目标就是让所有点的权值都为。

最后就是玩消消乐，消完以后每种权值的数量不会超过，子集dp一下就行了。

11.CF232E Quick Tortoise

题目大意：

在一个的网格上，有一些格子是障碍。给定个询问，每次询问是否能只通过向下走和向右走从格子走到格子。

难度：Normal，*3000

有点套路的题，考虑分治。

如果当前这些询问中满足存在一行使得所有询问可能的路径都必须经过这一行的一个点，那么这些询问可以在的时间内完成。我们可以对这个网格上的每一个点维护一个bitset，第为表示能不能到那一行（所有询问必须经过的那一行）的第个点，转移的话随便或一下就可以了。

然后就可以分治了。起点和终点都在行上面、都在下面、剩下的都是必须经过行的。

12.CF1707E Replace

题目大意：

给定一个长为的序列，其中对于任意的满足。

定义一个二元组函数如下：

你需要回答次询问，每次给定，问其最少经过多少次的调用（即）使得变成，若无解请输出 -1。

难度：Hard++，清新思维题，*3500

这题中有区间max/min，就很自然的想到了ST表和倍增。

如果裸的倍增会很烦，因为有种区间，寄。

考虑能不能用类似ST表的方法来处理，就是用两个较大的、有交集的区间并称一个大区间，就能将缩小为了。

注意到，然后可以证明，这就可以用倍增维护了。

13.CF1710D Recover the Tree

题目大意：

你需要根据题目给出的信息构造出一棵树，满足如下条件：

树的节点个数为。
对于每个区间给出是或不是连通块。

数据保证有解，。

难度：Normal++，*3400

好题。

我们从小到大考虑所有可能的区间（类似区间dp的套路）。

假设我们当前考虑到有一个联通的区间，其中他们分别属于，其中。可以发现为中所有点属于的不同的连通块个数。如果的时候可以发现无解，的时候可以直接连接，如果的时候可以这么连接：。这样就可以保证和前面一个连通块之间的所有连通块不能构成一个大的连通块，而到就可以了。

14.CF1616G Just Add an Edge

这场的H也在这篇blog中，是#6，但应该没有这个G难/hsh

题目大意：

给定一个 DAG，边一定从编号小的点连向编号大的点，求有多少对使得且添加这条边后的图存在哈密顿路径。

难度：Hard+(*114514)，不会！

先咕着，明天中午看题解。

我超，终于看懂了，神仙题。

暴力很trivial。唯一的路径方式比较显然，就是，其中是一步到位，和是一步一步跳。

所以我们可以枚举考虑有多少个满足条件。令表示考虑到一个位置，能否由当前枚举的走到或者，转移显然。

考虑怎么优化。我们找到一个最靠做的满足和之间没有边，此时即为必经之路。我们可以将这个数断开来，左边和右边分别dp，然后容斥一下答案就行了。

证明可达的话，如果左边的能到，能到右边的，那么显然能到，反之同理。

注意一些细节。以及注意当时不好定义，所以这才是要加上和两个虚点的理由。

15.[AGC010E] Rearranging

题目大意：

有一个个数组成的序列。

高桥君会把整个序列任意排列，然后青木君可以进行任意次操作，每次选择两个相邻的互质的数交换位置。

高桥君希望最终序列的字典序尽量小，而青木君希望字典序尽量大。求最终序列。

难度：Normal，difficulty 3887

有这么难吗？洛谷和AT都恶评？我独立切了好吧。

哦等下我不会证明这个结论/qd

反正就是说，我们考虑建立图论模型。如果和不互质，那么怎么交换和之间的相对位置也不会改变。

所以，第一个人的操作就相当于对这个无向图定向，第二个人的擦欧总相当于求出这张DAG的一个最大拓扑序。

手玩以后可以发现结论：对于每个连通块，我们从最小的一个数入手，每到一个点，从小到大枚举其所有邻居，搜，并把指向。

然后用个priority_queue进行topsort就行了。

证明：贺的。

16.[AGC027E] ABBreviate

题目大意：

给定一个只含小写字母的字符串，每次你可以执行以下两种操作：

选取中连续的两个字符，把它们删去，替换成一个字符。
选取中连续的两个字符，把它们删去，替换成一个字符。

请你求出执行若干次操作后，能够得到的本质不同的字符串有多少个，答案对取模。

难度：Hard，difficulty *3634

根据大眼观察可以发现，如果令为，为，那么每次操作过后这个的总和是不变的。

我们考虑什么能由得到。对于中的每一个字符，都对应了中的一段字符，当且仅当中的这段字符的和和中这个字符的权值在模意义下同余，且中这段字符不是形如的结构。

证明参考小粉兔的blog

然后就可以dp了。记录以下前缀和，和一个数组表示后面第一个到的和模为的位置。