2023年7月~11月FZOJ做题记录

FZOJ3030 [2018NOI前模拟] 狗

$n$ 条狗在排队。狗有很多品种，我们把品种也从 $1$ 到 $n$ 标号，相同标号的狗是同一种。狗按照 $1$ 到 $n$ 的顺序依次前来排队，但是狗会插队，每条狗希望插队到一个最靠前的位置。第 $i$ 只狗到来之时，他会找到一个和他相同品种的狗，并插到他身边，这样就不怕挨打，当然，他也可以站在队尾，也不用挨打。狗还有一个良心值 $a_i$ ，表示他最多愿意插队到最后 $a_i$ 个人之前，否则他的良心会隐隐作痛。（良心值越高其实越不良心，心安理得.jpg）
现在，告诉你每只狗的颜色和良心值，求出最后的队列顺序。
$100\%$ 的数据：$n≤400000$。

FZOJ3701 [2019NOI前模拟] C

这是一道交互题。
题目描述
给定一棵树 $T$，我们定义这棵树上的某个点集 $S$ 的最小连通块为包含这个点集中所有点的最小的树上连通块。
给定一棵树的大小 $n$，你可以进行若干次询问，每次询问你可以给出一个点集 $S$ 和这棵树上的一个点 $x$，交互库会返回一个布尔值表示 $x$ 是否在点集 $S$ 的最小连通块上。你需要确定这棵树的形态。
任务
你需要实现下面的函数：
std::vector<std::pair<int,int> > work(int n) 其中 $n$ 表示这棵树的大小，也就是题面描述中的。
你返回的 std::vector<std::pair<int,int> > 中每个 std::pair<int,int> 表示树的一条边的两个端点，你需要保证返回的 std::vector<std::pair<int,int> > 的大小为 $n - 1$ 且构成一棵树，否则你的程序将得到0分。
你可以调用以下函数和交互库进行交互：
bool ask(std::vector<int> S, int x) 其中 S 表示你给出的点集 $S$，也就是题面描述中的 $S$； x 表示你给出的点 $x$，也就是题面描述中的 $x$ 。你需要保证 $S$ 不为空，且 $S$ 中的点和 $x$ 在 $[1,n]$上，否则你的程序将得到0分。如果 $x$ 在 $S$ 的最小连通块上则返回值为 $true$ 否则返回值为$ false$ 。
详情可以参见下发的示例代码。
请注意：交互函数所需的时间复杂度为 $O(|S|)$，你可能会因为你给定的 $\sum|S|$ 过大而获得 Time Limit Exceeded。
评测方式
评测程序示例将读入如下格式的输入数据：
第一行包括一个正整数 $n$，表示这棵树的大小。
接下来 $n-1$ 行，每行两个整数 $x,y$，表示一条边的两个端点。点的编号从$1$开始。
评测程序示例将返回你的错误信息或以如下格式返回：
Your answer is correct.You made AAA queries with total size BBB.
其中 $\texttt{AAA}$ 表示你的询问次数，$\texttt{BBB}$ 表示你询问给定的点集的总大小。
请添加头文件 C.hpp 。
评分方式
本题共有一个测试包，内含若干个测试点。
对于每个测试点，若你的程序有不合法的询问或返回，或返回的树的形态不正确，则你在该测试点获得 $0$ 分，否则令$step$表示你的程序的询问次数，则你在该测试点获得的分数将评定为$min(\lfloor \frac{2.2 \times 10^6}{step} \rfloor,100)$ 。
你所获得的这道题的分数即为所有数据点的分数的最小值。
对于所有数据，均满足 $n=1000$。

FZOJ3753 [2019NOI前模拟] B

给定一个二分图，两个部分我们称之为 $A$ 部和 $B$ 部。
对于一个 $A$ 部的点 $A_i$，其在 $B$ 部中相邻的点是一个连续的区间，记为 $[L_i, R_i]$。
现在你需要找一个尽量大的匹配，使之在具有匹配的性质的前提下，所有匹配边互不相交。（即不存在两条匹配边 $(A_i, B_x), (A_j, B_y)$，使得 $i < j, x > y$）。
$100\%$ 的数据：$N \le 100000, 1 \le L_i \le R_i \le N$。

