西安交通大学2026年程序设计竞赛校赛

Updated 2026-06-07 16:04 GMT+8

Compiled by Hongfei Yan (2026 Spring)

Contest: https://www.luogu.com.cn/contest/314922#problems

Problems A–O, each with title, description, solution approach, and Python code.

A. P16436 幽灵×毕业✅

https://www.luogu.com.cn/problem/P16436?contestId=314922

:::校队机房中的对话] 哦不，我补考估计要挂科了！"

"那又如何，至少你去参加了补考，这就已经超越你学长了。" :::

题目描述

长江后浪推前浪，一代新人换旧人。随着 XJTUPC2026 的举办，又一届学长即将毕业，不过在那之前，还有一件事情需要办理……

众所周知，在某所西安高校，毕业学生需要修读 12 学分的通识类课程，一般由 $3$ 门通识类核心课和 $3$ 门通识类选修课构成。

现在假定所有学生均只修读了 $6$ 门通识类课程，第 $i$ 门课程要么是通识类核心课，要么是通识类选修课。

现在由于众所周知的系统问题，学生们只能人工计算自己是否修读了足够的课程，即判断是否修读了至少 $3$ 门通识类核心课和至少 $3$ 门通识类选修课。不过这太麻烦了，希望你能写一个程序完成这个功能。

输入格式

输入共一行，包含六个整数 $x_1,x_2,\cdots ,x_6$（$x_1,x_2\cdots ,x_6\in \{0,1\}$），用一个空格分隔。对于第 $i$ 个整数 $x_i$：

• $x_i=0$ 表示该学生修读的第 $i$ 门通识类课程为通识类核心课；
• $x_i=1$ 表示该学生修读的第 $i$ 门通识类课程为通识类选修课。

输出格式

输出共一行，包含一个字符串：

• 当该学生修读了至少 $3$ 门通识类核心课和至少 $3$ 门通识类选修课，输出 $\mathtt{C}\mathtt{o}\mathtt{n}\mathtt{g}\mathtt{r}\mathtt{a}\mathtt{t}\mathtt{u}\mathtt{l}\mathtt{a}\mathtt{t}\mathtt{i}\mathtt{o}\mathtt{n}\mathtt{s}\mathtt{o}\mathtt{n}\mathtt{g}\mathtt{r}\mathtt{a}\mathtt{d}\mathtt{u}\mathtt{a}\mathtt{t}\mathtt{i}\mathtt{o}\mathtt{n}\mathtt{!}$
• 否则，输出 $\mathtt{S}\mathtt{o}\mathtt{n}\mathtt{g}\mathtt{f}\mathtt{e}\mathtt{s}\mathtt{i}\mathtt{n}\mathtt{J}\mathtt{a}\mathtt{p}\mathtt{a}\mathtt{n}\mathtt{.}\mathtt{.}\mathtt{.}$

输入输出样例 #1

输入 #1

0 0 0 1 1 1

输出 #1

Congratulations on graduation!

输入输出样例 #2

输入 #2

0 1 0 0 0 0

输出 #2

Songfes in Japan...

思路

签到题。统计 0 的个数（核心课）和 1 的个数（选修课），若均 ≥ 3 则输出毕业祝贺，否则输出挂科提示。

代码

nums = list(map(int, input().split()))
cnt0 = nums.count(0)
cnt1 = nums.count(1)
if cnt0 >= 3 and cnt1 >= 3:
    print("Congratulations on graduation!")
else:
    print("Songfes in Japan...")

B. P16437 全都登不上 2✅

https://www.luogu.com.cn/problem/P16437?contestId=314922

:::[------ Shirost] 第一章：沉淀。

第二章：那场大雨毁了我的 OI 梦。

第三章：程序设计校赛一等奖也是一等。

第四章：什么叫打不开 Domjudge？

第五章：神秘断网毁了我的一等梦。

第六章：沉淀，备战 2027 年程序设计校赛。 :::

题目描述

有 $n$ 个机房，分属 $m$ 个小组，第 $i$ 个机房属于小组 $a_i$。OJ 服务器放在小组 $v$ 的某个机房中。

神秘管理员误操作，将 $k$ 个小组“隔离”了。一个小组被隔离后，该小组内的机房将无法联系其他任何小组的机房。没有被隔离的小组之间都可以正常通信。小组 $v$ 永远不会被隔离。

请你计算：在隔离了这 $k$ 个小组之后，总共有多少个机房仍然能够访问 OJ 服务器。

输入格式

输入的第一行，包含三个整数 $n,m$ 和 $k$（$1\le k<m\le n\le {10}^5$），用一个空格分隔，分别表示机房总数、小组总数和被隔离的小组数量。

第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$（$1\le a_i\le m$），用一个空格分隔，其中 $a_i$ 表示第 $i$ 个机房所属的小组编号。

第三行包含一个整数 $v$（$1\le v\le m$），表示 OJ 服务器所在的小组编号。

接下来 $k$ 行，每行包含一个整数 $u$（$1\le u\le m$，$u\ne v$），表示一个被隔离的小组编号。保证每个小组至多被隔离一次。

输出格式

输出共一行，包含一个整数，表示最终能够访问 OJ 的机房数量。

输入输出样例 #1

输入 #1

6 4 2
1 2 4 3 2 1
1
2
3

输出 #1

3

思路

• 与 OJ 服务器同组的机房可以直接访问（同组内部通信不受隔离影响）。
• 没有被隔离的组的机房可以互相通信，因此它们也能访问 OJ 服务器。
• 统计所有属于组 v 的机房数量，以及所有未被隔离的组（除 v 外）的机房数量，求和即可。

代码

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
v = int(input())
isolated = set()
for _ in range(k):
    isolated.add(int(input()))

cnt = 0
for g in a:
    if g == v:
        cnt += 1
    elif g not in isolated:
        cnt += 1
print(cnt)

C. P16438 共同特征✅

https://www.luogu.com.cn/problem/P16438?contestId=314922

在计算机科学中，按位与（$\mathrm{and}$）是一种二元运算。对于任意的非负整数 $a$ 和 $b$，设其二进制表示为 $a=\sum _{i=0}^{\mathrm{\infty }}{a}_i{2}^i$，$b=\sum _{i=0}^{\mathrm{\infty }}{b}_i{2}^i$，其中 $a_i,b_i\in \{0,1\}$ 仅有有限个非零，我们记 $a$ 和 $b$ 进行按位与运算的结果 $a\mathrm{and}b$ 为：

$$a\mathrm{and}b=\sum _{i=0}^{\mathrm{\infty }}(a_i\cdot b_i)2^i$$

在数学中，整除（$\mid$）是一种二元关系。对于任意的正整数 $a$ 和 $b$，当且仅当存在一个正整数 $k$，满足 $a=b\cdot k$，我们称 $b$ 整除 $a$，记作 $b\mid a$。

在数学中，最大公约数（$gcd$）是一种二元运算。对于任意的正整数 $a$ 和 $b$，我们记 $a$ 和 $b$ 的最大公约数 $gcd(a,b)$ 为最大的能同时整除 $a$ 和 $b$ 的正整数，即：

$$gcd(a,b)=max\{d\in {\mathbb{N}}^{+}:d\mid a\wedge d\mid b\}$$

现在有一个正整数 $x$，请找出最小的正整数 $y$，使得 $x$ 和 $y$ 进行按位与运算的结果等于 $x$ 和 $y$ 的最大公约数。即求解：

$$y_{min}=min\{y\in {\mathbb{N}}^{+}:(x\mathrm{and}y)=gcd(x,y)\}$$

输入格式

本题包含多组测试用例。输入的第一行，包含一个正整数 $T$（$1\le T\le {10}^5$），表示测试用例的数量。

接下来是 $T$ 组测试用例的描述。

每个测试用例共一行，包含一个正整数 $x$（$1\le x<2^{60}$）。

输出格式

对于每个测试用例，输出一行，包含一个正整数 $y_{min}$，表示 $y_{min}=min\{y\in {\mathbb{N}}^{+}:(x\mathrm{and}y)=gcd(x,y)\}$。

输入输出样例 #1

输入 #1

4
9
16
3108
56109

输出 #1

1
16
4
1

思路

数学题。设 d = gcd(x, y)，则 x = d·x', y = d·y' 且 gcd(x', y') = 1。 条件 (x & y) = d 需要 d 的二进制位是 x 和 y 的子集，且没有进位冲突。

观察发现：

• 若 x 为奇数，取 y = 1。此时 gcd(x, 1) = 1，且 (x & 1) = 1，成立。
• 若 x 为偶数，取 y = lowbit(x) = x & -x（x 的最低置位）。此时 gcd(x, y) = y（因为 y 整除 x），且 (x & y) = y（因为 y 是 x 的二进制子集）。证明 y 最小：任何比 lowbit(x) 小的正数 z 都不包含 bit lowbit(x)，因此 gcd(x, z) < lowbit(x) ≤ z，不可能等于 (x & z) ≤ z。若 z = 0 不是正整数，因此 lowbit(x) 是最小值。

算法：对每个 x，若 x 为奇数输出 1，否则输出 x & -x。

代码

import sys
data = sys.stdin.buffer.read().split()
T = int(data[0])
out = []
for i in range(1, T + 1):
    x = int(data[i])
    if x & 1:
        out.append("1")
    else:
        out.append(str(x & -x))
sys.stdout.write("\n".join(out))

D. P16439 鲜艳 / 方格✅

https://www.luogu.com.cn/problem/P16439?contestId=314922

Y2hlOTYw 是一名国际象棋爱好者。然而，他没有自己的棋盘。

一天，他得到了一张 $n$ 行 $m$ 列的黑白双色网格纸。这当然不会是一个标准的国际象棋棋盘，不过 Y2hlOTYw 可管不了这么多。他认为，如果所有同色格子通过上下左右相邻形成的每个连通块，其形状都必须是矩形，这张网格纸就能当成棋盘用。

现在 Y2hlOTYw 想让你帮忙判断一下，这张网格纸能不能当成棋盘用。

形式化地，设网格纸为 $G=\{(i,j)\mid 1\le i\le n,1\le j\le m\}$，其中 $n$ 和 $m$ 为正整数。每个格子 $(i,j)$ 被赋予一种颜色 $\text{color}(i,j)\in \{\text{black},\text{white}\}$。

两个格子 $(i,j)$ 与 $(i^{\prime },j^{\prime })$ 相邻当且仅当 $|i-i^{\prime }|+|j-j^{\prime }|=1$。

对于固定的颜色 $c\in \{\text{black},\text{white}\}$，考虑子集 $S_c=\{(i,j)\in G\mid \text{color}(i,j)=c\}$。在 $S_c$ 上定义等价关系：两个格子等价当且仅当存在格子序列 $(i_1,j_1),(i_2,j_2),\dots ,(i_k,j_k)$ 使得每个格子都属于 $S_c$，且对于任意的 $t$（$1\le t\le k-1$）都有格子 $(i_t,j_t)$ 与格子 $(i_{t+1},j_{t+1})$ 相邻。每个等价类称为一个连通块。一个连通块是极大的，即不能通过添加任何相邻的同色格子而扩大。

一个格子集合 $R\subseteq G$ 的形状被称为矩形，如果存在整数 $r_1\le r_2$ 和 $c_1\le c_2$ 使得：

$$R=\{(i,j)\mid r_1\le i\le r_2,c_1\le j\le c_2\}$$

现在需要判断：每一个连通块的形状，是否都是矩形。

输入格式

本题包含多组测试用例。输入的第一行，包含一个正整数 $T$（$1\le T\le 8266$），表示测试用例的数量。

接下来是 $T$ 组测试用例的描述。

每个测试用例的第一行，包含两个整数 $n$ 和 $m$ ($1\le n,m\le 500$)，用一个空格分隔，表示网格纸有 $n$ 行 $m$ 列。

