26牛客暑假多校6

点击查看题面

H题 Hard Problem

题目大意

给定一个整数 $n$，要求找出长度为 $n$ 的字典序最小的排列 $p$，使得对于任意 $1\le i\le n$，相邻元素（含首尾相连）之差的绝对值 $|p_i-p_{(imodn)+1}|$ 都不是质数。如果不存在符合要求的排列，输出 -1。

数据范围：

• $t$（测试用例数）：$1\le t\le {10}^4$
• $n$（排列长度）：$2\le n\le 2\cdot {10}^5$
• 保证所有测试用例的 $n$ 之和不超过 $2\cdot {10}^5$

---

思路

1. 天然升序与贪心判定：

• 为了获得字典序最小的排列，首选构造方案是标准升序排列 $p=[1,2,3,\dots ,n]$。
• 对于序列内部任意相邻两项 $p_i$ 和 $p_{i+1}$，其差值绝对值为 $|(i+1)-i|=1$。因为 $1$ 既非质数也非合数，即不是质数，所以内部相邻元素均满足条件。
• 唯一需要检验的是首尾环形相邻处的差值，即 $|p_n-p_1|=n-1$。
• 如果 $n-1$ 不是质数，则自然升序排列即为合法且字典序严格最小的极佳解。

2. 质数冲突与调整构造：

• 当 $n-1$ 为质数时，自然升序排列会因首尾差值为质数而失效。
• 注意到当 $n-1$ 为质数且 $n-1>2$ 时，$n-1$ 必为奇质数，由此可推导出 $n$ 必为偶数。
• 当 $n<8$ 且 $n-1$ 为质数时（对应 $n=3,4,6$），不存在可满足条件的合法排列，应输出 -1。
• 当 $n\ge 8$ 且 $n-1$ 为质数时，可对末尾 4 个元素进行局部翻转，构造排列为：

$$[1,2,\dots ,n-4,n,n-1,n-2,n-3]$$

• 验证此构造方案的相邻差值：

• 前 $n-4$ 项与后 4 项内部的相邻差绝对值均为 $1$（非质数）。

• 衔接处 $p_{n-4}$ 与 $p_{n-3}$（实际填入 $n$）的差绝对值为 $|n-(n-4)|=4$（合数，非质数）。

• 环形首尾衔接处 $p_n$（实际填入 $n-3$）与 $p_1$（实际填入 $1$）的差绝对值为 $|(n-3)-1|=n-4$。由于 $n$ 为偶数，故 $n-4\ge 4$ 必定为偶数，即必定为合数（非质数）。

• 该构造在前 $n-4$ 位置上保持了最小可能数值，确保了字典序最小的要求。

复杂度分析

时间复杂度： 预处理埃氏筛判定质数的时间复杂度为 $O(N\log \log N)$，其中 $N=2\cdot {10}^5$。对于每个测试用例，构造并输出排列的时间复杂度为 $O(n)$。总时间复杂度为 $O(N\log \log N+\sum n)$，可以在 $1\text{s}$ 内运行通过。

空间复杂度： 预处理质数标记数组占用的空间为 $O(N)$，辅助空间复杂度为 $O(1)$。

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
int Prime[N];

// 预处理埃氏筛：Prime[i] == 0 表示 i 为质数，Prime[i] == 1 表示非质数
void init() {
    Prime[0] = Prime[1] = 1; // 0 和 1 不是质数
    for (int i = 2; i * i < N; ++i) {
        if (!Prime[i]) {
            for (int j = i * i; j < N; j += i) {
                Prime[j] = 1;
            }
        }
    }
}

bool is(int k) {
    return Prime[k] == 0;
}

void fc() {
    int n; 
    std::cin >> n;
    
    if (!is(n - 1)) {
        for (int i = 1; i <= n; i++) std::cout << i << ' ';
    } 
    else if (n < 8) {
        std::cout << "-1";
    } 
    else {
        for (int i = 1; i <= n - 4; i++) std::cout << i << ' ';
        for (int i = n; i > n - 4; i--) std::cout << i << ' ';
    }
    std::cout << "\n";
}

