非传统题目与算法综合题

常规的传统题目采用黑箱评测，让选手程序读入输入数据，将选手输出与输出数据全文比较或者采用 Special Judge 比较。但比赛中还有一些非传统题目。对于题目解法也有特殊的手段，比如随机化算法。当然，也可以尝试各种方法来乱搞。

把它们放在一起讲的另一个原因是它们之间有联系。

交互题

这是什么呢？大概就是说，你要写一个程序和计算机做游戏，选手程序向测评程序发出询问，并得到其反馈，最终要获取答案。

交互方式

交互方式是指交互题的实现方式，一般有两种。

Grader 交互

NOI、IOI 系列比赛的交互题均采用了 Grader 交互，通常不需要选手实现 main 函数，只需要实现特定的函数。它会下发一个 grader.cpp 文件^[1]，供选手检验自己的程序。

常规情况下你只需要在程序中引用一个头文件（题目会给定），但是常用 OJ 洛谷的交互方式比较奇怪，请参考题目说明（都会说明的）。

模板，代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

extern "C" int Seniorious(int);

extern "C" int Chtholly(int n, int c) {
    int L = 0, R = n + 1;
    while (L + 1 != R) {
        int mid = L + R >> 1;
        if (Seniorious(mid) == 1) R = mid;
        else L = mid; 
    }
    return L;
}

STDIO 交互

Codeforces 和 ATCoder 采用的都是这种交互方式，ICPC 系列比赛中也是。这种类型可以正常编写程序，只需要刷新缓冲区就可以从标准输入读取结果。C++ 的刷新方式有两种：调用 fflush(stdout) 或者输出一个 endl。

模板，代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

int main(void) {
    int L = 0, R = 1e9 + 1;
    while (L + 1 != R) {
        int mid = L + R >> 1, t;
        printf("%d\n", mid); fflush(stdout);
        scanf("%d", &t);
        if (t == 0) return printf("%d\n", mid), 0;
        else if (t == 1) R = mid;
        else L = mid;
    }
    return 0;
}

注意，当你的交互方式有问题时，可能会获得 Idleness limit exceeded（ILE，懒惰超过限制）的评测结果。

简单交互题

我们来看几道简单的交互题，交互题的具体方法请见构造一节。

[CF843B] Interactive LowerBound

Portal.

由于完全不知道链表的构造，因此唯一的逼近方式就是随机撒点，找出一个最大的小于 $x$ 的然后开始暴力找。

查看代码

#include <bits/stdc++.h>
using namespace std;
mt19937 Rand(time(0)); 

int n, start, x, m, ans = -1, p;
int a[50005];

int main(void) {
    scanf("%d%d%d", &n, &start, &x); m = min(1000, n); p = start; 
    printf("? %d\n", p); fflush(stdout); 
    int val, nxt; scanf("%d%d", &val, &nxt); ans = val; 
    for (int i = 1; i <= n; ++i) a[i] = i; 
    shuffle(a + 1, a + n + 1, Rand);
    for (int i = 1; i <= m; ++i) {
        printf("? %d\n", a[i]); fflush(stdout); 
        int val, nxt; scanf("%d%d", &val, &nxt);
        if (val < x && val > ans) ans = val, p = a[i];
    }
    while (p != -1 && ans < x) {
        printf("? %d\n", p); fflush(stdout); 
        int val, nxt; scanf("%d%d", &val, &nxt);
        ans = val; p = nxt;
    }
    printf("! %d\n", ans < x ? -1 : ans);
    return 0;
}

[CF1592D] Hemose in ICPC ?

Portal.

给定一棵树，但是不知道边权。定义距离 $d(u,v)$ 为路径上的边权的 $\gcd$ 。你可以询问交互库一个点集，交互库会回答这些点两两点对的距离的最大值。你最多可以询问交互库 $12$ 次，要找出 $d(u,v)$ 最大的 $(u,v)$ 。可以输出任意一组解， $2\le n\le 10^3$ 。

可以发现距离定义为 $\gcd$ ，那么最大距离就相当于找出最大边权。

首先询问一次所有点来找出最大的边权，叫做答案。对树进行一次 dfs，求出遍历的顺序，这样每两个树上相邻的点都可以在序列中找到。我们对序列进行二分，最大值等于答案的那一半就是答案出现的地方。这样就可以求出点对了。

查看代码

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

int n, maxx, a[2005], tot = 0;
vector<int> G[1005];

void dfs(int x, int fa) {
    a[++tot] = x;
    for (int y : G[x]) if (y != fa) {
        dfs(y, x);
        a[++tot] = x;
    }
}

int p[1005];
int check(int L, int R) {
    memset(p, 0, sizeof(p)); int cnt = 0;
    for (int i = max(0, L); i <= R; ++i) p[a[i]] = true;
    for (int i = 1; i <= n; ++i) if (p[i]) ++cnt;
    printf("? %d ", cnt);
    for (int i = 1; i <= n; ++i) if (p[i]) printf("%d ", i);
    cout << endl;
    int t; scanf("%d", &t); return t;
}

int main(void) {
    scanf("%d", &n);
    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d%d", &u, &v); 
        G[u].emplace_back(v), G[v].emplace_back(u);
    }
    printf("? %d ", n); for(int i = 1; i <= n; ++i) printf("%d ", i); 
    cout << endl; scanf("%d", &maxx); dfs(1, 0);
    int L = 1, R = tot;
    while (L + 1 != R) {
        int mid = L + R >> 1;
        if (check(L, mid) != maxx) L = mid;
        else R = mid;
    }
    int x = a[L], y = a[R];
    printf("! %d %d\n", a[L], a[R]);
    return 0;
}

构造与交互

构造题是指构造满足题目要求的答案，是一种~~考察选手智力的~~非传统题目。虽然交互题是交互，但有些交互就是构造方案，因此这里有的方法会出现一些交互题。

另外，很多些题目可能没有特别的办法，需要发挥“人类智慧”，也就是 Ad-Hoc 类题目，可能需要从多个角度思考并发挥自己的想象力。

鸽笼原理

在构造时，如果遇到了 $n\div k$ 的限制操作次数，可以考虑将所有数划分为 $k$ 个集合，这样最小的那个集合就一定小于等于 $n\div k$ 。

