河南省萌新联赛第四场（河南大学）题解

难度评估

签到：A，C，G，J
简单：B，D，L
中等：F，H，I
困难：E，K

A-完美序列

$\text{Tag}$ ：枚举

观察到本题 $a_i$ 的范围较小，考虑枚举 $b_1+b_2$ 的值，然后统计序列 $b$ 的长度，取所有情况的最大值即可。

时间复杂度： $O(n + R^2)$ ，其中 $R$ 为 $a_i$ 的值域。

#include <bits/stdc++.h>
constexpr int MAXN = 5000;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n;
    std::cin >> n;
    std::vector<int> tot(2 * MAXN + 1);
    for(int i = 1; i <= n; ++i) {
        int x;
        std::cin >> x;
        tot[x]++;
    }
    int ans = 0;
    for(int i = 1; i <= 2 * MAXN; ++i) {
        int res = 0;
        for(int j = 1; j <= i - j; ++j) {
            if(j == i - j) {
                res += tot[j] / 2 * 2;
            } else {
                res += std::min(tot[j], tot[i - j]) * 2;
            }
        }
        ans = std::max(ans, res);
    }
    std::cout << ans << '\n';
    return 0;
}

B-0!!!!!

$\text{Tag}$ ：数论分块

设 $F_p(n)$ 为满足 $p^x$ 整除区间 $[1, n]$ 中所有整数的因数的乘积的最大非负整数 $x$ 。

由于 $0$ 的个数之和 $2$ 和 $5$ 有关，可以得出答案为 $\min \{F_2(R) - F_2(L-1),F_5(R) - F_5(L-1)\}$ 。

对于 $F_p(n)$ 可以得到如下递推式：

F_p(n) = \sum\limits_{i=1}^{n} \sum\limits_{d|i} \sum \limits_{k = 1}[p^k|d]\\

交换求和次序：

F_p(n) = \sum\limits_{k = 1} \sum\limits_{i=1}^{n} \sum\limits_{d|i} [p^k|d]\\

从枚举 $[1, n]$ 改为先枚举约数：

F_p(n) = \sum\limits_{k = 1} \sum\limits_{d=1, p ^ k | d}^{n} \lfloor\frac{n}{d} \rfloor\\

$d$ 和 $n$ 同除 $p^k$ ：

F_p(n) = \sum\limits_{k = 1} \sum\limits_{d=1}^{\lfloor \frac{n}{p ^ k} \rfloor} \lfloor\frac{\lfloor\frac{n}{p ^ k}\rfloor}{d} \rfloor \\

对于第一部分直接枚举，第二部分使用数论分块优化即可。

不难观察出该式子的时间复杂度为等比数列求和，首项为 $\sqrt{\frac{n}{p}}$ ，公比为 $\sqrt{\frac{1}{p}}$ 。

时间复杂度： $O(\sqrt n)$ 。

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
    i64 L, R;
    std::cin >> L >> R;
    auto f = [&](i64 x, i64 lim) ->i64 {
        i64 num = 0;
        for(i64 i = x; i <= lim; i *= x) {
            i64 n = lim / i;
            for(i64 l = 1; l <= n; l = n / (n / l) + 1) {
                i64 r = n / (n / l);
                num += (r - l + 1) * (n / l);
            }
        }
        return num;
    };
    i64 a = f(2, R) - f(2, L - 1);
    i64 b = f(5, R) - f(5, L - 1);
    std::cout << std::min(a, b) << '\n';
}

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

C-合并石子

$\text{Tag}$ ：前缀和

由题意可得，所有石子最后一定会合并到某一个位置，可以枚举最终位置，取所有情况中所花费体力的最小值。

对于位置 $x$ ，在 $[1, x - 1]$ 区间中的石子一定会不断向 $x$ 合并，在 $[x + 1, n]$ 区间中的石子也一定会不断向 $x$ 合并。

由于每次合并是向上取整的，所以从离 $x$ 位置最远的石子开始合并一定更优，预处理前缀和后缀的体力消耗便可 $O(1)$ 得到合并到位置 $x$ 所花费体力的最小值。

