QOJ杂题合集

QOJ #838. Horrible Cycles

QOJ #894. Longest Loose Segment/#21705.【PNR #4】序列

今天是 YQH 的生日，她得到了一个长度为 \(n\) 的整数序列 \(a_1,a_2,\dots,a_n\) 作为生日礼物。
然而，YQH 并不对这个序列满意，因为这个序列可能并不合法。
一个序列 \(\{a_i\}\) 合法，当且仅当 \(\max_{i=1}^n \{a_i\}+\min_{i=1}^n \{a_i\}>n\)，其中 \(n\) 为序列长度，特别的，我们规定 \(\varnothing\)是合法的。
为了让 YQH 满意，你需要找到一个 \(a_1,a_2,\dots,a_n\) 的一个子段，使得这个子段是合法的。一个序列 \(b_1,b_2,…,b_m\) 是 \(a_1,a_2,\dots,a_n\) 的子段当且仅当 \(b_1,b_2,\dots,b_m\) 可以由 \(a_1,a_2,\dots,a_n\) 删掉若干个（可以为 \(0\)）开头及结尾的元素得到，比如 \([2,3],[1,2]\),\([3,4],[1,2,3,4],\varnothing\) 都是 \([1,2,3,4]\) 的子段。
符合条件的子段可能很多，所以 YQH 只想要你找到，\(a_1,a_2,\dots,a_n\) 的所有合法子段的长度的最大值。
然而，YQH 得到的序列有魔力，所以它会产生变化，YQH 希望你对于初始的以及每次变化后的 \(\{a_i\}\) 都求出答案。
令所有变化的交换次数 \(k\) 之和为 \(K\)。
对于所有数据，保证 \(1\leq n\leq 10^6\)，\(0\leq m\leq 30\)，\(0\leq K\leq 10^6\)，\(|a_i|\leq 10^9\)，\(x_i\neq y_i\)。

QOJ #895. Color

给定一个有 \(n\) 个节点的无向完全图 \(G\)，每条边都被染成了 \(m\) 种颜色中的一种，颜色编号为 \(1\sim m\)。
我们称一个无向完全图合法，当且仅当对于 \(\forall x\in G\)，若存在 \((x,y),(x,z)\in E\)，满足 \(c(x,y)\neq c(x,z)\)，其中 \(c(u,v)\) 表示边 \((u,v)\) 的颜色。
可以证明合法的无向完全图的最大节点数量为 \(m+1\)。
请你求出是否可以在 \(G\) 的基础上扩展得到一个有 \(m+1\) 个节点的合法的无向完全图 \(G’\)。如果有，需要构造一组合法方案。
对于全部数据，满足 \(n,m\leq 200\)，\(n\leq m+1\)。

QOJ #957. Assignment Problem

QOJ #959. Multiple?

QOJ #962. Thanks to MikeMirzayanov/#21795.【PNR #6】排序

今天是 YQH 的生日，她得到了一个 \(1\sim n\) 的排列作为礼物。
YQH 是一个有强迫症的女孩子，她希望把这个排列从小到大排序，具体的，她可以进行这样的操作：
\(•\) 把 \([1,n]\) 分成若干个区间，假如是 \(m\) 段，依次为 \([l_1,r_1],[l_2,r_2],\dots,[l_m,r_m]\)，其中 \(l_1=1,r_m=n,l_{i+1}=r_{i+1},l_i\leq r_i\)。
\(•\) 假如原来的排列为 \(a_{1,\dots,n}\)，那么把排列变为 \(a_{l_m},a_{l_m+1},\dots,a_{r_m},a_{l_{m−1}},a_{l_{m−1}+1},\dots,a_{r_{m−1}},\dots,a_{l_1},a_{l_1+1},\dots,a_{r_1}\)，即把每一段看作一个整体，然后把这个排列进行 reverse。
YQH 希望进行尽可能少的操作，把序列从小到大排序。但是她太笨了，所以她找到你帮忙。注意，你不需要得到最小操作数。
对于全部数据，满足 \(n\leq 20000\)，你需要保证操作数 \(\leq 120\)。

QOJ #970. Best Subsequence

QOJ #1085. Brave Seekers of Unicorns/#21695.【PNR #3】异或序列

我们说一个长为 \(m\) 的正整数序列 \([a_1,\dots,a_m]\) 是好的，当且仅当它满足以下性质：
\(•\) \(m\neq 0\)，也就是序列非空。
\(•\) \(a_i>a_{i−1}\) (\(2\leq i\leq m\))，也就是序列严格递增。
\(•\) \(1\leq a_i\leq n\) (\(1\leq i\leq m\))，也就是序列的元素都是 \(\leq n\) 的正整数。
\(•\) \(a_i\operatorname{xor}a_{i+1}\operatorname{xor}a_{i+2}\ne 0\ (1\le i\le m-2)\)，也就是序列任意连续三项异或和都不是 \(0\)。
给定 \(n\)，请你数一数总共有多少个不同的好的序列。两个序列不同，当且仅当它们长度不同或者长度相同但是某个位置上的数不同。答案对 \(\text{mod}\) 取模。
对于所有测试点，\(1\leq n\leq 10^6\)，\(10^8\leq mod\leq 10^9\)。

QOJ #1088. Border Similarity Undertaking/#21696.【PNR #3】数圈圈

当今世界，科技飞速发展，AI 也会绘画了！不过本题中你要解决的任务比绘画简单很多，给你一张画，你要求出其中有多少个“圈”。
一幅画可以抽象为一个 \(n\) 行 \(m\) 列的字符数组 \(a_{i,j}\) (\(1\leq i\leq n,1\leq j\leq m\))，其中仅包含小写字母。如果一对字符数组中的位置 \((x_1,y_1),(x_2,y_2)\) 满足：
我们就说有一个以 \((x_1,y_1)\) 为左上角、\((x_2,y_2)\) 为右下角的“圈”。比如，下图中的所有 b 就构成一个圈：
\(•\) \(1\le x_1\lt x_2\le n,1\le y_1\lt y_2\le m\)；
\(•\) \(\forall i\in [x_1,x_2],j\in [y_1,y_2],a_{i,y_1}=a_{x_1,j}=a_{x_2,j}=a_{i,y_2}\)。

aaaaaaaaaaa
aabbbbbbbaa
aabaaaaabaa
aabaaaaabaa
aabbbbbbbaa

请你输出给定的字符数组中“圈”的数量。
对于所有测试点，\(1\leq n,m\leq 2000\)。

QOJ #1173. Knowledge Is…

QOJ #1177. Bookface/#21807.【PR #12】电塔

今天是 YQH 的生日，她得到了一套益智玩具—— \(n\) 个电塔作为生日礼物。所有电塔位于同一条直线上。具体的，把电塔所在直线抽象为一条数轴的非负半轴，那么第 \(i\) 个电塔位于数轴上 \(x_i\) 的位置。
假如两个电塔之间的相对距离严格小于 \(d\)，那么它们就会放电。在游玩一段时间后，YQH 感到厌倦了，于是她准备把这些电塔收拾起来。为了不浪费电，她希望把电塔调到都不放电的状态。
具体的，YQH 每次可以把某个电塔沿数轴正方向移动一个单位或沿数轴负方向移动一个单位，但是必须保证电塔位于数轴的非负半轴。你可以认为其他电塔不会干扰电塔的移动。
移动电塔是一个很累的行为，所以 YQH 希望求出移动电塔的最小次数，使得所有电塔都不放电。
对于全部数据，保证 \(1\leq T\leq 10^5\)，\(1\leq n\leq 2\times 10^5\)，\(1\leq d\leq 10^6\)，\(0\leq x_i\leq 3×10^{11}\)，\(\sum n\leq 10^6\)。