int main() {
    // 优化标准输入输出流性能
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    init(); // 初始化质数表
    int t = 1;
    std::cin >> t;
    while (t--) fc();
    return 0;
}

---

D题 Divisibility

题目大意

给定由 $n$ 个顶点和 $m$ 条边组成的无向图 $G$（包含自环和重边）以及正整数 $k$。对于每个顶点 $u$，求满足以下条件的最小非负整数 $d$：

1. $d$ 可以被 $k$ 整除（即 $d(\mathrm{mod}k)=0$）；
2. 存在一条从顶点 $1$ 到顶点 $u$ 长度为 $d$ 的路径（路径可多次访问相同顶点或边）。

若不存在这样的 $d$，则 $f(u)=-1$。要求输出所有顶点 $f(u)$ 的值。

数据范围：

• $t$（测试用例数）：$1\le t\le 5\cdot {10}^4$
• $n$（顶点数）：$2\le n\le 5\cdot {10}^5$
• $m$（边数）：$0\le m\le 5\cdot {10}^5$
• $k$（常数）：$1\le k\le {10}^9$
• 保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $5\cdot {10}^5$

---

思路

1. 奇偶状态 BFS 求解最短距离： 从起点 $1$ 出发，使用 BFS 维护每个节点到达时的最小偶数步数 $dis[u][0]$ 和最小奇数步数 $dis[u][1]$。因为所有边权均为 $1$，BFS 首次扩展到状态 $(u,t)$ 时的距离即为最短距离。
2. 分类讨论计算最小倍数 $d=c\cdot k$： 对于顶点 $u$，需要寻找最小的非负整数 $c$，使得 $c\cdot k\ge dis[u][p]$ 且 $c\cdot k$ 的奇偶性与 $p$ 一致。

• 情形一：$k$ 为偶数 由于偶数的任意整数倍 $c\cdot k$ 均为偶数，因此不可能产生奇数长度的路径。 只需考虑偶数路径：

$$c=\lceil \frac{dis[u][0]}{k}\rceil =\lfloor \frac{dis[u][0]+k-1}{k}\rfloor$$

对应的最小步数为 $c\cdot k$。若 $dis[u][0]=\mathrm{\infty }$，则 $f(u)=-1$。

• 情形二：$k$ 为奇数 当 $k$ 为奇数时，$c\cdot k$ 的奇偶性与系数 $c$ 的奇偶性完全一致：
• 偶数路径贡献：初始系数 $c_0=\lfloor \frac{dis[u][0]+k-1}{k}\rfloor$。若 $c_0$ 为奇数，需调整为最近的偶数 $c_0+1$，候选值为 $c_0\cdot k$。
• 奇数路径贡献：初始系数 $c_1=\lfloor \frac{dis[u][1]+k-1}{k}\rfloor$。若 $c_1$ 为偶数，需调整为最近的奇数 $c_1+1$，候选值为 $c_1\cdot k$。 最终答案 $f(u)$ 为两类候选值中的最小值。若两状态均不可达，则 $f(u)=-1$。

复杂度分析

时间复杂度： BFS 遍历整张图的时间复杂度为 $O(n+m)$，计算每个顶点的答案复杂度为 $O(1)$。单次测试用例复杂度为 $O(n+m)$，总时间复杂度为 $O(\sum n+\sum m)$。

空间复杂度： 链式前向星存储图需要 $O(n+m)$ 空间，$dis$ 数组与 BFS 队列占用 $O(n)$ 空间，总空间复杂度为 $O(n+m)$。

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll inf = 1e18;
const int N = 5e5 + 5;

int n, m;
ll k;
int head[N], nxt[N << 1], to[N << 1], cnt;
ll dis[N][2];