FZOJ3891 [2019省选前模拟] 数据结构

对于长度为$n$的初始正整数数列$A$，定义矩阵$B_{n \times n}$，初始时$B_{i, j} =\sum_{k=i}^jA_k$。
有$m$个操作，每个操作为以下两种之一：
$1.$给出整数$p, x$，将$A_p$修改为$x$。然后对所有的$B_{i, j}$，更新为$\min(B_{i, j},\sum_{k=i}^jA_k)$。
$2.$给出整数$l,r$，请回答$B_{l,r}$的值。
$1 \le n, m \le 10^5, 0 \le A_i, x \le 10^9$。保证询问操作有$l \le r$。

FZOJ3905 [2020省选前模拟] Short But Scary

这是一道可怕的题目，因此简化题意：
给定一棵 $n$ 个点的无根树，点的编号依次为 $1$ 到 $n$。每条树边的状态都是 “可用” 或者 “不可用” 之一，一开始所有树边的状态都是 “可用”。
你需要支持 $2$ 种操作：
$1.$ $1$ $u$ $v$，将 $u$ 点到 $v$ 点简单路径上的所有树边的状态都进行修改，即 “可用” 的变成 “不可用”，“不可用” 的变成 “可用”。
$2.$ $2$ $x$，查询通过当前可用的树边，$x$ 点能到达的点数 (包括 $x$ 点本身)。
对于 $100\%$ 的数据，$1 \le a_i, b_i, x \le n$ 且 $1 \le u \lt v \le n$。

FZOJ3944 [2020省选前模拟] 小 ω 数排列

小 $ω$ 想数具有某些条件的排列的个数。
小 $ω$ 得到了 $n$ 个互不相同的正整数 $A_i(1\le i\le n)$。
小 $ω$ 想知道有多少个大小为 $n$ 的排列 $p_i$ 满足

\[\sum_{i=1}^{n-1}|A_{p_i}-A_{p_{i+1}}|\le L \]

答案对 $10^9 + 7$ 取模。
对于所有数据，$1\le n\le 100,~1\le L\le 1000,~1\le A_i\le 1000$。

FZOJ4162 [2020省选前模拟] 普及良

小样在 OI 取得了良好的成绩后，开始研究一款奇怪的消消乐隔膜(game)。
这个隔膜会给你一个长度为正奇数的$01$ 字符串$S$，然后隔膜的目标是通过若干次以下操作，使得最后的串变成一个长度为 $1$ 的字符串$1$：
$1.$ 选择一个奇数$i(3 \le i \le |S|)$，
$2.$ 将$S$ 分成两个字符串$S^′$ 和$T^′$，其中$S = S^′ + T′$ 且$|S′| = i$。
$3.$ 重复地将$S^′$ 的最后三个字符组成的子串$U$ 替换成$f(U)$，直到 $|S^′| = 1$。
$4.$ 令新的$S = S^′ + T^′$。
其中，$f(S) = T$ 是给定的一个函数，满足$|S| = 3,|T| = 1$。
众所周知小样不会止步于简单的模拟，所以他挖去了串的一些位置，改成了问号$?$，表示这位可以变成字符 $0$ 或 $1$ 。
他想知道，有多少种本质不同的方案，使得把所有问号都变成字符 $0$ 或 $1$ 之后，能够达成这个隔膜的目标，答案对$998244353 = 2^{23} \times 119 + 1$ 取模。
两种方案本质不同当且仅当存在至少一个问号在这两种方案中变成了不同的字符。
注意本题有多组测试，注意清空数组。
对于所有数据，都有$1 \le T \le 10，|S| \le 10^5$。

FZOJ4488 [2021冬令营前模拟] 欢迎来到塞莱斯特山

相貌可是十人十样

因此才会互相吸引

2020年寒假，百无聊赖的薇在妈妈种