时间复杂度： $O(n)$ 。

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
    int n, k;
    std::cin >> n >> k;
    std::vector<i64> a(n + 1), pre(n + 1), suf(n + 1);
    for(int i = 1; i <= n; ++i) {
        std::cin >> a[i];
    }
    i64 sum = 0;
    for(int i = 2; i <= n; ++i) {
        sum += a[i - 1];
        pre[i] = pre[i - 1] + (sum + k - 1) / k;
    }
    sum = 0;
    for(int i = n - 1; i >= 1; --i) {
        sum += a[i + 1];
        suf[i] = suf[i + 1] + (sum + k - 1) / k;
    }
    i64 ans = 2E18;
    for(int i = 1; i <= n; ++i) {
        ans = std::min(ans, pre[i] + suf[i]);
    }
    std::cout << ans << '\n';
}

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

D-箭头谜题Ⅰ

$\text{Tag}$ ：最短路

考虑每个格子的上下左右四个移动方向，若当前格子地板的移动方向与要移动的方向相同，则连接一条边权为 $0$ 的单向边，反之连接一条边权为 $1$ 的单向边。

于是该问题可以转化为从 $(1,1)$ 到 $(n, m)$ 的最短路问题，由于边权只有 $0$ 和 $1$ ，于是可以用双端队列实现 $\text{01BFS}$ 。

时间复杂度： $O(n \cdot m)$ 。

#include <bits/stdc++.h>
using i64 = long long;
std::vector<std::pair<int, int>> d = {
    {-1, 0}, {1, 0}, {0, -1}, {0, 1}
};
std::string idx = "UDLR";

void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;
    std::vector<std::string> v(n);
    std::vector vis(n, std::vector<int>(m, -1));
    for(int i = 0; i < n; ++i) {
        std::cin >> v[i];
    }
    std::deque<std::tuple<int, int, int>> dq;
    dq.push_back({0, 0, 0});
    while(!dq.empty()) {
        auto [x, y, num] = dq.front();
        dq.pop_front();
        if(vis[x][y] != -1) continue;
        vis[x][y] = num;
        for(int i = 0; i < 4; ++i) {
            const auto &[dx, dy] = d[i]; 
            int xx = x + dx;
            int yy = y + dy;
            if(xx < 0 || xx >= n || yy < 0 || yy >= m || vis[xx][yy] != -1) continue;
            if(v[x][y] == idx[i]) {
                dq.push_front({xx, yy, num});
            } else {
                dq.push_back({xx, yy, num + 1});
            }
        }
    }
    std::cout << (vis[n - 1][m - 1] <= k ? "YES" : "NO") << '\n';
}

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

E-箭头谜题Ⅱ

$\text{Tag}$ ：构造

约定 $|x|$ 表示 $x$ 地板的数量。

首先考虑无解的情况，若不能填满除点 $(n, m)$ 的所有方格，则一定无解，然后对于从点 $(1, 1)$ 到点 $(n, m)$ ，至少需要 $n-1$ 个 $D$ 和 $m-1$ 个 $R$ 才能到达。

综上若不满足 $|U| + |D| + |L| + |R| \geq n \cdot m - 1$ ， $|D| \geq n - 1$ ， $|R| \geq m - 1$ 其中之一，则一定无解。

对于满足以上条件的情况一定有解，下面给出一种构造方法：

首先使用 $n-1$ 个 $D$ 和 $m-1$ 个 $R$ 构造一条从点 $(1, 1)$ 到点 $(n, m)$ 的路径 $S$ ，那么可以发现路径 $S$ 把矩阵分隔为两部分：

对于路径 $S$ 右上方的格子，任意放置 $D$ 或 $L$ 都可以到达路径 $S$ 然后通过路径 $S$ 到达 $(n, m)$ 。
对于路径 $S$ 左下方的格子，任意放置 $U$ 或 $R$ 都可以到达路径 $S$ 然后通过路径 $S$ 到达 $(n, m)$ 。