接下来 $n$ 行，第 $i$ 行包含一个长度恰为 $m$ 的字符串 $S_i$，表示给定的网格纸。保证字符串 $S_i$ 仅包含字符 $\mathtt{\text{0}}$ 和 $\mathtt{\text{1}}$。其中，对于任意的整数 $i$ 和 $j$（$1\le i\le n,1\le j\le m$）：

• 若第 $i$ 行第 $j$ 个字符为 $\mathtt{\text{1}}$，表示网格纸第 $i$ 行第 $j$ 列的格子 $(i,j)$ 的颜色为黑色（$\text{black}$）；
• 若第 $i$ 行第 $j$ 个字符为 $\mathtt{\text{0}}$，表示网格纸第 $i$ 行第 $j$ 列的格子 $(i,j)$ 的颜色为白色（$\text{white}$）。

保证所有测试用例中 $n\cdot m$ 的总和不超过 $2.5\times {10}^5$。

输出格式

对于每个测试用例，输出一行，包含一个字符串：

• 若这张网格纸能当成棋盘用，即每一个连通块的形状都是矩形，则输出 $\mathtt{Y}\mathtt{e}\mathtt{s}$；
• 否则，输出 $\mathtt{N}\mathtt{o}$。

答案对大小写不敏感。例如 $\mathtt{y}\mathtt{E}\mathtt{s}$，$\mathtt{Y}\mathtt{e}\mathtt{s}$，$\mathtt{y}\mathtt{e}\mathtt{s}$ 和 $\mathtt{Y}\mathtt{E}\mathtt{S}$ 都会被视为 $\mathtt{Y}\mathtt{e}\mathtt{s}$。

输入输出样例 #1

输入 #1

4
2 3
110
110
4 3
110
111
111
111
5 5
00000
01110
01010
01110
00000
8 8
01010101
10101010
01010101
10101010
01010101
10101010
01010101
10101010

输出 #1

Yes
No
No
Yes

思路

对每个连通块，记录最小/最大行、最小/最大列，统计块内格子数。若 (max_row − min_row + 1) × (max_col − min_col + 1) = 块内格子数，且该区域内没有异色格子，则为矩形。

实现时可以用 BFS/DFS 遍历连通块，同时记录边界。更高效的方法：遍历所有格子，检查每个格子的右侧和下侧，若同色但不同块（即父节点不同）则不构成矩形。

简化实现：对每个连通块，BFS 后检查边界矩形内是否全同色。

代码

import sys
sys.setrecursionlimit(1 << 20)

def solve():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    T = int(next(it))
    out_lines = []
    for _ in range(T):
        n = int(next(it)); m = int(next(it))
        grid = [next(it).decode() for _ in range(n)]
        visited = [[False] * m for _ in range(n)]
        ok = True
        for i in range(n):
            for j in range(m):
                if not visited[i][j]:
                    color = grid[i][j]
                    stack = [(i, j)]
                    visited[i][j] = True
                    min_r = max_r = i
                    min_c = max_c = j
                    cells = [(i, j)]
                    while stack:
                        r, c = stack.pop()
                        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                            nr, nc = r + dr, c + dc
                            if 0 <= nr < n and 0 <= nc < m and not visited[nr][nc] and grid[nr][nc] == color:
                                visited[nr][nc] = True
                                stack.append((nr, nc))
                                cells.append((nr, nc))
                                min_r = min(min_r, nr)
                                max_r = max(max_r, nr)
                                min_c = min(min_c, nc)
                                max_c = max(max_c, nc)
                    total = (max_r - min_r + 1) * (max_c - min_c + 1)
                    if total != len(cells):
                        ok = False
                        break
                    for r in range(min_r, max_r + 1):
                        for c in range(min_c, max_c + 1):
                            if grid[r][c] != color:
                                ok = False
                                break
                        if not ok:
                            break
                if not ok:
                    break
            if not ok:
                break
        out_lines.append("Yes" if ok else "No")
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    solve()

E. P16440 公式战士✅

https://www.luogu.com.cn/problem/P16440?contestId=314922

你一定在各类社交平台或短视频软件上刷到过这样让人血压升高的游戏广告：玩家操控的角色顶着一个极其可怜的战斗力数值，面对战斗力「$\times 10$」和「$÷2$」两扇门，偏偏毫不犹豫地走向了「$÷2$」，最后遇到高等级的怪物被无情击败。

每次看到这种视频，你都恨不得冲进屏幕替他操作。现在，你终于下载到了这款名为《公式战士（Formula Warriors）》的游戏，你决定亲自上手，打破游戏广告的弱智操作，向所有人展示什么才是真正的最强战士。

初始时，你控制的战士战斗力为一个正整数 $x$。

游戏共有 $n$ 个关卡。在每个关卡中，战士的面前会出现 $2$ 扇门，战士必须且只能选择其中一扇门通过。

每一扇门上都写有一个公式，当战士通过这扇门时，战士的战斗力 $x$ 会变为：

$$x\leftarrow \lfloor \text{Expression1}\text{Operator}\text{Expression2}\rfloor$$

其中：

• $\text{Operator}$ 为加（$+$）、减（$-$）、乘（$\times$）、除（$÷$）四种运算符中的一种；
• 在 $\text{Expression1}$ 和 $\text{Expression2}$ 中，恰有一个是战士当前的战斗力 $x$，恰有一个是门上给定的正整数常量 $v$；
• $\lfloor A\rfloor$ 表示对 $A$ 向下取整。

保证不论你在游戏中做出何种合法的选择，在完成第 $i$（$1\le i\le n$）次操作后，战士当前的战斗力 $x$ 始终满足 $1\le x\le {10}^{18}$。

你需要合理规划这 $n$ 次选择，使得 $n$ 个关卡全部通过后，最终战士的战斗力 $x$ 被最大化。请输出这个可能的最大战斗力。

输入格式

本题包含多组测试用例。输入的第一行，包含一个正整数 $T$（$1\le T\le {10}^3$），表示测试用例的数量。

接下来是 $T$ 组测试用例的描述。

每个测试用例的第一行，包含两个正整数 $n$ 和 $x$（$1\le n\le {10}^4$，$1\le x\le {10}^{18}$），用一个空格分隔，分别表示关卡数量和战士的初始战斗力。

接下来 $n$ 行，第 $i$ 行表示第 $i$ 个关卡的 $2$ 扇门上的公式信息，包含 $6$ 个以一个空格分隔的元素，前 $3$ 个元素描述第一扇门，后 $3$ 个元素描述第二扇门。

对于每一扇门，其给定的 $3$ 个元素格式严格为 $\text{Expression1}\text{Operator}\text{Expression2}$，其中：

• $\text{Operator}$ 为字符 $\mathtt{\text{+}}$，$\mathtt{\text{-}}$，$\mathtt{\text{*}}$，$\mathtt{\text{/}}$ 中的一种，分别代表加、减、乘、除；
• $\text{Expression1}$ 和 $\text{Expression2}$ 中，恰有一个是字符 $\mathtt{\text{x}}$，代表玩家当前战斗力；恰有一个是正整数 $v$（$1\le v\le {10}^{18}$），代表门上给定的常量。

例如，$\mathtt{\text{x + 5}}$ 表示将战斗力变为 $\lfloor x+5\rfloor$；$\mathtt{\text{100 / x}}$ 表示将战斗力变为 $\lfloor 100÷x\rfloor$。

保证不论你在游戏中做出何种合法的选择，在完成第 $i$（$1\le i\le n$）次操作后，战士当前的战斗力 $x$ 始终满足 $1\le x\le {10}^{18}$。

保证所有测试用例中 $n$ 的总和不超过 ${10}^4$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示战士通过 $n$ 个关卡后，战士能获得的最大战斗力。

输入输出样例 #1

输入 #1

2
3 2
x + 3 x * 2
100 / x x * 10
x - 10 1000 / x
1 1145141919810
1145141919810 + x 3 * x

输出 #1

50
3435425759430

说明/提示

在样例测试用例 1 中，一种最优的选择方案为：第一扇门 $\to$ 第一扇门 $\to$ 第二扇门。

对应的战斗力的变化为：$2\to 5\to 20\to 50$。

这道题可以通过单调性和动态规划（或递推）的思想来高效解决。

分析

1. 值域始终在 $[1,{10}^{18}]$ 内：题目保证了无论如何选择门，每一阶段的战斗力都会保持在 $[1,{10}^{18}]$ 内。

2. 运算符的单调性： 门上的表达式形如 x op v 或 v op x，其中 op 是 +, -, *, / 之一。 由于 $x\ge 1$ 且 $v$ 为常数，这些函数在正数区间 $[1,{10}^{18}]$ 内都具有单调性（单调递增或单调递减）。

   • 例如：$x+v$、$x\times v$、$x/v$（当 $v>0$ 时）是单调递增（非递减）的；而 $v-x$、$v/x$ 是单调递减（非递增）的。
   • 下取整函数 $\lfloor \text{expr}\rfloor$ 也是单调的。如果 $f(x)$ 单调，那么 $\lfloor f(x)\rfloor$ 也必然单调。

3. 维护区间的极值： 因为所有的转移函数都是单调的，所以一个数值区间 $[L,R]$ 经过转移函数 $f(x)$ 后的新取值区间，其最大值和最小值一定在边界点 $f(L)$ 或 $f(R)$ 处取得。

   因此，我们不需要记录所有可能达到的战斗力，而只需要记录当前阶段战斗力的最小值 min_val 和最大值 max_val。

   在每一关中，有两扇门 $f$ 和 $g$：

   • 经过第一扇门后，可能的取值范围由 $\{f(\text{min\_val}),f(\text{max\_val})\}$ 决定。
   • 经过第二扇门后，可能的取值范围由 $\{g(\text{min\_val}),g(\text{max\_val})\}$ 决定。

   我们只需计算这 4 个值，并将其中的最小值作为新的 min_val，最大值作为新的 max_val 即可。

Python 3 实现

由于涉及到大整数（最高达 ${10}^{18}$），Python 默认支持高精度整数，所以使用 // 进行整除（等价于正数下的下取整 $\lfloor \text{expr}\rfloor$）可以完美避免精度问题。

import sys

def solve():
    # 快速读入所有输入
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    iterator = iter(input_data)
    
    try:
        T_str = next(iterator)
        T = int(T_str)
    except StopIteration:
        return
    
    out = []
    for _ in range(T):
        n = int(next(iterator))
        x = int(next(iterator))
        
        min_val = x
        max_val = x
        
        for _ in range(n):
            t1 = next(iterator)
            op1 = next(iterator)
            t3 = next(iterator)
            t4 = next(iterator)
            op2 = next(iterator)
            t6 = next(iterator)
            
            # 计算第一扇门转移后的极值
            if t1 == 'x':
                v = int(t3)
                if op1 == '+':
                    v1, v2 = min_val + v, max_val + v
                elif op1 == '-':
                    v1, v2 = min_val - v, max_val - v
                elif op1 == '*':
                    v1, v2 = min_val * v, max_val * v
                elif op1 == '/':
                    v1, v2 = min_val // v, max_val // v
            else:
                v = int(t1)
                if op1 == '+':
                    v1, v2 = v + min_val, v + max_val
                elif op1 == '-':
                    v1, v2 = v - min_val, v - max_val
                elif op1 == '*':
                    v1, v2 = v * min_val, v * max_val
                elif op1 == '/':
                    v1, v2 = v // min_val, v // max_val
            
            # 计算第二扇门转移后的极值
            if t4 == 'x':
                v = int(t6)
                if op2 == '+':
                    v3, v4 = min_val + v, max_val + v
                elif op2 == '-':
                    v3, v4 = min_val - v, max_val - v
                elif op2 == '*':
                    v3, v4 = min_val * v, max_val * v
                elif op2 == '/':
                    v3, v4 = min_val // v, max_val // v
            else:
                v = int(t4)
                if op2 == '+':
                    v3, v4 = v + min_val, v + max_val
                elif op2 == '-':
                    v3, v4 = v - min_val, v - max_val
                elif op2 == '*':
                    v3, v4 = v * min_val, v * max_val
                elif op2 == '/':
                    v3, v4 = v // min_val, v // max_val
            
            # 更新当前阶段的全局极值
            min_val = min(v1, v2, v3, v4)
            max_val = max(v1, v2, v3, v4)
            
        out.append(str(max_val))
        
    print('\n'.join(out))