的花盆里埋了几个榆钱。（从此那几个榆钱杳无音信）
几天后，薇得到了一棵包含 $n$ 个节点而根节点为 $1$ 的榆树。她定义节点 $x$ 的深度 $dep(x)$ 为 $x$ 到根节点的最短路径上的点数。
她随手写下了一个式子：$$\sum_{p是一个{1,2,\cdots n}的排列} \prod_{i=1}^{n-1} dep(lca(p_i,p_{i+1})) \pmod {10^9+7}$$
并决定把这个式子的值作为送给 JZmster 和 LJZ_C 的新年礼物。
因为薇还要陪妹妹 Lucy 读英语，所以她请你帮她算出这个值。
对于所有的数据均保证 $n\le 500$。

FZOJ4507 [2021冬令营前模拟] 星空

【题目背景】
2021 元旦，小 P 注视着星空，眼睑通红
苦中带涩不是常态吗，我们得用笑容面对苦涩
使劲揉揉眼睛，我将不负过去，不畏将来
【题目描述】
星空中充斥着星辰，小 P 想将其一一配对，一个星辰用两个参数描述 $a_i,b_i$ 分别表示其大小和闪烁程度。
两个星辰 $i,j$ 可以配对，当且仅当 $a_i\leq a_j$ 并且获得 $b_j-b_i$ 的整体闪烁程度（因为小 P 眼睑通红看不清楚，所以会相互抵消）。
一个星辰配对后无法再次配对，小 P 想知道对于 $k\in \left[1,\left\lfloor \frac{k}{2}\right\rfloor \right]$ 求出至多配对 $k$ 的最大闪烁程度和。
对于所有数据，满足 $n\leq 10^5,a_i\leq 10^9,b_i\leq 10^9$

FZOJ4508 [2021冬令营前模拟] 嫖怪

【题目背景】
社会生产力的发展，使得人们的消费能力与需求与日俱增。
正因如此，小 P 搬运食品的速度已经远远无法跟上机房嫖怪们的需求了若再不想些对策，小 P 那点可怜的劳动价值也要被血腥的嫖怪资本家们榨取殆尽了……
【题目描述】
小 P 用食品贮藏点的方式储存自己的食品，且一开始没有任何贮藏点。接下来会有 $q$ 个操作。
$type = 2$：对抗操作。
为了应对可能发生的事件，小 P 会模拟自己与嫖怪们的对抗过程。
具体地，对抗从 $0s$ 时刻开始，在时间段 $(ts, ts + 1s], t ∈ N$ 间，小 P 会在 $ts+ 0.5s$ 时选择一个贮藏点，向其中投放 $1$ 单位食品。嫖怪们则会在 $ts+ 1s$ 时选择一个贮藏点，至多取出 $2$ 单位的食品。
如果一个食品贮藏点贮藏的食品单位数 $\le 0$，嫖怪们就会认为它不再具有利用价值并摧毁它。若被摧毁的食品贮藏点达到了 $K$ 个，小 P 就不得不修建新储藏点了。
但是小 P 很懒惰，因此他希望被摧毁点数达到 $K$ 个的时刻尽量大。小 P 认为嫖怪们也很懒惰，因此小 P 认为他们希望这个时刻尽量小。
对于这个操作，你需要输出对抗结束的时刻 $T$，这显然是个整数。
这个操作不具有后效性。
$type = 1$：修改操作。
小 P 会将储存食品数为 $X$ 的贮藏点的数目改为 $Y$ 。
这个操作具有后效性。
对于所有数据，满足 $q \le 10^6, type \in \{1, 2\}, X, Y \le 10^6, K \le$ 当前贮藏点的总数。

FZOJ4513 [2021冬令营前模拟] 基因进化

2xxx 年，一种基因修改技术在 Y 大陆流行；
为了简化问题，我们把基因看做一个长度为 $N$ 的正整数序列；
人们可以对基因进行多次修改。具体来讲，对于每次修改可以表述为：选择这个基因序列的一个前缀，然后翻转它们；
但是这个技术有很多限制，首先，必须先翻转长度小的前缀，再翻转长度大的前缀；
其次，有一些长度的前缀是无法被翻转的，这样的前缀一共有 $M$ 个；
大部分人都认为，字典序越小的基因序列越优越，越先进，所以它们想知道，在通过这个技术翻转基因序列后，所能得到的最小字典序的序列是什么。
对于 $100\%$ 的数据，$0 \le M \le N \le 300000,T \le 100,\sum N \le 1000000,1 \le a_i \le 10^9,1 \le b_i \le N$。