那么可以通过控制路径 $S$ 的形态，来使 $S$ 右上方的格子总数小于等于 $|D| + |L| - n + 1$ 且左下方的格子总数小于等于 $|U| + |R| - m + 1$ ，再把右上方格子全部填上 $D$ 或 $L$ ，左下方格子全部填上 $U$ 或 $R$ 即可。

时间复杂度： $O(n \cdot m)$ 。

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
    int n, m;
    std::cin >> n >> m;
    i64 U, D, L, R;
    std::cin >> U >> D >> L >> R;
    if((U + D + L + R) < n * m - 1 || R < m - 1 || D < n - 1) {
        std::cout << "NO\n";
        return;
    }
    std::vector ans(n, std::vector<char>(m, '#'));
    D -= n - 1, R -= m - 1;
    for(int i = 0; i < n - 1; ++i) {
        for(int j = m - 1; j >= 1; --j) {
            if(L > 0) {
                ans[i][j] = 'L';
                L--;
            } else if(D > 0) {
                ans[i][j] = 'D';
                D--;
            }
        }
    }
    for(int i = n - 1; i > 0; --i) {
        for(int j = 0; j < m - 1; ++j) {
            if(ans[i][j] != '#') break;
            if(ans[i - 1][j + 1] != '#') break;
            if(i + 1 < n && ans[i + 1][j] == '#') break;
            if(R > 0) {
                ans[i][j] = 'R';
                R--;
            } else if(U > 0) {
                ans[i][j] = 'U';
                U--;
            }
        }
    }
    std::cout << "YES\n";
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(ans[i][j] == '#' && i + 1 < n && ans[i + 1][j] == '#') {
                ans[i][j] = 'D';
            }
            if(ans[i][j] == '#' && j + 1 < m && ans[i][j + 1] == '#') {
                ans[i][j] = 'R';
            }
            std::cout << ans[i][j];
        }
        std::cout << '\n';
    }
}

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

F-Minecraft

$\text{Tag}$ ：二分拓扑排序

若直接考虑如何分配物品向上合成，则难以解决。

不难发现是否能合成 $x$ 个物品 $1$ 具有单调性，那么可以考虑二分能合成物品 $1$ 的个数为 $x$ ，判断是否有解。

由题意可得，这些物品之前的依赖关系构成一个 DAG（有向无环图），那么可以用拓扑排序求出所有物品的拓扑序，然后按照拓扑序逐层向下传递每个物品的需求，若存在一个物品没有合成它的配方并且其需求大于实际物品个数则不满足，反之则满足。

注意数据范围，若依赖关系为链的情况，则最多可以合成 $10^{10}\times10^{5}=10^{15}$ 件物品 $1$ ，二分右边界应该不小于 $10^{15}$ 。

此外二分判断过程中某一件物品的需求量可能会超过 $long$ $long$ 的范围，应及时返回 $false$ 。

时间复杂度： $O(n \log(n \cdot R))$ ，其中 $R$ 为 $a_i$ 的值域。

#include <bits/stdc++.h>
using i64 = long long;

constexpr i64 MAXN = 1E15;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m;
    std::cin >> n >> m;
    std::vector<i64> f(n + 1);
    std::vector<int> d(n + 1);
    std::vector<std::vector<int>> v(n + 1); 
    for(int i = 1; i <= n; ++i) {
        std::cin >> f[i];
    }
    for(int i = 1; i <= m; ++i) {
        int x, num;
        std::cin >> x >> num;
        for(int j = 1; j <= num; ++j) {
            int y;
            std::cin >> y;
            v[x].push_back(y);
            d[y]++;
        }
    }
    auto check = [&](i64 mid) ->bool {
        std::vector<i64> need(n + 1);
        std::vector<int> ind = d;
        for(int i = 2; i <= n; ++i) {
            need[i] = -f[i];
        }
        need[1] = mid;
        std::queue<int> q;
        q.push(1);
        while(!q.empty()) {
            int id = q.front();
            q.pop();
            if(need[id] > 1E18 ||(id > 1 && v[id].size() == 0 && need[id] > 0)) {
                return false;
            }
            for(const auto &nxt : v[id]) {
                need[nxt] += std::max(0LL, need[id]);
                ind[nxt]--;
                if(ind[nxt] == 0) q.push(nxt);
            }
        }
        return true;
    };
    i64 l = 1, r = MAXN, ans = 0;
    while(l <= r) {
        i64 mid = (l + r) / 2;
        if(check(mid)) {
            l = mid + 1;
            ans = mid;
        } else {
            r = mid - 1;
        }
    }
    std::cout << ans + f[1] << '\n';
    return 0;
}

