题解：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_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;
}