QOJ #1197. Draw in Straight Lines

QOJ #1337. Parity Sort

QOJ #1346. The Spellbook/#21749.【PR #8】饼干

今天是 YQH 的生日，她得到了一个记载了 \(n\) 条魔咒的魔法书和 \(k\) 个魔法饼干作为礼物，其中第 \(i\) 条魔咒需要花费 \(a_i\) 点蓝。作为一名见习魔法师，YQH 初始拥有 \(m\) 点蓝。
YQH 是一个充满好奇心的女孩子，她在得到魔法书的那一刻就想要把魔法书里的每一条魔咒都至少使用一次。但是她自己的蓝太少了，而补蓝需要花钱。具体的，YQH 可以做下列三种操作：
\(•\) 选择一条未使用过的魔咒，假设选择的魔咒是第 \(i\) 条。如果 YQH 持有的蓝大于等于 \(a_i\) 点，那么她持有的蓝减去 \(a_i\) 点，并记录第 \(i\) 条魔咒为使用过。
\(•\) 如果还有魔法饼干，YQH 可以吃掉一个魔法饼干并选择一条魔咒，假设选择的魔咒是第 \(i\) 条。如果此时 \(a_i\geq 1\)，那么令 \(a_i\) 减一。
\(•\) 假如现在 YQH 持有 \(a\) 点蓝，且 \(a<m\)，那么 YQH 可以花费 \(m−a\) 块钱来使自己持有的蓝加一。也就是说，假如 \(m=4,a=1\)，那么 YQH 把蓝补满的花费为 \(3+2+1=6\)。
聪明的你一定知道 YQH 把每条魔咒都使用过一遍所需最少的钱了，请把这个数目告诉她吧。注意，你不需要最小化饼干的使用数，也不需要关心最后 YQH 持有多少蓝。
对于所有数据，保证 \(1\leq n\leq 10^5\)，\(1\leq m\leq 10^6\)，\(1\leq a_i\leq m,0\leq k\leq \sum a_i\)。

QOJ #1359. Setting Maps

QOJ #1395. Trzy drogi [A]/#21729.【PCR #1 Day2】桥桥桥

给定一张 \(n\) 个点和 \(m\) 条边的无向联通图 \(G=(V,E)\)，其中第 \(i\)（\(1\leq i\leq m\)）条边连接了顶点 \(u_i\) 与 \(v_i\)（\(1\leq u_i,v_i\leq n\)）。
对于一个边集 \(E\) 的子集 \(E′\subseteq E\)，如果在删除 \(E′\) 后，存在两个顶点 \(u,v\in V\) 满足 \(u\neq v\)，且顶点 \(u\) 与 \(v\) 在新图中不连通，则我们称 \(E′\) 为图 \(G\) 的一个割集。
你想要知道 \(G\) 的边集 \(E\) 的所有子集中，有多少个大小恰好为 \(3\) 的割集。
对于所有数据，\(2\leq n\leq 2\times 10^5\)，\(3\leq m\leq 5\times 10^5\)。保证给出的图是一张连通无向图，可能包含重边，但不包含自环。

QOJ #1427. Flip/#21673.【PNR #1】波特分组

有 \(2n\) 个 bot，编号分别为 \(1\sim 2n\)，你想把他们分为两组，每组 \(n\) 个 bot，分法如下：
\(•\) 所有 bot 按编号从小到大顺序抛一枚完全均匀（正反面朝上概率均为 \(0.5\)）的硬币。
\(•\) 如果硬币正面朝上就被分进 A 组，除非 A 组已经有 \(n\) 个 bot（这时他被分进 B 组）。
\(•\) 如果硬币反面朝上就被分进 B 组，除非 B 组已经有 \(n\) 个 bot（这时他被分进 A 组）。
有 \(q\) 次相互独立的询问，每次询问给定 \(k\) 个 bot 的编号 \(b_1\sim b_k\)，求这 \(k\) 个 bot 被分进同一组的概率。答案对 \(998244353\) 取模。
对于所有数据，\(2\le n\le 10^5\)，\(1\le q\le 10^5\)，\(1\le b_i\le 2n\)，\(b_i>b_{i-1}\)，\(2\le k\le n\)，\(\sum k\le 2\times 10^5\)。

QOJ #1429. Hit

数轴上有 \(n\) 个区间。你要在数轴上撒至多 \(n\) 个点，使得每个区间内至少有 \(1\) 个点，并要求使区间内点数最大值最小。
对于全部数据，满足 \(n\leq 10^5\)。

QOJ #1431. Joy/#21758.【PR #9】比赛

有 \(n\) 个人参加一场比赛，小多是其中之一。这里，\(n\) 一定是 \(2\) 的正整数次幂。
参加比赛的 \(n\) 个人排成一队，从左到右分别编号为 \(1,2,\dots,n\)。第 \(i\) 个人有自己的能力值 \(a_i\)。能力值为 \(x\) 的人和能力值为 \(y\) 的人决斗，胜者为前者的概率是 \(\dfrac{x}{x+y}\)，为后者的概率是 \(\dfrac{y}{x+y}\)。
比赛的过程如下：
\(•\) 若现在只剩下一个人，这个人就是最终赢家。
\(•\) 否则，让现在队列里排在最左边的两个人，不妨设为 \(A\) 和 \(B\)，进行决斗。\(A\) 和 \(B\) 中的败者离开比赛，胜者回到队列的最右边。
现在，小多已经摸清了所有人的能力值（包括自己），也知道了除了自己以外其它人在队列中的顺序，但他不知道自己在队列中的位置。把自己插进剩下 \(n−1\) 个人的队列中，共有 \(n\) 种可能。对于每种可能，请你求出小多成为最终赢家的概率。
所有数据满足 \(2\leq n\leq 4096\)，\(1\leq x,a_i\leq 10^4\)，存在正整数 \(k\) 使得 \(n=2^k\)。

QOJ #1436. Split in Sets

QOJ #1462. Euclid’s Algorithm

给定两个正整数 \(d,k\)，求出最大的正整数 \(x\)，使得 \(x|((a+d)^k−a^k)\) 对所有正整数 \(a\) 成立。
对于所有数据，保证 \(1\leq d,k\leq 10^{100}\)。

QOJ #1809. Find the MST for Grid/#21625.【PR #3】最小生成树

有一张 \(n\times m\) 的网格图，第 \(x\) 行第 \(y\) 列的格点记为 \((x,y)\)，给定四个单调不降数组 \(A,B,C,D\)，网格图的边权由这四个数组决定，具体的：
\((x,y)\) 和 \((x+1,y)\) 之间的边权为 \(A_x+B_y\)。
\((x,y)\) 和 \((x,y+1)\) 之间的边权为 \(C_x+D_y\)。
你需要求出这张网格图最小生成树的大小。
对于所有数据，保证 \(2\leq n,m\leq 10^5, 1\leq A_i,B_i,C_i,D_i\leq 10^6\)。保证 \(A_i\leq A_{i+1}, B_i\leq B_{i+1}, C_i\leq C_{i+1}, D_i\leq D_{i+1}\)。

QOJ #1813. Joy with Permutations/#21651.【PR #4】猜猜看

hhz 有一个 \(1\) 到 \(n\) 的排列，你需要猜出它。
你只能问 hhz 以下两个问题：
给定不同的两个数 \(i,j\)，hhz 会告诉你 \(a_i\) 和 \(a_j\) 的大小关系。
给定两两不同的 \(i,j,k\)，hhz 会告诉你 \(a_i,a_j,a_k\) 的中位数。
你只能进行 \(2\) 次询问 \(1\) 和 \(m\) 次询问 \(2\)，你需要猜出这个排列。
对于所有数据，\(50\leq n\leq 5\times 10^5\)，\(2n\leq m\leq 10^6\)。交互库自适应。

