Znzryb's Blog
0%

Posted on Edited on

题目大意

题目总结

问题描述

给定一个正整数 nn（3≤n≤2⋅1053 \le n \le 2 \cdot 10^5）。你需要构造一个长度为 nn 的排列 pp（包含 11 到 nn 的所有整数各一次），使得对于每一个 ii（1≤i≤n−11 \le i \le n-1），都能在索引范围 [i,n][i, n] 中找到一个下标 jj（即 i≤j≤ni \le j \le n），满足以下异或条件：

pi=pj⊕ip_i = p_j \oplus i

如果不存在满足条件的排列，则输出 −1-1。

输入输出

  • 输入：测试用例数量 tt，每个案例包含一个整数 nn。

  • 输出：若存在，输出 nn 个整数表示排列 pp；否则输出 −1-1。

样例解释

以 n=3n=3 为例，输出为 2 1 3：

  • 当 i=1i=1 时：需要存在 j∈{1,2,3}j \in \{1, 2, 3\} 使得 p1=pj⊕1p_1 = p_j \oplus 1。
    已知 p1=2p_1=2，若取 j=3j=3，则 p3⊕1=3⊕1=2p_3 \oplus 1 = 3 \oplus 1 = 2。满足条件。

  • 当 i=2i=2 时：需要存在 j∈{2,3}j \in \{2, 3\} 使得 p2=pj⊕2p_2 = p_j \oplus 2。
    已知 p2=1p_2=1，若取 j=3j=3，则 p3⊕2=3⊕2=1p_3 \oplus 2 = 3 \oplus 2 = 1。满足条件。

  • 所有 i∈[1,2]i \in [1, 2] 均满足条件，故 2 1 3 是合法解。

以 n=4n=4 为例：

  • 不存在任何长度为 44 的排列能满足上述所有约束，故输出 −1-1。

思路讲解

这道题目，一种方法是打表找规律，比较神秘，呃，也比较费时间，只不过由于我 C1 是打表打出来的，C2 也这样子尝试了，由于选取的规律比较奇怪，在某些情况下会出现问题，后需要与下标 lowbit(n)\text{lowbit}(n) 交换啊什么的，在这里就不介绍了。

不过可以总结一下，就是这种打表找规律的话，首先要确定没有答案的条件，其次就是写的检查器尽量报出更多的信息（在错误时），比如说这道题目，如果你构造出来的序列是错的，你写的检查器最好要报出来哪一位错了，有哪些位构造错误？这一位你填了什么值？反正信息越多越好。

那么构造方法如何解决 C1 呢？那么由于是要求 pi=pj⊕ip_i = p_j \oplus i，不妨就令 pi=i⊕1p_i=i\oplus 1，把 1 放在最后就可以了，最后这样子生成的序列第一位可能有点问题，这个特判一下就行。

那么如果你会解决 C1 的话，其实只需要增加一行代码：

1
2
3
4
5
6
if (N%2==0) {
    ans_ls[1]=N;
    swap(ans_ls[1],ans_ls[lowbit(N)]);
}else {
    ans_ls[1]=N-1;
}

即 swap(ans_ls[1],ans_ls[lowbit(N)]); 这一行代码。首先 lowbit(n)⊕1\text{lowbit}(n)\oplus 1 肯定不愁找不到满足的 jj，因为他都处于第一个位置了。那么对于 nn 呢？那么由于 n≥n⊕lowbit(n)≥lowbit(n)+2n≥n\oplus \text{lowbit}(n)≥\text{lowbit}(n)+2（nn 是偶数），所以说也不用愁找不到 jj。

当然，注意，nn 是 2 的幂次的时候是没有答案的，这也很容易理解，因为这个时候 nn 无论异或上 [1,n][1,n] 中的任何一个数字，其结果都超过了 [1,n][1,n] 的范围。

AC代码

AC
https://codeforces.com/contest/2189/submission/359568527

AC
https://codeforces.com/contest/2189/submission/359512601

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

题目总结：F. Prufer Vertex

1. Prufer 顶点 P(T)P(T) 的定义

对于一棵拥有 n≥2n \ge 2 个节点的树 TT，按照以下标准过程生成 Prufer 序列：

  • 重复寻找当前树中编号最小的叶子节点并将其删除。

  • 直到树中只剩下最后 2 个节点。
    已知节点 nn 必然是最后剩下的两个节点之一，设另一个剩下的节点为 vv，则定义该树的 Prufer 顶点 P(T)=vP(T) = v。

2. 问题描述