// 链式前向星建图
void add(int u, int v) {
    to[++cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt;
}

void fc() {
    cnt = 0;
    std::cin >> n >> m >> k;
    
    // 初始化节点表头与距离数组
    for (int i = 1; i <= n; i++) {
        head[i] = -1;
        dis[i][0] = dis[i][1] = inf;
    }
    
    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;
        add(u, v);
        add(v, u);
    }
    
    // 0 步到达起点 1，偶数路径长度为 0
    dis[1][0] = 0;
    
    // BFS 队列存储 {当前节点 u, 当前路径奇偶性 t}
    std::queue<std::pair<int, int>> q;
    q.push({1, 0});
    
    while (q.size()) {
        auto [u, t] = q.front();
        q.pop();
        
        for (int i = head[u]; i > 0; i = nxt[i]) {
            int v = to[i];
            // 奇偶状态转移：偶变奇，奇变偶
            if (dis[v][t ^ 1] != inf) continue;
            dis[v][t ^ 1] = dis[u][t] + 1;
            q.push({v, t ^ 1});
        }
    }
    
    // 分类讨论 k 的奇偶性
    if (k & 1) {
        // k 为奇数：系数 c 的奇偶性决定路径长度 d 的奇偶性
        for (int i = 1; i <= n; i++) {
            ll ans = inf;
            
            // 1. 考虑偶数最短路径 dis[i][0]
            if (dis[i][0] != inf) {
                ll d = (dis[i][0] + k - 1) / k; // 向上取整求最小系数
                if (d & 1) d++;                  // 若为奇数系数，调整为偶数系数
                ans = std::min(ans, d * k);
            }
            
            // 2. 考虑奇数最短路径 dis[i][1]
            if (dis[i][1] != inf) {
                ll d = (dis[i][1] + k - 1) / k; // 向上取整求最小系数
                if (d % 2 == 0) d++;             // 若为偶数系数，调整为奇数系数
                ans = std::min(ans, d * k);
            }
            
            std::cout << (ans == inf ? -1 : ans) << " ";
        }
    } else {
        // k 为偶数：只能通过偶数路径到达
        for (int i = 1; i <= n; i++) {
            std::cout << (dis[i][0] == inf ? -1 : (dis[i][0] + k - 1) / k * k) << " ";
        }
    }
    std::cout << "\n";
}

int main() {
    // 优化 I/O 效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t = 1;
    std::cin >> t;
    while (t--) fc();
    return 0;
}

---

G题 Game on a Graph

题目大意

给定一个包含 $n$ 个顶点和 $m$ 条边的简单连通无向图 $G$，保证所有顶点的度数不超过 $3$。同时给定由 $k$ 个特殊顶点组成的集合。

Alice 和 Bob 在图上进行如下游戏：

• Alice 初始站在一个非特殊顶点 $s$ 上，Alice 先手，两人轮流操作。
• Alice 的操作：若当前处于特殊顶点则直接获胜；否则选择一条相连的边移动到相邻顶点。若无边可选则 Bob 获胜。
• Bob 的操作：选择图中的任意一条边并将其永久删除。若无边可删则什么都不做。

求出所有能让 Alice 在双方均采取最优策略下必胜的起始顶点 $s$。

数据范围：

• $t$（测试用例数）：$1\le t\le 2\cdot {10}^4$
• $n$（顶点数）、$k$（特殊点数）：$1\le k<n\le 2\cdot {10}^5$
• $m$（边数）：$n-1\le m\le min(\frac{3n}{2},2\cdot {10}^5)$
• 保证所有顶点度数 $\le 3$，且所有测试用例中 $n$ 与 $m$ 的总和均不超过 $2\cdot {10}^5$。

---

思路

1. 终端必胜态定义：将题目指定的特殊顶点集合 $S$ 初始化为绝对必胜态集合。
2. 中间过程的安全转移：对于图中的任意非特殊顶点 $v$，假设 Alice 在游戏过程中移动到了 $v$。由于接下来轮到 Bob 操作且 Bob 会删去一条边，若要保证 Alice 之后仍能到达必胜态，顶点 $v$ 在当前时刻必须至少连接 $2$ 个位于必胜态集合 $S$ 中的邻接点。这样即使 Bob 删去其中一条边，Alice 依然可以沿着另一条边进入必胜态。因此，当一个非特殊点邻接的必胜点数量达到 $2$ 时，该点即可被升格为新的必胜态并加入集合 $S$ 进行拓展。
3. 起始点的特殊性（先手优势）：游戏开始时 Alice 为先手，Bob 尚未进行任何删边操作。因此，如果起始顶点 $s$ 邻接的必胜态集合 $S$ 中至少存在 $1$ 个顶点，Alice 即可在第一回合直接步入必胜态并赢得游戏。
4. 算法实现流程：

