自动搬运

查看原文

来自洛谷，原作者为

	天野星河 这个家伙很勤劳，但还是什么也没有留下

搬运于2025-08-24 22:36:12，当前版本为作者最后更新于2023-04-01 17:04:58，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

理解题意

这是一个交互题，给定一个长度为 $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]$ 中的数得到一组解。

次数为

。

#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();
	}
}

审核大大求过…