给定一个含有 nn 个顶点和 mm 条边的森林。假设该森林有 kk 个连通块，其大小分别为 s1,s2,…,sks_1, s_2, \dots, s_k。

已知将该森林添加 k−1k-1 条边使其成为一棵树的方案总数为：

nk−2∏i=1ksin^{k-2} \prod_{i=1}^{k} s_i

任务： 对于每一个 vv (1≤v<n1 \le v < n)，计算在所有可能的加边成树方案中，满足 P(T)=vP(T) = v 的方案数量。

3. 输出要求

输出 n−1n-1 个整数，第 ii 个整数表示满足 P(T)=iP(T) = i 的方案数，结果对 998244353998244353 取模。

样例解释（以样例 1 为例）：

输入 n=3,m=0n=3, m=0，森林由三个孤立点 {1,2,3}\{1, 2, 3\} 组成。补全为树的方案共有 33−2⋅(1⋅1⋅1)=33^{3-2} \cdot (1 \cdot 1 \cdot 1) = 3 种：

  1. 添加边 (1,2) 和 (1,3)： 叶子节点为 2 和 3。最小叶子 2 被删除，剩余 {1,3}\{1, 3\}。故 P(T)=1P(T)=1。

  2. 添加边 (2,1) 和 (2,3)： 叶子节点为 1 和 3。最小叶子 1 被删除，剩余 {2,3}\{2, 3\}。故 P(T)=2P(T)=2。

  3. 添加边 (3,1) 和 (3,2)： 叶子节点为 1 和 2。最小叶子 1 被删除，此时 2 变为叶子，删除 2，剩余 {3}\{3\} 与另一节点（在此情况下 Prufer 过程最后剩下的非 nn 节点为 2）。

最终输出：1 2（代表 P(T)=1P(T)=1 有 1 种，P(T)=2P(T)=2 有 2 种）。

思路讲解

我们阐述一下题意，叶子在无根树树中应该就是指的是度为 1 的点（虽然给的是森林，不过我们最后都会连成树），样例 1 的答案生成过程如图所示：

image

我们发现，只要一个点，是只和最大点相连的点（最大点和该点连接且仅和该点连接），那么这个点一定可以被保下来。因为这个点，是最后成为这个叶子节点的。原因：反证法，如果比较早把这个点删除了，那么最大点就变为孤零零一个人了，这显然是不可能的。

那么更进一步的推论就是，答案一定是和最大点直接相连的点。不过，虽然我们知道了答案是和最大点直接相连的点，但是我们不太清楚，到底是哪个点。

我们进行一个猜测，就是以这个点为根的子树，其内部的最大点，是所有的子树中最大的（即其他子树中的最大点，都比这颗子树小）。这样子，在删除这个内部最大点之前，我们会把其他子树全部删除，最后就只剩一颗子树了，结果就确定了。

当然，这个所谓的内部最大点，就是次大值 n−1n-1 啦，以 nn 为根，n−1n-1 所在的子树的根就是所能留下来的点。

不过现在的难点就来到了这个统计答案。

从 n−1n-1 的特殊情况看起，我们发现，如果 n−1n-1 已经连接在了 nn 的联通块上，且 n−1n-1 与 nn 之间未直接相连，此时答案为 0。如果直接相连，那么其实其他连通块要连接到 nn 的连通块上，这个要怎么算呢？我们不妨参考一下题目中的这个式子。

给定一个含有 nn 个顶点和 mm 条边的森林。假设该森林有 kk 个连通块，其大小分别为 s1,s2,…,sks_1, s_2, \dots, s_k。已知将该森林添加 k−1k-1 条边使其成为一棵树的方案总数为：

nk−2∏i=1ksin^{k-2} \prod_{i=1}^{k} s_i

实际上这个式子是凯莱公式的推论？

我们先来看一下凯莱公式吧，凯莱公式即：

image

其证明方法有：

image

呃😅，那我们还是用这个 prufer 序列吧，其实 prufer 序列就是把题目中描述的删点过程：每次我们记录一下这个我们删的点的父节点，得到的就是长度为 n−2n-2 的 prufer 序列。这个序列有 nn−2n^{n-2} 种选择，由于每颗生成树对应的 prufer 序列显然是唯一的，prufer 序列也唯一对应一颗生成树，因此生成树的数量就是 nn−2n^{n-2}（这个说的比较粗糙，只是引入一下 prufer 序列这个工具，帮助后面我们的这个理解）。

那么这个连通块的式子是怎么来的？

首先从 prufer 序列的角度来看，那么由于其中的每个点，都可以作为长度为 k−2k-2 的 prufer 序列中的点，所以就是 nk−2n^{k-2}，那么由于每个连通块还需选出来一个代表点连接，因此是：