QOJ #1825. The King’s Guards/#21614.【PR #1】守卫

在 P 国有 \(n\) 个村子，以及 \(m\) 条待修建的双向公路，第 \(i\) 条公路连接 \(u_i\) 和 \(v_i\)，修建的代价为 \(w_i\)。
国王找到了 \(k\) 个守卫，每个守卫将入驻一个村子，第 \(i\) 个守卫能入驻的村子是集合 \(S_i\)。
国王将派遣每个守卫去一个村子，并修建一些公路。
国王希望整个国家得到保护的同时，尽可能节省开支。因此他希望每个村子可以被恰好一个守卫经过若干条公路到达。
国王想要知道，是否存在一种修建公路和派遣守卫的方案，如果存在，修建公路的代价之和最小是多少。
对于所有数据，\(1\leq n\leq 300\)，\(0\leq m\leq \dfrac{n(n-1)}{2}\)，\(1\leq k\leq n\)，\(1\leq w_i\leq 1000\)。保证 \(1\leq u_i\lt v_i\leq n\)，\(1\leq |S_i|\leq n\)，\(1\leq s_{i,j}\leq n\)，\(\forall i\neq j,(u_i,v_i)\neq (u_j, v_j)\)，\(\forall x,i\neq j,s_{x,i}\neq s_{x,j}\)。

QOJ #1839. Joke/#21750.【PR #8】消愁

对于两个排列 \(p,q\)，称 \(01\) 串 \(s\) 是消愁的当且仅当存在存在一个 \(2\times n\) 的矩阵 \(a\) 满足：
\(•\) \(1\) 到 \(2n\) 中的每个元素都在矩阵中出现；
\(•\) \(a_{1,i}<a_{1,j}\)，当且仅当 \(p_i<p_j\)；
\(•\) \(a_{2,i}<a_{2,j}\)，当且仅当 \(q_i<q_j\)；
\(•\) \(a_{1,i}<a_{2,i}\)，当且仅当 \(s_i=0\)。
定义 \(f(p,q)\) 为有多少 \(01\) 串对于这两个排列是消愁的。
现在给定排列 \(q\) 的一部分和排列 \(p\)，求对于所有把 \(q\) 补全的方案，\(f(p,q)\) 之和。
对于 \(100\%\) 的数据，\(1\leq n\leq 100\)，\(1\leq p_i\leq n\)，\(0\leq q_i\leq n\)，对于 \(i=\neq j\)，\(p_i=\neq p_j\)，且若 \(q_iq_j\neq 0\)，\(q_i\neq q_j\)。

QOJ #1849. 2048 [TAG: Removed Problem]/#21633.【PER #2】2048

pb 大师喜欢玩 2048。
pb 大师在一个 \(1\times n\) 的网格上玩 2048，初始 \(n\) 个格子都是空的。
游戏会进行若干轮，每轮将发生如下事件：
\(•\) 如果没有空位，游戏结束。否则随机一个 \(1\) 到 \(m\) 的数，随机到 \(i\) 的概率是 \(p_i\)，再等概率随机一个空位，在空位中填入 \(2^{i−1}\)；
\(•\) 将所有数顺序不变移到最左侧。例如 _ _ x _ y z 会变成 x y z _ _ _。
\(•\) 如果没有相邻相同的数，这一轮结束。否则从左往右最后一对相同的数变成他们的和以及一个空位，并且他的得分会加上产生的和，例如 x y y z _ _ 会变成 x 2y _ z _ _，并且 pb 大师会得到 \(2y\) 分，接下来回到第二步。
pb 大师想要知道：他的期望总得分是多少。
对于 \(100\%\) 的数据，\(1\leq n,m\leq 2000,1\leq a_i\leq 100\)。

QOJ #1869. Power Station of Art/#21688.【PNR #2】图同构

有两张边集相同的图 \(A,B\)，每个点都是红黑二色之一，并且带着点权 \(a_i\)。
你可以执行以下操作零次或任意次：
\(•\) 选择一张图和相邻的两个点 \(u,v\)。
\(•\) 交换 \(a_u\) 和 \(a_v\)。
\(•\) 如果 \(u\) 和 \(v\) 同色，则将他们同时反色，否则颜色保持不变。
你想要知道，两张图能否变得相同，即所有点的颜色和点权对应相同。
对于所有数据，保证 \(1\leq T\leq 3\times 10^4\)，\(1\leq n,\sum n\leq 10^6\)， \(0\leq m,\sum m\leq 10^6\)，\(1\leq u, v\leq n\)，\(0\leq a_i,b_i\leq 10^9\)，\(c_i,d_i\in \{‘R’,’B’\}\)，图中无重边无自环。

QOJ #1875. Nein/#21652.【PR #4】到底有没有九

对于正整数 \(k\)，定义魔法数 \(x\) 满足 \(x\times (10^k−1)\) 的十进制表示不包含 \(9\) 的正整数，你需要求出第 \(n\) 个魔法数。
对于所有数据，\(1\leq k\leq 18\)，\(1\leq n\leq 10^{18}\)。

QOJ #1878. No Rest for the Wicked

QOJ #1880. Nikanor Loves Games/#21650.【PR #4】赌徒

萌新小 H 和他的 \(n\) 个好朋友玩游戏！
他们将要玩的游戏是抛硬币，小 H 和他的对手分别抛出硬币，如果小 H 抛出的数值大于等于对方的，则小 H 赢，否则对手赢。
第 \(i\) 个好朋友有一个两面分别为 \(a_i\) 和 \(b_i\) 的硬币，他和小 H 赌 \(x_i\) 个钢镚，即如果小 H 赢则他获得 \(x_i\) 个钢镚，否则失去 \(x_i\) 个钢镚。
小 H 还没有硬币，它可以去邪恶工匠大 D 定制一枚硬币。若小 H 得到的硬币两面分别是\(a,b\)，则 \(a,b\) 都需要是正整数，并且他需要支付 \(ab\) 个钢镚。
小 H 想知道，如果他选择一枚合适的硬币，他期望最多能挣到多少钢镚。
注意小 H 很富有，他初始有足够多的钢镚，不需要考虑钢镚不足以支付的情况。
对于所有数据，保证 \(1\leq n\leq 5\times 10^5\)，\(1\leq a_i,b_i,x_i\leq 10^9\)。

QOJ #2065. Cyclic Distance

QOJ #2068. Fast as Ryser/#21682.【PER #3】匹配求和

给定一张 \(n\) 个点 \(m\) 条边的无向图 \(G=(V,E)\) 与常数 \(c\)。定义一个边集的子集 \(S\subseteq E\) 的权值 \(f(S)\) 如下：
\(•\) 如果存在两条边 \(e_1,e_2\in S\) 满足其交于一个公共的顶点，那么 \(f(S)=0\)；
\(•\) 否则，\(f(S)=c^{|S|}\)。
即当 \(S\) 为 \(G\) 的一个匹配时，\(f(S)=c^{|S|}\)，否则 \(f(S)=0\)。
现在你需要求：$$g(G) = \sum_{S \subseteq E} f(S)$$ 由于答案可能很大，因此你只需要输出它对 \(10^9+7\) 取模后的结果即可。

QOJ #2378. Tree Permutations

QOJ #2544. Flatland Currency/#21689.【PNR #2】找零