[CF1198C] Matching vs Independent Set

Portal.

我们暴力查找边的独立集，如果最后独立集中有 $x$ 条边，那么点的独立集至少有 $3n-2x$ 个点，这两个至少有一个 $\ge n$ 。

查看代码

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

int n, m;
bool a[300005];

int main(void) {
    int T; scanf("%d", &T); while (T--) {
        scanf("%d%d", &n, &m); fill(a + 1, a + n * 3 + 1, 0); vector<int> ans; 
        for (int i = 1; i <= m; ++i) {
            int u, v; scanf("%d%d", &u, &v);
            if (!a[u] && !a[v]) a[u] = a[v] = 1, ans.emplace_back(i);
        }
        if (ans.size() >= n) {
            puts("Matching");
            for (int i = 0; i < n; ++i) printf("%d ", ans[i]); 
        } else {
            puts("IndSet");
            for (int i = 1, cnt = 0; i <= n * 3 && cnt < n; ++i)
                if (!a[i]) printf("%d ", i), ++cnt; 
        }
        putchar('\n');
    }
    return 0;
}

[CF1534D] Lost Tree

Portal.

令这棵树的根为 $1$ ，先求出所有点的深度，深度为奇数的和深度为偶数的点的个数中至少有一个不大于 $n\div 2$ ，因此询问那个小的，所有距离为 $1$ 的点对间都有一条边。

查看代码

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

int n, dep[2005], c[2]; 
vector<pair<int, int>> e;

int main(void) {
    scanf("%d", &n); puts("? 1"); fflush(stdout); 
    for (int i = 1; i <= n; ++i) scanf("%d", dep + i), ++c[dep[i] & 1];
    if (c[1] < c[0]) {
        for (int i = 1; i <= n; ++i) if (dep[i] & 1) {
            printf("? %d\n", i); fflush(stdout); 
            for (int j = 1, x; j <= n; ++j) {
                scanf("%d", &x); 
                if (x == 1) e.emplace_back(i, j);
            }
        }
    } else {
        for (int i = 1; i <= n; ++i) if (dep[i] == 1) e.emplace_back(1, i); 
        for (int i = 2; i <= n; ++i) if (!(dep[i] & 1)) {
            printf("? %d\n", i); fflush(stdout); 
            for (int j = 1, x; j <= n; ++j) {
                scanf("%d", &x); 
                if (x == 1) e.emplace_back(i, j);
            }
        }
    }
    puts("!"); for (auto [u, v] : e) printf("%d %d\n", u, v);
    return 0;
}

[CF1450C2] Errich-Tac-Toe

Portal.

根据坐标 $(x+y)\bmod 3$ 将格子分成三类，只需要将其中两类分别改成 X，O 就能满足条件。这样总修改次数是 $k$ ，最小的修改次数必定 $\le \left\lfloor\frac{k}{3}\right\rfloor$

查看代码

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

int n, k1, k2, k3; 
char a[305][305]; 
char a1[305][305], a2[305][305], a3[305][305]; 

void print(char s[][305]) {
    for (int i = 1; i <= n; ++i) printf("%s\n", s[i] + 1); 
}

void solve(void) {
    scanf("%d", &n); k1 = k2 = k3 = 0; 
    for (int i = 1; i <= n; ++i) scanf("%s", a[i] + 1);
    memcpy(a1, a, sizeof(a)); memcpy(a2, a, sizeof(a)); memcpy(a3, a, sizeof(a));
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            int t = (i + j) % 3; 
            if (t == 0) {
                if (a[i][j] == 'O') a1[i][j] = 'X', ++k1;
                if (a[i][j] == 'X') a3[i][j] = 'O', ++k3; 
            } else if (t == 1) {
                if (a[i][j] == 'O') a2[i][j] = 'X', ++k2; 
                if (a[i][j] == 'X') a1[i][j] = 'O', ++k1; 
            } else {
                if (a[i][j] == 'O') a3[i][j] = 'X', ++k3; 
                if (a[i][j] == 'X') a2[i][j] = 'O', ++k2; 
            }
        }
    if (k1 <= k2 && k1 <= k3) print(a1);
    else if (k2 <= k3 && k2 <= k1) print(a2); 
    else print(a3);  
}

int main(void) {
    int T; scanf("%d", &T); while (T--) solve();
    return 0;
}

问题化简 | [CF618F] Double Knapsack

Portal.

给定两个长度为 $n(n\le 10^6)$ 的序列 $A,B$ ，当中每个元素都在 $[1,n]$ 中。请分别选出 $A,B$ 的一个子序列，使得这两个子序列的元素之和相等，无解输出 $-1$ 。

本题会初步告诉你什么叫做“人类智慧”。

事实上，一定有解，而且不需要找子序列，找子段就可以了。

怎么想的？~~我也不知道~~。事实上，构造题有一种解法是主动加强条件来减少决策量，尽量简化问题。当然，也可以考虑弱化条件（绝对值拆开， $\max(x,y)$ 改成主动选择是 $x$ 或 $y$ ）。

现在我们来证明为什么只需要找子段就有解。设原序列为 $a,b$ ，其前缀和序列为 $A,B$ ，并令 $A[n]\le B[n]$ （反之同理）。

定义 $j_i$ 代表满足 $A[i]\ge B[j_i]$ 的最大数，那么 $A[i]<B[j_i]+b[j_i+1]\Rightarrow A[i]-B[j_i]<b[j_i+1]\Rightarrow 0\le A[i]-B[j_i]<n$ ，有 $n$ 种取值，但是这个下标有 $0\sim n$ 共 $n+1$ 种取值。根据鸽笼原理， $A[i]-B[j_i]$ 一定有一组相等的。

找出这个 $A[p_0]-B[q_0]=A[p_1]-B[q_1]\Rightarrow A[p_1]-A[p_0]=B[p_1]-B[p_0]$ ，直接输出就好。

查看代码

#include <bits/stdc++.h>
#define i64 long long

using namespace std;