if __name__ == '__main__':
    solve()

复杂度分析

• 时间复杂度：每个关卡只需要进行 $O(1)$ 次基本的算术运算。对于每个测试用例，时间复杂度为 $O(n)$。总时间复杂度为 $O(\sum n)$，在 $\sum n\le {10}^4$ 的数据范围内可以非常快速地运行完毕（通常少于 0.05 秒）。
• 空间复杂度：仅需 $O(1)$ 的辅助空间来维护 min_val 和 max_val（除了读入数据的存储空间外）。

F. P16441 直播获奖✅

https://www.luogu.com.cn/problem/P16441?contestId=314922

你常常追忆过去。生命瞬间定格在脑海。你将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。

时间被裁剪、折叠、蜷曲。咦，你好像不在联合省选 2025 的赛场上。你该在哪里停留？你问你自己。

时光荏苒，小 Z 和小 J 也会散去。而你们和一个人保持连接的方式就是记住，仅此而已。

时光走过，小 Z 和小 J 会再遇见。回首往事，大家都过上了各自想要的生活。

好像有什么不对。咦，你好像也不在 NOI2024 的赛场上。你该在哪里停留？你问你自己。

NOI2233 即将举行。为了增加观赏性，FFC 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。

你终于想到了。你今年刚上初一，你正在 CSP-J 2020 的赛场上，比赛的第二题叫“直播获奖”。由于你不会桶排序，你在这题中取得了 95 分的高分。

咦，你怎么预知了你在“直播获奖”这一题上的得分呢？这真的可能吗？这可能被完成吗？

一年一度的 XJTUPC 又要举办了，但是老牌杂鱼猫娘出题人小标准突然有急事要回趟渐江。

原来你已经退役了。你正坐在 XJTUPC2026 的赛场上做一道叫做“直播获奖”的题目。你该在哪里停留？你问你自己。

题目描述

你正在玩一款被称为「ZJOI2022」的游戏。游戏发生在一个被称作「渐江」的幻想世界。你将扮演一位名为「咋克」的神秘角色，在自由的旅行中邂逅性格各异、能力独特的同伴们，和他们一起击败强敌，找回失散的亲人------同时，逐步发掘「九条可怜」的真相。

每位玩家在结束游戏后，拥有四个属性：

• 游戏 UID。游戏 UID 是每一位玩家的唯一标识符，为一个正整数。所有玩家的 UID 各不相同。
• 游玩游戏所使用的元素。元素为「阴」或者「阳」。
• 所在的游戏公会。每一位玩家属于一个公会，公会由正整数编号标识。
• 游戏成绩。游戏成绩为一个正整数。保证所有玩家的成绩互不相同。

这个游戏使用非常特别的结算方式。具体来说，「评测机」将会按 UID 从小到大的顺序揭露每一位玩家的总分。每位玩家的分数被揭露以后，预示着胜利者的「渐江省队」名单会随之更新。「渐江省队」由 A 队和 B 队组成，两队的成员互不重叠。

根据当前所有已揭露的玩家，按照下述规则更新「渐江省队」名单：

规则一：A 队选拔

设当前已揭露的玩家集合为 $S$。记集合 $S$ 的大小为 $|S|$。

A 队最多容纳 $5$ 位玩家。设 A 队中的玩家构成集合 $A$，按以下步骤确定 $A$：

• 若 $|S|\le 4$，则 $A=S$。
• 若 $|S|\ge 5$，则：
  • 将 $S$ 中的玩家按成绩从高到低排序，取前 $5$ 名构成集合 $T$。
  • 若 $T$ 中同时包含「阴」和「阳」两种元素，则 $A=T$。
  • 否则，$T$ 中所有玩家均为同一元素 $x$（即全「阴」或全「阳」）。此时：
    • 取 $S$ 中元素为 $x$ 的玩家中成绩最高的前 $4$ 名，记作 $A_x$。
    • 取 $S$ 中元素为另一种元素 $y$（$y\ne x$）的玩家中成绩最高的 $1$ 名（若存在），记作 $a_y$。
    • 若 $a_y$ 存在，则 $A=A_x\cup \{a_y\}$；否则 $A=A_x$。

规则二：B 队选拔

在确定 A 队后，从剩余玩家 $S\setminus A$ 中选拔 B 队。

B 队最多容纳 $12$ 位玩家。设 B 队中的玩家构成集合 $B$，按以下步骤确定 $B$：

• 将 $S\setminus A$ 中的玩家按成绩从高到低排序，得到一个顺序列表。
• 初始化 $B$ 为空，并记录当前省队（$A\cup B$）中每个公会已入选的人数。
• 按顺序遍历列表中的每位玩家：
  • 若当前 B 队人数已达 $12$，则停止选拔。
  • 否则，检查该玩家所属的公会：若该公会在省队中的当前人数严格小于 $5$，则将该玩家加入 B 队，并更新该公会的人数；否则跳过该玩家，继续下一个。
• 当列表遍历完毕或 B 队满 $12$ 位玩家时，选拔结束。

你需要在每一位玩家的分数被揭露以后，给出当前的「渐江省队」名单。

你需要给出当前的「渐江省队」名单中所有玩家的 UID，按以下顺序排列：

• 先列出 A 队的所有玩家的 UID，再列出 B 队的所有玩家的 UID；
• 在同一队内，玩家 UID 按从小到大的顺序排列。

输入格式

输入的第一行，包含一个正整数 $n$（$1\le n\le 100$），表示游戏的玩家人数。

接下来 $n$ 行，第 $i$ 行包含三个整数 $x_i,y_i$ 和 $z_i$（$0\le x_i\le 1,1\le y_i\le n,1\le z_i\le {10}^9$），用一个空格分隔，表示一位玩家的信息。具体地：

• 游戏 UID 为 $i$。
• $x_i=0$ 时，所使用的元素为「阴」；$x_i=1$ 时，所使用的元素为「阳」。
• 所在的游戏公会编号为 $y_i$。
• 游戏成绩为 $z_i$。

保证所有玩家的成绩互不相同。

输出格式

输出共 $n$ 行，第 $i$ 行包含若干个整数，用一个空格分隔，表示前 $i$ 位玩家的成绩被揭露后，「渐江省队」名单中所有玩家的 UID。

每一行先输出 A 队的所有玩家的 UID，再输出 B 队的所有玩家的 UID。同一个队内按照 UID 从小到大的顺序输出。

输入输出样例 #1

输入 #1

20
0 1 87
1 8 300
0 2 12
0 8 260
1 3 145
1 8 240
0 4 60
0 8 230
1 5 170
1 8 220
0 6 50
1 7 215
0 9 80
1 10 200
0 11 40
0 8 20
1 8 150
0 8 210
1 12 190
0 13 70

输出 #1

1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
1 2 4 5 6 3
1 2 4 5 6 3 7
2 4 5 6 8 1 3 7
2 4 6 8 9 1 3 5 7
2 4 6 8 10 1 3 5 7 9
2 4 6 8 10 1 3 5 7 9 11
2 4 6 8 10 1 3 5 7 9 11 12
2 4 6 8 10 1 3 5 7 9 11 12 13
2 4 6 8 10 1 3 5 7 9 11 12 13 14
2 4 6 8 10 1 3 5 7 9 11 12 13 14 15
2 4 6 8 10 1 3 5 7 9 11 12 13 14 15
2 4 6 8 10 1 3 5 7 9 11 12 13 14 15
2 4 6 8 10 1 3 5 7 9 11 12 13 14 15
2 4 6 8 10 1 3 5 7 9 11 12 13 14 15 19
2 4 6 8 10 1 3 5 7 9 11 12 13 14 15 19 20

思路

n ≤ 100，暴力模拟即可。每次加入新玩家后，按规则排序选择。

• 用列表维护当前所有玩家 (成绩, 元素, 公会, UID)
• A 队：按成绩降序取前 5，检查元素多样性规则。
• B 队：移除 A 队成员，按成绩降序遍历，用字典记录每个公会当前入选人数，≤ 4 才入选，直到满 12 人或遍历完毕。

代码

def solve():
    n = int(input())
    players = []
    for i in range(1, n + 1):
        x, y, z = map(int, input().split())
        players.append((i, x, y, z))
    
    revealed = []
    for uid, elem, guild, score in players:
        revealed.append((score, elem, guild, uid))
        revealed.sort(key=lambda t: -t[0])
        
        S = revealed[:]
        if len(S) <= 4:
            A = S[:]
        else:
            top5 = S[:5]
            elems = {e for _, e, _, _ in top5}
            if len(elems) == 2:
                A = top5
            else:
                x_elem = list(elems)[0]
                y_elem = 1 - x_elem
                x_list = [p for p in S if p[1] == x_elem][:4]
                y_list = [p for p in S if p[1] == y_elem]
                A = x_list + ([y_list[0]] if y_list else [])
        A.sort(key=lambda t: t[3])
        
        A_set = set(p[3] for p in A)
        remaining = [p for p in S if p[3] not in A_set]
        B = []
        guild_cnt = {}
        for p in remaining:
            if len(B) == 12:
                break
            g = p[2]
            cur = guild_cnt.get(g, 0) + sum(1 for ap in A if ap[2] == g)
            if cur < 5:
                B.append(p)
                guild_cnt[g] = guild_cnt.get(g, 0) + 1
        B.sort(key=lambda t: t[3])
        
        out = [str(p[3]) for p in A] + [str(p[3]) for p in B]
        print(" ".join(out))

if __name__ == "__main__":
    solve()

G. P16442 机房分配

https://www.luogu.com.cn/problem/P16441?contestId=314922

你常常追忆过去。生命瞬间定格在脑海。你将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。

时间被裁剪、折叠、蜷曲。咦，你好像不在联合省选 2025 的赛场上。你该在哪里停留？你问你自己。

时光荏苒，小 Z 和小 J 也会散去。而你们和一个人保持连接的方式就是记住，仅此而已。

时光走过，小 Z 和小 J 会再遇见。回首往事，大家都过上了各自想要的生活。

好像有什么不对。咦，你好像也不在 NOI2024 的赛场上。你该在哪里停留？你问你自己。

NOI2233 即将举行。为了增加观赏性，FFC 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。

你终于想到了。你今年刚上初一，你正在 CSP-J 2020 的赛场上，比赛的第二题叫“直播获奖”。由于你不会桶排序，你在这题中取得了 95 分的高分。

咦，你怎么预知了你在“直播获奖”这一题上的得分呢？这真的可能吗？这可能被完成吗？

一年一度的 XJTUPC 又要举办了，但是老牌杂鱼猫娘出题人小标准突然有急事要回趟渐江。

原来你已经退役了。你正坐在 XJTUPC2026 的赛场上做一道叫做“直播获奖”的题目。你该在哪里停留？你问你自己。

题目描述

你正在玩一款被称为「ZJOI2022」的游戏。游戏发生在一个被称作「渐江」的幻想世界。你将扮演一位名为「咋克」的神秘角色，在自由的旅行中邂逅性格各异、能力独特的同伴们，和他们一起击败强敌，找回失散的亲人------同时，逐步发掘「九条可怜」的真相。