在一个遥远的国家用着这样一套货币系统：纸币的面额分别是 \(500,100,50,10,5,1\)。
在一家商店里有 \(n\) 个物品出售，第 \(i\) 个物品的价格是 \(a_i\)，每样物品只有一个。
你有 \(X\) 元钱，并且手上的纸币恰好是能表示出 \(X\) 的方案里最少的一组。
你可以进行若干次操作，每次顺序执行每一步：
\(•\) 选择若干个没买过的物品。
\(•\) 用你手上的一些纸币付钱。可以多付，不能少付。
\(•\) 商店用最少的纸币给你找零。商店的纸币是无限的。
你希望在进行若干次操作之后最大化手上面额为 \(1\) 的纸币数量。求出最大数量。
对于所有数据，保证 \(1\leq n\leq 10^5\)，\(1\leq X\leq 10^{14}\)，\(1\leq a_i\leq X\)。

QOJ #2550. Lion and Zebra

QOJ #2559. Endless Road/#21659.【PR #6】区间数颜色

给定数轴上的 \(N\) 个区间 \([L_i,R_i)\)，满足两两不同且长度单调不降，即对 \(1\leq i<j\leq n\) 保证 \(R_i−L_i\leq R_j−L_j\)，且 \(L_i=L_j\) 和 \(R_i=R_j\) 不同时成立。
初始时数轴是白色的，进行 \(N\) 次操作，每次选择一个之前没有选择过的区间 \([L_i,R_i)\)，将这个区间染成黑色，要求染完之后黑色部分的总长度尽量小，若相同则选择编号最小的。求每次操作选择的区间的编号。
对于所有数据，\(0\leq N\leq 2.5\times 10^5\)，\(0\leq L_i<R_i\leq 10^9\)，对 \(1\leq i<j\leq n\) 保证 \(R_i−L_i\leq R_j−L_j\)，且 \(L_i=L_j\) 和 \(R_i=R_j\) 不同时成立。

QOJ #2562. Fake Plastic Trees 2/#21624.【PR #2】背包

给定一棵 \(n\) 个点的树，点编号从 \(1\) 到 \(n\)。每个点有一个非负权值 \(a_i\)。
你需要把树上的一些边删掉。你需要保证，删掉之后，每个连通块的权值之和在区间 \([L,R]\) 中。
给定非负整数 \(K\)，对于每个 \(0\leq i\leq K\)，判断能否恰好删去 \(i\) 条边。
对于所有数据，\(1\le T\le 1000\)，\(1\le n,\sum n\le 1000\)，\(0\le K\le \min(50,n-1)\)，\(0\le L\le R\le 10^{15}\)，\(0\le a_i\le 10^{15}\)。

QOJ #2570. Maximal Subsequence/#21631.【PER #1】子序列

给定一个长度为 \(n\) 的序列，你需要找到一个最长的子序列，使得这个子序列的最长上升子序列长度小于原序列的最长上升子序列长度。
对于所有数据，\(1\leq n\leq 5\times 10^5\)，\(1\leq a_i\leq 10^9\)。

QOJ #2571. Aidana and Pita/#21632.【PER #1】平均分

有 \(n\) 个饼，第 \(i\) 个饼的权值为 \(a_i\)。
你想用胎教时候就学过的除法把这 \(n\) 个饼平均分成三份，使得每一份的权值之和都相等。
但是你发现饼不能切开，所以只能退而求其次，最小化极差，也就是最大的权值之和减去最小的权值之和。
对于所有数据，保证 \(3\leq n\leq 25\)，\(1\leq a_i\leq 10^7\)。

QOJ #2606. Gachapon/#21627.【PR #3】抽卡

你在玩一个抽卡游戏。
这个游戏有 \(n+1\) 种级别的抽卡方式，编号为 \(0,1,\dots,n\)。抽出来的每张卡的等级是 \([0,m]\) 中的一个整数。
一次 \(0\) 级抽卡就是只抽一次卡，而一次 \(i\) 级抽卡 \((1\leq i\leq n)\) 会包含 \(b_i\) 次 \(i−1\) 级抽卡，并且这次 \(i\) 级抽卡合法当且仅当它包含的所有 \(i−1\) 级抽卡合法，且抽出来的卡中至少有一张的等级大于等于 \(i\)。
对于每次 \(0\) 级抽卡，抽出一张等级为 \(j\) 的卡的概率是 \(\dfrac{a_j}{\sum_{k=0}^m a_k}\)。
设 \(p_j\) 表示在一次合法的 \(n\) 级抽卡中抽出等级为 \(j\) 的卡的期望次数，\(q\) 表示一次 \(n\) 级抽卡合法的概率。你需要对于 \(0\leq j\leq m\) 求出 \((p_j\cdot q)\bmod {998244353}\)。
对于所有数据，\(1\le n\le m\le 4000,1\le a_i\le 4000,2\le b_i\le 4000\)，保证 \(a_i,b_i\) 在范围内均匀随机。

QOJ #2609. Number Guessing/#21626.【PR #3】猜数

这是一道交互题。
Alice 有一个 \([1,1018]\) 的整数 \(y\)，而 Bob 想要求出这个数，所以 Bob 每次会选一个 \([0,1018]\) 的整数 \(x\) 向 Alice 提问。如果 \(y>x\) 则 Alice 返回 \(2\)，如果 \(y=x\) 则 Alice 返回 \(1\)，如果 \(y<x\) 则 Alice 返回 \(0\)。
然而，Alice 和 Bob 的通信被 Eve 截获了。Eve 写了一个伪随机数生成器：

const long long P=998244353; // 不一定是这个数。
const int n=3; // 也不一定是这个数。
long long seed=233; // 更不一定是这个数。
int gen()
{
    seed=seed*n%P;
    return seed%n;
}

每次 Alice 返回一个数 \(a\) 时，Eve 会用这个伪随机数生成器生成一个数 \(b\)，并给 Bob 返回 \(a\oplus b\)（异或，即 c++ 里的 ^ ）。
你是 Bob，并且你用一些操作得到了 \(P\) 和 \(n\)，但是你不知道 \(seed\)。你需要在 \(100\) 次询问内得到 \(y\)。
对于所有数据，\(10^3\le P\le 10^{18},3\le n\le 4,0\le seed<P,T\le 100,Q_{\min}=100,Q_\text{max}=200\)，保证 \(P\) 为质数。

QOJ #2610. Build a City/#21663.【PR #7】杜杜和 DUDU

DUDU 是只可爱的小熊，喜欢乱吃农场主杜杜的蜂蜜，因此杜杜希望修一个长方形的篱笆，包裹住所有蜂蜜点，从而将 DUDU 隔离在外。
具体而言，杜杜有 \(n\) 个养殖蜂蜜点，依次为 \((x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)\)。任何时刻篱笆都是长方形的。假设有篱笆位于 \((X,Y)\)，\((x_i,y_i)\) 位于长方形里边当且仅当 \(x_i\leq X\) 且 \(y_i\leq Y\)。由于修建过程不能被 DUDU 知晓，杜杜建造篱笆要满足特定的规律！
我们需要进行一轮轮的扩建，直到我们的篱笆包裹住了所有蜂蜜点。假设当前篱笆位于 \((X,Y)\)，扩建的时候我们会选择一个 \((x_j,y_j)\) 满足其不在篱笆里边，然后我们会扩建至 \((\max(X,x_j),\max(Y,y_j))\)。令 \(A=\max(X,x_j),B=\max(Y,y_j)\)。DUDU 有个察觉值 \(m\)，所以这次扩建还需要满足 \((A,B)\) 的篱笆周长减去 \((A,B)\) 和 \((X,Y)\) 的公共部分不超过 \(m\)。详细解释如下:
\(•\) 若 \(X=A\)，那么 \(2(B−Y)+X\leq m\)。
\(•\) 若 \(Y=B\)，那么 \(2(A−X)+Y\leq m\)。
\(•\) 其他情况，\(2A+2B−X−Y\leq m\)。
试问杜杜有没有扩建的方案，多组测试数据。
对于所有数据，\(x,y\leq 10^9\)，\(m \leq 4\times 10^9\)，\(\sum n\leq 5\times 10^5\)，记 \(L\) 为所有数据中 \(n\) 的最大值，记 \(S=\sum n^2\)，\(H=\sum n^3\)。