int n;
int a[1000005], b[1000005];
i64 A[1000005], B[1000005];
int j[1000005], cnt[1000005];

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), A[i] = A[i - 1] + a[i];
    for (int i = 1; i <= n; ++i) scanf("%d", b + i), B[i] = B[i - 1] + b[i];
    int is_swap = 0;

    if (A[n] > B[n]) {
        for (int i = 1; i <= n; ++i) swap(a[i], b[i]), swap(A[i], B[i]);
        is_swap = 1;
    }

    for (int i = 0, q = 0; i <= n; ++i) {
        while (q < n && B[q + 1] <= A[i]) ++q;
        j[i] = q;
    }

    int finder = -1, p[2], q[2];
    for (int i = 0; i <= n; ++i) {
        if (cnt[A[i] - B[j[i]]]) {
            finder = A[i] - B[j[i]]; p[1] = i, q[1] = j[i];
            break;
        }
        ++cnt[A[i] - B[j[i]]];
    }

    for (int i = 0; i <= n; ++i)
        if (A[i] - B[j[i]] == finder) {
            p[0] = i, q[0] = j[i];
            break;
        } 
    if (is_swap) swap(p[0], q[0]), swap(p[1], q[1]);

    cout << p[1] - p[0] << "\n";
    for (int i = p[0] + 1; i <= p[1]; ++i) printf("%d ", i);
    putchar('\n');
    cout << q[1] - q[0] << "\n";
    for (int i = q[0] + 1; i <= q[1]; ++i) printf("%d ", i);
    putchar('\n');

    return 0;
}

归纳法

考虑找到有解的充要条件来判掉无解，然后将原文题转化成规模减一的一定有解的子问题。

[CF1470D] Strange Housing

Portal.

$n=1$ 时一定有解，而且染不染都无所谓，我们可以将所有染色状况取反。

若 $n-1$ 有解，则考虑将点 $n$ 加入。如果点 $n$ 连接的点都没有被染色那么它必须染色，否则不能染色。

最后如果有点没有加入，那么是无解的。

查看代码

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

int n, m; 
bool v[300005];
int tag[300005]; // -1 未遍历，0 不染，1 染
vector<int> G[300005]; 
queue<int> q; 

void solve(void) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) G[i].clear(), v[i] = 0, tag[i] = -1;
    while (!q.empty()) q.pop();
    while (m--) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].emplace_back(v); G[v].emplace_back(u);
    }
    q.emplace(1); v[1] = 1; tag[1] = 1; 
    while (!q.empty()) {
        int x = q.front(); q.pop();
        bool flag = true; 
        for (int y : G[x]) if (tag[y] != -1) flag &= !tag[y]; 
        tag[x] = flag; 
        for (int y : G[x]) if (!v[y]) v[y] = 1, q.emplace(y); 
    }
    for (int i = 1; i <= n; ++i) if (!v[i]) return puts("NO"), void(); 
    puts("YES"); int ans = 0; 
    for (int i = 1; i <= n; ++i) ans += tag[i];
    printf("%d\n", ans);
    for (int i = 1; i <= n; ++i) if (tag[i]) printf("%d ", i); 
    putchar('\n');
}

int main(void) {
    int T; scanf("%d", &T); 
    while (T--) solve();
    return 0;
}

[CF1515F] Phoenix and Earthquake

Portal.

首先图必须连通，点权之和需要大于等于 $x(n-1)$ ，否则必定无解。

可以证明任意一棵生成树都是有解的，证明：

若 $a_u\ge x$ ，那么直接修建和它父亲的边，这样仍然满足条件；
$a_u<x$ ，修建了之后点权之和的减小量小于 $x$ ，这样只需要最后修建这个即可。

查看代码

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

int n, m, x; i64 a[300005], sum; 
int fa[300005], ans[300005], tot1, tot2;
int find(int x) { if (fa[x] == x) return x; return fa[x] = find(fa[x]); }
pair<int, int> e[300005]; 
vector<pair<int, int>> G[300005]; 

void dfs(int u, int fa, int id) {
    for (auto [v, p] : G[u]) if (v != fa) dfs(v, u, p);
    if (u == 1) return; 
    if (a[u] >= x) a[fa] += a[u] - x, ans[++tot1] = id;
    else ans[--tot2] = id; 
}

int main(void) {
    scanf("%d%d%d", &n, &m, &x); tot2 = n; 
    for (int i = 1; i <= n; ++i) scanf("%lld", a + i), fa[i] = i, sum += a[i]; 
    if (sum < 1ll * (n - 1) * x) return puts("NO"), 0; 
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &e[i].first, &e[i].second);
        if (find(e[i].first) == find(e[i].second)) continue; 
        fa[find(e[i].first)] = find(e[i].second); 
        G[e[i].first].emplace_back(e[i].second, i);
        G[e[i].second].emplace_back(e[i].first, i);
    }
    for (int i = 1; i <= n; ++i) if (find(i) != find(1)) return puts("NO"), 0; 
    puts("YES"); dfs(1, 0, 0); 
    for (int i = 1; i < n; ++i) printf("%d\n", ans[i]); 
    return 0;
}

[ARC122E] Increasing LCMs

Portal.

考虑归纳构造。

$n=1$ 时显然成立。

对于 $n>1$ ，我们考虑找出这个序列的最后一个数。这最后一个数需要满足前面数的 $\operatorname{lcm}$ 不是它的倍数，也就是说 $\gcd(\operatorname{lcm}_{j\ne i}\{a_j\},a_i)<a_i$ 。这个式子相当于 $\operatorname{lcm}_{j\ne i}\{\gcd(a_j,a_i)\}<a_i$ ，这样就可以转化为规模为 $n-1$ 的问题。

由于 $\operatorname{lcm}$ 随着问题规模的减小不会上升，可以放在最后一个的 $a$ 越来越多，因此找到一个就放入答案不会使少掉可能的解。因此如果找不到这最后一个 $a$ 就无解。

时间复杂度 $O(n^3\log V)$ 。

查看代码

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

int n; 
vector<i64> ans; 

i64 gcd(i64 x, i64 y) { if (y == 0) return x; return gcd(y, x % y); }
i64 lcm(i64 x, i64 y) { return x / gcd(x, y) * y; }