FZOJ4540 [2021省选前模拟] 行列式

给一个矩阵 $A=(a_{i,j})_{n\times n}$ ，你需要求出 $A$ 的行列式 $\det(A)$ 。
其中，

\[a_{i,j}=\begin{cases}b_i & \text{if}\ i=p_j\\c_i & \text{if}\ j=p_i\\ d_i & \text{if}\ i=j\\ x & \text{others}\end{cases} \]

这里 $d_i$ 是给定的下标为 $1\sim n$ 序列，$p_i,b_i,c_i$ 是给定的下标为 $2\sim n$ 序列，$x$ 是给定的常数。
由于答案可能很大，你只需要求出它对 $10^9+7$ 取模的值。
对于所有数据，$1\le n\le 10^6$，$0\le b_i,c_i,d_i,x\le 10^9$，$1\le p_i<i$ 。

FZOJ4555 [2021省选前模拟] 传统游戏

寒假里，小 H 的表弟到小 H 家做客。由于小 H 的母亲觉得小 H 整天宅在房间里影响非常不好，于是下令小 H 陪表弟玩耍。
由于年龄差过大，小 H 并不想浪费自己的时间。她随便翻开一本书中一页，书上介绍了传统的 Nim 游戏。小 H 心生一计。
传统的 Nim 游戏是这样的：有 $n$ 堆石子，第 $i$ 堆石子有 $a_i$ 个。博弈的双方轮流取石子，每一次每个人只能在一堆中取若干个，不能取的一方将会输掉游戏。
由于这个游戏非常好用计算机实现，因此小 H 决定写一个程序代替自己和表弟对战，这样一来她就可以做自己的事了。
小 H 先规定了一个巨大的数 $m$ ，接着小 H 将选取一个大小为 $n$ 的集合 $S$，$S$ 中的每个数都是 $0 \sim m - 1$ 的整数。接着，小 H 将会把这集合中的 $n$ 个数作为一个局面。
由于表弟年龄较小，所以小 H 会让表弟先手。但是表弟又不是好糊弄的，所以小 H 需要有十足的把握保证自己能够获胜。因此，在游戏开始前，小 H 想知道，有多少种初始局面能够保证自己获胜。由于这个数比较大，你只需要输出其对 $10^9 + 7$ 取模后的结果。
注意：由于小 H 选的是集合，所以初始局面要求石子数互不相同，而且方案数与石子排列的顺序无关。
对于所有测试点，满足 $1 \le n \le 3000, 1 \le L \le 5 \times 10^6, 1 \le nL \le 3.5 × 10^7$。

FZOJ4586 [2021省选前模拟] 猜数游戏

Alice 和 Bob 玩游戏。
Alice 有一个 $1 \sim n$ 中的正整数 $y$。Bob 不知道这个数。
游戏中的每一轮，Bob 选一个正整数 $x$，并提问 Alice：$y$ 是否大于等于 $x$？然后 Alice 需要回答是或否。
Alice 可以说至多一次谎。Bob 想要用尽量少的轮数确定 $y$，Alice 则希望 Bob 用的次数尽量多。
假设双方除第一轮外均采用最优策略。
作为一只 Goodeat，你既不是 Alice，也不是 Bob。
但你需要求出，对每个 $x = 1, 2, \dots, n$，当 Bob 第一轮问 $y$ 是否大于等于 $x$ 且 Alice第一轮回答了是的情形下，Bob 还需要多少轮能确定 $y$。
（Alice 第一轮有可能说谎。）
对于 $100\%$ 的数据 $2\le n\le 2000$。

FZOJ4597 [2021省选前模拟] 菜肴挑选