每位玩家在结束游戏后，拥有四个属性：

• 游戏 UID。游戏 UID 是每一位玩家的唯一标识符，为一个正整数。所有玩家的 UID 各不相同。
• 游玩游戏所使用的元素。元素为「阴」或者「阳」。
• 所在的游戏公会。每一位玩家属于一个公会，公会由正整数编号标识。
• 游戏成绩。游戏成绩为一个正整数。保证所有玩家的成绩互不相同。

这个游戏使用非常特别的结算方式。具体来说，「评测机」将会按 UID 从小到大的顺序揭露每一位玩家的总分。每位玩家的分数被揭露以后，预示着胜利者的「渐江省队」名单会随之更新。「渐江省队」由 A 队和 B 队组成，两队的成员互不重叠。

根据当前所有已揭露的玩家，按照下述规则更新「渐江省队」名单：

规则一：A 队选拔

设当前已揭露的玩家集合为 $S$。记集合 $S$ 的大小为 $|S|$。

A 队最多容纳 $5$ 位玩家。设 A 队中的玩家构成集合 $A$，按以下步骤确定 $A$：

• 若 $|S|\le 4$，则 $A=S$。
• 若 $|S|\ge 5$，则：
  • 将 $S$ 中的玩家按成绩从高到低排序，取前 $5$ 名构成集合 $T$。
  • 若 $T$ 中同时包含「阴」和「阳」两种元素，则 $A=T$。
  • 否则，$T$ 中所有玩家均为同一元素 $x$（即全「阴」或全「阳」）。此时：
    • 取 $S$ 中元素为 $x$ 的玩家中成绩最高的前 $4$ 名，记作 $A_x$。
    • 取 $S$ 中元素为另一种元素 $y$（$y\ne x$）的玩家中成绩最高的 $1$ 名（若存在），记作 $a_y$。
    • 若 $a_y$ 存在，则 $A=A_x\cup \{a_y\}$；否则 $A=A_x$。

规则二：B 队选拔

在确定 A 队后，从剩余玩家 $S\setminus A$ 中选拔 B 队。

B 队最多容纳 $12$ 位玩家。设 B 队中的玩家构成集合 $B$，按以下步骤确定 $B$：

• 将 $S\setminus A$ 中的玩家按成绩从高到低排序，得到一个顺序列表。
• 初始化 $B$ 为空，并记录当前省队（$A\cup B$）中每个公会已入选的人数。
• 按顺序遍历列表中的每位玩家：
  • 若当前 B 队人数已达 $12$，则停止选拔。
  • 否则，检查该玩家所属的公会：若该公会在省队中的当前人数严格小于 $5$，则将该玩家加入 B 队，并更新该公会的人数；否则跳过该玩家，继续下一个。
• 当列表遍历完毕或 B 队满 $12$ 位玩家时，选拔结束。

你需要在每一位玩家的分数被揭露以后，给出当前的「渐江省队」名单。

你需要给出当前的「渐江省队」名单中所有玩家的 UID，按以下顺序排列：

• 先列出 A 队的所有玩家的 UID，再列出 B 队的所有玩家的 UID；
• 在同一队内，玩家 UID 按从小到大的顺序排列。

输入格式

输入的第一行，包含一个正整数 $n$（$1\le n\le 100$），表示游戏的玩家人数。

接下来 $n$ 行，第 $i$ 行包含三个整数 $x_i,y_i$ 和 $z_i$（$0\le x_i\le 1,1\le y_i\le n,1\le z_i\le {10}^9$），用一个空格分隔，表示一位玩家的信息。具体地：

• 游戏 UID 为 $i$。
• $x_i=0$ 时，所使用的元素为「阴」；$x_i=1$ 时，所使用的元素为「阳」。
• 所在的游戏公会编号为 $y_i$。
• 游戏成绩为 $z_i$。

保证所有玩家的成绩互不相同。

输出格式

输出共 $n$ 行，第 $i$ 行包含若干个整数，用一个空格分隔，表示前 $i$ 位玩家的成绩被揭露后，「渐江省队」名单中所有玩家的 UID。

每一行先输出 A 队的所有玩家的 UID，再输出 B 队的所有玩家的 UID。同一个队内按照 UID 从小到大的顺序输出。

输入输出样例 #1

输入 #1

20
0 1 87
1 8 300
0 2 12
0 8 260
1 3 145
1 8 240
0 4 60
0 8 230
1 5 170
1 8 220
0 6 50
1 7 215
0 9 80
1 10 200
0 11 40
0 8 20
1 8 150
0 8 210
1 12 190
0 13 70

输出 #1

1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
1 2 4 5 6 3
1 2 4 5 6 3 7
2 4 5 6 8 1 3 7
2 4 6 8 9 1 3 5 7
2 4 6 8 10 1 3 5 7 9
2 4 6 8 10 1 3 5 7 9 11
2 4 6 8 10 1 3 5 7 9 11 12
2 4 6 8 10 1 3 5 7 9 11 12 13
2 4 6 8 10 1 3 5 7 9 11 12 13 14
2 4 6 8 10 1 3 5 7 9 11 12 13 14 15
2 4 6 8 10 1 3 5 7 9 11 12 13 14 15
2 4 6 8 10 1 3 5 7 9 11 12 13 14 15
2 4 6 8 10 1 3 5 7 9 11 12 13 14 15
2 4 6 8 10 1 3 5 7 9 11 12 13 14 15 19
2 4 6 8 10 1 3 5 7 9 11 12 13 14 15 19 20

H. P16443 矩阵拆分

https://www.luogu.com.cn/problem/P16443?contestId=314922

给定一个 $n\times n$ 的非负整数矩阵 $B$。你需要构造一个 $n\times n$ 的非负整数矩阵 $A$，满足：

• $A+A^{\mathsf{T}}=B$。其中 $A^{\mathsf{T}}$ 表示 $A$ 的转置，即将其行和列互换得到的新矩阵（原来 $A$ 中第 $i$ 行第 $j$ 列的元素，在 $A^{\mathsf{T}}$ 中位于第 $j$ 行第 $i$ 列）。
• 对于任意 $i=1,2,\cdots ,n$，都有

$$\lfloor \frac{1}{2}\sum _{j=1}^n{B}_{ij}\rfloor \le \sum _{j=1}^n{A}_{ij}\le \lceil \frac{1}{2}\sum _{j=1}^n{B}_{ij}\rceil$$

• 对于任意 $j=1,2,\cdots ,n$，都有

$$\lfloor \frac{1}{2}\sum _{i=1}^n{B}_{ij}\rfloor \le \sum _{i=1}^n{A}_{ij}\le \lceil \frac{1}{2}\sum _{i=1}^n{B}_{ij}\rceil$$

或报告无解。

其中，$A_{ij}$ 为矩阵 $A$ 第 $i$ 行第 $j$ 列的元素，$B_{ij}$ 为矩阵 $B$ 第 $i$ 行第 $j$ 列的元素。

如果存在多个解，输出任意一个即可。

输入格式

本题包含多组测试用例。输入的第一行，包含一个正整数 $T$（$1\le T\le 1000$），表示测试用例的数量。

接下来是 $T$ 组测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1\le n\le 2200$），表示矩阵的大小。

接下来 $n$ 行，每行 $n$ 个整数，用一个空格分隔，描述矩阵 $B$，其中第 $i$ 行第 $j$ 个整数表示 $B_{ij}$（$0\le B_{ij}\le {10}^9$）。

保证所有测试用例中 $n^2$ 的总和不超过 $5\times {10}^6$。

输出格式

对于每个测试用例，若无解，输出一行，仅包含一个字符串 $\mathtt{N}\mathtt{o}$。

否则，输出 $n+1$ 行，其中：

• 第一行包含一个字符串 $\mathtt{Y}\mathtt{e}\mathtt{s}$；
• 接下来 $n$ 行，每行包含 $n$ 个整数，用一个空格分隔，描述你构造的矩阵 $A$，其中第 $i$ 行第 $j$ 个整数表示 $A_{ij}$（$0\le A_{ij}\le {10}^9$）。

如果存在多个解，输出任意一个即可。

答案对大小写不敏感。例如 $\mathtt{y}\mathtt{E}\mathtt{s}$，$\mathtt{Y}\mathtt{e}\mathtt{s}$，$\mathtt{y}\mathtt{e}\mathtt{s}$ 和 $\mathtt{Y}\mathtt{E}\mathtt{S}$ 都会被视为 $\mathtt{Y}\mathtt{e}\mathtt{s}$。

输入输出样例 #1

输入 #1

3
4
2 1 0 0
1 2 0 0
0 0 2 3
0 0 3 2
4
0 2 1 2
2 0 3 3
1 3 0 2
2 3 2 0
3
1 2 3
4 5 6
7 8 9

输出 #1

Yes
1 1 0 0
0 1 0 0
0 0 1 2
0 0 1 1
Yes
0 1 1 1
1 0 1 2
0 2 0 1
1 1 1 0
No

I. P16444 Used to be✅

https://www.luogu.com.cn/problem/P16444?contestId=314922

"Who am I...?"

这是一个关于记忆的故事。故事的主角之一，是一个长为 $m$ 的 01 串。

故事的第一层，是变化。

故事穿行于 $n-1$ 个节点间。每经过一个节点，主角都会受到微妙的影响：它可能保持不变，抑或在某一位上发生翻转。这些变化不断累积，最终的串也许和最初判若两人。

故事的第二层，是遗忘。

曾经，剧本上记录着主角最初的状态，以及经过每个节点后的状态。然而，随着岁月的流逝，书页上一些位置的字迹渐渐模糊，化作无法辨认的 ?。

故事的第三层，是追寻。

另一群主角------你们，找到了这份尘封的记录。尽管你们可能无法确定唯一的真相，你们仍然希望拼凑出一份可能的原貌，复现你们心中的故事。

"Make her story complete."

"I know... you will not disappoint me."

形式化题意

给定 $n$ 个长度恰为 $m$ 的字符串 $S_1,S_2,\cdots ,S_n$。字符串 $S_i$ 仅包含字符 $\mathtt{\text{0}}$，$\mathtt{\text{1}}$ 和 $\mathtt{\text{?}}$。

判断是否存在一种将每一个 $\mathtt{\text{?}}$ 分别替换为 $\mathtt{\text{0}}$ 或 $\mathtt{\text{1}}$ 的方案，使得相邻两个字符串不同的位置至多有一位。即在替换后，对于任意的 $i$（$1\le i\le n-1$），第 $i$ 个字符串 $S_i=a_1{a}_2\cdots a_m$ 和第 $i+1$ 个字符串 $S_{i+1}=b_1{b}_2\cdots b_m$ 满足下面条件的任意一个：

• 对于任意的 $j$（$1\le j\le m$），有 $a_j=b_j$；
• 存在一个 $x$（$1\le x\le m$），使得 $a_x\ne b_x$ 且对于任意的 $j$（$1\le j\le m$ 且 $x\ne j$），有 $a_j=b_j$。

若存在，请输出一种满足要求的方案。如果存在多种方案，输出任意一种即可。

输入格式

本题包含多组测试用例。输入的第一行，包含一个正整数 $T$（$1\le T\le {10}^5$），表示测试用例的数量。

接下来是 $T$ 组测试用例的描述。

每个测试用例的第一行，包含两个正整数 $n$ 和 $m$（$1\le n\cdot m\le {10}^6$），用一个空格分隔，分别表示字符串的数量与字符串的长度。

接下来 $n$ 行，第 $i$ 行包含一个长度恰为 $m$ 的字符串 $S_i$。保证字符串 $S_i$ 仅包含字符 $\mathtt{\text{0}}$，$\mathtt{\text{1}}$ 和 $\mathtt{\text{?}}$。