void solve(vector<i64> a) {
    if (a.size() == 1) return ans.emplace_back(a[0]), void(); 
    for (int i = 0; i < a.size(); ++i) {
        bool flag = 1; i64 l = 1;
        for (int j = 0; j < a.size(); ++j) if (i != j) l = lcm(l, gcd(a[j], a[i])); 
        if (l < a[i]) {
            ans.emplace_back(a[i]); 
            vector<i64> tmp; 
            for (int j = 0; j < a.size(); ++j) if (i != j) tmp.emplace_back(a[j]);
            solve(tmp); return; 
        }
    }
}

int main(void) {
    cin >> n; vector<i64> a(n); 
    for (int i = 0; i < n; ++i) cin >> a[i]; 
    solve(a); 
    if (ans.size() != n) puts("No"); 
    else {
        puts("Yes"); 
        reverse(ans.begin(), ans.end()); 
        for (i64 x : ans) cout << x << ' '; 
        cout << '\n'; 
    }
    return 0;
}

[CF963B] Destruction of a Tree

Portal.

$n$ 为偶数时度数是不对的，奇数时考虑归纳构造。

找一个 DFS 序最小的来杀，这样可以将原问题分裂成规模更小的子问题。

查看代码

#include <bits/stdc++.h>
#define pii pair<int, int> 
using namespace std;

int n, root, deg[200005]; 
int f[200005];  
int st[200005], tot; 
bool del[200005]; 
vector<int> G[200005], ans; 

void dfs(int x) {
    st[++tot] = x; 
    for (int y : G[x]) if (y != f[x]) dfs(y); 
}
void dfs2(int x) {
    del[x] = 1; ans.emplace_back(x); 
    for (int y : G[x]) {
        --deg[y]; 
        if (y == f[x] || del[y]) continue; 
        if (deg[y] % 2 == 0) dfs2(y); 
    }
}

int main(void) {
    scanf("%d", &n); 
    for (int i = 1; i <= n; ++i) {
        scanf("%d", f + i); 
        if (!f[i]) root = i; 
        else {
            ++deg[i]; ++deg[f[i]]; 
            G[i].emplace_back(f[i]); G[f[i]].emplace_back(i); 
        }
    } dfs(root); 
    while (tot) {
        int u = st[tot--]; 
        if (deg[u] % 2 == 0) dfs2(u); 
    }
    if (ans.size() == n) {
        puts("YES"); 
        for (int x : ans) printf("%d\n", x); 
    } else puts("NO"); 
    return 0;
}

DFS 树

DFS 树可以处理一些与图论相关的问题。

[CF1364D] Ehab’s Last Corollary

Portal.

找环！如果环的大小 $\le k$ 可以直接输出，否则就在环上每隔一个点输出一个来输出独立集。当然图有可能是树，要判掉。

查看代码

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

int n, m, k, S, T, mx = 1e9; 
int dep[100005], cnt[100005]; 
vector<int> G[100005], ans; 

void dfs(int x) {
    ans.emplace_back(x); 
    dep[x] = ans.size(); 
    for (int y : G[x]) {
        if (!dep[y]) dfs(y); 
        if (dep[y] < dep[x] - 1) { // 回到非爸爸祖先，或者是
            int t = dep[x] - dep[y] + 1; 
            if (t <= k) {
                printf("2\n%d\n", t); 
                for (int i = dep[y] - 1; i <= dep[x] - 1; ++i) printf("%d ", ans[i]); 
                putchar('\n'); 
                exit(0); 
            }
            if (t <= mx) {
                mx = t; 
                S = x; T = y; 
            }
        }
        
    }
    ans.pop_back(); 
}

void print(int x) {
    ans.emplace_back(x); 
    dep[x] = ans.size(); 
    if (x == T) {
        puts("1"); 
        for (int i = 0; i < k; i += 2) printf("%d ", ans[i]);
        putchar('\n'); 
    }
    for (int y : G[x]) {
        if (x == S && y == T) continue; 
        if (!dep[y]) print(y); 
    }
    ans.pop_back(); 
}

int col[100005]; 
vector<int> res[2]; 
void dfs2(int x) {
    res[col[x]].emplace_back(x); 
    for (int y : G[x]) if (col[y] == -1) {
        col[y] = !col[x]; 
        dfs2(y); 
    }
}

int main(void) {
    scanf("%d%d%d", &n, &m, &k); 
    while (m--) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].emplace_back(v); G[v].emplace_back(u);  
    } dfs(1); 
    if (S) return memset(dep, 0, sizeof dep), print(S), 0; 
    memset(col, -1, sizeof col); col[1] = 0; int t = (k + 1) / 2; dfs2(1);
    puts("1"); 
    if (res[0].size() >= t) {
        for (int i = 0; i < t; ++i) printf("%d ", res[0][i]);
        putchar('\n'); 
    } else {
        for (int i = 0; i < t; ++i) printf("%d ", res[1][i]);
        putchar('\n'); 
    }
    return 0;
}

与图论相关的问题

最优化问题

二进制分组

调整法

提交答案题

很谔谔的一类题目。正常的题目是黑箱评测，但是提交答案题会将输入数据下发给你（但是在 Problemset 中有更离谱的！），然后让你求出输出，直接提交。

通常以下类型的数据点会被组合成提交答案题：

可以被手玩或者超级大暴力解出来的数据点；
特殊构造的数据点，可以使用特别的解法；
需要使用乱搞方法解决的数据点。

这种题如果出现一般就很离谱，我们来看几道相对正常的。

不是那么离谱的题

很正常的题。

[eJOI2018] 互素树

Portal.

由于题目中保证存在 $X=0$ ，随机一个排列然后按照条件贪心往树里填都是很容易出解的，因此直接随机化加贪心即可。

查看代码

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

int n, id[100005], a[100005], tmp[100005], res; 
vector<int> G[100005]; 
mt19937 Rand(time(0)); 
set<int> s; 

int gcd(int x, int y) {
    if (y == 0) return x; 
    return gcd(y, x % y); 
}

void dfs(int x, int fa) {
    if (res) return; 
    for (int i : s) if (!fa || gcd(tmp[fa], id[i]) == 1) { // 给当前点填数
        tmp[x] = id[i]; s.erase(i); 
        break; 
    }
    if (!tmp[x]) return ++res, void(); 
    for (int y : G[x]) if (y != fa) dfs(y, x); 
}