QOJ #2620. Escaped from NEF/#21637.【PER #2】仙人掌

在参加 P 国主办的 Pre-SDOI Training Camp（也被称作 Public Easy Round #2）时，你遇到了一道这样的题：
给定一个 \(n\) 个点 \(m\) 条边的有向图 \(G\)，保证其基图 \(G’\) 是仙人掌且没有重边自环。你需要求出有序点对 \((x,y)\) 的个数，使得在 \(G\) 中存在一条从 \(x\) 到 \(y\) 的路径。特别地，\((x,x)\) 也需要计入答案。
仙人掌的定义：一个连通的简单无向图，且每条边都在至多一个简单环内。
基图的定义：对于一个有向图 \(G=(V,E)\)，定义一个新的无向图 \(G’=(V,E’)\)，且 \(E’\) 就是把 \(E\) 的每条有向边替换为无向边得到的边集。称 \(G′\) 为 \(G\) 的基图。
对于所有数据，保证 \(1\le T\le 10^5, 2\le n\le 2.5\times 10^5, n-1\le m\le \left\lfloor \dfrac{3(n-1)}{2}\right\rfloor, \sum n\le 2.5\times 10^5\)。

QOJ #2624. Implemented Incorrectly/#21656.【PR #5】循环移位

有一个非常简单的问题：给定一个 \(1\sim n\) 的排列 \(p\)，求出它唯一一个以 \(1\) 开始的循环移位。
小 T 写出了如下代码：

for (int i=2;i<=n;i++)
    if (p[i]<p[1])
        shift(i); // 把 p 变成 p[i],p[i+1],...,p[n],p[1],...,p[i-1]

给定正整数 \(n\)，求出有多少个不同的排列 \(p\) 会使得上面这个算法输出错误的结果。注意答案不需要取模。
对于所有数据，\(3\leq n\leq 42\)，保证在同一档数据中，\(n\) 近似均匀分布。

QOJ #2709. Travelling Merchant

QOJ #2808. Gardening/#21621.【PR #2】划分

P 国的领土包含 \(N\times M\) 个城市，排成 \(N\) 行 \(M\) 列的网格，第 \(i\) 行第 \(j\) 列的城市的坐标记为 \((i,j)\)。
我们认为两个城市 \((i_1,j_1)\) 与 \((i_2,j_2)\) 相邻当且仅当 \(|i_1−i_2|+|j_1−j_2|=1\)。
国王想把城市划分为 \(K\) 个省，满足以下条件：
\(•\) 每个城市恰好属于一个省；
\(•\) 每个省至少包含一个城市；
\(•\) 对于同省的两个城市，存在一条该省城市的路径以这两个城市为端点，使得路径上相邻的两个城市在网格上相邻；
每个城市恰好有两个相邻的城市与其同在一个省。
请你帮助国王给出划分的一个方案，若有多种方案输出任意一种均可，若无解则输出 NO。
对于所有数据，\(K\leq NM\)，\(\sum NM\leq 2\times 10^5\)。

QOJ #2812. Paths/#21622.【ExPR #1】守卫 2

在 P 国有 \(n\) 个村子，以及 \(n−1\) 条待修建的双向公路，第 \(i\) 条公路连接 \(u_i,v_i\)，修建的代价为 \(c_i\)，保证任意两个村子可以通过一些双向公路互相到达。
已知国王和 \(k\) 个守卫在某个村子 \(r\)，第 \(i\) 个守卫需要到达某个村子 \(x_i\)。
国王会选择代价之和尽可能少的一些公路进行修建，使得每个守卫可以从 \(r\) 出发经过这些公路到达目的地。
对于每个 \(r\in [1,n]\)，求在所有选择 \(x_i\in [1,n]\) 的情况下，国王修建公路所需代价之和的最大值。
对于所有数据，\(1\leq k\leq n\leq 10^5\)，\(0\le c_i\le 10^9\)。

QOJ #3039. Cleaning

QOJ #3040. Container

有一个长度为 \(n\) 的序列 \(a\)，满足 \(a_i=\dfrac 12\)。你希望通过若干次变换将其变换为另一个序列 \(b\)（保证两序列 \(1\) 和 \(2\) 的个数相同）。
一次变换中，你可以选择 \(a\) 序列的一个长度不超过 \(3\) 的连续子序列并将其翻转，代价为被选中的连续子序列的 \(a_i\) 之和加上一个固定的常数 \(C\)。
要求构造出一种总代价最小的变换方案。
对于全部数据，满足 \(1\leq n\leq 500,0\leq C\leq 1000\)。

QOJ #3300. Cactus Competition

给定一张 \(n\times m\) 的网格图，一个长为 \(n\) 的序列 \(A\)，和一个长为 \(m\) 的序列 \(B\)。若 \(A_i+B_j\geq 0\)，则格子 \((i,j)\) 为黑色，否则格子 \((i,j)\) 为白色。
询问有多少对 \(x,y\)，满足存在一条从 \((1,x)\) 到 \((n,y)\)，只经过黑色格子且只向下或向右走的路径。
对于全部数据，满足 \(1\leq n,m\leq 2\times 10^5\)，\(−10^9\leq A_i,B_i\leq 10^9\)。

QOJ #3301. Economic One-way Roads/#21655.【PR #5】双向奔赴

小 D 和大 D 生活在一张简单无向图上。
很可惜，这张无向图马上就要变成有向图了。每条边的两种定向方式分别有一个代价，小 D 和大 D 决定找出一种定向方式，使得无论他们俩分别在哪两个点，小 D 都能走过一些有向边找到大 D，在这基础上，他们想要最小化代价总和。
对于 \(100\%\) 的数据：保证 \(1\leq n\leq 18\)，\(−1\leq a_{i,j}\leq 10^6\)。

QOJ #3575. Where is the legend?/#21613. 【PR #1】删数

给定一个长为 \(n\) 的正整数序列 \(a_1,\dots,a_n\)。
你可以进行若干次操作，每次操作你可以选择一个位置 \(i\in [2,n−1]\) 使得 \(a_i=\dfrac {a_{i−1}+a_{i+1}}2\)，随后将 \(a_i\) 删去，之后的数按顺序向前补空位。
求若干次操作后序列长度最小可以是多少。
对于所有数据，\(n≥3\)，\(1\leq T\leq 10^3\)，\(\sum n\leq 3\times 10^5\)，\(1\leq a_i\leq 10^9\)。

QOJ #3576. Zhylan.io/#21619.【PR #2】史莱姆

给定 \(n\) 只史莱姆排成一列，第 \(i\) 只史莱姆的大小为 \(a_i\)。
对于一些史莱姆，可以进行一局游戏：给定非负整数 \(k\)，设第 \(i\) 只史莱姆可以吃掉第 \(j\) 只史莱姆当且仅当 \(a_i−a_j\geq k\)，此时第 \(j\) 只史莱姆被删除而 \(a_i\) 变为 \(a_i+a_j\)；史莱姆之间可以任意互相吃，若没有史莱姆能吃掉其他史莱姆则游戏结束；若最后仅剩下一只史莱姆则这只史莱姆获胜，否则没有史莱姆获胜。
\(q\) 次询问 \(l,r,k\)，求在 \([l,r]\) 这段区间的史莱姆进行游戏的情况下，有多少只史莱姆可能获胜。
注意每组询问之间是独立的，即在询问过程中不会有史莱姆吃掉其他史莱姆。
对于所有数据，\(2\leq n\leq 2\times 10^5\)，\(1\leq q\leq 2\times 10^5\)，\(1\leq a_i\leq 10^9\)，\(1\leq l\leq r\leq n\)，\(0\leq k\leq 10^9\)。