G-封闭运算

$\text{Tag}$ ：枚举

按照题意枚举所有数对，判断其按位或的值是否在数组中（暴力枚举或用 $\text{std::set}$ 判断均可），若不存在，则答案为 "NO"，反之答案为 "YES"。

时间复杂度： $O(n^2\log(n))$ 。

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> v(n);
    std::set<int> st;
    for(int i = 0; i < n; ++i) {
        std::cin >> v[i];
        st.insert(v[i]);
    }
    std::sort(v.begin(), v.end());
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            if(!st.contains(v[i] | v[j])) {
                std::cout << "NO\n";
                return;
            }
        }
    }
    std::cout << "YES\n";
}

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

H-杀戮尖塔第四厉害高手

$\text{Tag}$ ：dp 图论

由题意可得，这个图是一个有向无环图（DAG），因此我们可以在这个DAG上进行DP。

设 $\text{dp}[i][j]$ 表示用了 $j$ 次传送，到达 $i$ 点时最大战斗力，如果不能到达则置为负无穷。

由于状态只能通过一个点转移到相邻的点，或者用传送转移到满足 $d_k = d_i+ 1$ 的节点 $k$ 。

不难写出以下转移方程：

\text{dp}[i][j] = \begin{cases} \max\{\text{dp}[i][j], \space \text{dp}[k][j] + \text{b}[i]\}, & \text{dp}[k][j] \geq \text{a}[i] \wedge \text{存在一条$k$到$i$的路径} \\ \max\{\text{dp}[i][j], \space \text{dp}[k][j - 1] + \text{b}[i]\}, & j > 0 \wedge \text{dp}[k][j - 1] \geq a[i] \wedge \text{d}[i] = \text{d}[k] + 1 \end{cases}\\

如果直接按上转移，可能会到 $O(n ^ 2)$ 级别的复杂度，因此需要进行优化。

考虑使用传送时，

\text{dp}[i][j] = \max\{\text{dp}[i][j], \space \max\limits_{\text{d}[i] = \text{d}[k] + 1}\{\text{dp}[k][j - 1]\} + \text{b}[i]\}, \quad j \neq 0\wedge \text{dp}[k][j - 1] \geq \text{a}[i]

即第 $\text{d}[i]$ 层都是由上一层的 $\max\limits_{\text{d}[i] = \text{d}[k] + 1}\{\text{dp}[k][j - 1]\}$ 转移而来。

因此可通过维护每一层的最大值来加速转移。

设 $\text{mx}[i][j]$ 表示用了 $j$ 次传送，到达 $i$ 这一层最大战斗力，如果不能到达则置为负无穷。

因此最终转移方程为：

\text{dp}[i][j] = \begin{cases} \max\{\text{dp}[i][j], \space \text{dp}[k][j] + \text{b}[i]\}, & \text{dp}[k][j] \geq \text{a}[i] \wedge \text{存在一条$k$到$i$的路径} \\ \max\{\text{dp}[i][j], \space \text{mx}[\text{d}[i] - 1] + \text{b}[i]\}, & \text{d}[i] > 0 \wedge \text{mx}[\text{d}[i] - 1] \geq \text{a}[i] \end{cases} \\ \\ \text{mx}[i][j] = \max\limits_{\text{d}[k] = i} \{ \text{dp}[k][j] \}

时间复杂度： $O(n + m)$ 。

#include <bits/stdc++.h>
using i64 = long long;
constexpr i64 INF = 2E14;
constexpr int NUM = 3;