int main(void) {
    int T; scanf("%d", &T); 
    while (T--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i) {
            vector<int> tmp; 
            G[i].swap(tmp); id[i] = i; 
        }
        for (int i = 1; i < n; ++i) {
            int u, v; scanf("%d%d", &u, &v); 
            G[u].emplace_back(v), G[v].emplace_back(u); 
        }
        int ans = n; 
        for (int op = 1;; ++op) {
            shuffle(id + 1, id + n + 1, Rand); s.clear(); 
            for (int i = 1; i <= n; ++i) tmp[i] = 0, s.insert(i); 
            res = 0; dfs(1, 0); 
            if (res < ans) {
                ans = res; 
                for (int i = 1; i <= n; ++i) a[i] = tmp[i]; 
            }
            if (!ans) break; 
        }
        for (int i = 1; i <= n; ++i) printf("%d ", a[i]); putchar('\n'); 
    }      
    return 0;
}

[JRKSJ R2] Dark Forest

Portal.

$O(1)$ 计算交换位置的贡献，然后随机接受时把答案也给接受了就行（因为方案不好存储）。注意特判 #3。

查看代码

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

int n, p[1005]; 
i64 a[1005], ans; 
mt19937 Rand(time(0)); 

inline int rndint(int l, int r) { return uniform_int_distribution<>(l, r)(Rand); }
inline double rnddb(double l, double r) { return uniform_real_distribution<>(l, r)(Rand); }

inline int P(int x) {
    if (x <= 0) return x + n; 
    if (x > n) return x - n; 
    return x; 
}
void calc(int x, int y) { // 将 p[x] 赋值为 y 时答案改变
    int A = p[P(x - 2)], B = p[P(x - 1)], &C = p[x], D = p[P(x + 1)], E = p[P(x + 2)]; 
    ans -= (B * a[A] * a[B] + C * a[B] * a[D] + D * a[D] * a[E]) * a[C]; 
    C = y; 
    ans += (B * a[A] * a[B] + C * a[B] * a[D] + D * a[D] * a[E]) * a[C]; 
}

void SA(double T, const double ET, const double delta) {
    for (int i = 1; i <= n; ++i) calc(i, i); 
    while (T > ET) {
        int x = rndint(1, n), y = rndint(1, n), px = p[x], py = p[y]; 
        i64 tmp = ans; calc(x, py); calc(y, px); 
        if (ans <= tmp && exp((ans - tmp) / T) < rnddb(0, 1)) // 回退答案
            ans = tmp, swap(p[x], p[y]); 
        T *= delta; 
    }
    cerr << "ans = " << ans << "\n"; 
    for (int i = 1; i <= n; ++i) printf("%d ", p[i]); 
    putchar('\n');  
}

int main(void) {
    scanf("%d", &n); 
    for (int i = 1; i <= n; ++i) scanf("%lld", a + i); 
    return SA(1e15, 1e-15, 0.99999), 0; 
}

Problemset

Problemset 不倒，陪你到老！

简单构造

都非常的有趣！

[CF1278E] Tests for problem D

Portal.

使用如下的构造方式：对于一个节点 $x$ 的所有儿子 $y$ 都在右边和 $x$ 相交，并且互相包含，父亲则在左边和 $x$ 相交。

显然是对的，如何构造呢？计算当前线段的右端点会到哪里，然后让儿子的左端点从右端点开始从右往左排，并递归遍历即可。

查看代码

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

int n, l[500005], r[500005], num; 
vector<int> G[500005]; 

void dfs(int x, int fa) {
    num += G[x].size() + (fa == 0); r[x] = num; 
    int cnt = 1; 
    for (int y : G[x]) if (y != fa) {
        l[y] = r[x] - cnt; ++cnt; 
        dfs(y, x); 
    }    
}

int main(void) {
    scanf("%d", &n); num = 1; 
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v); 
        G[u].emplace_back(v); G[v].emplace_back(u); 
    } l[1] = 1; dfs(1, 0); 
    for (int i = 1; i <= n; ++i) printf("%d %d\n", l[i], r[i]); 
    return 0; 
}

深入分析问题

挖掘题目的性质，根据此设计解法。此类问题的思维难度可能会很大。

[NOIP2022] 喵了个喵

Portal.

$k=2n-2$ 显然是好做的，我们留一个空栈，如果来的牌与栈顶有相同就消除，否则就与栈底相同，放到空栈来消除栈底。

现在来看多的那种牌怎么安放。如果下一张牌是它自己那么随便找一个位置放，如果下一张牌是一个栈底牌那么把它放到那个栈上，然后消掉栈底它就成为了新的栈顶。

而如果下一张牌是栈顶牌呢？谔谔的事情发生了，似乎不能简单处理。我们将空栈设为 $sp$ ，当前这个神秘的牌为 $x$ 。不像羊了个羊，这题中我们可以看到后面所有的牌。我们找到下一个 $x$ 或栈底元素 $b$ （看哪个先出现）。

找到了 $x$ ！将 $x$ 加入空栈，由于接下来还没有栈底元素进来，因此不需要这个空栈干活。期间出现的所有栈顶元素都可以直接消掉。
没有 $x$ $x$ ，悲。设这个栈底元素 $b$ $b$ 对应的栈顶元素为 $t$ $t$ 。
- 这个 $t$ 在 $b$ 之前出现了奇数次，那么将 $x$ 加入 $sp$ ，处理完之后会发现 $t$ 被消掉了，这样 $b$ 放进去即可。这样会发现其成为了新的空栈。
- 这个 $t$ 在 $b$ 之前出现了偶数次，则将 $x$ 放入 $b$ 所在的栈。这样我们可以在 $sp$ 将 $t$ 杀干净（甚至不用空栈，在原来的栈上方也可），然后 $b$ 来了，消掉栈底， $t$ 就成为了栈底，而 $x$ 成为了新的栈顶。

实现也是个问题，上述过程可能细节很多，我们需要一个高效的实现（因为数据不小）。记录一下每个数在栈的位置位于的编号，每个栈的值。并且注意多测清空。