QOJ #3798. Planning Railroad Discontinuation/#21662.【PR #7】道路重建

在一个遥远的国家里有 \(l\) 个城市，编号为 \(0,1,\dots,l−1\)，围着一个大湖建成一圈。城市内和城市间有很多交通线路，并且它们都是双向的。
每个城市里都有 \(n\) 个火车站，编号为 \(0,1,\dots,n−1\)，由 \(m\) 条动车线路相连。由于这些城市是一起修建的，所以任意两个城市内的火车站连接情况完全一致，即点集和边集都相等。
有些火车站是枢纽站。如果火车站 \(s\) 在某个城市是枢纽站，那么所有城市的 \(s\) 号火车站都是枢纽站。相邻城市的编号相同的枢纽站会被高铁线路连接。
一场天灾之后，所有这些线路都需要重建才可以被投入使用。由于城市之间非常相似，重建的费用也很有规律，具体如下：
\(•\) 每个城市 \(i\) 都有两个正整数 \(a_i,b_i\)。
\(•\) 每条动车线路都有一个正整数 \(d_j\)，不同城市的同一条动车线路的 \(d_j\) 相等。
\(•\) \(i\) 号城市的 \(j\) 号动车线路的重建费用是 \(b_i+d_j\)。
\(•\) \(i\) 号城市和 \((i+1)\bmod l\) 号城市之间的任意一条高铁线路的重建费用都是 \(a_i\)。
你需要花费尽可能少的代价，重建若干条线路，使得国家里的任意两个火车站可以互达。
对于所有数据，\(2\le n\le 10^4\)，\(1\le m\le 10^5\)，\(0\le u_i,v_i,s_k<n\)，\(1\le d_j,a_i,b_i\le 10^9\)，\(3\le l\le 10^5\)，\(1\le r\le n\)。

QOJ #3801. Cancer DNA/#21658.【PR #6】DNA 匹配

称一个字符串 \(s\) 是 DNA 序列，当且仅当 \(s\) 只由 A,C,G,T 组成。
给定 \(m\) 个字符串 \(s_1,\dots,s_m\)，每个序列的长度均为 \(n\)，且只由 A,C,G,T,? 组成。
对于一个长度为 \(n\) 的 DNA 序列 \(t\) ，称 \(t\) 是合法的，当且仅当存在一个 \(s_i\)，且存在一种把 \(s_i\) 中的 \(?\) 替换的方法，使得替换后得到的 \(\tilde s_i\) 等于 \(t\)。
你需要求出，当 \(t\) 在所有长度为 \(n\) 的 DNA 序列中等概率随机时，\(t\)合法的概率。
你的答案在相对误差不超过 \(5\%\) 时会被视为正确。换句话说，若真实概率是 \(w\)，而你输出了 \(v\)，那么当且仅当 \(0.95w\leq v\leq 1.05w\) 时你会被视为正确。
对于 \(100\%\) 的数据，保证 \(1\leq n\leq 100,1\leq m\leq 40\)。

QOJ #3835. Oracle/#21760.【PR #9】选择

给定一个长度为 \(n\) 的整数序列 \(p_1,\dots,p_n\) ，以及两个非负整数 \(a,b\)。
对于每个 \(1\leq k\leq n\)，你需要选出 \(p\) 的一个长度为 \(k\) 的子序列 \(q_1,\dots,q_k\) ，最大化 \(\sum_{i=1}^k q_i(i^2+ai+b)\)。
对于所有数据，保证 \(1\leq T\leq 20,n\leq 50000,|p_i|\leq 50000,0\leq a,b\leq 100,a^2\geq 4b\)。

QOJ #3875. Fruits/#21706.【PNR #4】水果

你在超市里工作。
超市里有 \(n\) 个水果，第 \(i\) 个水果的美味度为 \(i\)，价格为 \(c_i\) ，并且保证 \(c_i\) 单调不降。
现在要把这 \(n\) 个水果摆成一排放到货架上，第 \(j\) 个位置摆的水果是 \(a_j\)。但是你还没想好摆的顺序，所以可能会有 \(a_j=−1\)，表示这个位置摆的水果未定。
在你决定了摆放顺序之后，一位顾客进来买水果。他会从第一个位置开始往后走，每当遇到一个美味度比之前都要高的水果时就会把它买下，直到看完第 \(k\) 个位置后离开。
你希望选择一个最优的摆放顺序，使得这位顾客出的钱最多。
但是你并不知道 \(k\) 是多少，因此你希望对每个 \(k\) 都求出答案。你对不同的 \(k\) 给出的顺序可以不同。
对于所有数据，保证 \(1\leq n\leq 4\times 10^5\)，\(−1\leq a_i\leq n\)，\(a_i\neq 0\)，\(1\leq c_i\leq 10^9\)，\(a\) 中不存在两个相同的正整数，\(c\) 单调不降。

QOJ #3998. The Profiteer

QOJ #4218. Hidden Graph

有一张 \(n\) 个点 \(m\) 条边的无向图。
每次你可以给交互库一个点集，交互库会返回点集内的一条边，或报告这个点集是独立集。
你需要在 \(n+2m\) 次询问内猜出整张图。
对于全部数据，满足 \(n,m\leq 2000\)。

QOJ #4219. Insects/#21657.【PR #5】和平共处

二维平面上有 \(n\) 只黑蚂蚁。
在接下来的一段时间内，陆陆续续来了 \(m\) 只白蚂蚁。然而，黑蚂蚁和白蚂蚁之间会打架，小 H 不希望看到这种现象。
小 H 可以给一只蚂蚁喂食，这样它就不想打架了。而如果有一只黑蚂蚁 \((x,y)\) 和白蚂蚁 \((x’,y’)\) 满足 \(x\leq x’,y\leq y’\)，并且它们都没得到食物，它们就会打架。
小 H 想知道，在每只白蚂蚁到来后，他至少需要喂食多少蚂蚁才能使蚂蚁不会打架。
注意小 H 不会真的喂食，每次他需要计算时，所有蚂蚁都饥肠辘辘。
对于所有数据，保证 \(1\leq n,m\leq 1\times 10^5,0\leq x_i,y_i\leq 10^9\)。

QOJ #4635. Graph Operation

QOJ #4758. Captivating process/#21674.【PNR #1】别急

小 A 和小 B 来到了古神的宫殿。
他们在墙上发现了 \(2n\) 个不超过 \(n\) 的正整数 \(f_1,f_2,\dots,f_n,g_1,g_2,\dots,g_n\)。
他们在地上发现了 \(m\) 块石板，第 \(i\) 块石板上写了两个不超过 \(n\) 的正整数 \(x_i,y_i\)。
根据传说，每过一秒，\(x_i\) 就会变为 \(f_{x_i}\)，\(y_i\) 就会变为 \(g_{y_i}\)。而当 \(x_i=y_i\) 时（包括初始时），第 \(i\) 块石板就会裂开。
小 A 想分别知道每块石板是否会裂开，但他觉得一直等下去太慢了。
小 B 让小 A 别急，但小 A 很急，你也很急，所以你要在一秒内帮小 A 找到答案。
对于所有数据 \(1\leq n,m\leq 10^5\)，\(1\leq f_i,g_i,x_i,y_i\leq n\)。