void solve() {
    i64 n, m, k;
    std::cin >> n >> m >> k;
    std::vector<std::vector<int>> v(n + 1);
    std::vector<i64> a(n + 1), b(n + 1);
    for(int i = 1; i <= n; ++i) {
        std::cin >> a[i] >> b[i];
    }
    for(int i = 1; i <= m; ++i) {
        int x, y;
        std::cin >> x >> y;
        v[x].push_back(y);
    }
    v[0].push_back(1);
    std::vector<int> dis(n + 1), vis(n + 1);
    std::vector mx(n + 1, std::vector<i64>(NUM + 1, -INF));
    std::vector dp(n + 1, std::vector<i64>(NUM + 1, -INF));
    dp[0][0] = k;
    std::queue<int> q;
    q.push(0);
    while(!q.empty()) {
        int id = q.front();
        q.pop();
        for(int i = 1; dis[id] - 1 >= 0 && i <= NUM; ++i) {
            if(mx[dis[id] - 1][i - 1] < a[id]) continue;
            dp[id][i] = std::max(dp[id][i], mx[dis[id] - 1][i - 1] + b[id]);
        }
        for(int i = 0; i <= NUM; ++i) {
            for(const auto &j : v[id]) {
                if(dp[id][i] >= a[j]) {
                    dp[j][i] = std::max(dp[j][i], dp[id][i] + b[j]);
                }
                if(vis[j]) continue;
                q.push(j);
                dis[j] = dis[id] + 1;
                vis[j] = 1;
            }
            mx[dis[id]][i] = std::max(mx[dis[id]][i], dp[id][i]);
        }
    }
    std::cout << (std::ranges::max(dp[n]) <= -INF ? "NO" : "YES") << '\n';
}

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

I-故障机器人的奇妙冒险

$\text{Tag}$ ：数据结构

由于除去操作 $1$ 和 $2$ ，其余操作均为全局操作，可以考虑维护全局 $\text{Tag}$ 。

钦定 $\text{mintag}$ 为全局取 $\min$ ， $\text{addtag}$ 为全局减， $mn$ 为 $a_i$ 中的全局最小值。

钦定 $\text{Tag}$ 对 $a_i$ 的复合顺序为 $\min(a_i - \text{addtag}, \text{mintag} )$ 。

对于操作 $5$ ，显然直接输出 $\min (mn - \text{addtag}, \text{mintag} )$ 即可。

对于操作 $4$ ，对全局数组取 $\min$ ，那么使标记的复合操作变为 $\min ( \min (a_i - \text{addtag}, \text{mintag} ) , x)$ ，等价于 $\min (a_i - \text{addtag}, \min (\text{mintag}, x) )$ ，即把 $\text{mintag}$ 更新为 $\min (\text{mintag}, x)$ 。

对于操作 $3$ ，对全局数组减 $x$ ，那么使标记的复合操作变为 $\min (a_i - \text{addtag}, \text{mintag} ) - x$ ，等价于 $\min (a_i - (\text{addtag} + x), \text{mintag} - x )$ ，即把 $\text{addtag}$ 更新为 $\text{addtag} + x$ ，把 $\text{mintag}$ 更新为 $\text{mintag}- x$ 。

对于操作 $2$ ，查询 $a_{pos}$ 的值，直接输出 $\min (a_{pos} - \text{addtag}, \text{mintag} )$ 即可。

对于操作 $1$ ，对 $a_{pos}$ 单点减 $x$ ，那么使 $a_{pos}$ 的标记复合操作变为 $\min (a_{pos} - \text{addtag}, \text{mintag} ) - x$ ，但是由于为了保证的 $\text{Tag}$ 的全局性，需要对 $a_{pos}$ 进行修改，那么等价于 $\min(\min(a_{pos}, \text{mintag} + \text{addtag})- x - \text{addtag}, \text{mintag} )$ 。

若 $a_{pos} - \text{addtag} < \text{mintag}$ ：

则有 $\min(a_{pos} - \text{addtag}, \text{mintag}) - x = a_{pos} - \text{addtag} - x$

