A Kaky 的 76 大学习

知识点：枚举、字符串、构造

只需要枚举 $76$ 的倍数。令 $cur$ 从 $76$ 开始，每次增加 $76$，先跳过位数小于 $n$ 的倍数，再检查所有位数等于 $n$ 的候选。对候选的十进制表示查找连续子串 $\texttt{76}$；首个没有该子串的数就是答案。枚举顺序覆盖了全部 $n$ 位正整数倍数，且正整数表示天然没有前导零。若扫描到位数超过 $n$ 仍未找到，则无解。

时间复杂度 $\mathcal{O}\left(\frac{n\cdot10^{n-1}}{76}\right)$。

void solve() {
    int n;
    cin >> n;
    int cur = 76;
    while (to_string(cur).size() < n) cur += 76;
    while (to_string(cur).size() <= n) {
        if (to_string(cur).find("76") == string::npos) return cout << "Yes\n" << cur << endl, void();
        cur += 76;
    }
    cout << "No" << endl;
}

当然，也可以直接输出答案，这里给出一组比较简单的构造方法。

void solve() {
    int n;
    cin >> n;
    if (n <= 2) cout << "No" << endl;
    else cout << "Yes\n152" + string(n - 3, '0') << endl;
}

B Kaky 的传送石碑

知识点：排序、贪心、最大化最小值

石碑坐标已经递增。目标点在第一个石碑左侧时，最远点是坐标 $1$，贡献为 $a_1-1$；在最后一个石碑右侧时，贡献为 $n-a_k$。对于相邻石碑 $a_i,a_{i+1}$ 之间的目标点，最近石碑距离在两端分别为 $0$，在中点附近达到最大值，因此该段的贡献是

$$\left\lfloor\frac{a_{i+1}-a_i}{2}\right\rfloor.$$

答案就是所有端点贡献和相邻间隔贡献的最大值，顺序扫描即可。

时间复杂度 $\mathcal{O}(k)$。

void solve() {
    int n, k, p;
    cin >> n >> k >> p;
    int ans = p - 1;
    for (int i = 1, x; i < k; ++i) cin >> x, ans = max(ans, x - p >> 1), p = x;
    ans = max(ans, n - p);
    cout << ans << endl;
}

C Kaky 的平面游走

知识点：可达性、曼哈顿距离、前缀状态

每次 $\texttt{N}$ 都相当于让每个障碍物的“可碰撞范围”向外扩张 $1$。因此，对障碍物 $(u,v)$ 而言，经过 $c$ 次 $\texttt{N}$ 后，它对应的可碰撞区域就是以它为中心、半径为 $c$ 的曼哈顿球：

$$|u-x|+|v-y|\le c.$$

若当前基准位置 $(x,y)$ 落入某个障碍物的曼哈顿球中，就能通过安排此前所有 $\texttt{N}$ 的移动，使 Kaky 恰好进入该障碍物，从而发生碰撞。反之，若不在球内，则 $c$ 次自由操作不足以补齐到该障碍物的曼哈顿距离，不可能撞到它。

因此，依次枚举每个指令前缀，维护 $(x,y)$ 和 $c$，扫描所有障碍物；第一次满足上述不等式时输出 $\texttt{Yes}$，否则输出 $\texttt{No}$。

时间复杂度 $\mathcal{O}(nk)$。

void solve() {
    int n, k;
    string s;
    cin >> n >> k >> s;
    vector<pii> p(k);
    for (auto &[u, v] : p) cin >> u >> v;
    int x = 0, y = 0, cnt = 0;
    for (auto c : s) {
        x += (c == 'D') - (c == 'U');
        y += (c == 'R') - (c == 'L');
        cnt += c == 'N';
        for (auto [u, v] : p)
            if (llabs(u - x) + llabs(v - y) <= cnt) return cout << "Yes" << endl, void();
    }
    cout << "No" << endl;
}

D Kaky 的竹林谜题

知识点：构造、排列、最短路下界

很容易想到向右 $n-1$ 次，并在某一列向下走 $1$ 次。那么我们只需要构造一行长度为 $\lfloor\frac{n}{2}\rfloor+1$ 路径就可以了。

不难想到，如果构造以 $2$ 为公因数的路径，长度是 $\lfloor\frac{n}{2}\rfloor$。我们再补一个数字就行了（这里选的是 $3$，用于连接的数字是 $6$ ，是额外数字最小的情况）。

所以由上面的推导，当 $n < 6$ 时，不存在 $6$ ，也就无法构建出路径。

时间复杂度 $\mathcal{O}(n)$。

void solve() {
    int n;
    cin >> n;
    if (n < 6) return cout << "No" << endl, void();
    cout << "Yes" << endl;
    vector<int> a;
    for (int i = 1; i <= n; i += 2) {
        if (i == 3) continue;
        a.push_back(i);
    }
    for (int i = 2; i <= n; i += 2) {
        if (i == 6) continue;
        a.push_back(i);
    }
    for (auto v : a) cout << v << " ";
    cout << endl;
    reverse(a.begin(), a.end());
    for (auto v : a) cout << v << " ";
    cout << endl;
}