这样可以做到 $O(n+m)$ 。

查看代码

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

int n, m, k, a[2000005]; 
int up[605], down[605]; // 元素作为栈顶、栈底，栈的编号
int val[605][2], siz[605]; // 栈 x 上面(0)和下面(1)的元素
int cnt[605]; // 记录卡牌出现次数
vector<pair<int, int>> ans; 
vector<int> L; 

void solve(void) {
    for (int i = 1; i < n; ++i) L.emplace_back(i); 
    int sp = n; // 空栈
    for (int l = 1, r = 0; l <= m; l = r + 1) {
        r = l; int i = l; 
        if (down[a[i]]) { // 有 a[i] 作为栈底
            int u = down[a[i]]; 
            ans.emplace_back(sp, 0); ans.emplace_back(sp, u);
            if (siz[u] == 2) {
                int v = val[u][0]; siz[u] = 1; 
                val[u][1] = val[u][0]; val[u][0] = 0; 
                down[v] = u; up[v] = 0; 
                L.emplace_back(u); 
            } else {
                siz[u] = 0; 
                val[u][1] = 0; 
            }
            down[a[i]] = 0; 
        } else if (up[a[i]]) { // 作为栈顶
            int u = up[a[i]]; ans.emplace_back(u, 0); 
            up[a[i]] = 0; siz[u] = 1; val[u][0] = 0; 
            L.emplace_back(u);
        } else if (!L.empty()) { // 还有空栈
            int u = L.back(); L.pop_back(); 
            ans.emplace_back(u, 0); 
            if (siz[u] == 0) {
                siz[u] = 1; 
                val[u][1] = a[i]; down[a[i]] = u; 
                L.emplace_back(u); 
            } else {
                siz[u] = 2; 
                val[u][0] = a[i]; up[a[i]] = u; 
            }
        } else { // 谔谔，此时一定除了空栈全满，并且当前是谔谔牌
            while (r + 1 <= m) {
                ++r; 
                if (a[r] == a[i]) { // 找到了 x！
                    ans.emplace_back(sp, 0); 
                    for (int j = l + 1; j < r; ++j) ans.emplace_back(up[a[j]], 0); 
                    for (int j = l + 1; j < r; ++j) if (up[a[j]] && cnt[up[a[j]]]) {
                        int u = up[a[j]]; cnt[u] = 0; 
                        up[a[j]] = 0; siz[u] = 1; val[u][0] = 0; 
                        L.emplace_back(u); 
                    }
                    ans.emplace_back(sp, 0); 
                    break; 
                }
                if (down[a[r]]) { // 这是个栈底，悲
                    int u = down[a[r]]; 
                    if (cnt[u]) ans.emplace_back(sp, 0);
                    else ans.emplace_back(u, 0);  

                    for (int j = l + 1; j < r; ++j) ans.emplace_back(up[a[j]], 0); 
                    for (int j = l + 1; j < r; ++j) if (up[a[j]] && cnt[up[a[j]]] && up[a[j]] != u) {
                        int u = up[a[j]]; cnt[u] = 0; 
                        up[a[j]] = 0; siz[u] = 1; val[u][0] = 0; 
                        L.emplace_back(u); 
                    }

                    if (cnt[u]) {
                        ans.emplace_back(u, 0); cnt[u] = 0; 

                        down[val[u][1]] = up[val[u][0]] = 0; 
                        val[u][1] = val[u][0] = 0; 
                        down[a[l]] = sp; val[sp][1] = a[l]; siz[sp] = 1; 

                        L.emplace_back(sp); sp = u; 
                    } else {
                        ans.emplace_back(sp, 0); ans.emplace_back(sp, u); 

                        down[val[u][1]] = 0; 
                        up[val[u][0]] = 0; down[val[u][0]] = u; 
                        up[a[l]] = u;

                        val[u][1] = val[u][0]; val[u][0] = a[l];
                        siz[u] = 2; 
                    }

                    break; 
                }
                cnt[up[a[r]]] ^= 1; 
            }
        }
    }
}

int main(void) {
    int T; scanf("%d", &T); 
    while (T--) {
        scanf("%d%d%d", &n, &m, &k); 
        for (int i = 1; i <= m; ++i) scanf("%d", a + i); 
        L.clear(); ans.clear(); memset(down, 0, sizeof down); memset(up, 0, sizeof up); memset(val, 0, sizeof val); memset(siz, 0, sizeof siz); memset(cnt, 0, sizeof cnt);
        solve(); 
        printf("%d\n", ans.size()); 
        for (auto [x, y] : ans)
            if (!y) printf("1 %d\n", x); 
            else printf("2 %d %d\n", x, y); 
    }
    return 0;
}

[eJOI2018] 循环排序

Portal.

实际上可以套路地分析。

弱化题目条件。最优解？我不管！我们可以只交换两个数，但是这样还是很难办，数没有放的唯一位置，那么就先做排列！

观察样例。比如样例 $5$ ，它合并了两个操作，但是后面多出了一个操作。手玩后发现操作是可以合并的，但是最后要多出来一个长度为合并的操作数的操作。

现在考虑怎么将这个做法扩展到可以重复的数上。排列给了什么便利？每个点的入度出度都为 $1$ ，但如果它不是排列，它只会满足入度出度相等。

可以使用有向图的方式刻画这个过程：将 $a_i$ 的最终位置向 $a_i$ 连边，然后在这个图上找环，并且每条边经过恰好一次。这是欧拉路！在存边的时候记录一下 $i$ ，因为这就是方案。

查看代码

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

int n, s, m; 
int a[200005], b[200005], to[200005]; 
bool vis[200005]; 
vector<pair<int, int>> G[200005];
vector<bool> ban[200005]; 
vector<vector<int> > ans; 
vector<int> road; int cur[200005]; 

void dfs(int x) {
    vis[x] = 1; 
    for (; cur[x] < G[x].size(); ++cur[x]) if (!ban[x][cur[x]]) {
        int y = G[x][cur[x]].first, w = G[x][cur[x]].second; 
        ban[x][cur[x]] = 1; 
        dfs(y); road.emplace_back(w); 
    }
}