• 初始化队列 $q$，将 $k$ 个特殊顶点加入队列并标记为必胜点。
• 使用多源 BFS 进行逆向传播，对于队头节点 $u$，遍历其邻接点 $v$。维护 $c[v]$ 记录 $v$ 邻接的必胜点数量。当 $c[v]=2$ 且 $v$ 还不是必胜点时，将 $v$ 标记为必胜点并压入队列 $q$。
• 拓扑传播结束后，统计所有非特殊点中满足 $c[i]\ge 1$ 的顶点 $i$，这些顶点即为 Alice 的起始必胜点。

复杂度分析

时间复杂度： 基于队列的多源 BFS 中，每个顶点最多入队一次，每条无向边最多被遍历两次，时间复杂度为 $O(n+m)$。

空间复杂度： 需要邻接表存储图结构以及队列和状态标记数组，空间复杂度为 $O(n+m)$。

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 2e5 + 5;
int n, m, k;
int head[N], nxt[N << 1], to[N << 1], cnt;
int is[N], c[N];

void add(int u, int v) {
    to[++cnt] = v;
    nxt[cnt] = head[u];
    head[u] = cnt;
}

void fc() {
    cnt = 0;
    std::cin >> n >> m >> k;
    
    for (int i = 1; i <= n; i++) {
        head[i] = -1;
        is[i] = 0;
        c[i] = 0;
    }
    
    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;
        add(u, v);
        add(v, u);
    }
        
    std::queue<int> q;
    for (int i = 0; i < k; i++) {
        int x;
        std::cin >> x;
        is[x] = 1;
        q.push(x);
    }
    
    // 拓扑/BFS 传播必胜状态
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = head[u]; ~i; i = nxt[i]) {
            int v = to[i];
            if (is[v]) continue; // 已是特殊点/扩展必胜点，跳过
            c[v]++;              // 统计 v 邻接的必胜点数量
            if (c[v] == 2) {     // 邻接 2 个及以上必胜点即可转化为扩展必胜点
                is[v] = 1;
                q.push(v);
            }
        }
    }
    
    // c[i] >= 1 的非特殊点即为 Alice 起始必胜点
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (c[i]) ans++;
    }
    
    std::cout << ans << "\n";
    for (int i = 1; i <= n; i++) {
        if (c[i]) std::cout << i << ' ';
    }
    std::cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    std::cin >> t;
    while (t--) fc();
    return 0;
}

F题 Full Alphabet

前置知识：z函数+状压dp

题目大意

给定一个由小写英文字母组成的字符串 $s$。字母表 $A$ 是 26 个小写字母的一个排列，决定了字符间的字典序大小。要求计算有多少种不同的字母表 $A$，使得字符串 $s$ 在字母表 $A$ 的字典序下成为一个 Lyndon 串。答案对 $2^{32}$ 取模（利用 32 位无符号整数自然溢出即可）。

数据范围：

• $2\le |s|\le 2\cdot {10}^7$
• 字符串仅包含小写英文字母。
• 时间限制：10 秒，空间限制：1024 MB。

思路

1. 无解条件判定： 根据 Lyndon 串定义，对于每个后缀 $s[i\dots n-1]$ ($1\le i\le n-1$)，必须满足 $s{<}_{A}s[i\dots n-1]$。利用 Z 函数求出 $z[i]=\text{LCP}(s,s[i\dots n-1])$：

• 若 $i+z[i]=n$，说明后缀 $s[i\dots n-1]$ 是字符串 $s$ 的真前缀。由于前缀的长度小于 $s$，在任何字典序下真前缀都严格小于 $s$，因此 $s$ 必定不可能成为 Lyndon 串，直接输出 $0$。

2. 偏序关系提取：