小 H 所在的食堂共有 $n$ 种不同菜肴。每天中午，小 H 都会到食堂挑选恰好三道不同的菜品食用。
小 H 吃午饭时总是喜欢将两种不同的菜品组合起来吃。如果小 H 某天选择了 $a, b, c$ 三种菜品，那她就能吃到 $\left(a, b\right), \left(b, c\right), \left(c, a\right)$ 三种不同的组合。
由于小 H 不挑食，所以她对每种组合的喜爱程度是均等的，因此她也希望在某一天能够使所有组合被吃的次数相等。
形式化的：记 $f\left(a, b\right)$ 表示在前 $k$ 天中有多少天吃到了组合 $\left(a, b\right)$，那么小 H 希望存在一个 $k$ 和一种方案，使得对于所有 $i\ne j$，$f\left(i, j\right)$ 的值都相等。当然 $k$ 需要大于 $0$，不然小 H 就什么都没吃了。
不过小 H 不希望她在毕业后才能达成这个愿望，所以她希望 $k$ 需要小于等于 $n^2$。
由于小 H 还有别的事要做，因此她把这个任务交给了你。
对于所有数据，满足 $3\le n\le 1000$。

FZOJ4628 [2021NOI前模拟] 签到

老虎和蒜头是好朋友。
老虎最近学习了 $\mathrm{SG}$ 函数，一个状态的 $\mathrm{SG}$ 函数值即为其所有次态的 $\mathrm{mex}$ 值。在经过了一番练习之后，老虎认为自己已经熟练掌握了 $\mathrm{SG}$ 函数的本质。并且，老虎还学会了一些高超的 $\mathrm{mex}$ 计算方法：例如，对于一个长度为 $n$ 的序列 $a_1, \cdots, a_n$，老虎能够快速计算某个区间 $\left[l_i, r_i\right]$ 的 $\mathrm{mex}$ 值。换句话说，老虎可以计算出最小的非负整数 $x_i$ 使得不存在 $l_i \le j \le r_i, a_j = x_i$。
不过，乐于给老虎出难题的蒜头这次又有了一个想法：蒜头仍然会给出老虎一个长度为 $n$ 的序列 $a_1, \cdots, a_n$。但在每次询问中，蒜头首先会要求老虎将下标在 $l_i$ 到 $r_i$ 之间的元素取出作为一个可重集合 $S$。随后蒜头会进行一种操作：该操作每次可以选择一个数 $x$，如果 $x$ 在 $S$ 中出现至少两次，那么蒜头可以删去一个 $x$，并往集合中加入 $x - 1$ 或 $x + 1$。现在蒜头想要知道，所有可能通过有限次以上操作得到的可重集合 $S'$ 中，最大的 $\mathrm{mex}$ 值是多少。
你能帮帮老虎解决这个问题吗？
对于 $100\%$ 的数据，$1 \le n, q \le 5 \times 10^5, 0 \le a_i \le 5 \times 10^5$。

FZOJ4635 [2021NOI前模拟] 染色

现在有个 $n \times m$ 的棋盘，每次你可以将一行或者一个斜对角线（从左下到右上）的格子给染黑，请问共有多少种可能的最终状态。
由于答案可能很大，答案对 $modu$ 取模。
对于 $100\%$ 的数据，$n, m \le 500$，$10^8 \le modu \le 10^9 + 7$。

FZOJ4649 [2021NOI前模拟] 喂鱼

PTY，又称鳙鱼，俗称胖头鱼。
又到了开饭的时间，PTY 愉快的游出来恰饭。鱼塘是一个 $n \times m$ 的二维平面，一共有 $n$ 个鱼饲料，每一个鱼饲料都是条状的，第 $i$ 个鱼饲料分布在 $(i, l_i)-(i, r_i$) 这两个点之间。
PTY 的嘴也是条状的，恰饭时他会平行于 $x$ 轴游动，吃掉第二维处于 $\left[ L, R \right]$ 之间的饲料，具体的，PTY 能吃到饲料 $i$，当且仅当 $\left[ l_i, r_i \right] \cap \left[ L, R \right] \ne \varnothing$
PTY 定义一个饲料区间是“爽的”当且仅当他能吃到这个区间中所有的饲料（不一定每个饲料都吃完，能吃到就算），他想知道，对于所有“爽的”区间，其中最长的区间是多长。
PTY 会询问多次，即你对于多个 $L_i, R_i$ 你都需要回答最长的” 爽区间”的长度（询问之间相互独立，没有后效性）。
对于 $100\%$ 的数据，保证 $1 \le n, m \le 10^5, 0 \le l_i, r_i, L_i, R_i \le 10^9, l_i \le r_i, L_i \le R_i$