int main(void) {
    scanf("%d%d", &n, &s);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), b[i] = a[i];
    sort(b + 1, b + n + 1); int nn = unique(b + 1, b + n + 1) - (b + 1);  
    for (int i = 1; i <= n; ++i) to[i] = a[i] = lower_bound(b + 1, b + nn + 1, a[i]) - b;
    sort(to + 1, to + n + 1); // to 为最终的 a
    for (int i = 1; i <= n; ++i) if (a[i] != to[i]) {
        ++m; 
        G[to[i]].emplace_back(a[i], i); ban[to[i]].emplace_back(0);
    }
    if (m > s) return puts("-1"), 0;
    for (int i = 1; i <= n; ++i) if (!vis[i] && G[i].size()) {
        road.clear(); dfs(i); 
        ans.push_back(road); 
    } 
    for (int i = 0; i < ans.size(); ++i) reverse(ans[i].begin(), ans[i].end());
    
    if (min(int(ans.size()), s - m) > 1) {
        int t = min(int(ans.size()), s - m); road.clear(); road.emplace_back(ans[0][0]);
        for (int i = ans.size() - t + 1; i < ans.size(); ++i) {
            for (int x : ans[i]) ans[0].emplace_back(x); 
            road.emplace_back(ans[i][0]); ans[i].clear(); 
        }
        for (int i = 1; i < t; ++i) ans.pop_back(); 
        reverse(road.begin(), road.end()); ans.push_back(road); 
    }
    printf("%u\n", ans.size()); 
    for (int i = 0; i < ans.size(); ++i) {
        printf("%u\n", ans[i].size()); 
        for (int x : ans[i]) printf("%d ", x); 
        putchar('\n'); 
    }
    return 0;
}

[CF1764G] Doremy’s Perfect DS Class

G1，G2，G3。给定一个 $1\sim n$ 的排列 $p$ （ $n \le 1024$ ，注意 $2^{10}=1024$ ），每次你可以询问 $l,r,k$ ，交互库会返回 $\left\lfloor\cfrac{p_l}k\right\rfloor,\left\lfloor\cfrac{p_{l+1}}k\right\rfloor,\cdots,\left\lfloor\cfrac{p_r}k\right\rfloor$ 中不同数的个数，需要找到 $1$ 的位置。交互次数分别限制在 $30,25,20$ 次。

询问能告诉我们什么？好奇怪啊，不知道。尝试从给定的 $k$ 值开始分析。 $k=1$ 没什么意义，然后尝试从特殊的，比如 $k=2,n$ 开始分析。 $k=n$ 比较好说，只有 $n$ 可以被记入答案，可以根据此找出 $n$ 的位置。 $k=2$ 则可以将数分为两组，在 $n$ 为奇数时只有 $1$ 是单独一组， $n$ 为偶数时只有 $1,n$ 是单独一组。

从别的地方再想一想，都要求 $\log$ 级别的询问，不难想到二分。设 solve(l, r) 代表答案在 $[l,r]$ 的位置中，我们需要确定 $1$ 在 $[l,mid]$ 还是 $[mid+1,r]$ 里。咦，感觉不太对，不是严格的子问题！但是我们只需要寻找答案在哪里，因此只需要分别答案在 $[1,mid]$ 还是 $[mid+1,n]$ 就好了。

选择从 $k=2$ 入手， $x,y$ 分为一组仅当它们除以二下取整后的值相等。我们可以求出两个区间中在自己区间内没有匹配的数的数量，然后这个数量大的，答案就在那里（因为剩下的每有一个都是成对的）。

$n$ 是偶数怎么办呢？我们只需要找到 $n$ 就行，不难发现 $k=n$ 可以很好的完成这个任务。当两个区间的值相等时，说明 $1,n$ 各占一个，我们令 $k=n$ ，询问其中一个，看 $n$ 是否在其中。找到 $n$ 的位置之后发现之后的递归不会受到影响（如果 $p_n> mid$ ，我们会递归到 $[l,mid]$ ，必定有 $p_n>mid'$ ）。

这个做法可以通过 G2，代码。想过掉 G3，我们需要想方法杀掉那一次多余的询问。

怎么杀？对于 $r-l+1=2$ 的情况，使用两次询问有点扯皮，我们看能不能只用一次询问杀掉它。核心思想是，充分利用我们之前问出来的信息。当我们递归到 $[l,r]$ 时，曾令一个 $mid=l-1$ ，也令了一个 $mid=r$ ，因此我们知道 $Q(1,l-1,2),Q(1,r,2),Q(l,n,2),Q(r+1,n,2)$ 的答案。现在 $l,r$ 中一个是 $1$ ，一个是和其他数能匹配上的某个奇怪的东西，吗？注意，另一个可能是 $n$ ，如果我们还没有确定 $n$ 的位置，那么通过询问 $Q(r,n,n)$ 或 $Q(1,l,n)$ 将其判掉。

现在再看怎么搞 $l,r$ 一个是 $1$ ，另一个是可匹配数。可匹配数只能配在 $[1,l-1]$ 或 $[r+1,n]$ ，如果 $Q(1,l-1,2)+1=Q(1,r,2)$ ，那么说明可匹配数的匹配数是开在 $[1,l-1]$ 的（这个数除以二下去整的值与 $[1,l-1]$ 中的某个数撞了），否则开在 $[r+1,n]$ 。确定了这一点之后，我们就可以锁定 $1$ 的位置了！以开在 $[1,l-1]$ 为例，如果 $Q(1,l-1,2)=Q(1,l,2)$ ，说明 $l$ 处开可匹配数，与 $[1,l-1]$ 中的某个数匹配， $1$ 就开在 $r$ 处。

这样在 $r-l+1=2$ 时我们只花费了一次询问，可以通过 G3。

查看代码

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

int n, flag; 
map<pair<int, int>, int> f; 
int query(int l, int r, int k) {
    if (l >= r) return l == r; 
    if (l == 1 && r == n) return n / k + 1; 
    if (k == 2 && f.find({l, r}) != f.end()) return f[{l, r}]; 
    printf("? %d %d %d\n", l, r, k); fflush(stdout); 
    int ans; scanf("%d", &ans); 
    if (k == 2) f[{l, r}] = ans; 
    return ans; 
}

