P8122 题解

· · 题解

理解题意

这是一个交互题，给定一个长度为 N 的未知的数列 x_i，并且保证其单调递增，你可以用任意顺序询问其中至多 S 个数，并且对于给定的值 A 和 K，要求从 N 个数中选出 K 个数（不能重复），使得它们的和 \in[A,2A]。

分析

  1. 先取前 K-1 个，然后二分找到序列中最后一个 i，使得 (\sum_{j=1}^{K-1}x_j)+x_i\le 2A。
  2. 如果不存在这样的 i 则无解。
  3. 如果找到的这样的和恰好 \ge A，则找到一组解。
  4. 否则，如果存在解则一定可以用 [1,K-1] 和 [i-K+1,i] 中的数得到一组解。

次数为

\log n+2K-2

。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
extern "C" {
    long long skim(int i);
    void answer(vector<int> v);
    void impossible();
    void solve(int n, int k, ll L, int m) {
        static const int N = 1e6 + 10;
        assert(m >= 40);
        if (k > n) return impossible();
        static ll a[N];
        rep(i, 1, n) a[i] = -1;
        ll s = 0;
        rep(i, 1, k - 1) s += a[i] = skim(i);
        if (s > 2 * L) return impossible();
        int l = k, r = n, res = -1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            a[mid] = skim(mid);
            if (s + a[mid] >= L && s + a[mid] <= 2 * L) {
                vector <int> t;
                rep(i, 1, k - 1) t.pb(i);
                t.pb(mid);
                return answer(t);
            }
            if (s + a[mid] > 2 * L) r = mid - 1;
            else l = mid + 1, res = mid;
        }
        if (res == -1) return impossible();
        if (a[k] == -1) a[k] = skim(k);
        rep(i, max(k + 1, res - k + 1), res) if (a[i] == -1) a[i] = skim(i);
        static int pos[N], c = 0;
        rep(i, 1, res) if (~a[i] && (i <= k || i > res - k)) pos[c++] = i;
        rep(S, 0, (1 << c) - 1) if (__builtin_popcount(S) == k) {
            ll v = 0;
            rep(i, 0, c - 1) if (S & (1 << i)) v += a[pos[i]];
            if (v >= L && v <= 2 * L) {
                vector <int> t;
                rep(i, 0, c - 1) if (S & (1 << i)) t.pb(pos[i]);
                return answer(t);
            }
        }
        return impossible();
    }
}

审核大大求过…