由条件得 $a_{pos} < \text{mintag} + \text{addtag}$ ：

则有 $\min(\min(a_{pos}, \text{mintag} + \text{addtag})- x - \text{addtag}, \text{mintag} ) = min(a_{pos} - x - \text{addtag}, \text{mintag}) = a_{pos} - \text{addtag} - x$
若 $a_{pos} - \text{addtag} \geq \text{mintag}$ ：

则有 $\min(a_{pos} - \text{addtag}, \text{mintag}) - x = \text{mintag} - x$

由条件得 $a_{pos} \geq \text{mintag} + \text{addtag}$ ：

则有 $\min(\min(a_{pos}, \text{mintag} + \text{addtag})- x - \text{addtag}, \text{mintag} ) = min(\text{mintag} + \text{addtag} - x - \text{addtag}, \text{mintag}) = \text{mintag} - x$

综上上述式子等价。

即把 $a_{pos}$ 更新为 $\min(a_{pos}, \text{mintag} + \text{addtag})- x$ 。同时这里需要把 $mn$ 更新为 $\min (a_{pos},mn)$ 。

时间复杂度： $O(n + q)$ 。

#include <bits/stdc++.h>
using namespace std;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
 
constexpr i64 INF = 1e18;
 
struct AllTag {
    i64 mn = INF, addtag = 0, mintag = INF;
    i64 queryMin() {
        return min(mn - addtag, mintag);
    }
    i64 query(i64 x) {
        return min(x - addtag, mintag);
    }
    void add(i64 &x, i64 y) {
        x = min(x, mintag + addtag) - y;
        mn = min(mn, x);
    }
    void allAdd(i64 x) {
        addtag += x;
        mintag -= x;
    }
    void allMin(i64 x) {
        mintag = min(mintag, x);
    }
};
 
void solve() {
    int n, q;
    cin >> n >> q;
    vector<i64> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    AllTag tag;
    tag.mn = *min_element(a.begin() + 1, a.end());
    while (q--) {
        i64 op;
        cin >> op;
        if (op == 1) {
            i64 x, y;
            cin >> x >> y;
            tag.add(a[x], y);
        } else if (op == 2) {
            i64 x;
            cin >> x;
            cout << tag.query(a[x]) << "\n";
        } else if (op == 3) {
            i64 x;
            cin >> x;
            tag.allAdd(x);
        } else if (op == 4) {
            i64 x;
            cin >> x;
            tag.allMin(x);
        } else {
            cout << tag.queryMin() << "\n";
        }
    }
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

J-故障机器人的完美牌组

$\text{Tag}$ ：贪心

如果进行操作，为了使字典序最大，如果 $i$ 不为 $1$ ，则答案一定不会更优。那么为了使 $a_1$ 最大，则 $j$ 一定为 $a_2,a_3 \ldots a_n$ 中的最大值的索引，如果存在多个最大值，为了保证字典序最大，则选择最后一个最大值的索引。

考虑 $a_2,a_3 \ldots a_n$ 中最大值为 $0$ 的情况，此时如果进行操作，不仅对 $a_1$ 没有贡献，还会使数组长度减一，导致字典序变小，此时应不进行操作。

时间复杂度： $O(n)$ 。

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> v(n + 1);
    for(int i = 1; i <= n; ++i) {
        std::cin >> v[i];
    }
    int idx = 0;
    for(int i = 2; i <= n; ++i) {
        if(v[i] == 0) continue;
        if(std::tie(v[i], i) > std::tie(v[idx], idx)) {
            idx = i;
        }
    }
    std::cout << n - (idx != 0) << '\n';
    v[1] += v[idx];
    for(int i = 1; i <= n; ++i) {
        if(idx == i) continue;
        std::cout << v[i] << ' ';
    }
    std::cout << '\n';
}

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

K-故障机器人的完美尖塔

$\text{Tag}$ ：边双连通分量 LCA 树上差分

对于一个环上的要求，我们必然可以通过将其设置为有向的环来满足环上所有要求。