FZOJ4652 [2021NOI前模拟] 锻炼

体育馆里有 $k$ 件不同的器材，编号 $1$ 到 $k$。
有 $n$ 个人，第 $i$ 个人希望在第 $a_i,a_i+1,\dots,b_i$ 天之中挑选一天，并在这天使用第 $p_i$ 件器材进行锻炼。同一件器材同一天只能由一个人使用。
如果某一天体育馆里没有人在锻炼，那么这一天体育馆就可以关闭，否则体育馆需要在这一天开放。
请给每个人安排锻炼时间，满足所有人的需求，同时使得体育馆的开放总天数尽量少。你只需要输出最少的开放总天数就可以了。
对于 $100\%$ 的数据，满足 $1\le n\le5\times10^5$，$1\le k\le10^9$，$1\le a_i\le b_i\le10^9$，$1\le p_i\le k$。

FZOJ4719 [2021NOI前模拟] 分割

小 D 正在研究图的分割。
小 D 想了一张 $n$ 个点 $m$ 条边的连通无向图 $G$。小 D 想要分割这张图；换言之，把这张图变得不连通。
小 D 不希望分割的手段过于复杂。例如，删去一条边就是一个不错的选择。
小 D 通过检索文献，知道了这样的边被称为桥，已经有十分成熟的算法可以求解这一问题。
于是，小 D 想要将这个问题稍微改一改：删边时，不仅删去这条边，还将其两个端点也删去。
小 D 便开始着手解决这个问题。具体而言，他想要知道，对于每一条边，如果删去其以及其端点（以及与这两个端点相连的那些边），图是否被分割呢？但他并不会，请你帮帮他。
对于所有测试数据，$3 \le n \le 3 \times 10^5,n - 1 \le m \le 3 \times 10^5,1 \le u, v \le n$，保证图连通、无自环、无重边。

FZOJ4720 [2021NOI前模拟] 相似

小 D 正在研究相似性。
小 D 认为两个等长字符串 $S$ 和 $T$ 是相似的，当且仅当将它们各删去一些字符后，它们变得一样了。
顾名思义，既然这两个字符串是相似的，那么这里的一些不能太多。具体而言，小 D 想了一个小阈值 $k$，认为如果删去的字符数不超过 $k$，那么我们就认为这两个字符串的确是相似的。
小 D 想了一个长度为 $n$ 的大写字符串 $S$。他想要知道，在所有长度同样为 $n$ 的大写字符串中，和 $S$ 相似的有多少个呢？
但他并不会，请你帮帮他。因为这个答案可能很大，所以你只要求出答案对 $998, 244, 353 \left( = 2^{23} \times 7 \times 17 + 1 \right)$ 取模的结果即可。
对于所有测试数据，$1 \le n = \vert S\vert \le 3 \times 10^4,0 \le k \le 4$，保证 $S$ 仅由大写字母组成。

FZOJ4729 [2021NOI前模拟] 笛镭特

给定一棵树，先后手轮流操作，先手每次删掉每个连通块内最小的点，后手每次删掉每个连通块内最大的点，求在多少轮删除后所有点都被删除。
形式化地，定义 $F\left(T,x\right)$ 为以 $T$ 中点权最小 / 最大（$x$ 为 $0$ 则最小，$x$ 为 $1$ 则最大）的点 $u$ 为根时，$1 +\max_{v,u\rightarrow v} F\left(\text{subtree}_v,x\oplus 1\right)$，给定树 $T$ , 求 $F\left(T,0\right)$。
你也可以认为是求每次不选择重心而轮流选择最小最大点的点分树深度。
现在给出这棵 $n$ 个点的树，保证其点权为排列。
对于全部数据，满足 $n\leq 3\times 10^5$。

FZOJ5031 [2022省选前模拟] 给国与地震

