CF1977E Tensor 题解

首先有一个经典结论：连通性具有传递性。具体来说，图上若 $a$ 可以到达 $b$ ，$b$ 可以到达 $c$ ，那么 $a$ 就必然可以到达 $c$ 。在给定的图中，因为边总是从小编号连向大编号的，因此只需要判断编号相邻的两个点是否都连通，就可以知道是否整个集合内所有点都连通了。

考虑维护两个栈 $S_1,S_2$ ，其中 $S_1$ 为所有黑点按照编号从小到大组成的集合， $S_2$ 为所有白点按照编号从小到大组成的集合。那么若当前考虑到 $1\sim i-1$ 的所有点都已经按照条件放入 $S_1,S_2$ 两个栈中了，当前要将 $i$ 放入其中的一个，则考虑构造出一个合法的策略：

• 若 $S_1$ 栈为空，那么将 $i$ 放入 $S_1$ 栈的栈顶。
• 若 $S_2$ 栈为空，那么将 $i$ 放入 $S_2$ 栈的栈顶。
• 若 $S_1$ 栈栈顶元素和 $i$ 连通，那么将 $i$ 放入 $S_1$ 栈的栈顶。
• 若 $S_2$ 栈栈顶元素和 $i$ 连通，那么将 $i$ 放入 $S_2$ 栈的栈顶。
• 若上述四个简单的条件均不满足，则考虑一直暴力的将 $S_1$ 栈栈顶的元素丢入栈 $S_2$ 的栈顶，直到栈 $S_1$ 为空，或 $S_1$ 栈顶元素和 $i$ 连通为止。此时将 $i$ 放入 $S_1$ 栈的栈顶。

下面来证明这个看似胡编乱造的策略的正确性：

一、交互次数

首先可以简单发现前两种操作不会耗费任何询问次数，三、四种操作只会耗费一次询问次数。问题在于五操作。若对每一次询问的答案进行记忆化处理，则可以发现，此时 $S_2$ 栈中所有元素都不会参与询问，而 $S_1$ 栈中所有元素最多被询问一次，就会被扔入 $S_2$ 栈中，因此总共最多耗费 $n$ 次询问。合起来就不超过 $2n$ 次询问。因此交互次数正确。

二、时间复杂度

交互次数是对的，那么因为时间复杂度完全等同于交互次数，所以为 $O(n)$ ，可以通过。

三、正确性分析

若不存在最后一种操作，则因为 $S_1,S_2$ 栈中所有元素编号必然在所在栈中相邻，且相邻两个元素都连通。根据连通的传递性可知 $S_1,S_2$ 两个栈中所有元素必然两两可达。

问题在于最后一个操作。考虑到该图的特殊性，任意三个点 $a,b,c$ 都必然有至少两个点之间存在可达关系。因此考虑三个元素 $i,t1,t2$ ，其中 $t1$ 为 $S_1$ 栈的栈顶元素， $t2$ 为 $S_2$ 栈的栈顶元素。因为 $i$ 和 $t1,t2$ 之间都没有可达关系，所以此时必有 $t1,t2$ 之间存在可达关系。因此 $t1$ 和栈 $S_2$ 中所有结点都具有可达关系，可以将 $t1$ 丢入栈 $S_2$ 中。

但是此时无法保证 $S_2$ 栈的单调性。有一种可行的策略是用 set 来提到栈维护 $S_1,S_2$ 两个点集合，但是其实没有必要。同样由于连通具有传递性，而且图中任意三个点都必然有至少两个点存在可达关系，所以其实没有必要要求 $S_2$ 栈顶为 $S_2$ 栈中编号最小的元素，任意一个元素都可以满足条件。因此直接按照上述方法模拟即可，时间复杂度为 $O(n)$ 可以解决问题。

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 110;
int res[N], n, vis[N][N];
int ok(int i, int j) {
    if (vis[i][j] == 1) return 1;
    if (vis[i][j] == 0) return 0;
    cout << "? " << i << ' ' << j << endl;
    string o; cin >> o;
    return vis[i][j] = vis[j][i] = (o == "YES");
}
signed main() {
    // cin.tie(0)->sync_with_stdio(false);
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(5);
    int T;
    cin >> T;
    while (T--) {
        memset(vis, -1, sizeof vis);
        cin >> n;
        stack<int> s1, s2;
        for (int i = 1; i <= n; ++i) {
            if (s1.empty()) s1.emplace(i);
            else if (s2.empty()) s2.emplace(i);
            else if (ok(s1.top(), i)) s1.emplace(i);
            else if (ok(s2.top(), i)) s2.emplace(i);
            else {
                while (s1.size() && !ok(s1.top(), i)) s2.emplace(s1.top()), s1.pop();
                s1.emplace(i);
            }
        }
        while (s1.size()) res[s1.top()] = 0, s1.pop();
        while (s2.size()) res[s2.top()] = 1, s2.pop();
        cout << "! ";
        for (int i = 1; i <= n; ++i) cout << res[i] << ' ';
        cout << endl;
    }
    return 0;
}