保证所有测试用例中 $n\cdot m$ 的总和不超过 ${10}^6$。

输出格式

对于每个测试用例，如果不存在满足要求的方案，输出一行，仅包含一个字符串 $\mathtt{N}\mathtt{o}$。

否则，输出 $n+1$ 行，其中：

• 第一行包含一个字符串 $\mathtt{Y}\mathtt{e}\mathtt{s}$；
• 接下来 $n$ 行，第 $i$ 行包含一个长度恰为 $m$ 的字符串，字符串中仅包含字符 $\mathtt{\text{0}}$ 和 $\mathtt{\text{1}}$，表示构造的方案中第 $i$ 个字符串。

如果存在多种满足要求的方案，输出任意一种即可。

答案对大小写不敏感。例如 $\mathtt{y}\mathtt{E}\mathtt{s}$，$\mathtt{Y}\mathtt{e}\mathtt{s}$，$\mathtt{y}\mathtt{e}\mathtt{s}$ 和 $\mathtt{Y}\mathtt{E}\mathtt{S}$ 都会被视为 $\mathtt{Y}\mathtt{e}\mathtt{s}$。

输入输出样例 #1

输入 #1

3
2 3
000
010
3 3
010
1?1
010
3 4
00?1
01?1
1?01

输出 #1

Yes
000
010
No
Yes
0001
0101
1101

这道题可以抽象为一个关于超立方体上的路径构造与区间匹配的问题。

题目分析与建模

我们可以独立地看每一个位置（字符通道） $j\in \{1,2,\dots ,m\}$：

1. 每个位置 $j$ 都有一些确定（即非 ?）的限制字符 $S_i[j]$。
2. 邻近两个字符串最多只能有一位不同，这意味着在每一步 $i\in \{2,\dots ,n\}$ 中，至多只能有一个位置的值发生翻转（即 0 变 1 或 1 变 0）。
3. 如果我们在某个位置 $j$ 上，从一个确定字符（例如第 $i_1$ 步的 0）过渡到另一个确定字符（例如第 $i_2$ 步的 1，其中中间所有位置均为 ?），那么在区间 $[i_1+1,i_2]$ 之间，我们必须且只需进行奇数次翻转。 为了最大化保留其他位置翻转的机会（因为每一步至多只能有一个位置翻转，翻转次数是稀缺资源），我们应该恰好翻转 1 次。
4. 如果相邻两个确定字符相同（例如 0 变 0），最省资源的方法是翻转 0 次。

因此，对于每个位置 $j$，我们可以找出所有相邻且不同的确定字符对。设它们的下标分别为 $i_1$ 和 $i_2$（且 $S_{i_1}[j]\ne S_{i_2}[j]$），这意味着我们必须在步骤区间 $[i_1+1,i_2]$ 内为位置 $j$ 安排一次翻转。

于是，原问题转化为一个经典的区间贪心匹配问题：

• 每一个位置的每次“异值相邻确定字符对”对应一个可选的翻转区间 $[L,R]$。
• 我们需要为每个区间 $[L,R]$ 匹配一个独一无二的整数点 $p\in [L,R]$，代表在第 $p$ 步翻转这个位置。
• 如果能找到这样一个匹配方案，则说明存在解，并可以由此直接重构出每个字符串；否则无解。

贪心匹配算法

我们可以使用经典的贪心算法来解决这个区间匹配问题（按位置从左到右扫描，优先匹配右端点最早结束的区间）：

1. 遍历 $p=1\dots n-1$：
   • 将所有左端点 $L=p$ 的区间加入小根堆（以右端点 $R$ 为关键字排序）。
   • 如果堆不为空：
     • 取出堆顶（即当前可用区间中 $R$ 最小的区间）。
     • 如果其右端点 $R<p$，说明该区间已经过期，无法被匹配，直接判定为无解。
     • 否则，将该步 $p$ 分配给对应的位置 $j$ 进行翻转，即 flip[p] = j。
2. 遍历结束后，如果堆中仍有未匹配的区间，说明无解。
3. 否则，根据记录的每一步翻转信息 flip 依次递推重构出最终的 $n$ 个字符串即可。

Python 3 实现

import sys
import heapq

def solve():
    # 读入所有数据
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    iterator = iter(input_data)
    try:
        num_test_cases = int(next(iterator))
    except StopIteration:
        return
    
    out = []
    
    for _ in range(num_test_cases):
        try:
            n = int(next(iterator))
            m = int(next(iterator))
        except StopIteration:
            break
        
        S = [next(iterator) for _ in range(n)]
        
        # intervals_at[L] 存储左端点为 L 的所有区间，每个区间用 (R, 对应的位置 j) 表示
        intervals_at = [[] for _ in range(n)]
        first_val = ['0'] * m  # 记录每个位置的初始值（如果全为 '?' 则默认为 '0'）
        
        for j in range(m):
            last_pos = -1
            last_val = -1
            has_fixed = False
            for i in range(n):
                char = S[i][j]
                if char != '?':
                    if not has_fixed:
                        first_val[j] = char
                        has_fixed = True
                    else:
                        if char != last_val:
                            # 对应 0-based 索引，翻转区间为 [last_pos + 1, i]
                            intervals_at[last_pos + 1].append((i, j))
                    last_pos = i
                    last_val = char
        
        # flip[p] 记录第 p 步要翻转的位置，-1 表示不翻转
        flip = [-1] * n
        heap = []
        possible = True
        
        # 贪心匹配
        for p in range(1, n):
            for R, j in intervals_at[p]:
                heapq.heappush(heap, (R, j))
            if heap:
                R, j = heapq.heappop(heap)
                if R < p:
                    possible = False
                    break
                flip[p] = j
        
        if heap:
            possible = False
            
        if not possible:
            out.append("No")
        else:
            out.append("Yes")
            # 递推重构并保存结果
            curr_state = list(first_val)
            out.append("".join(curr_state))
            for i in range(1, n):
                j = flip[i]
                if j != -1:
                    curr_state[j] = '1' if curr_state[j] == '0' else '0'
                out.append("".join(curr_state))
                
    sys.stdout.write('\n'.join(out) + '\n')

if __name__ == '__main__':
    solve()

J. P16445 The Whole Rest✅

https://www.luogu.com.cn/problem/P16445?contestId=314922

这，就是我们的故事。

给定一棵包含 $n$ 个顶点的树，顶点编号为 $1,2,\dots ,n$。每条边 $(u,v)$ 有一个非负整数权值 $w(u,v)$。

定义树上的一条途径为一个顶点序列 $v_1,v_2,\dots ,v_k$（$k\ge 1$），满足对于任意的 $i$（$1\le i\le k-1$），都有一条边 $(v_i,v_{i+1})$。请注意，途径中的顶点可以重复，即如果存在 $1\le i<j\le k$ 满足 $v_i=v_j$，仍然认为这是一条途径。

途径的边数定义为 $k-1$，即途径经过的边的数量。

途径经过的顶点集定义为 $\{v_1,v_2,\dots ,v_k\}$，即途径中所有出现过的顶点（重复只计一次）。

途径的代价定义为沿途经过的边的权值的异或和：$w(v_1,v_2)\oplus w(v_2,v_3)\oplus w(v_3,v_4)\oplus \cdots \oplus w(v_{k-1},v_k)$，其中 $\oplus$ 表示按位异或。特别地，当 $k=1$ 时（即途径只包含一个顶点），途径的代价为 $0$。

要求选择一条途径，满足如下条件：

• 它经过树中所有的顶点，即途径经过的顶点集等于全部 $n$ 个顶点；
• 在所有满足条件 1 的途径中，途径的代价最小；
• 如果有多条途径同时满足条件 1 和 2，则选择途径的边数最少的；
• 如果有多条途径同时满足条件 1、2 和 3，则选择任意一条，都会被视为正确。

输出一条满足上述条件的途径，以顶点序列的形式给出。

输入格式

输入的第一行，包含一个整数 $n$（$1\le n\le 5\times {10}^5$），表示给定的树有 $n$ 个顶点。

接下来 $n-1$ 行，每行包含三个整数 $u,v$ 和 $w$（$1\le u,v\le n,0\le w<2^{30}$），表示树上存在一条边 $(u,v)$，边权为 $w$。保证给出的边构成一棵树。

输出格式

输出两行。第一行包含一个整数 $k$（$1\le k\le 4\times {10}^6$），表示途径的顶点序列的长度。

第二行包含 $k$ 个整数 $v_1,v_2,\dots ,v_k$，用一个空格分隔，表示一条满足条件的途径，其顶点序列为 $v_1,v_2,\dots ,v_k$。

可以证明，在题目的约束下：

• 所有顶点的编号都需要至少出现一次；
• 对于任意一条满足题目条件 1、2 和 3 的途径，其顶点序列的长度均不超过 $4\times {10}^6$。

输入输出样例 #1

输入 #1

4
1 2 0
1 3 2
3 4 2

输出 #1

4
4 3 1 2

输入输出样例 #2

输入 #2

6
1 2 1
3 6 5
3 1 2
2 5 3
4 2 4

输出 #2

8
3 6 3 1 2 4 2 5

Pypy3 AC

这是一道经典的树上问题。下面我们来详细分析并解决它。

题目分析

1. 途径的性质

在树上，任何遍历所有节点的途径都必须经过每条边至少一次。如果我们指定途径的起点为 $S$，终点为 $T$：

• 唯一连接 $S$ 到 $T$ 的简单路径上的边，在途径中必须被经过奇数次（最少为 1 次）。
• 不在 $S\to T$ 简单路径上的边，因为需要进去访问其子树并返回，必须被经过偶数次（最少为 2 次）。

由于我们要使途径的边数（即长度）最小，我们会让所有不属于 $S\to T$ 路径上的边正好经过 2 次，而属于 $S\to T$ 路径上的边正好经过 1 次。

2. 代价与长度的计算

途径的代价定义为所有经过边的边权异或和。

• 经过 2 次的边，其边权在异或和中贡献两次：$w\oplus w=0$。
• 经过 1 次的边，贡献一次：$w$。

因此，整个途径的异或和，正好等于 $S$ 到 $T$ 的简单路径上的边权异或和。

设 $d(u)$ 表示从根节点（假设为 1）到 $u$ 的简单路径上所有边的异或和，则 $S$ 到 $T$ 路径的异或和为：

$$\text{XOR}(S,T)=d(S)\oplus d(T)$$

我们希望最小化这个异或和。显然，异或和的最小可能值为 $0$。

• 我们可以始终选择 $S=T$，此时 $\text{XOR}(S,S)=d(S)\oplus d(S)=0$。这说明最小异或和必然为 0。
• 为了使异或和为 $0$，我们必须满足 $d(S)=d(T)$。

在保证异或和为 0 的前提下，我们希望最小化途径的边数。 如果 $S\to T$ 路径包含 $L$ 条边，那么总边数为：

$$\text{Total Edges}=L\times 1+(n-1-L)\times 2=2n-2-L$$

要使总边数最小，我们应该最大化路径长度 $L$。

3. 算法步骤

1. 求出所有节点的 $d(u)$：通过一次 BFS/DFS，求出每个节点到根节点的异或和 $d(u)$ 以及深度 $depth(u)$。
2. 分组：将所有 $d(u)$ 相同的节点归为一组。
3. 寻找最大距离：在每一组节点中，我们需要找到距离最远的两个点（即这一组节点在树上的直径）。
   • 对于一个节点集合 $G$，我们可以使用两遍搜索法寻找其最远点对：
     1. 任选 $x\in G$，找到 $G$ 中距离 $x$ 最远的点 $y$。
     2. 找到 $G$ 中距离 $y$ 最远的点 $z$。
     3. 那么 $(y,z)$ 就是集合 $G$ 中距离最远的点对。
   • 树上两点 $u,v$ 的距离公式为：$dist(u,v)=depth(u)+depth(v)-2\cdot depth(\text{LCA}(u,v))$。我们可以使用倍增法在 $O(\log n)$ 内求出 $\text{LCA}$。