补一个有点帅的写法

void solve() {
    int n;
    cin >> n;
    if (n < 6) return cout << "No" << endl, void();
    vector<int> a = {3, 6};
    for (auto v : views::iota(1LL, n + 1) | views::filter([&](int x) { return !(x & 1) && x != 6; })) a.push_back(v);
    for (auto v : views::iota(1LL, n + 1) | views::filter([&](int x) { return (x & 1) && x != 3; })) a.push_back(v);
    auto out = [&](auto a) { ranges::copy(a, ostream_iterator<int>(cout, " ")); };
    cout << "Yes" << endl;
    ranges::copy(a, ostream_iterator<int>(cout, " "));
    cout << endl;
    ranges::reverse(a);
    ranges::copy(a, ostream_iterator<int>(cout, " "));
    cout << endl;
}

E Kaky 的数组交换

知识点：不变量、置换、奇偶性

我们把 $a$ 和 $b$ 排成两排

$$\begin{array}{cccc}a_1 & a_2 & \cdots & a_n \\b_1 & b_2 & \cdots & b_n\end{array}$$

对于一次交换，每一列的元素不变，但是位置发生了变化。我们把每一列的元素看成一个块，那么一次交换就是交换两个块的位置，并把这两个块各自反向。

所以我们用 $\textrm{id}[x]$ 去记录每个元素的列号，用 $\textrm{side}[x]$ 去记录它在该列中是上方还是下方元素。

检查合法时，首先检查 $\textrm{id}[c_i]=\textrm{id}[d_i]$，否则两个数字原本不在同一列，永远无法组成这一列。若条件满足，我们只需要检查 $c,d$ 两行的反转块个数是否是偶数即可。

时间复杂度 $\mathcal{O}(n)$。

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n), d(n);
    for (auto &v : a) cin >> v;
    for (auto &v : b) cin >> v;
    for (auto &v : c) cin >> v;
    for (auto &v : d) cin >> v;
    vector<int> id(2 * n + 1), side(2 * n + 1);
    for (int i = 0; i < n; ++i) {
        id[a[i]] = id[b[i]] = i;
        side[a[i]] = 0, side[b[i]] = 1;
    }
    int rev = 0;
    for (int i = 0; i < n; ++i) {
        if (id[c[i]] != id[d[i]]) return cout << "No" << endl, void();
        rev ^= side[c[i]];
    }
    cout << (!rev ? "Yes" : "No") << endl;
}

F Kaky 的缤纷路径

知识点：桥、边双连通分量、Tarjan

转换一下题意，任意两点之间要有缤纷路径，等价于任意两点之间都有一条长度至少为 $2$ 的路径，且没有重复的边。

题目保证图连通。若两点不相邻，它们之间任取一条简单路径，长度自然至少为 $2$，且不会重复边。因此只需考虑相邻的两个点。设相邻点 $u,v$ 之间的边为 $e$。

若 $e$ 不是桥，则 $e$ 一定在某个环上。删去 $e$ 后，环的其余部分仍是一条从 $u$ 到 $v$ 的路径，长度至少为 $2$。
若 $e$ 是桥，则从 $u$ 到 $v$ 的缤纷路径必须恰好经过这条桥一次。若 $u$ 或 $v$ 在某个环上，可以先绕该环一圈，再经过桥，因此也能得到长度至少为 $2$ 的路径。
若 $e$ 是桥，且 $u,v$ 都不在任何环上，则无法满足条件。因为一旦经过桥，就不能再次经过它；想额外走边只能在 $u$ 或 $v$ 一侧绕回原点，这要求该端点所在某个环上，矛盾。

因此，当且仅当存在一条桥，其两个端点都不在任何环上，答案为 $\texttt{No}$ 。

时间复杂度 $\mathcal{O}(n+m)$。

struct EBCC {...} // 边双连通分量，返回bel为该点所属的边双连通分量编号，若一条边两个端点的bel不同，则该边为桥

void solve() {
    int n, m;
    cin >> n >> m;
    EBCC g(n);
    vector<pii> e;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        g.add(u, v);
        e.push_back({u, v});
    }
    auto bel = g.work();
    vector<pii> b, nb;
    for (auto [u, v] : e) (bel[u] == bel[v] ? nb : b).push_back({u, v});
    vector<int> inc(n);
    for (auto [u, v] : nb) inc[u] = inc[v] = 1;
    for (auto [u, v] : b)
        if (!inc[u] && !inc[v]) return cout << "No" << endl, void();
    cout << "Yes" << endl;
}

约定

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

#define int long long
#define pii array<int, 2>
#define endl "\n"

void solve() {
    
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cout << fixed << setprecision(20);
    int t = 1;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}

使用到的算法模板见 $\texttt{github}$ 仓库林月的XCPC模板库