• 若 $i+z[i]<n$，则 $s$ 与后缀 $s[i\dots n-1]$ 在位置 $z[i]$ 处首次出现不同字符。
• 记 $v=s[z[i]]$，$u=s[i+z[i]]$。为使 $s{<}_{A}s[i\dots n-1]$ 成立，必须满足 $v{<}_{A}u$，即字符 $v$ 在字母表 $A$ 中的位置必须早于字符 $u$。
• 遍历所有后缀 $i\in [1,n-1]$，将提取到的所有字符偏序关系存入有向图中。

3. 状压 DP 求解拓扑序数量：

• 统计 $s$ 中出现的不同字符数量 $m$ ($m\le 26$)，并将字符映射至 $[0,m-1]$。
• 设 $dp[\text{mask}]$ 表示已将二进制掩码 $\text{mask}$ 所代表的字符集合排好序的合法方案数。
• 状态转移：枚举下一个可以放入排列的字符 $i$，当且仅当 $i$ 的所有前置依赖字符均已在 $\text{mask}$ 中时，$dp[\text{mask}\mid (1\ll i)]\leftarrow dp[\text{mask}\mid (1\ll i)]+dp[\text{mask}]$。

4. 未出现字符的排列乘积：

• 最终状态 $dp[(1\ll m)-1]$ 给出 $s$ 中出现的 $m$ 个字符的合法排列数。
• 对于未在 $s$ 中出现的剩余 $(26-m)$ 个字符，它们可以在字母表中任意插入到已排好的 $m$ 个字符之间。插入位置的选择数为 $(m+1)\times (m+2)\times \cdots \times 26=\frac{26!}{m!}$。
• 将两者相乘并利用 unsigned int 自然对 $2^{32}$ 取模即可得到最终答案。

复杂度分析

时间复杂度

• Z 函数计算字符串前缀匹配的时间复杂度为 $O(n)$。
• 提取偏序关系遍历 $n$ 个后缀，时间复杂度为 $O(n)$。
• 状压 DP 求解拓扑序数量，共有 $2^m$ 个状态，每个状态转移为 $O(m)$，时间复杂度为 $O(2^m\cdot m)$。
• 整体时间复杂度为 $O(n+2^m\cdot m)$。由于 $m\le 26$，算法在规定的时限内可以高效完成计算。

空间复杂度

• Z 数组与辅助数组大小为 $O(n)$。
• DP 数组大小为 $O(2^m)$。
• 整体空间复杂度为 $O(n+2^m)$。

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ui = unsigned int;

// 计算字符串 s 的 Z 数组 (扩展 KMP)
vector<int> zArray(const string& s) {
    int n = s.size();
    vector<int> z(n, 0);
    for (int i = 1, r = 0, c = 0; i < n; i++) {
        if (r > i) z[i] = min(z[i - c], r - i);
        while (i + z[i] < n && s[i + z[i]] == s[z[i]]) ++z[i];
        if (i + z[i] > r) r = i + z[i], c = i;
    }
    return z;
}

void solve() {
    string s;
    if (!(cin >> s)) return;
    int n = s.size();
 
    auto z = zArray(s);

    vector<int> id(26, -1);
    int m = 0;
    for (char c : s) {
        if (id[c - 'a'] == -1) id[c - 'a'] = m++;
    }

    vector<int> pred(m, 0);
    for (int i = 1; i < n; i++) {
        if (i + z[i] == n) {
            cout << "0\n";
            return;
        }
        int v = id[s[z[i]] - 'a'];
        int u = id[s[i + z[i]] - 'a'];
        pred[v] |= (1 << u);
    }

    // 4. 状压 DP 计算拓扑序数量
    vector<ui> dp(1 << m, 0);
    dp[0] = 1;
    for (int mask = 0; mask < (1 << m); mask++) {
        if (!dp[mask]) continue;
        for (int i = 0; i < m; i++) {
            if (!(mask & (1 << i)) && ((pred[i] & mask) == pred[i])) {
                dp[mask | (1 << i)] += dp[mask];
            }
        }
    }

    ui ans = dp[(1 << m) - 1];
    for (int i = m + 1; i <= 26; i++) {
        ans *= (ui)i;
    }

    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}