4. 构造方案：选出全局最大距离对应的起点 $S$ 和终点 $T$ 后，找出 $S\to T$ 的路径 $P$。
   • 对于路径 $P$ 上的每个节点 $u$，我们先遍历其不在路径 $P$ 上的子树（进行标准的欧拉环游，即进出均记录），然后再走向路径上的下一个节点。

---

Python 实现

from collections import defaultdict, deque
import sys

# 设置递归深度和优化输入输出
sys.setrecursionlimit(2000000)


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    n = int(input_data[0])

    adj = [[] for _ in range(n + 1)]
    idx = 1
    for _ in range(n - 1):
        u = int(input_data[idx])
        v = int(input_data[idx + 1])
        w = int(input_data[idx + 2])
        idx += 3
        adj[u].append((v, w))
        adj[v].append((u, w))

    # 1. BFS 计算深度、父节点和路径异或值 d
    depth = [0] * (n + 1)
    parent = [0] * (n + 1)
    d = [0] * (n + 1)

    queue = [1]
    depth[1] = 1
    parent[1] = 0
    d[1] = 0

    head = 0
    while head < len(queue):
        u = queue[head]
        head += 1
        for v, w in adj[u]:
            if v != parent[u]:
                parent[v] = u
                depth[v] = depth[u] + 1
                d[v] = d[u] ^ w
                queue.append(v)

    # 2. 预处理 LCA 倍增表
    LOGN = 20
    up = [[0] * (n + 1) for _ in range(LOGN)]
    up[0] = parent
    for i in range(1, LOGN):
        up_i = up[i]
        up_prev = up[i - 1]
        up_i[:] = [up_prev[up_prev[u]] for u in range(n + 1)]

    # 快速求 LCA
    def get_lca(u, v):
        if depth[u] < depth[v]:
            u, v = v, u
        diff = depth[u] - depth[v]
        for i in range(20):
            if (diff >> i) & 1:
                u = up[i][u]
        if u == v:
            return u
        for i in range(19, -1, -1):
            up_i = up[i]
            if up_i[u] != up_i[v]:
                u = up_i[u]
                v = up_i[v]
        return parent[u]

    def get_dist(u, v):
        return depth[u] + depth[v] - 2 * depth[get_lca(u, v)]

    # 3. 按 d[u] 分组
    groups = defaultdict(list)
    for u in range(1, n + 1):
        groups[d[u]].append(u)

    max_dist = -1
    best_S, best_T = 1, 1

    # 4. 在每组内寻找直径
    for G in groups.values():
        if len(G) < 2:
            if max_dist < 0:
                max_dist = 0
                best_S, best_T = G[0], G[0]
            continue

        # 第一遍：从 G[0] 出发找最远点 y
        x = G[0]
        max_d_y = -1
        y = x
        for w in G:
            dw = get_dist(x, w)
            if dw > max_d_y:
                max_d_y = dw
                y = w

        # 第二遍：从 y 出发找最远点 z
        max_d_z = -1
        z = y
        for w in G:
            dw = get_dist(y, w)
            if dw > max_d_z:
                max_d_z = dw
                z = w

        if max_d_z > max_dist:
            max_dist = max_d_z
            best_S, best_T = y, z

    # 5. 提取 S 到 T 的路径 P
    L = get_lca(best_S, best_T)
    path1 = []
    curr = best_S
    while curr != L:
        path1.append(curr)
        curr = parent[curr]

    path2 = []
    curr = best_T
    while curr != L:
        path2.append(curr)
        curr = parent[curr]
    path2.append(L)

    P = path1 + path2[::-1]

    # 标记路径上的点
    on_path = [False] * (n + 1)
    for node in P:
        on_path[node] = True

    # 6. 构造欧拉环游途径 (使用非递归迭代防止栈溢出)
    ans = []

    def euler_tour_iterative(start, p_start):
        stack = [[start, p_start, 0]]
        ans.append(start)
        while stack:
            u, p, idx = stack[-1]
            neighbors = adj[u]
            while idx < len(neighbors):
                v, _ = neighbors[idx]
                idx += 1
                stack[-1][2] = idx
                if v != p and not on_path[v]:
                    ans.append(v)
                    stack.append([v, u, 0])
                    break
            else:
                stack.pop()
                if stack:
                    ans.append(stack[-1][0])

    # 依次沿着路径行走并访问旁侧分支
    ans.append(P[0])
    for i in range(len(P)):
        u = P[i]
        for v, _ in adj[u]:
            if not on_path[v]:
                euler_tour_iterative(v, u)
                ans.append(u)
        if i < len(P) - 1:
            ans.append(P[i + 1])

    # 输出结果
    sys.stdout.write(f"{len(ans)}\n")
    sys.stdout.write(" ".join(map(str, ans)) + "\n")


if __name__ == "__main__":
    solve()

K. P16446 修罗指数

https://www.luogu.com.cn/problem/P16446?contestId=314922

你正在一款「多角色恋爱养成游戏」中，同时尝试攻略 $N$ 位角色。对第 $i$ 位角色来说，有两个关键数值：

• $a_i$：她对你的容忍度；
• $b_i$：她对你的期待值。

初始时，所有角色的状态给定且相同：$a_i=A,b_i=B$（$1\le i\le N$）。

接下来你会进行 $Q$ 次行动，行动为如下三种之一：

• $1rx$，你在前 $r$ 位角色那里「集体翻车」，导致她们的容忍度下降。

  即对于所有的 $i$（$1\le i\le r$），$a_i\leftarrow min\{a_i,x\}$。

• $2lx$，你给第 $l$ 位到第 $N$ 位角色送礼物，导致她们的期待值提高。

  即对于所有的 $i$（$l\le i\le N$），$b_i\leftarrow max\{b_i,x\}$。

• $3lr$，查询第 $l$ 位到第 $r$ 位角色的「修罗指数」。

  「修罗指数」定义为 $\sum _{i=l}^r|a_i-b_i|$。

输入格式

输入的第一行，包含三个整数 $N,A$ 和 $B$（$1\le N\le 5\times {10}^5,-{10}^9\le A,B\le {10}^9$），用一个空格分隔，分别表示角色个数、容忍度初始值和期待值初始值。

第二行包含一个整数 $Q$（$1\le Q\le 5\times {10}^5$），表示行动次数。

接下来 $Q$ 行，每行三个整数，用一个空格分隔。这三个整数为如下三种情况中的一种，表示一次行动：

• $1rx$（$1\le r\le N,-{10}^9\le x\le {10}^9$），表示对于所有的 $i$（$1\le i\le r$），$a_i\leftarrow min\{a_i,x\}$。
• $2lx$（$1\le l\le N,-{10}^9\le x\le {10}^9$），表示对于所有的 $i$（$l\le i\le N$），$b_i\leftarrow max\{b_i,x\}$。
• $3lr$（$1\le l\le r\le N$），表示查询第 $l$ 位到第 $r$ 位角色的「修罗指数」$\sum _{i=l}^r|a_i-b_i|$。

输出格式

对于每个查询「修罗指数」的行动，输出一行，包含一个整数，表示「修罗指数」的值。

输入输出样例 #1

输入 #1

11 38 11
21
3 4 7
2 3 23
3 2 6
2 9 29
3 3 4
1 11 13
3 2 7
1 1 38
3 1 8
1 9 11
3 2 8
1 11 33
3 1 10
2 9 25
3 2 10
1 10 31
3 1 3
1 3 39
3 3 8
2 7 21
3 5 9

输出 #1

108
87
30
52
64
72
106
106
12
72
66

L. P16447 ADOIAF✅

https://www.luogu.com.cn/problem/P16447?contestId=314922

ShwStone 正在游玩一款叫做 A Dance Of Ice And Fire（ADOIAF）的游戏。这是一款单按键音游。ShwStone 需要在正确的时间按下按键。但是，ShwStone 太菜了，总是因为按键时机不对而损失分数。ShwStone 想知道，如果所有按键的判定按照自己的想法进行匹配，他最高能得多少分。

形式化地说，ADOIAF 有 $n$ 个判定点 $t_{a_1},t_{a_2},\cdots ,t_{a_n}$。ShwStone 一共按下了 $m$ 次按键，按下按键的时刻序列为 $t_{b_1},t_{b_2},\cdots ,t_{b_m}$。ADOIAF 有一个内置判定参数 $k$。如果选择将第 $j$ 个按键和第 $i$ 个判定点进行匹配，则得到的分数是 $max(k^2-(t_{a_i}-t_{b_j}{)}^2,0)$。

注意在最终方案中，一个按键至多满足一个判定点，一个判定点至多被满足一次。被匹配的按键和判定点没有先后顺序要求。

你需要输出最大分数。

输入格式

本题包含多组测试用例。输入的第一行，包含一个正整数 $T$（$1\le T\le {10}^4$），表示测试用例的数量。

接下来是 $T$ 组测试用例的描述。

每个测试用例的第一行，包含三个正整数 $n,m$ 和 $k$（$1\le n,m\le {10}^5$，$1\le k\le 50$），用一个空格分隔，分别表示判定点的数量、按键次数和判定参数。

接下来一行，包含 $n$ 个正整数 $t_{a_1},t_{a_2},\cdots ,t_{a_n}$（$1\le t_{a_i}\le {10}^6$），用一个空格分隔，表示判定点的时间序列。保证 $t_{a_i}$ 之间互不相同。不保证 $t_{a_i}$ 输入有序。

接下来一行，包含 $m$ 个正整数 $t_{b_1},t_{b_2},\cdots ,t_{b_m}$（$1\le t_{b_j}\le {10}^6$），用一个空格分隔，表示按键的时间序列。保证 $t_{b_j}$ 之间互不相同。不保证 $t_{b_j}$ 输入有序。

保证所有测试用例中 $n$ 的总和不超过 ${10}^5$，$m$ 的总和不超过 ${10}^5$。

输出格式

对于每个测试用例，输出一行，包含一个非负整数，表示在最优配对下，ShwStone 能得到的最大分数。

输入输出样例 #1

输入 #1

2
7 7 3
5 4 14 8 1 17 6
6 13 3 12 15 14 10
8 8 4
9 6 14 11 12 5 2 13
14 7 15 5 20 12 11 9

输出 #1

36
109

pypy3 AC

这是一个利用双指针和动态规划（DP）解决最大权匹配问题的思路。

解题思路

1. 排序与不交叉性质： 我们将判定点序列 $A$ 和按键时间序列 $B$ 分别升序排序。 对于一维轴上的点进行匹配，如果存在最优匹配，那么最优匹配中的配对线段一定是不交叉的。即：若 $a_i$ 匹配 $b_j$，且 $a_{i'} $ 匹配 $b_{j^{\prime }}$（其中 $i<i^{\prime }$），那么必定有 $j<j^{\prime }$。这一性质使得我们可以使用动态规划。

2. 状态定义与滑动窗口： 设 $dp[i][j]$ 表示使用 $A$ 的前 $i$ 个元素和 $B$ 的前 $j$ 个元素能够获得的最大分数。 由于只有 $|A[i]-B[j]|<k$ 的配对才能获得正分数，因此对于固定的 $i$，$j$ 的有效范围只有 $[L_i,R_i]$（即满足 $A[i]-k<B[j]<A[i]+k$ 的区间）。 因为 $k\le 50$，该区间长度最大只有 $2k\le 100$。我们可以只显式维护和更新这一小段区间的 DP 值。

3. 双指针优化： 由于 $A$ 和 $B$ 均是有序的，随着 $i$ 的增加，区间 $[L_i,R_i]$ 也是单调向右移动的。我们可以使用双指针以 $O(N+M)$ 的总时间复杂度求出所有 $i$ 对应的区间 $[L_i,R_i]$。

4. 滚动数组与 DP 转移： 传统的转移方程为：

   $$dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+\text{score}(i,j))$$

   在实现中，我们可以用一个大小为 $M$ 的一维数组 dp 记录上一行的状态。每次转移到 $i$ 时，仅更新区间 $[L_i,R_i]$。对于区间之外的值，其更新逻辑可以利用前一轮的边界值进行常数复杂度的快速推导。