QOJ #4794. Salaj

QOJ #4811. Be Careful

给定一棵大小为 \(n\) 的树，根为 \(1\) 号点。
对于每个叶结点 \(x\)，它的权值 \(a_x\) 是一个 \([0, n]\) 之间独立均匀随机的整数。
对于每个非叶结点 \(u\)，它的权值 \(a_u\) 是 \(u\) 的所有儿子的权值的 \(\text{mex}\)。
你需要对每个整数 \(k\in [0, n]\)，求出 \(a_1 = k\) 的概率。
对 \(998244353\) 取模。
对于全部数据，满足 \(2\leq n\leq 200\)。

QOJ #4812. Counting Sequence

一个序列 \(a_1,\dots, a_m\) 是好的当且仅当：
\(•\) \(a_i > 0\)；
\(•\) \(|a_i − a_{i+1}| = 1\)；
\(•\) \(\sum_{i=1}^m a_i = n\)；
对于好的序列，定义权值 \(f(a) =\sum_{i=1}^{m−1} [a_i > a_{i+1}]\)，求所有好的序列的 \(c^{f(a)}\) 之和。
对于全部数据，满足 \(n\leq 3\times 10^5\)。

QOJ #4815. Flower’s Land

给定一棵 \(n\) 个点的树，每个点有点权。对于每个点，求出包含它的大小恰为 \(k\) 的所有子联通块中，最大的权值和。
对于全部数据，满足 \(n\leq 40000\)，\(k\leq 3000\)。

QOJ #4878. Easy Problem/#21751.【PR #8】养鸡

有 \(n\) 只鸡站成一排，第 \(i\) 只鸡至多能吃 \(a_i\) 的谷子。
有 \(m\) 个波特，第 \(j\) 个波特可以给第 \(l_j,l_{j+1},\dots,r_j\) 只鸡喂谷子，并且它只携带了 \(c_j\) 的谷子。波特不需要把携带的所有谷子都喂出去，只需要保证喂出去的谷子不超过 \(c_j\) 即可。
对于每个 \(i\)，求出如果只保留满足 \(l_j\leq i\leq r_j\) 的波特，那么最多一共能喂多少谷子。
对于所有数据，保证 \(1\leq T\leq 10^4\)，\(1\leq \sum n,\sum m\leq 10^5\)，\(0\leq a_i\leq 10^9\)，\(1\leq l_j\leq r_j\leq n\)，\(0\leq c_j\leq 10^9\)。

QOJ #4882. String Strange Sum

给定一个长为 \(n\) 的字符串 \(s\)，定义 \(f(l,r)\) 表示 \(s[1,l−1]\) 的最长后缀的长度，满足这个后缀可以被划分成若干 \(s[l,r]\) 的前缀。
求 \(\sum_{l=2}^n\sum_{r=l}^n f(l,r)\)。
对于全部数据，满足 \(1\leq n\leq 2\times 10^5\)。

QOJ #4884. Battleship: New Rules

Alice 和 Bob 在玩游戏。
有一个 \(n\times n\) 的棋盘，Alice 会选择一个整数 \(k\)，满足 \(n\leq k\leq \lceil \dfrac{n}{2}\rceil^2\)。
一艘船是一个 \(1\times a\) 或 \(a\times 1\) 的矩形，其中 \(a\) 为 \(1\) 到 \(n\) 中的
任意整数。两艘船对应的矩形在棋盘上不能有公共边或公共点。
接下来，Alice 会在棋盘上放 \(k\) 艘船，且要求它们所在占据的格子数是所有可能的 \(k\) 艘船占据的格子数的最大值。
Bob 开始时只知道棋盘大小 \(n\)。
Bob 每次可以询问某个格子是否被某艘船占据。询问次数不超过 \(6n\)。
Bob 需要在棋盘上找到一个 \(2\times 2\) 的矩形，使得这个矩形内的四个格子均没被船占据。如果棋盘上没有这样的矩形输出无解。
请帮 Bob 取得胜利。
对于全部数据，满足 \(3\leq n\leq 1000\)。

QOJ #4887. Fast Bridges

QOJ #5071. Check Pattern is Good

QOJ #5241. Miny [A]

QOJ #5423. Perfect Matching

QOJ #5416. Fabulous Fungus Frenzy

给一个 \(n\times m\) 的字符矩阵 \(A\)，同时给定 \(k\) 个字符矩阵作为模板。可以进行如下两种操作：
\(•\) 交换两个相邻字符。
\(•\) 选择一个模板矩阵，在 \(A\) 中选择一个与模板矩阵形状相同的矩形，将该矩形内的内容替换为模板中的内容。
给定目标状态，判断是否可以达到目标状态。如果可以同时构造方案。
对于全部数据，满足 \(n, m, k\leq 20\)。
操作次数限制：第一种操作 \(4\times 10^5\) 次 (\(\mathcal{O}(n^4)\))，第二种操作 \(400\) 次。

QOJ #5425. Proposition Composition

有一条 \(1\) 到 \(n\) 的链，接下来有 \(m\) 次加边操作。
每次加边操作结束后，你需要求出，有多少删除两条边的方式，使得图不连通。
对于全部数据，满足 \(n, m\leq 2.5\times 10^5\)。

QOJ #5439. Meet in the Middle

QOJ #5440. P-P-Palindrome

给你 \(n\) 个字符串，总长度不超过 \(10^6\)。
求出有多少种字符串有序对 \((P,Q)\)，满足:
\(•\) \(P,Q,P+Q\) 都是回文串。
\(•\) \(P\) 为 \(n\) 个字符串中至少一个的子串。
\(•\) \(Q\) 为 \(n\) 个字符串中至少一个的子串。
\((P_1,Q_1)\) 和 \((P_2,Q_2)\) 不同，当且仅当 \(P_1\neq Q_1\) 或 \(P_2\neq Q_2\)。

QOJ #5475. Make a Loop

QOJ #5526. Jewel of Data Structure Problems

给定一个长度为 \(n\) 的排列，\(Q\) 次操作，每次交换两个位置。
每次操作后，求它的最长的、逆序对个数为奇数的子序列长度(可以不连续)，或报告不存在。
对于全部数据，满足 \(n,Q\leq 2\times 10^5\)。

QOJ #5568. Cyclic Shifts

给定一个 \(1\sim n\) 的排列 \(p\)。
你可以进行任意多次操作，每次选择一个 \(k>0\)，以及 \(k\) 个位置 \(x_1,x_2,\dots,x_k\)。然后将这些位置向右循环移位，即同时将 $$p_{x_2}:=p_{x_1},$$$$p_{x_3}:=p_{x_2},$$$$\dots,$$$$p_{x_k}:=p_{x_{k-1}},$$$$p_{x_1}:=p_{x_k}$$ 一次操作的代价为 \(\dfrac 1k\)，总费用为所有操作的代价之和。
你需要在不超过 \(2\) 的总费用下将 \(p\) 排序。
对于全部数据，满足 \(n\leq 5000\)。

QOJ #5573. Holiday Regifting

给定一个 \(n\) 个点 \(m\) 条边的 DAG，每个点有给定的容量 \(c_i\) 和可变的权值 \(a_i\)，初始所有的 \(a_i=0\)。
定义一次对点 \(u\) 的更新如下：
\(•\) 令 \(k := \lfloor \dfrac{a_i}{c_i}\rfloor\)。
\(•\) 对于所有边 \(u\to v\)，将 \(a_v\) 加 \(k\)。
\(•\) 令 \(a_u := a_u \bmod c_u\)。
现进行若干轮操作，每轮操作中，先将 \(a_1\) 加 \(1\)，然后按拓扑序依次更新所有点。
求至少多少轮操作使得所有的 \(a_i=0\)，答案对 \(998244353\) 取模。
对于全部数据，满足 \(n\leq 10^4\), \(m\leq 3\times 10^4\)，\(c_i\leq 10^5\)，所有 \(u\) 的出度 \(\leq c_u\)。