考虑边双连通分量中的部分，必然可以将其中的极大环设置为有向环，让连通分量中残余的链指向环来满足要求。

如下图中，先置有向环 $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6 \rightarrow 1$ ，将剩余的两条边 $6 - 7$ 和 $7 - 3$ 按一定方向指向环即可。

alt

可以将边双连通分量缩点，将问题转化为树上问题，其中边双连通分量可以用 $\text{tarjan}$ 算法来求。

对于一组要求 $(x, y)$ ，其路径为 $x \rightarrow \text{lca}(x, y) \rightarrow y$ ，其中 $\text{lca}$ 可以用树上倍增，树链剖分等做法求得。

如果同一条边上的两个要求方向相反，则必然不能满足。

定义数组 $\text{down}$ 和 $\text{up}$ ，其中 $\text{down}$ 表示当前节点与父亲节点之间的边指向当前节点的要求数量， $\text{up}$ 表示当前节点与父亲节点之间的边指向父亲节点的要求数量。

通过树上差分可以快速求得。

对于一条边，如果对应的 $\text{down}$ 和 $\text{up}$ 都不为 $0$ ，则表示这条边的方向是矛盾的，即不满足条件，输出 "NO"，否则若全部满足，则输出 "YES" 。

时间复杂度： $O(n + m + q\log(n))$ 。

#include <bits/stdc++.h>
using i64 = long long;

void solve() {
    int n, m, q;
    std::cin >> n >> m >> q;
    std::vector<std::vector<std::pair<int, int>>> v(n + 1);
    for(int i = 1; i <= m; ++i) {
        int x, y;
        std::cin >> x >> y;
        v[x].push_back({y, i});
        v[y].push_back({x, i});
    }
    std::vector<std::pair<int, int>> need(q);
    for(auto &[x, y] : need) {
        std::cin >> x >> y;
    }

    //求解边双连通分量
    std::vector<std::vector<int>> ecc(n + 1);
    std::vector<int> dfn(n + 1), low(n + 1), bel(n + 1);
    std::stack<int> stk;
    int cnt = 0, tot = 0;
    auto dfs = [&](auto self, int id, int lid) ->void {
        dfn[id] = low[id] = ++cnt;
        stk.push(id);
        for(const auto &[nxt, eid] : v[id]) {
            if(!dfn[nxt]) {
                self(self, nxt, eid);
                low[id] = std::min(low[id], low[nxt]);
            } else if(lid != eid) {
                low[id] = std::min(low[id], dfn[nxt]);
            }
        }
        if(dfn[id] == low[id]) {
            ++tot;
            while(true) {
                int num = stk.top();
                ecc[tot].push_back(num);
                bel[num] = tot;
                stk.pop();
                if(id == num) break;
            }
        }
    };
    for(int i = 1; i <= n; ++i) {
        if(!dfn[i]) {
            dfs(dfs, i, 0);
            //建立超级源点
            v[0].push_back({i, 0});
            v[i].push_back({0, 0});
        }
    }

    //缩点
    int nn = tot; 
    std::vector<std::vector<int>> g(nn + 1);
    for(int i = 0; i <= n; ++i) {
        for(const auto &[j, _] : v[i]) {
            if(bel[i] == bel[j]) continue;
            g[bel[i]].push_back(bel[j]);
        }
    }

    const int MAXN = std::__lg(nn);
    std::vector kfa(MAXN + 1, std::vector<int>(nn + 1));
    std::vector<int> dep(nn + 1);
    auto dfs1 = [&](auto self, int id, int lst) ->void {
        for(auto nxt : g[id]) {
            if(nxt == lst) continue;
            kfa[0][nxt] = id;
            dep[nxt] = dep[id] + 1;
            for(int i = 1; i <= MAXN; ++i) {
                kfa[i][nxt] = kfa[i - 1][kfa[i - 1][nxt]];
            }
            self(self, nxt, id);
        }
    };
    dfs1(dfs1, 0, -1);
    auto lca = [&](int x, int y) ->int {
        while(dep[x] != dep[y]) {
            if(dep[x] < dep[y]) {
                std::swap(x, y);
            }
            int k = std::__lg(dep[x] - dep[y]);
            x = kfa[k][x];
        }
        if(x == y) return x;
        for(int i = MAXN; i >= 0; --i) {
            if(kfa[i][x] != kfa[i][y]) {
                x = kfa[i][x];
                y = kfa[i][y];
            }
        }
        return kfa[0][x];
    };
  
    std::vector<int> upsum(nn + 1), downsum(nn + 1);
    for(const auto &[x, y] : need) {
        int xx = bel[x], yy = bel[y];
        if(xx == yy) continue;
        int p = lca(xx, yy);
        if(p == 0) {
            std::cout << "NO\n";
            return;
        } else {
            upsum[xx]++;
            upsum[p]--;
            downsum[yy]++;
            downsum[p]--;
        }
    }

    auto dfs3 = [&](auto self, int id, int lst) ->void {
        for(auto nxt : g[id]) {
            if(nxt == lst) continue;
            self(self, nxt, id);
            upsum[id] += upsum[nxt];
            downsum[id] += downsum[nxt];
        }
    };
    dfs3(dfs3, 0, -1);
    for(int i = 1; i <= nn; ++i) {
        if(upsum[i] > 0 && downsum[i] > 0) {
            std::cout << "NO\n";
            return;
        }
    }
    std::cout << "YES\n";
}

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