以下是高效的 Python 3 代码：

import sys

def solve():
    # 快速读入所有数据
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    T = int(input_data[0])
    idx = 1
    out = []
    
    for _ in range(T):
        n = int(input_data[idx])
        m = int(input_data[idx+1])
        k = int(input_data[idx+2])
        idx += 3
        
        A = [int(x) for x in input_data[idx : idx + n]]
        idx += n
        B = [int(x) for x in input_data[idx : idx + m]]
        idx += m
        
        # 排序
        A.sort()
        B.sort()
        
        dp = [0] * m
        R_prev = -1
        k2 = k * k
        
        # 双指针初始化
        L = 0
        R = 0
        
        for i in range(n):
            val_a = A[i]
            left_val = val_a - k + 1
            right_val = val_a + k - 1
            
            # 双指针维护匹配区间
            while L < m and B[L] < left_val:
                L += 1
            while R < m and B[R] <= right_val:
                R += 1
            actual_R = R - 1
            
            # 若当前 A[i] 无法匹配任何 B 中的元素，直接跳过
            if L > actual_R:
                continue
            
            # 维护边界 dp[L-1]
            if L > 0:
                if L - 1 > R_prev:
                    dp[L - 1] = dp[R_prev] if R_prev >= 0 else 0
                val_L_minus_1 = dp[L - 1]
            else:
                val_L_minus_1 = 0
            
            len_part = actual_R - L + 1
            new_dp = [0] * len_part
            dp_R_prev = dp[R_prev] if R_prev >= 0 else 0
            
            # 预处理上一行对应的 dp[j] 值，避免在循环中进行复杂的条件判断
            if L > R_prev:
                val1_arr = [dp_R_prev] * len_part
            else:
                mid = min(actual_R, R_prev)
                val1_arr = dp[L : mid + 1] + [dp_R_prev] * (actual_R - mid)
            
            B_part = B[L : actual_R + 1]
            
            # 转移计算
            for idx_j in range(len_part):
                val1 = val1_arr[idx_j]
                
                if idx_j > 0:
                    val2 = new_dp[idx_j - 1]
                    prev_j_val = val1_arr[idx_j - 1]
                else:
                    val2 = val_L_minus_1
                    prev_j_val = val_L_minus_1
                
                diff = val_a - B_part[idx_j]
                score = k2 - diff * diff
                val3 = prev_j_val + score
                
                # 手写 max 略微加快 Python 运行速度
                if val1 > val2:
                    m_val = val1
                else:
                    m_val = val2
                if val3 > m_val:
                    m_val = val3
                new_dp[idx_j] = m_val
            
            # 更新全局 dp 数组
            for idx_j in range(len_part):
                dp[L + idx_j] = new_dp[idx_j]
                
            R_prev = actual_R
            
        out.append(str(dp[R_prev] if R_prev >= 0 else 0))
        
    print('\n'.join(out))

if __name__ == '__main__':
    solve()

M. P16448 Triple Mirror: The Harmony of Repetition✅

https://www.luogu.com.cn/problem/P16448?contestId=314922

:::[------ 帕林多姆] 空白是唯一不会说谎的语言。 :::

你正在玩一款被称为「Mirror Fragments」的游戏。在这个游戏里，你穿行于一座由镜面构筑的古老遗迹。遗迹中的铭文会在镜中发生奇异的变化。

你曾观察到一段字符序列经过镜面反射后，看到的内容会像被「展开」一样，每个字符都重复出现两次。比如，序列 $\mathtt{h}\mathtt{u}\mathtt{a}$ 在镜中会呈现出 $\mathtt{a}\mathtt{a}\mathtt{u}\mathtt{u}\mathtt{h}\mathtt{h}$ 的形态。若从侧方同时观察镜外原物与镜中虚像，两者会前后叠加，形成 $\mathtt{a}\mathtt{a}\mathtt{u}\mathtt{u}\mathtt{h}\mathtt{h}\mathtt{h}\mathtt{u}\mathtt{a}$。这种叠加后的整体，便是该序列的完整映射。

你对这样的映射关系很感兴趣。现在给定一个长度为 $n$ 的字符串 $S=s_1{s}_2\cdots s_n$，请你统计其中有多少个非空子串 $T=S[l\dots r]$（其中，$S[l\dots r]=s_l{s}_{l+1}{s}_{l+2}\cdots s_r$）可以成为这样的映射的像。具体地，长度为 $m$ 的子串 $T=t_1{t}_2\cdots t_m$ 需要满足以下条件：

• $m$ 是 $3$ 的倍数；
• 设 $m=3k$，则对于所有 $i=1,2,\dots ,k$ 都有 $t_{2i-1}=t_{2i}=t_{3k-i+1}$。

换而言之，$T$ 必须形如：

$$a_1{a}_1{a}_2{a}_2{a}_3{a}_3\cdots a_k{a}_k{a}_k{a}_{k-1}{a}_{k-2}\cdots a_1$$

其中，$a_1,a_2,\dots ,a_k$ 是某个字符序列。

请注意，对于两个子串 $S[l\dots r]=s_l{s}_{l+1}{s}_{l+2}\cdots s_r$ 和 $S[l^{\prime }\dots r^{\prime }]=s_{l^{\prime }}{s}_{l^{\prime }+1}{s}_{l^{\prime }+2}\cdots s_{r^{\prime }}$，被视为两个不同的子串，需要被统计两次，当且仅当 $l\ne l^{\prime }$ 或者 $r\ne r^{\prime }$。

输入格式

输入共一行，仅包含一个字符串 $S$（字符串 $S$ 的长度 $|S|$ 满足 $1\le |S|\le 2\times {10}^5$）。保证 $S$ 仅由小写拉丁字母 $\mathtt{\text{a}},\mathtt{\text{b}},\mathtt{\text{c}},\cdots ,\mathtt{\text{z}}$ 构成。

输出格式

输出一行，仅包含一个整数，表示满足题目条件的子串个数。

输入输出样例 #1

输入 #1

aaaaaa

输出 #1

5

输入输出样例 #2

输入 #2

aaaaaabbbcccccc

输出 #2

11

pypy3 AC

这道题要求我们统计一个字符串中，有多少个非空子串 $T$ 满足特定的映射结构。

题目分析

设 $T$ 的长度为 $m=3k$，则 $T$ 的结构可以表示为：

$$T=a_1{a}_1{a}_2{a}_2\dots a_k{a}_k{a}_k{a}_{k-1}\dots a_1$$

我们将 $T$ 拆分为前 $2k$ 个字符和后 $k$ 个字符：

1. 前 $2k$ 个字符：由 $k$ 个长度为 $2$ 的相同字符块组成，即对所有的 $1\le i\le k$，都有 $t_{2i-1}=t_{2i}$。
2. 后 $k$ 个字符：是前 $2k$ 个字符块代表字符的逆序，即对所有的 $1\le i\le k$，都有 $t_{3k-i+1}=t_{2i}$。

假设该子串在原串 $S$ 中的起始位置为 $l$（以 $0$ 为起始下标）。那么：

• $T$ 的前 $2k$ 个字符为 $S[l\dots l+2k-1]$，后 $k$ 个字符为 $S[l+2k\dots l+3k-1]$。
• 定义分界点 $mid=l+2k$。那么子串的范围是 $S[mid-2k\dots mid+k-1]$。
• 此时，上述两个条件可以转化关于 $mid$ 的限制（对所有的 $1\le j\le k$）：
  1. $S[mid-2j]=S[mid-2j+1]$ （即 $2k$ 前缀中的相邻字符块相等条件）
  2. $S[mid+j-1]=S[mid-2j+1]$ （即前后两部分字符的对应相等条件）

结合上述两点，对于确定的分界点 $mid$，合法的 $k$ 必须满足： 对所有 $1\le j\le k$，有 $S[mid+j-1]=S[mid-2j]=S[mid-2j+1]$。

算法设计

对于每个可能的 $mid\in [2,n-1]$，我们需要求出最大的 $K(mid)$，使得对于所有的 $1\le j\le K(mid)$，上述条件均成立。那么以 $mid$ 为分界点的合法子串数量即为 $K(mid)$。最终答案为 $\sum K(mid)$。

我们可以将条件拆分为两个独立的部分：

1. 块相等的限制

设 $dp[x]$ 表示在位置 $x$ 左侧，连续满足 $S[x-2j]=S[x-2j+1]$ 的最大 $j$。 这可以通过递推在 $O(n)$ 时间内求得：