QOJ #5749. Directed Vertex Cacti

求有多少 \(n\) 个点的有向图，满足：
\(•\) 无自环重边（可以存在端点相同方向相反的边）；
\(•\) 每个点至多在一个简单环中；
\(•\) 有恰好 \(m\) 条边不在任何环中。
答案对 \(10^9+9\) 取模。
对于全部数据，满足 \(n,m\leq 10^6\)。

QOJ #6101. Ring Road

QOJ #6119. Frustration and Bracket Sequences

QOJ #6194. Knapsack Problem

有 \(2^{k−1}\) 个取值为非负整数的变量 \(x_1,\dots,x^{2^k−1}\)，第 \(i\) 个变量有 \(c_i\) 的权值。
给定 \(k\) 个正整数 \(a_0,\dots,a_{k−1}\)，对于所有 \(0\leq j<k\)，限制：\(\displaystyle\sum_{i=1}^{2^k-1}(\lfloor \dfrac i{2^j}\rfloor\bmod 2)x_i=a_j\)。
请求出 \(\sum_{i=1}^{2^k-1} x_ic_i\) 的最大值。
对于所有数据，满足 \(1\leq T\leq 100\)，\(2\leq k\leq 4\)，\(0\leq c_i\leq 10^8\)，\(1\leq a_i\leq 10^9\)。

QOJ #6196. Minimum Element Problem

定义两个排列等价，当且仅当它们在任意区间的最小值位置相同。
给定 \(n,x\)，你需要对于所有 \(1\leq y\leq n\) 求出：长度为 \(n\) 的，满足 \(p_x=y\) 排列构成了多少等价类，对 \(998244353\) 取模。
对于全部数据，满足 \(n\leq 5\times 10^5\)。

QOJ #6299. Binary String

给定一个长为 \(n\) 的 \(01\) 字符串 \(S\)。在每一单位时刻中，同时将 \(S\) 中所有 \(01\) 替换成 \(10\)。
询问在所有时刻一共有多少不同的 \(S\)，答案对 \(998244353\) 取模。
对于全部数据，满足 \(1\leq n\leq 10^7\)。

QOJ #6303. Inversion

你要猜一个排列 \(p_1,p_2,\dots,p_n\)。
你可以询问区间 \([l,r]\) 中的逆序对奇偶性。
对于全部数据，满足 \(n\leq 2000\)，最多询问 \(40000\) 次。

QOJ #6308. Magic

QOJ #6322. Forestry

QOJ #6366. Message

QOJ #6380. LaLa and Divination Magic

用 \(01\) 矩阵输入一个 \(n\) 个点的简单无向图，你需要对每一对 \((u,v)\)
求出是否有一条从 \(u\) 到 \(v\) 的哈密顿路径。
对于全部数据，满足 \(n\leq 24\)。

QOJ #6404. Shuttle Tour

给定一棵树，边有边权，每个点有一个 \(0/1\) 状态，你需要进行两种操作：
\(•\) 更改某个单点的状态。
\(•\) 询问点编号在区间 \([l,r]\) 中且状态为 \(1\) 的点所构成的虚树边权之和。
保证树的叶子结点个数不超过 \(50\)。
对于全部数据，满足 \(n,q\leq 2\times 10^5\)。

QOJ #6406. Stage Clear

有 \(n\) 个关卡形成一个 \(m\) 条边的 DAG，保证所有点能从点 \(1\) 到达。
每个关卡 \(i\) 有一个参数为 \((a_i,b_i)\) 的敌人，和这个敌人战斗会先使得血量减少 \(a_i\),再增加 \(b_i\)。
从点 \(1\) 开始，你可以沿着边移动，或者传送回点 \(1\)。第一次到达某个关卡时，需要和其中的敌人战斗，然后你就通过了这个关卡，并且以后都不会再和这个敌人战斗了。
目标是通过所有关卡，并使得血量一直大于等于 \(0\)，求初始血量最少是多少。
对于全部数据，满足 \(n+m\leq 72\)。

QOJ #6540. Beautiful Sequence

给定一个长为 \(n\) 的序列 \(a\)，你需要将其重排成序列 \(b\) 使得其好元素最多，输出最多的好元素个数。
一个元素 \(i\) 是好的，当且仅当 \(a_i \geq \max(a_{i−1}, a_{i+1})\)（我们认为 \(a_0 = a_{n+1} = 0\)）。
有多组测试数据。
对于 \(100\%\) 的数据，\(1 \leq \sum n \leq 3 \times 10^5\)，\(1\leq a_i \leq n\)。

QOJ #6555. Sets May Be Good

QOJ #6638. Treelection

QOJ #6659. Ring Road 2

QOJ #6807. Travel Dream

给出一个 \(n\) 个点 \(m\) 条边的无向图，边有边权，问图中边权和最大的 \(k\) 元环的边权和是多少，或判断图中不存在 \(k\) 元环。
对于全部数据，满足 \(n,m\leq 300\)，边权 \(w_i\leq 10^8\)，\(3\leq k\leq 10\)。

QOJ #7106. Infinite Parenthesis Sequence

QOJ #7417. Honorable Mention

给定序列 \(a_1,a_2,\dots,a_n\)。
你需要回答 \(q\) 次形如“选择 \([l_i,r_i]\) 的 \(k_i\) 个不交非空子区间，它们在 \(a\) 上的和最大是多少”的查询。
对于全部数据，满足 \(n,q,|a_i|,k_i\leq 35000\)。

QOJ #7419. Jiry Matchings

QOJ #7510. Independent Set

QOJ #7520. Monster Generator

QOJ #7605. Yet Another Mex Problem/#21809.【PR #12】划分序列

有一个长度为 \(n\) 的序列 \(a\)。
设一个区间的价值为此区间的 \(\text{mex}\) 值乘上区间元素总和。其中 \(\text{mex}\) 值定义为该集合中不属于集合的最小非负整数，例如 \(\text{mex}(0,1,3,5)=2\)。
你需要将数组划分成若干非空区间，其中每个区间的长度不超过 \(k\)。一个划分方案的价值为每个区间的价值之和。
你需要找到满足题意的划分方案下的最大价值。
对于全部数据，满足 \(2\leq n\leq 2\times 10^5\)，\(1\leq k\leq n\)，\(0\leq a_i\leq n\)。

QOJ #7606. Digital Nim

QOJ #7607. The Doubling Game 2

QOJ #7742. Suffix Structure

QOJ #7748. Karshilov’s Matching Problem II

QOJ #7751. Palindrome Path

QOJ #7777. Intro: Dawn of a New Era

QOJ #7782. Ursa Minor

QOJ #7945. Apricot Seeds

QOJ #8038. Hammer to Fall

有一张 \(n\) 个点，\(m\) 条边的无向图，每个点上初始有一个人。有 \(q\) 天，第 \(i\) 天会袭击点 \(b_i\)。每个人可以在图上以无限的速度行走，但是袭击时必须停留在某个不是袭击点的点上。
问 \(q\) 天结束之后，所有人行走距离之和最小是多少。
对于全部数据，满足 \(n,m,q\leq 10^5\)，\(w\leq 10^9\)。

QOJ #8140. Customs Controls 2

QOJ #8179. 2D Parentheses

QOJ #8213. Graffiti

QOJ #8240. Card Game