给国是一个神秘的国家。这个国家的 $n$ 个城市通过 $m$ 条无向道路互相连通。第 $i$ 个城市有 $a_i$ 的劳动力。
给国最近发生了一次巨大的地震，各条道路都发生了不同程度的损坏。具体来说，第 $i$ 条道路需要 $s_i$ 的劳动力来修复。而这些劳动力只能来自这条道路直接连接的两个城市 $u_i, v_i$。不过只要两个城市之间的道路被修复，这两个城市就连通了。已经连通的城市之间劳动力可以任意移动。
形式化说，对于道路 $i$，当且仅当 $u_i$ 已修复道路组成联通块中的 $a_j$ 权值加上 $v_i$ 已修复道路组成联通块中的 $a_j$ 权值之和 $\ge s_i$，这条道路可以被修复。
现在，作为给国的总工程师，你需要给出一种修复方案，使得最后修复的道路数尽可能多。
不过人命关天，你不能为了业绩而不顾效率。所以你无论何时都不应当修复一条无用的道路，即修复道路两端的城市 $u_i, v_i$ 必须不连通。
由于修复道路要做的工作非常繁重，在一个单位时间你最多只能指挥一条道路的修复工作。
所以最后给出的方案应当是一个长度为 $k$ 的序列 $b_i$，其中 $k$ 是最多能够修复的道路数。$b_i$ 表示i 时刻修复的道路编号。
为了展现你高超的设计能力，在满足上述条件下，你需要让 $b$ 序列的字典序尽可能小。
形式化题意
一张 $n$ 个点 $m$ 条边的无向连通图，点有点权 $a_j$，第 $i$ 条边加入的条件是 $u_i$ 和 $v_i$ 不连通，且 $u_i$ 所在联通块所有 $a_j$ 之和加上 $v_i$ 所在联通块所有 $a_j$ 之和 $\ge s_i$。
构造一个加边的序列，在序列尽可能长的情况下，序列字典序最小。
对于 $100\%$ 的数据，保证给定的图连通且无自环，$0 \le s_i, a_i \leq 10^6$，$1 \le u_i, v_i \le n$。

FZOJ5062 [2022省选前模拟] 排列

考虑所有满足 $1 \leq a \le b\leq n$ 的 $(a, b)$ 的排列。
称其合法，当且仅当对于每一个 $1 \leq a < b < c \leq n$ ，都有 $(a, c)$ 处在 $(a, b)$ 和 $(b, c)$ 之间。
另外再给出 $m$ 个限制，每个限制形如 $(a, b, c, d)$ ，要求 $(a, b)$ 在 $(c, d)$ 前面。
求满足限制的合法排列个数，模 $998244353$ 。
对于所有数据，保证 $1 \leq n \leq 10, 0 \leq m \leq 30$ 。

FZOJ5087 [2022省选前模拟] 嘉然

嘉然今天吃欧拉函数。
给定一个长为 $n$ 的排列 $p$ ，$q$ 组询问。每组询问给定 $l,r$ ，请求出：

\[\max_{l\leq i< j\leq r}\varphi(p_i\times p_j) \]

对于全部数据，满足 $1 \leq n,q \leq 5 \times 10^5 , 1 \leq l < r \leq n$。

FZOJ5201 [2022NOI前模拟] 幽灵

幽灵有两个串 $S$ 和 $T$，现在她想知道 $T$ 在 $S$ 出现了多少次。
这个题被可怜秒了，幽灵加强到了区间询问，然后又被可怜秒了。
现在幽灵用 $S$ 造了一个新的字符串 $P$，其中 $P$ 是由 $S$ 的若干个前缀拼起来的。
具体地，$P$ 由 $n$ 个 $S$ 的前缀拼起来，第 $i$ 个前缀长是 $a_i$。
现在幽灵进行了若干次区间询问，而可怜一次都回答不出来了，于是可怜来求助你。
对于 $100\%$ 的数据，满足 $2 \le |S|, |T| \le 5 \times 10 ^ 5, 1 \le a_i \le |S|, 1 \le n, q \le 5 \times 10^5, 1 \le l \le r \le \sum\limits_{i = 1} ^ n a_i$，字符串中只会出现小写英文字母。