nk−2∏i=1ksin^{k-2} \prod_{i=1}^{k} s_i

可以想象，nk−2n^{k-2} 代表了这个接收端，∏i=1ksi\prod_{i=1}^{k} s_i 代表了这个发送端。不过还有一个特例，就是没有被 prufer 序列覆盖的根连通块的这个贡献也包含在了这个 ∏i=1ksi\prod_{i=1}^{k} s_i 当中。换句话说，一个长度为 k−2k-2 的 prufer 序列的贡献是 ∏i=1ksi\prod_{i=1}^{k} s_i**，原因在于你要确定所有非根连通块的发送端****（**这个是固定的，只有一个的，否则会成环），还要确定根连通块的接收端（在 prufer 中未体现）（严格来讲是最后一个被删除的块所连接的这个根连通块的接收点）。

哎，我们回来看题目：

我们之前所说的结论：

以 nn 为根，n−1n-1 所在的子树的根就是所能留下来的点

说明，n−1n-1 连接在 ii 的子树下，是必要条件，是必须满足的。

你就抓住这个，进行分类讨论即可，因为太过细节，这里就不展开了。

然后，你会发现答案不对。

1
2
3
4
_______________[ Sample Testcase #1 OUTPUT]_______________
1 2
0 0 0 1
10 0 1 5 5

这道题目的难点，特别是计数难点在于，如何去解决一些先 kk 连通块连上 ii 的子树，然后 n−1n-1 再连上 kk 连通块去的这个情况（或者更加复杂情况下的计数）。

具体而言，我们以样例 3 的这个第一个计数为例：

image

但是这个计数问题我们怎么解决？

我们用算概率的方式，得到这个答案，具体而言：

image

为什么我们可以使用算概率的方式呢？实际上，n−1n-1 连接到 11 的子树的概率就是 12\frac{1}{2}，无论他是通过 33 连接，还是不通过 33 连接，都是这个概率。这个概率就起到了相当于抽丝剥茧，剥开重重迷雾的作用。

AC代码

AC

https://codeforces.com/contest/2191/submission/360174534

心路历程（WA，TLE，MLE……）

  • n−1n-1 的答案是：

    • 如果 nn 与 n−1n-1 直接相连，答案就是 nk−2∏i=1ksin^{k-2} \prod_{i=1}^{k} s_i。如果不直接相连，还处于同一联通块，那么答案是 0。那么最后一种更普遍的情况，就是 nn 与 n−1n-1 处于两个连通块，这个时候就将 nn 与 n−1n-1 连接在一起，形成的新的森林，用上面那个公式计算即可。

  • 更加普遍的情况下，ii 的答案是：

    • ii 与 nn 处于相同连通块：
    • ii 与 nn 处于不同连通块：
      我们之前所说的结论：

以 nn 为根，n−1n-1 所在的子树的根就是所能留下来的点
说明，n−1n-1 连接在 ii 的子树下，是必要条件，是必须满足的。

Posted on Edited on

题目大意

  1. 任务目标

已知一个隐藏的长度为 nn 的排列 pp。你需要找到一个字典序最小的排列 qq，使得 qq 满足以下两个条件：

  • q>pq > p （qq 的字典序大于 pp）

  • rev(q)>rev(p)rev(q) > rev(p) （qq 翻转后的字典序大于 pp 翻转后的字典序）

注意： qq 必须是由 pp 中的元素重新排列得到的。你不需要直接输出 qq，而是输出一个下标排列 rr (1≤ri≤n1 \le r_i \le n)，使得 qi=priq_i = p_{r_i}。如果不存在满足条件的 qq，输出 −1-1。

2. 交互规则

  • 你可以进行询问，格式为 ? i j，查询 pi<pjp_i < p_j 是否成立。

  • 如果 pi<pjp_i < p_j，交互库返回 11；否则返回 00。

  • 每个测试点最多允许询问 3n3n 次。

  • 交互库是非自适应的（隐藏排列 pp 在交互开始前已确定）。

3. 样例解释

  • 样例 1： p=[5,4,2,3,1]p = [5, 4, 2, 3, 1]

    • 满足条件的最小 qq 为 [5,4,3,1,2][5, 4, 3, 1, 2]。
    • 验证：qq 比 pp 字典序大；rev(q)=[2,1,3,4,5]rev(q) = [2, 1, 3, 4, 5]，rev(p)=[1,3,2,4,5]rev(p) = [1, 3, 2, 4, 5]，显然 rev(q)>rev(p)rev(q) > rev(p)。
    • 输出 r=[1,2,4,5,3]r = [1, 2, 4, 5, 3]，因为 p1=5,p2=4,p4=3,p5=1,p3=2p_1=5, p_2=4, p_4=3, p_5=1, p_3=2。

  • 样例 2： p=[3,1,2,4]p = [3, 1, 2, 4]

    • 不存在同时满足 q>pq > p 且 rev(q)>rev(p)rev(q) > rev(p) 的排列 qq，故输出 −1-1。

4. 数据范围

  • t≤1000t \le 1000，n≤2⋅104n \le 2 \cdot 10^4，所有测试用例的 nn 之和不超过 2⋅1042 \cdot 10^4。

  • 时间限制 2 秒，内存限制 256 MB。

思路讲解

一开始看这道题目，不能看出来像下面这张图的解法，但是我们会误以为这个情况的一些其他性质比较重要，但是最重要的是单调性的变化，因为没有单调性的变化意味着没有这个答案。

因此，这道题目关键点在于这个单调性的变化（即未发生单调性变化下操作是没有意义的，一定会违反题设条件），我们先来看这个情况，不难发现，在单调性变化之后执行交换与这个反转操作最好。

image

那么如果先下降呢？经过对拍验证以及这个推理，如果先下降再上升，是无法构造出答案的。原因：设在当前点，你需要构造 qq，以满足题设条件。因此，你要提高 qq 的字典序，那么必须要在后面的点当中选一个比当前点高的（最优的是恰好高的），但是这样一来，就会导致 rev(q)\text{rev}(q) 的字典序下降（这个是无法挽救的，因为目前的更换的当前点处于上升序列，处于上升序列的其他点比当前点低，处于下降序列的其他点比当前点低），导致无法满足题设条件。

image

因此先下降，再上升的话，必须要再找一个下降。

image

然后，交换好以后，就想办法把这个上升序列插入到这个下降序列当中（有序插入，保持单调下降性），随便你用什么办法。

然后为了减少提问个数，我们使用了记忆化，就是问过的，就不再问了（注意问了 a b 的话，b a 也不要再问了）。

感觉这道题目难度主要还是在这个调试，代码和细节上。

AC代码

AC
https://codeforces.com/contest/2191/submission/359093232

心路历程（WA，TLE，MLE……）

Posted on Edited on

题目大意

1. 核心定义

  • 括号序列比较 (“Better Than”)：
    对于两个括号序列 aa 和 bb，满足以下条件之一则称 aa 比 bb “更好”：

    1. bb 是 aa 的前缀，且 a≠ba \neq b。
    2. 在第一个不相同的字符位置 ii，ai=′(′a_i = '(' 且 bi=′)′b_i = ')'。

  • 序列 tt 的得分 (Score)：

    1. 如果 tt 不是正则括号序列 (RBS)，得分为 00。
    2. 如果 tt 是 RBS，查找其所有的正则括号子序列 rr。如果存在某些 rr 满足 rr 比 tt “更好”，则得分为这些 rr 中长度 ∣r∣|r| 的最大值。
    3. 若不存在这样的 rr，得分为 00。

2. 任务要求

给定一个长度为 nn (1≤n≤1001 \le n \le 100) 的括号序列 ss，求 ss 的所有非空子序列的得分之和，结果对 998244353998244353 取模。

3. 样例解释

  • 样例 2：s = ()()()
    考虑其中一个子序列 t="()()()"t = "()()()"：

    • 它是一个 RBS。
    • 它有一个子序列 r="(())"r = "(())"（取原序列第 1, 3, 4, 6 位）。
    • 比较 tt 和 rr：第一位都是 (，第二位 t2=′)′t_2 = ')' 而 r2=′(′r_2 = '('。根据定义，rr 比 tt 更好。
    • rr 的长度为 44，经校验这是最长的更好子序列，故该子序列 tt 得分为 44。
    • 其他子序列得分均为 00，总和为 44。

  • 样例 3：****s = (())()

    • 对于子序列 t="(())()"t = "(())()"，虽然它是 RBS，但无法找到比它“更好”的 RBS 子序列。
    • 例如，要在某位置 ii 更好，必须 ti=′)′t_i = ')' 且 ri=′(′r_i = '('，但在该位置之前，tt 已经用完了所有的 ( 匹配了前面的 )，无法构造出更优的正则子序列。
    • 因此总和为 00。

思路讲解

首先，D1 当中，我们发现一个规律，就是只要 ss 串只要是有答案的，其答案就是 ∣s∣−2|s|-2，那么其有答案的条件是第一个 )) 出现的位置后，又至少出现了出现了两个 ((。

我们可以定义一个如下状态：

image

⚠️注意：这里的长度，个数，指的是合法方案个数及其合法方案的总（后缀）长度，这样子定义是为了方便记忆化搜索。

总体上的记忆化搜索过程可以描述为这样：

res←(0,0)if unbalance=0∧state=3:res←(1,1)lres←dfs(idx,unbalance,state)if idx≠0:lreslen←lreslen+lresnumres←res+lres\begin{aligned} & res \gets (0,0) \\ & \text{if } unbalance = 0 \land state = 3: res \gets (1,1) \\ & lres \gets \text{dfs}(idx, unbalance, state) \\ & \text{if } idx \neq 0: lres_{\text{len}} \gets lres_{\text{len}} + lres_{\text{num}} \\ & res \gets res + lres\end{aligned}

那么之所以不在 idx=0idx=0 的时候进行这个操作，是因为 0 是虚拟节点，没有实际字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
auto dfs=[&](auto && self,int idx,int unbalance,int state) -> Len_num{
    if (unbalance<0) {
        return {0,0};
    }
    if (vis[idx][unbalance][state]) {
        return dp[idx][unbalance][state];
    }
    vis[idx][unbalance][state]=true;
    // assert(idx<=N);
    Len_num res={0,0};
    if (unbalance==0 && state==3) {
        // 相当于只选这个 s【idx】的时候
        res={1,1};
    }
    for (int i=idx+1;i<=N;++i) {
        Len_num lres;
        if (s[i]==')') {
            lres=self(self,i,unbalance-1,max(1,state));
        }else {
            int to_state;
            if (state==0) to_state=0;
            else to_state=min(3,state+1);
            lres=self(self,i,unbalance+1,to_state);
        }
        res+=lres;
        // 0 是一个虚拟节点，不会增加这个 res 长度
        if (lres.len!=0 && idx!=0) {
            // 这里给所有的方案增加一个长度，即选了
            res.len+=lres.num;
        }
        res%=mod;
    }
    dp[idx][unbalance][state]=res;
    return res;
};
Len_num res=dfs(dfs,0,0,0);

AC代码

AC
https://codeforces.com/contest/2191/submission/358546432

心路历程（WA，TLE，MLE……）

res←{0,0}unbalance=0 and state=3:res←{1,1}lres←dfs(idx,unbalance,state)idx≠0:lres.len←lres.len+lres.numres←res+lresres\gets \{0,0\}\\ unbalance=0 \text{ and } state=3:res\gets \{1,1\} \\ lres\gets \text{dfs}(idx,unbalance,state)\\ idx≠0:lres.len\gets lres.len+lres.num\\ res\gets res+lres

Posted on Edited on

题目大意

Alice 和 Bob 在长度为 n 的二进制字符串 s(仅包含字符 0 和 1)上进行博弈游戏。Alice 先手,双方轮流操作。

游戏规则:

  • 每回合,玩家选择一个索引序列 i₁, i₂, …, iₘ(严格递增),使得这些位置的字符形成非增序列(s[i₁] ≥ s[i₂] ≥ … ≥ s[iₘ])

  • 然后将这些位置的字符重新排列为非减序列(先放所有 0,再放所有 1)

  • 有效移动必须严格改变字符串(即选中的字符中至少有一个 0 和一个 1)

  • 无法进行有效移动的玩家输掉游戏

任务:

  • 假设双方都采用最优策略,判断谁会获胜

  • 如果 Alice 获胜,输出她的一个获胜首步移动(索引序列)

输入格式:

  • 多组测试数据,第一行包含测试数据组数 t(1 ≤ t ≤ 10⁴)

  • 每组数据:第一行为字符串长度 n(1 ≤ n ≤ 2×10⁵),第二行为二进制字符串 s

  • 保证所有测试用例的 n 之和不超过 2×10⁵

输出格式:

  • 如果 Bob 获胜,输出 “Bob”

  • 如果 Alice 获胜,输出三行:第一行 “Alice”,第二行整数 m(选中的索引数量),第三行 m 个递增的索引

样例说明:

  • 样例 1(000):字符串已经有序,无法进行任何有效移动,Bob 直接获胜

  • 样例 3(10):Alice 可以选择位置 [1,2],将字符串变为 01,之后 Bob 无法移动,Alice 获胜

思路讲解

其实我们会发现，只需要一次操作即可解决这个问题。

AC代码

AC

https://codeforces.com/contest/2191/submission/358351618

心路历程（WA，TLE，MLE……）