题解 CF1466I 【The Riddle of the Sphinx】

· · 题解

神仙交互题......

题目链接：CF1466I The Riddle of the Sphinx

本题解同步发布于 My Blog

题意：

已知现有一个长 n 的数组，每个数字都是严格小于 2^b 的非负整数，每次可以给定 i,x 来询问 a_i>x 是否成立。

需要在 3\times(n+b) 次询问之内求出数组的最大值。

（本题解思路来自官方 \text{Tutorial}）

提前约定

以下所述的“前缀”均指一个二进制数从高位到低位的一部分，一个元素的前 k 位表示二进制从高位到低位的前 k 位。

接下来会有很多地方需要判断一个位置的元素的前 k 位与另一个数字 x 前 k 位的大小关系，这可以通过将 x 的前 k 位保留，后面补 0 或 1 来求出。

稍劣解法

考虑一个稍微劣的做法，可以在 5\times (n+b) 次询问之内求出答案。

由于位数较大，因此我们希望从高位到低位确定最大值的每一位。从 1 到 n 依次考虑每一个元素，同时维护一个栈，栈中保留一些元素，并求当前已经求出的最大前缀。

具体来说，该栈需要满足这样的条件：

再考虑加入元素 i 进行的操作，若当前栈中有 m\ (m<b) 个元素（同时确定的最大前缀有 m 位）：

考虑完所有元素之后，若栈中仍然存有 m 个元素（同时有一个长度为 m 的前缀），那么我们认为现在的前缀可能是最大的前缀。

为什么是可能？我们发现，上述算法中的每一个元素，对最大前缀的贡献最多只有一位。有可能某一个元素十分大，却只有一位被加入了贡献，这是十分不划算的。

例如栈中元素为：

10\red{1}0 1\red{0}01 \red{1}111

那么我们确定的前缀是 101，然而，最下面的元素有一个更大的前缀：111。

因此，现在需要做的是处理这样的情况，就算缩短确定的最大前缀长度，也要保证当前的前缀一定是最大的。

那么自栈顶向下考虑，若现在的最大前缀长度为 m ：

这样处理之后，我们发现虽然最大前缀变短了，但是由于每一个元素都再一次与最大前缀进行比较，因此这个最大前缀就一定是真的了。

假设最大前缀长度为 k，那么相当于我们已经确定了答案的前 k 位。因此接下来，直接递归处理即可。

为了进行递归，我们需要找出所有前 k 位恰好等于最大前缀的元素，只有他们才有可能成为最大值。因此还需要再对每一个数字扫一遍，保留满足上述条件的位置，再进行递归处理。

分析次数

分析一下上述做法为什么是 5\times (n+b) 的。

第一次对整个数组进行考虑时，扫描每一个位置，若选择将一个位置加入，则需要 3 次询问；若选择弹出栈顶，则需要 1 次询问；从栈顶向下考虑，每一个值都需要 1 次询问；寻找前缀与最大前缀相同的位置，每一个位置都需要 1 次询问。

因此第一次对整个数组进行扫描时，需要 5n 次询问左右。

再考虑递归的情况。可以证明，当我们在一轮中确定了一个长度为 k 的最大前缀，则与之匹配的位置至多只有 k 个。

那么我们会在答案中填上 k 位，同时下一轮只会花费 5k 次操作。

由于答案长度为 b，所以很好证明之后所有轮数加起来只会花费 5b 次询问。因此该做法可以在 5\times(n+b) 次询问内求出最大值。

考虑优化

想想上面的做法有哪里是浪费的。首先十分显然的，后面寻找哪些位置的前缀与最大前缀匹配的步骤都是浪费的——因为只有栈中最后留下的元素满足这个条件。

因此只需要将这些栈中留下的元素取出来进行递归即可。询问次数降低为 4\times(n+b)。

但是还是不够。发现上面我们在扫描每一个位置，考虑加入栈中的时候，对于一个元素进行 3 次询问实在是太亏了。

判断大于的一次询问肯定是无法省去的，因为我们需要他来判断是否需要弹出栈顶。

但是，判断等于和小于的两次，我们是否可以将他们合并为一次呢？当我们放宽一些要求，不要求栈中元素的前缀与最大前缀的前缀相同，而是变成这样的要求：

发现如果要求变成这样，就不需要判断是否小于了，而是直接确定位数并加入栈中。

至于继续维护他的正确性，我们发现在第二步自顶向下弹栈的时候，如果一个元素本来在加入时就小于当时的最大前缀，那么他一定会被弹掉！因此正确性就被保证了。

这样，我们就不需要判断小于或等于，而是直接判断该元素某一位是 0 还是 1。这样就将询问次数变为 3\times(n+b)，可以通过。

\text{Code:} 
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;

//#define FILE
//#define int long long
#define debug(x) cout << #x << " = " << x << endl
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define LINE() cout << "LINE = " << __LINE__ << endl
#define LL long long
#define ull unsigned long long
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fst first
#define scd second
#define inv(x) qpow((x),mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define vec vector

const int MAXN = 210;
const int INF = 2e9;
const double PI = acos(-1);
const double eps = 1e-6;
//const int mod = 1e9 + 7;
//const int mod = 998244353;
//const int G = 3;
//const int base = 131;

int n, b;
char s[5];
bool res;
vec<int> now;
string ans, opt;

template<typename T> inline bool read(T &a) {
    a = 0; char c = getchar(); int f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
    a *= f;
    return 1;
}

template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}

void print(int pos, string now, int op) {
    res = 0;
    cout << pos << ' ' << ans << now;
    for(int i = ans.length() + now.size(); i < b; ++i) putchar(op + '0');
    cout << endl;
    cin >> opt; 
    res = (opt[0] == 'y');
}

void solve(vec<int> id) {
    if(ans.size() == b) return;
    if(!id.size()) {
        int lim = ans.size();
        for(int i = lim + 1; i <= b; ++i) ans = ans + "0";
        return;
    }
    vec<int> stk(0);
    string cur = ""; 
    print(id[0], "0", 1);
    cur += (res ? "1" : "0");
    stk.pb(id[0]);
    for(int i = 1, p, ok; i < id.size(); ++i) {
        p = id[i], ok = false;
        print(p, cur, 1);
        if(res) ok = true;
        while(stk.size() && res) {
            cur.pop_back();
            stk.pop_back();
            print(p, cur, 1);
        }
        if(ans.size() + cur.size() == b) continue;
        res = false;
        if(!ok) print(p, cur + "0", 1);
        if(ok || res) cur += "1";
        else cur += "0";
        stk.pb(p);
    }
    for(int i = stk.size() - 1; ~i; --i) {
        print(stk[i], cur, 1);
        if(res) {
            while(stk.size() > i + 1) {
                stk.pop_back();
                cur.pop_back();
            }
        }
    }
    ans += cur; 
    solve(stk);
}

signed main () {
#ifdef FILE
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    read(n), read(b);
    for(int i = 1; i <= n; ++i) now.pb(i);
    solve(now);
    cout << 0 << ' ' << ans << endl;
    return 0;
}