L-故障机器人的完美遗物

$\text{Tag}$ ：素数筛数论

记 $d(n)$ 表示 $n$ 的因子个数。

根据唯一分解定理 $n = \prod\limits_{i=1}^{k} p_i^{\alpha_i} \space (p_i \in \mathbb{P}, \alpha_i \in \mathbb{N^+})$ ，可以知道 $d(n) = \prod\limits_{i=1}^{k} (\alpha_i + 1)$ 。

因此对于一个数 $x$ ，如果分解后 $k \geq 2$ ，则 $d(x)$ 一定为多个大于 $1$ 的正整数的乘积，一定不是质数。

所以满足条件的 $x$ 一定为 $a^{b-1}\space (a,b \in \mathbb{P} \wedge b \neq 2)$ 的形式。

由于 $b - 1 \geq 2$ 且 $R \leq 10^{12}$ （其中 $R$ 表示数组的值域），则 $a \leq 10^{6}$ ，且 $b$ 不会超过 $41$ ，只需要预处理出 $[1, 10^6]$ 中的素数。直接枚举所有可能的 $a$ 和 $b$ ，记录符合条件的 $x$ 即可。

也可以利用满足条件的数一定是平方数的性质，对进行 $\sqrt x$ 质因数分解求出因子个数来进行判断。

时间复杂度： $O(n + \sqrt R)$ ，其中 $R$ 表示 $a_i$ 的值域。

#include <bits/stdc++.h>
using namespace std;
using u32 = uint32_t;
using i64 = long long;
using u64 = uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
constexpr i64 N = 1e6;
vector<int> pri;
vector<bool> not_prime;
void pre(int n) {
    not_prime.resize(n + 1);
    for (int i = 2; i <= n; ++i) {
        if (!not_prime[i]) {
            pri.push_back(i);
        }
        for (int pri_j : pri) {
            if (i * pri_j > n) {
                break;
            }
            not_prime[i * pri_j] = true;
            if (i % pri_j == 0) {
                break;
            }
        }
    }
}

void solve() {
    vector<bool> v(N + 1);
    for (const auto &x : pri) {
        for (i64 i = 2, y = 1ll * x * x; y <= N * N; i++, y *= x) {
            if (!not_prime[i + 1]) {
                v[sqrtl(y)] = true;
            }
        }
    }
    int n;
    cin >> n;
    i64 ans = 0;
    for (int i = 1; i <= n; i++) {
        i64 x;
        cin >> x;
        i64 sqx = sqrtl(x);
        if (sqx * sqx == x && v[sqx]) {
            ans += x;
        }
    }
    cout << ans << '\n';
    return;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    pre(N);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}