黑题计划

· · 个人记录

已在NOIP2022后结束

大概是因为长期以来对黑题的恐惧，随着我的(水)紫题AC达到了356题，我的黑题只AC了26题（沉迷水紫无法自拔）

现在比赛中都是黑题，考的紫题也多是一些以前感觉没啥用的黑科技。

就算是常规的紫题，在质量上也要吊打我现在切的水紫。

为了继续走下去，我认为有必要打破现在的情况。

我将尝试用我OI生涯的最后一点时间，冲破 黑题=不可做题 这一印象。

初步计划在省选前(如果没有在NOIP后AFO）将黑题AC顶上100。

——2022.10.26

这大概是我唯一一个会保持更新的博客，要是停了，那大概就是我AFO的时候。

出于实用性考虑，初步将围绕动态规划练习 动态规划进阶中的黑题展开，以思考为主，代码先咕着。

正在考虑加入IOI2020国家集训队作业 Part 1 Part 2

1.P4229 某位歌姬的故事 2022.10.26

IA 是一名会唱歌的女孩子。
_IOI2018 就要来了，IA 决定给参赛选手们写一首歌，以表达美好的祝愿。这首歌一共有 n 个音符，第 i 个音符的音高为 h_i​​。IA 的音域是 A，她只能唱出 1\sim A 中的正整数音高。因此 1\le h_i\le A。_
_在写歌之前，IA 需要确定下这首歌的结构，于是她写下了 Q 条限制，其中第 i 条为：编号在 l_i 到 r_i 之间的音符的最高音高为 m_i。在确定了结构之后，她就可以开始写歌了。不过她还是想知道，一共有多少种可能的歌曲满足她的所有限制？她听说你还有 9 个月就要去 IOI 了，于是希望你帮她计算一下这个值。_

作为该计划的第一道黑题，思考过程意外的顺利，大概只用了一个大课间就冲出来了了。
手玩一下发现m_i不相同的区间相交时，可以直接用大的抠掉小的，m_i相同的可以直接套用[NOI2020] 命运 的dp方法。复杂度\mathcal{O}(TQ^2)（用线段树优化后\mathcal{O}(TQ\log Q)）（似乎题解都采用了更直接的dp方法）

代码感觉有点毒瘤，有空再补。

2.String Journey 2022.10.26

_对于一个字符串数组 t_1, \ldots, t_k，若对于每一个 t_i 都是 t_{i-1} 的真子串的话，即 t_i 是 t_{i - 1} 的子串且 t_i \ne t_{i-1}，则称为有序串组，列如 \{\mathtt{ab}, \mathtt{b}\} 是，\{\mathtt{ab}, \mathtt{c}\} 和 \{ \mathtt{a}, \mathtt{a}\} 不是。_

_给定字符串 s，构造有序串组 t_1,\ldots,t_k 和任意字符串数组 u_1,\ldots,u_{k+1}，使 s=u_1+t_1+u_2+t_2 + \cdots +t_k+u_{k+1}，其中 + 为字符串的拼接_

现在给定一个字符串，求满足条件的最大 k。

黑题？下午自习课20分钟就冲出了\mathcal{O}(n\sqrt n)的做法，感觉不如紫题，回来看了眼题解，都是基于后缀结构的\mathcal{O}(n )的做法。

以后复习SAM的时候再补。 #### 3.[[HNOI/AHOI2018]毒瘤 ](https://www.luogu.com.cn/problem/P4426) 2022.10.27 _从前有一名毒瘤。_ _毒瘤最近发现了量产毒瘤题的奥秘。考虑如下类型的数据结构题：给出一个数组，要求支持若干种奇奇怪怪的修改操作（比如区间加一个数，或者区间开平方），并支持询问区间和。毒瘤考虑了 $n$ 个这样的修改操作，并编号为 $1\sim n$。当毒瘤要出数据结构题的时候，他就将这些修改操作中选若干个出来，然后出成一道题。_ _当然了，这样出的题有可能不可做。通过精妙的数学推理，毒瘤揭露了这些修改操作的关系：有 $m$ 对“互相排斥”的修改操作，第 $i$ 对是第 $u_i$ 个操作和第 $v_i$ 个操作。当一道题同时含有 $u_i$ 和 $v_i$ 这两个操作时，这道题就会变得不可做。另一方面，一道题中不包含任何“互相排斥”的修改操作时，这个题就是可做的。此外，毒瘤还发现了一个规律：$m-n$ 是一个很小的数字，且任意两个修改操作都是连通的。两个修改操作 $a,b$ 是连通的，当且仅当存在若干操作 $t_0,t_1,\cdots,t_l$，使得 $t_0=a,t_l=b$，且对 $1\leq i\leq l$，$t_{i-1}$ 和 $t_i$ 都是“互相排斥”的修改操作。_ _一对“互相排斥”的修改操作称为互斥对。现在毒瘤想知道，给定值 $n$ 和 $m$ 个互斥对，他共能出出多少道可做的不同的数据结构题。两道数据结构题是不同的，当且仅当有一个修改操作在其中一道题中存在，而在另一道题中不存在。_ 不如紫+1，显然dfs树，画下图就能大概就能想到把非树边拉出来当关键点建虚树，预处理虚树上每条边端点不同情况下的贡献，最后枚举非树边端点的情况就结束了。 复杂度大概是$\mathcal O (n+3^{m-n+1})$，看了题解，突然想起来可以容斥，可以优化到$\mathcal O (n+2^{m-n+1})$。 代码过于复杂，有空再补（不愧是毒瘤）。 #### 4.[[ZJOI2010]基站选址 ](https://www.luogu.com.cn/problem/P2605) 2022.10.27 _有 $N$ 个村庄坐落在一条直线上，第 $i(i>1)$ 个村庄距离第 $1$ 个村庄的距离为 $D_i$。需要在这些村庄中建立不超过 $K$ 个通讯基站，在第 $i$ 个村庄建立基站的费用为 $C_i$。如果在距离第 $i$ 个村庄不超过 $S_i$ 的范围内建立了一个通讯基站，那么就村庄被基站覆盖了。如果第 $i$ 个村庄没有被覆盖，则需要向他们补偿，费用为 $W_i$。现在的问题是，选择基站的位置，使得总费用最小。_ 思维僵化了，想了大半节英语课才想到要用数据结构，然后问题就很明朗了，维护从每个点转移的dp值就行了，不如紫+1。 AC on 2022.10.29 [评测记录](https://www.luogu.com.cn/record/91979154) ### 5.[Shrinking Tree ](https://www.luogu.com.cn/problem/CF1060F) 2022.10.27 _对于一棵有 $n$ 个节点的树 $T$ 。当 $T$ 的节点数多于一个时，反复执行以下操作：_ - _等概率地选取 $T$ 中的一条边。_ - _收缩选取的边：即合并这条边连接的两个点 $u$ 和 $v$ 。得到的新点的编号等概率地从 $u$ 和 $v$ 中选取一个。_ _当这个过程结束时， $T$ 只剩一个节点了，它的编号可能是 $1,\ldots,n$ 中的任意一个数。对于每个编号，请输出最终得到这个编号的概率。_ _$1\le n\le 50$。_ 这回踢到铁板了，这题只有2900？想了2节课才看出来是一个类似为每个点赋一个唯一权值，然后统计某种树上LIS的东西，又用了1节课搞出了一个$\mathcal O (n^5)$的dp，大概就是把树划分成不同块，每块内的边权小于该块根节点的父边，连向其他块的边权大于该父边（整个下午一节课没听），晚自习又想了好久都没有优化的方法（而且当时得到dp方法经验证是假的）。 回来看了题解，是个神仙的dp。 （钦定30黑） AC on 2022.10.31 [评测记录](https://www.luogu.com.cn/record/92405744) #### 6.[[NOI2014] 购票 ](https://www.luogu.com.cn/problem/P2305) 2022.10.28 _今年夏天，NOI 在 SZ 市迎来了她三十周岁的生日。来自全国 $n$ 个城市的 OIer 们都会从各地出发，到 SZ 市参加这次盛会。_ _全国的城市构成了一棵以 SZ 市为根的有根树，每个城市与它的父亲用道路连接。为了方便起见，我们将全国的 $n$ 个城市用 $1\sim n$ 的整数编号。其中 SZ 市的编号为 $1$。对于除 SZ 市之外的任意一个城市 $v$，我们给出了它在这棵树上的父亲城市 $f_v$ 以及到父亲城市道路的长度 $s_v$。_ _从城市 $v$ 前往 SZ 市的方法为：选择城市 $v$ 的一个祖先 $a$，支付购票的费用，乘坐交通工具到达 $a$。再选择城市 $a$ 的一个祖先 $b$，支付费用并到达 $b$。以此类推，直至到达 SZ 市。_ _对于任意一个城市 $v$，我们会给出一个交通工具的距离限制 $l_v$。对于城市 $v$ 的祖先 A，只有当它们之间所有道路的总长度不超过 $l_v$ 时，从城市 $v$ 才可以通过一次购票到达城市 A，否则不能通过一次购票到达。_ _对于每个城市 $v$，我们还会给出两个非负整数 $p_v,q_v$ 作为票价参数。若城市 $v$ 到城市 A 所有道路的总长度为 $d$，那么从城市 $v$ 到城市 A 购买的票价为 $dp_v+q_v$。_ _每个城市的 OIer 都希望自己到达 SZ 市时，用于购票的总资金最少。你的任务就是，告诉每个城市的 OIer 他们所花的最少资金是多少。_ 裸的李超树，维护到根链的转移。 #### 7.[Lanterns](https://www.luogu.com.cn/problem/CF1476F) 2022.10.28 _有 $n$ 个灯笼拍成一排，第 $i$ 个灯笼具有 $p_i$ 的亮度。每个灯笼要么朝向左，照亮左边编号为 $[i - p_i,i - 1]$ 的灯笼，要么朝向右，照亮右边编号为 $[i + 1, i + p_i]$ 的灯笼。_ _寻找一种方案，为所有的灯笼确定朝向，使得每一个灯笼被至少一个其他灯笼照亮。_ 这玩意难度有3000？跟上面那道2900的dp比起来简直是逊爆了，晚自习半小时就搞出来了。 裸的线段树优化dp，考虑前i个位置向右能延伸多远(无空隙)，唯一有启发性的是本题可以将$f_i$的值作为转移的条件（或许这更像是贪心？）。 开始写丑了导致调了好久。 AC on 2022.10.28(本计划AC的第一道题) [评测记录](https://www.luogu.com.cn/record/91964300) #### 8.[[CEOI2017] Mousetrap ](https://www.luogu.com.cn/problem/P4654) 2022.10.29 _有一个有 $n$ 个房间和 $n-1$ 条走廊的迷宫，保证任意两个房间可以通过走廊互相到达，换句话说，这个迷宫的结构是一棵树。_ _一个老鼠被放进了迷宫，迷宫的管理者决定和老鼠做个游戏。_ _一开始，有一个房间被放置了陷阱，老鼠出现在另一个房间。老鼠可以通过走廊到达别的房间，但是会弄脏它经过的走廊。老鼠不愿意通过脏的走廊。_ _每个时刻，管理者可以进行一次操作：堵住一条走廊使得老鼠不能通过，或者擦干净一条走廊使得老鼠可以通过。然后老鼠会通过一条干净的并且没被堵住的走廊到达另一个房间。只有在没有这样的走廊的情况下，老鼠才不会动。一开始所有走廊都是干净的。管理者不能疏通已经被堵住的走廊。_ _现在管理者希望通过尽量少的操作将老鼠赶到有陷阱的房间，而老鼠则希望管理者的操作数尽量多。请计算双方都采取最优策略的情况下管理者需要的操作数量。_ _注意：管理者可以选择在一些时刻不操作。_ 手玩一下就能看出是一个没啥营养的分讨+dp，做法很显然，但可以感知有一大堆细节，有空再补。 #### 9.[ [AHOI2022] 山河重整 ](https://www.luogu.com.cn/problem/P8340) 2022.10.29 _生活在 $998244353$ 号小宇宙的艾和兰收到了归零者的讯息，决定响应回归运动。他们需要把大部分的物质归还给大宇宙，只留下极少的物质用于在新宇宙重建自己的文明。_ _艾和兰的文明总共有 $n$ 个关键信息，编号为 $1, 2, \ldots, n$。他们需要保留的信息是这些关键信息的一个子集 $S$。对于一个编号为 $x$ 的信息，只要 $S$ 中一个子集的编号和等于 $x$，那么他们设计的漂流瓶就可以在新宇宙将 $x$ 还原出来。_ _艾和兰不禁想要思考，他们有多少种选择子集 $S$ 的方案，使得关键信息 $1, 2, \ldots, n$ 均能被还原？艾和兰自然是只用 $1$ 微秒就算出了方案数的精确数值，现在他们想让你帮忙验算。由于方案数可能很大，你只需要输出方案数对 $M$ 取模的结果。_ 有了[[FJOI2016]神秘数 ](https://www.luogu.com.cn/problem/P4587)的经验，可以看出需要的是某种拆分数，每个数小于前面所有数的和+1。 但是接下来就卡住了，这个东西一看就很难搞。 看了题解，也是个比较神的东西（可能只是我太菜了）。 AC on 2022.10.31 [评测记录](https://www.luogu.com.cn/record/92351717) #### 10.[Mr. Kitayuta's Gift ](https://www.luogu.com.cn/problem/CF506E) 2022.11.4 给定一个小写字符串 $s$ 和一个正整数 $n$。 要求在 $s$ 中插入恰好 $n$ 个小写字符使其回文的方案数，两个方案不同当且仅当它们得到的串不同，与插入顺序和位置无关。 $|s| \le 200$，$n \le 10^9$，答案对 $10^4 + 7$ 取模。 容易想到$\mathcal O (|s|^6\log n)$的矩阵优化dp。 然后才是本题神仙的地方，把这个dp看成再自动机上的转移，于是可以把本质相同的链拉出来，本质不同的链只有$\mathcal O(|s|)$个，复杂度来到$\mathcal O(|s|^4 \log n)$。 然后发现一条足够长的链得到的矩阵蕴含了其他情况，于是有了$\mathcal O(|s|^3 \log n)

11.Summer Dichotomy 2022.11.8

有 T 名学生，你要从中选出至少 t 人，并将选出的人分成两组，可以有某一组是空的。

_有 n 名老师，每名老师要被分配到两个小组之一，对于第 i 名老师，要求所在的小组中的学生人数 \in [l_i, r_i]。_

此外，有 m 对老师不能在同一个小组中。

你需要判断能否满足所有要求，如果可以，请给出一种方案。

t \le T \le 10^9，n,m \le 10^5。

很有意思的构造题
AC on 2022.11.8 提交记录

12.Berserk Robot2022.11.8

有一个机器人，第 0 秒时在 (0,0) 位置。

机器人会循环执行一个长度为 l 的指令序列，每秒执行一个指令。

指令有 ULDR 四种，分别代表向上/左/下/右移动一格。

_你不知道这个指令序列具体是什么，但是你知道 n 条信息，第 i 条信息为「第 t_i 秒时机器人在 (x_i,y_i)」，保证 t 递增。_

你需要构造一个满足这些信息的指令序列，或判断不存在。

_n \le 2 \times 10^5，l \le 2 \times 10^6，t_i,|x_i|,|y_i| \le 10^{18}。_

并不难，关键在于一个奇妙的坐标变换（果然还是见识太少了），即将坐标轴旋转 45^\circ ,于是可以将横纵坐标分开考虑，接下来就简单了。
显然如果我们确定了第一个周期的终点就可以将其他周期的点映射到第一周期，反之我们可以用其他周期的点来限制这个终点，然后乱搞大概就行了。

13.Tavas in Kansas 2022.11.8

难度不大，感觉要降紫。
把到两个起点距离离散化，然后考虑两边选到哪里，当前是谁选，倒着dp就行了。
AC on 2022.11.8
提交记录

14.Restoring Map 2022.11.9

有一棵 n 个点的树，你不知道这棵树的边是怎么连的。

你得到了 n 条关于每个点信息，每条信息记录了距离某一个点 \le 2 的所有点。

但你不知道每条信息具体是哪个点的。

你需要构造一棵满足这些信息的树。

n \le 10^3。

不难，容易找到非叶节点之间有边的充要条件，然后得到一个\mathcal O(n^3)的做法。
然后卡住了，打开题解一看，是bitset，复杂度来到\mathcal O(\frac {n^3}{w})。

15.[九省联考 2018] 秘密袭击 coat 2022.11.15

Access Globe 最近正在玩一款战略游戏。在游戏中，他操控的角色是一名 C 国士兵。他的任务就是服从指挥官的指令参加战斗，并在战斗中取胜。

_C 国即将向 D 国发动一场秘密袭击。作战计划是这样的：选择 D 国的 s 个城市，派出 C 国战绩最高的 s 个士兵分别秘密潜入这些城市。每个城市都有一个危险程度 d_i。_

C 国指挥官会派遣战绩最高的士兵潜入所选择的城市中危险程度最高的城市，派遣战绩第二高的士兵潜入所选择的城市中危险程度次高的城市，以此类推（即派遣战绩第 i 高的士兵潜入所选择城市中危险程度第 i 高的城市）。D 国有 n 个城市，n - 1 条双向道路连接着这些城市，使得这些城市两两之间都可以互相到达。为了任务执行顺利，C 国选出的 s 个城市中，任意两个所选的城市，都可以不经过未被选择的城市互相到达。

Access Globe 操控的士兵的战绩是第 k 高，他希望能估计出最终自己潜入的城市的危险程度。Access Globe 假设 C 国是以等概率选出任意满足条件的城市集合 S，他希望你帮他求出所有可能的城市集合中，Access Globe 操控的士兵潜入城市的危险程度之和。如果选择的城市不足 k 个，那么Access Globe 不会被派出，这种情况下危险程度为 0。

当然，你并不想帮他解决这个问题，你也不打算告诉他这个值除以 998\,244\,353 的余数，你只打算告诉他这个值除以 64\,123 的余数。