int solve(int l, int r) {
    if (l == r) return l; 
    if (n % 2 == 0 && r - l + 1 == 2) {
        if (!flag) {
            if (r < n) return query(r, n, n) == 2 ? l : r; 
            return query(1, l, n) == 2 ? r : l; 
        }
        if (query(1, r, 2) - query(1, l - 1, 2) == 1) { // 与非 1 数的匹配在 [1, l-1]
            int x = query(1, l - 1, 2), y = query(1, l, 2); 
            if (x + 1 == y) return l; 
            return r; 
        } else {
            int x = query(r + 1, n, 2), y = query(r, n, 2); 
            if (x + 1 == y) return r; 
            return l; 
        }
    }
    int mid = l + r >> 1; 
    int L = 2 * query(1, mid, 2) - mid; 
    int R = 2 * query(mid + 1, n, 2) - (n - mid); 
    if (n % 2 == 0) {
        if (!flag) {
            if (L == R) {
                bool con = 0; 
                if (mid > 1 && query(1, mid, n) == 2) con = 1; 
                if (con) flag = 1, --L; 
                else flag = -1, --R; 
            }
        } else {
            if (flag == 1) --L; 
            else --R; 
        }
    }
    return L > R ? solve(l, mid) : solve(mid + 1, r); 
}

int main(void) {
    scanf("%d", &n); 
    return !printf("! %d\n", solve(1, n)); 
}

[CF1764E] Joking

E1，E2。

给定 $n$ ，猜出一个整数 $x$ 。可以询问一个集合 $S$ ，交互库会回答 $x$ 是否属于 $S$ 。但交互库是个骗子，它只保证连续两次询问的回答只至少有一次是真的。

最多可以猜测两次答案， $n\le 10^5$ ，交互次数分别限制在 $82,53$ 次。交互库自适应。

一个笨蛋做法是，一个询问连续询问两次。回答相同则一定是真的，但是不同就死了。

因此考虑将回答全部变成 YES。很简单，如果回答的是 NO，那么相当于我们询问了一个补集。

由于连续两次询问 $S,T$ ，不可能都为假，因此 $x$ 在 $S\cup T$ 里。

问题是如何选择合适的 $S,T$ ，最小化并集的最大值，也就是最大化 $S\cap T, \overline{S}\cap T,S\cap \overline{T},\overline{S}\cap \overline{T}$ 的最小值。

那么我们将 $U$ 平均分成 $U_1,U_2,U_3,U_4$ ，令 $S=U_1\cup U_2,T=U_3\cup U_4$ 即可。

最后需要特判 $n=3$ ，得益于我们可以猜测两次，因此只要使用两次或三次询问判掉一个或者两个后问两次即可。可以通过 E1。

问题出在了哪里？上一轮的 $T$ 和这一轮的 $S$ 的性质我们没有用到。

假定全集为 $U$ ，上一次交互库告诉我们 $x\in S$ ，令 $T=\complement_{U}S$ ，那么我们询问的是 $S_0\cup T_0$ 满足 $S_0\subset S,T_0\subset T,S_1=\complement_{S}S_0,T_1=\complement_{T}T_0$ ，如果回答了 YES，那么 $U$ 就取不到 $T_1$ 了。

考虑 DP 计算出最优的划分方式。设 $f_{i,j}$ 代表 $|S|=i,|T|=j$ 的次数，初始 $\forall i+j\le 2, f_{i,j}=0$ （直接问答案就行了），转移：

$f_{i,j}=1+\min_{0\le x\le i,0\le y\le j}\max\{f_{x+y,i-c},f_{i+j-x-y,x}\}$

前者是回答 YES 时新的 $S$ 为 $S_0\cup T_0$ ，新的 $T$ 为 $S_1$ ；后者是回答 NO 时新的 $S$ 为 $S_1\cup T_1$ ，新的 $T$ 为 $S_0$ 。

比较大的时候直接折半是很优秀的。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI; 
const int N = 100; 

int n; 
int f[105][105], x[105][105], y[105][105];

int main(void) {
    ios::sync_with_stdio(0); 

    memset(f, 0x3f, sizeof(f)); 
    for (int s = 0; s <= N; ++s)
        for (int i = 0; i <= s; ++i) {
            int j = s - i; 
            if (s <= 2) { f[i][j] = 0; continue; }
            for (int x = 0; x <= i; ++x)
                for (int y = 0; y <= j; ++y) {
                    int v = max(f[x + y][i - x], f[s - x - y][x]) + 1;
                    if (v < f[i][j])
                        f[i][j] = v, ::x[i][j] = x, ::y[i][j] = y; 
                }
        }

    cin >> n; VI S, T; 
    for (int i = 1; i <= n; ++i) S.push_back(i); 
    while (S.size() + T.size() > 2) {
        int x = S.size() / 2, y = T.size() / 2;
        if (S.size() + T.size() <= N) x = ::x[S.size()][T.size()], y = ::y[S.size()][T.size()]; 
        VI S0(S.begin(), S.begin() + x); 
        VI S1(S.begin() + x, S.end()); 
        VI T0(T.begin(), T.begin() + y); 
        VI T1(T.begin() + y, T.end()); 
        cout << "? " << S0.size() + T0.size() << " "; 
        for (int i : S0) cout << i << " "; 
        for (int i : T0) cout << i << " "; 
        cout << endl; 
        string res; cin >> res; S.clear(), T.clear(); 
        if (res == "YES") {
            for (int i : S0) S.push_back(i); 
            for (int i : T0) S.push_back(i); 
            for (int i : S1) T.push_back(i); 
        } else {
            for (int i : S1) S.push_back(i); 
            for (int i : T1) S.push_back(i); 
            for (int i : S0) T.push_back(i); 
        }
    }
    for (int i : T) S.emplace_back(i); 
    for (int i : S) {
        cout << "! " << i << endl; 
        string res; cin >> res; 
        if (res == ":)") return 0; 
    }
    return 0;
}

这一点不一定，在 NOI2022 D1T3 中，就只下发了一个 grader.cpp 编译后的可执行文件，这样会显著增加难度，因为你不再能打开 grader 源文件来调试或者寻找思路了。 ↩︎