$$dp[x]=\{\begin{array}{ll}dp[x-2]+1& \text{if }S[x-2]==S[x-1]\\ 0& \text{otherwise}\end{array}$$

所以，受块相等限制的最大 $k$ 为 $dp[mid]$。

2. 前后相等的限制

我们需要匹配以下两个序列的最长公共前缀（LCP）：

• 序列 A（从 $mid$ 开始，步长为 $1$）：$S[mid],S[mid+1],S[mid+2],\dots$
• 序列 B（从 $mid-1$ 开始，步长为 $-2$）：$S[mid-1],S[mid-3],S[mid-5],\dots$

由于序列 B 的步长为 $-2$，其所有字符的下标奇偶性与 $mid-1$ 相同。我们可以将原字符串 $S$ 按照下标的奇偶性拆分为 $S_{even}$ 和 $S_{odd}$，那么序列 B 实际上就是 $S_{even}$ 或 $S_{odd}$ 的反转字符串（记作 $R_{even}$ 和 $R_{odd}$）的某一个后缀。

因此，我们可以通过字符串哈希（Rolling Hash）+ 二分答案，在 $O(\log n)$ 的时间内求出这两个序列的 LCP 长度。 由于 $K(mid)$ 显然不能超过 $dp[mid]$，我们可以将二分的上界设为 $min(dp[mid],n-mid,\lfloor (mid-1)/2\rfloor +1)$，从而进一步加速二分过程。

在一些在线评测系统（如洛谷）的沙箱运行环境中，使用 random 库生成随机数或修改 sys.setrecursionlimit 可能会由于权限限制而触发 RE (Runtime Error)。

为了彻底解决此问题，我们可以进行以下安全优化：

1. 移除 random 库：改用固定的较大素数作为哈希基数（例如 1000003），这在绝大多数情况下已经足够安全且能避免平台限制。
2. 移除 sys.setrecursionlimit：由于我们的算法完全是迭代实现，无需任何递归，因此直接移除该设置。
3. 更健壮的输入读取：使用 sys.stdin.read().split()，可以自动过滤掉所有空白符、回车符 \r 以及可能存在的空行，确保读取到的字符串绝对正确。

优化后的完整代码如下：

import sys

def solve():
    # 极健壮的输入读取方式，防止 \r 或空行干扰
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    S = input_data[0]
    n = len(S)
    
    # 1. 预处理相邻块相等的 DP
    dp = [0] * n
    for x in range(2, n):
        if S[x-2] == S[x-1]:
            dp[x] = dp[x-2] + 1
            
    # 2. 提取奇偶下标子序列并反转
    S_even = S[0::2]
    S_odd = S[1::2]
    R_even = S_even[::-1]
    R_odd = S_odd[::-1]
    
    # 转换为字符编码列表以加速哈希计算
    S_ord = [ord(c) for c in S]
    R_even_ord = [ord(c) for c in R_even]
    R_odd_ord = [ord(c) for c in R_odd]
    
    # 3. 哈希参数（采用固定的大质数基数，避开随机数限制）
    B = 1000003
    M = (1 << 61) - 1
    
    # 预计算 B 的幂次
    P = [1] * (n + 1)
    for i in range(n):
        P[i+1] = (P[i] * B) % M
        
    def build_hash(s_ord):
        m = len(s_ord)
        H = [0] * (m + 1)
        for i in range(m):
            H[i+1] = (H[i] * B + s_ord[i]) % M
        return H

    H_S = build_hash(S_ord)
    H_Reven = build_hash(R_even_ord)
    H_Rodd = build_hash(R_odd_ord)
    
    len_Reven = len(R_even)
    len_Rodd = len(R_odd)
    
    ans = 0
    # 4. 遍历每个可能的分界点 mid
    for mid in range(2, n):
        p = (mid - 1) & 1
        idx_prime = (mid - 1) >> 1
        
        if p == 0:
            len_Rp = len_Reven
            H_R = H_Reven
        else:
            len_Rp = len_Rodd
            H_R = H_Rodd
            
        # 确定二分的上界
        high = dp[mid]
        if n - mid < high:
            high = n - mid
        if idx_prime + 1 < high:
            high = idx_prime + 1
            
        if high <= 0:
            continue
            
        start_idx = len_Rp - 1 - idx_prime
        
        # 二分查找最长公共前缀 (LCP)
        low = 1
        best = 0
        while low <= high:
            mid_len = (low + high) >> 1
            
            h1 = (H_S[mid + mid_len] - H_S[mid] * P[mid_len]) % M
            h2 = (H_R[start_idx + mid_len] - H_R[start_idx] * P[mid_len]) % M
            
            if h1 == h2:
                best = mid_len
                low = mid_len + 1
            else:
                high = mid_len - 1
        ans += best
        
    print(ans)

if __name__ == '__main__':
    solve()

N. P16449 怪商一克拉七鲜鱼丸

https://www.luogu.com.cn/problem/P16449?contestId=314922

从前有一对好朋友，他们名叫小移和小换。他们都是远近闻名的排序大师！对于一个长度为 $n$ 的排列 $p_1,p_2,\cdots ,p_n$，小移每次操作可以选一个区间将它循环右移一位，而小换每次操作可以交换两个不同元素的位置。

其中，排列 $p_1,p_2,\cdots ,p_n$，是指满足 $\{p_1,p_2,\cdots ,p_n\}=\{1,2,\cdots ,n\}$ 的一个序列。

形式化地，

• 小移的每次操作为：选择一段区间 $[l,r]$（$1\le l\le r\le n$），若原区间的元素为 $p_l,p_{l+1},p_{l+2},\dots ,p_r$，则操作后这一区间的元素变为 $p_r,p_l,p_{l+1},p_{l+2}\dots ,p_{r-1}$；
• 小换的每次操作为：选择两个不同的位置 $i,j$（$1\le i<j\le n$），交换 $p_i$ 与 $p_j$。

今天你打算主持一局黑影杀，结果平常总是参加的小移和小换却都没有来，你感觉很疑惑，于是你决定调查其中原委。原来是有个坏蛋来挑拨离间！这家伙先是对小移说：「你看 $[9,2,3,4,5,6,7,8,1]$ 这个排列，你竟然要操作整整 $8$ 次才能把它排序！要是小换来，一次就能排完，你实在是太不牛了，赶快退休吧！」小移愤怒地把他轰走了，可到了晚上这个排列却在小移心里挥之不去，他几乎一晚上没睡着……然后这个坏蛋又和小换讲：「你看 $[2,3,4,5,6,7,8,9,1]$ 这个排列，你竟然要操作整整 $8$ 次才能把它排序！换作小移来，一次就能完事，你实在是菜得没边了，速速退役吧！」小换愤怒地把他赶跑了，可到了晚上这个排列却在小换脑海里一直转悠，他简直做了一晚上噩梦……

这事简直是太魔怔了。当局者迷旁观者清，你打算用最直接的方式来彻底解除这个误会：对于给定的整数 $n$，你想对于任意的 $0\le i,j\le n-1$ 计算出满足「当采用最小化操作次数的策略时，小移需要操作 $i$ 次、小换需要操作 $j$ 次来完成排序」的长度为 $n$ 的排列数量 $P_{i,j}$。让数据说话，他们就能充分认识彼此的能力，从而解开心结，成为更好的朋友。你能完成这个任务吗？当然由于排列数量可能很大，给定 $mod$，请将答案对 $mod$ 取模。

请注意，对于两个长度为 $n$ 的排列 $p_1,p_2,\cdots ,p_n$ 和 $p_1^{\prime },p_2^{\prime },\cdots ,p_n^{\prime }$，被视为两个不同的排列，需要被统计两次，当且仅当存在 $i$（$1\le i\le n$）满足 $p_i\ne p_i^{\prime }$。

请注意，上述文本中的排序，是指将排列从小到大排序。即将一个排列 $p_1,p_2,\cdots ,p_n$，通过操作变为 $1,2,\cdots ,n$。

输入格式

输入共一行，仅包含两个整数 $n$ 和 $mod$（$1\le n\le 150$，$2\le mod\le {10}^9+7$），用一个空格分隔。

输出格式

输出 $n$ 行，每行包含 $n$ 个整数，用一个空格分隔。第 $i$ 行的第 $j$ 个整数表示 $P_{i-1,j-1}$ 对 $mod$ 取模的结果。

输入输出样例 #1

输入 #1

3 21

输出 #1

1 0 0
0 2 1
0 1 1

输入输出样例 #2

输入 #2

10 10

输出 #2

1 0 0 0 0 0 0 0 0 0
0 9 8 7 6 5 4 3 2 1
0 8 7 9 1 0 3 7 9 6
0 7 9 3 1 0 2 4 8 6
0 6 1 1 4 7 8 4 6 6
0 5 0 0 7 6 7 3 8 9
0 4 3 2 8 7 4 3 5 4
0 3 7 4 4 3 3 6 6 4
0 2 9 8 6 8 5 6 8 4
0 1 6 6 6 9 4 4 4 0

输入输出样例 #3

输入 #3

15 2

输出 #3

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1 1 0 1 1 1 0 1 1 1 0 1 1 1
0 0 0 1 0 1 1 0 1 0 0 1 0 1 1
0 1 1 0 0 1 1 0 1 1 1 0 0 1 1
0 0 1 1 1 0 0 1 0 1 0 0 0 1 1
0 1 1 1 1 0 0 1 0 0 0 0 0 1 1
0 0 0 0 0 1 1 0 1 0 0 0 0 1 1
0 1 1 1 1 0 0 1 1 0 0 0 0 1 1
0 0 1 0 1 1 0 0 0 0 1 0 1 1 0
0 1 1 0 1 0 0 0 0 1 1 0 1 0 0
0 0 0 1 0 0 0 0 0 0 0 1 0 0 0
0 1 1 0 0 0 0 0 0 1 1 0 0 0 0
0 0 1 1 1 1 1 1 1 1 0 0 0 0 0
0 1 1 1 1 1 1 1 1 0 0 0 0 0 0

O. P16450 但是什么也不会改变 3✅

https://www.luogu.com.cn/problem/P16450?contestId=314922

::: "你见识到这世界的厉害了吧？"

"我见识到我自己的厉害了！" :::

题目描述

在解开了小移和小换之间的心结之后，你又解决了好多好多的排列计数问题。

这些问题的形式形形色色，有的将简直八竿子打不着的信息结合到了一起，有的含有错综复杂的大小关系让人毫无头绪，有的源于经典问题却被不起眼的额外限制破坏掉了美好的性质，还有些看似结构简单却有着严苛以至于遥不可及的复杂度要求。它们之中有大眼观察题、有大分讨题、有 dp 题、还有容斥题、双射题、生成函数题、分治 NTT 题、整式递推题、拉格朗日反演题、格路计数题、杨表题、群论题，还有包括多重要素而无法分类的请输入文本题。尽管记忆已经遥远，你依然记得最初遇到这些题时的震撼，这有时似乎比最终解决问题时的感受来得还要更清晰。你帮助小 S 解释了使冒泡排序次数取下界的排列的分布、帮小 K 找到了让大家始终舒适的毕业旅行方案、找回了如意因为意外而失去的目标、发现了藏于起落与循环中的讲不完的故事、算出了当年的纸条上「套路」与「智力」的交汇处所蕴藏的可能性、回答了赫尔德在「心动」背后和「潮水」面前的疑惑……随着你解开了越来越多的问题，你的事迹传遍了每条大街小巷，人们都羡慕你的热情和能力，纷纷将自己无法解决的排列计数题求助于你，你成了远近闻名的排列计数大师——

——总之，那些起伏不定而紧张刺激的日子已经过去了，今天也是平常的一天。

记 $f(n,m)$（$3\le m\le n$）表示满足如下性质的数列 $P_1,P_2,\cdots ,P_m$ 的数量：

• $P_1,P_2,\cdots ,P_m$ 两两不同且都属于集合 $\{1,2,\cdots ,n\}$；
• 对于任意的 $i$（$3\le i\le m$)，满足 $[P_i<P_{i-1}]\ne [P_i<P_{i-2}]$。

其中，$[X]$ 的值在命题 $X$ 成立时为 $1$，反之为 $0$。

给定 $n$，求 $\sum _{i=3}^{n}f(n,i)$ 对 $998244353$ 取模的结果。

请注意，对于两个长度为 $m$ 的数列 $P_1,P_2,\cdots ,P_m$ 和 $P_1^{\prime },P_2^{\prime },\cdots ,P_m^{\prime }$，被视为两个不同的数列，需要被统计两次，当且仅当存在 $i$（$1\le i\le m$）满足 $P_i\ne P_i^{\prime }$。

输入格式

输入共一行，仅包含一个整数 $n$（$3\le n\le {10}^6$）。

输出格式

输出共一行，仅包含一个整数，表示答案对 $998244353$ 取模的结果。

输入输出样例 #1

输入 #1

5

输出 #1

32

思路

条件等价于 $P_i$ 严格位于 $P_{i-1}$ 和 $P_{i-2}$ 之间。序列长度有限，每次缩小区间。

对有序初始对 (a,b)，区间大小 d = |a-b|-1。定义 g(d) 为从该区间出发（选择第一个中间值 P₃ 及后续）的序列总数。

递推：$g(d)={\Sigma }_{k=0}^{d-1}(1+g(d-1-k))$，其中 1 是选 c 后停止（长度 3），g(d-1-k) 是继续扩展。

化简：$g(d)=d+{\Sigma }_{k=0}^{d-1}g(k)\to g(d)=d+pre[d-1]$，其中 $pre[d-1]={\Sigma }_{k=0}^{d-1}g(k)$。初始 g(0)=0。

答案 = ${\Sigma }_{d=0}^{n-2}2·(n-d-1)·g(d)modM$。

时间复杂度 O(n)。

验证 n=5：g=[0,1,3,7] → ans=0·8 + 1·6 + 3·4 + 7·2 = 0+6+12+14=32 ✓

代码

MOD = 998244353

def solve():
    n = int(input())
    if n < 3:
        print(0); return
    g = [0] * (n + 1)
    pre = 0
    for d in range(1, n):
        g[d] = (d + pre) % MOD
        pre = (pre + g[d]) % MOD
    ans = 0
    for d in range(0, n - 1):
        ans = (ans + 2 * (n - d - 1) * g[d]) % MOD
    print(ans)

if __name__ == "__main__":
    solve()

---