题解：AT_arc184_a [ARC184A] Appraiser

本质上还是官方题解的分组并利用 \(M\) 不大的思路。

询问次数 \(Q\) 离最简单的每个扫一遍就可以知道答案的做法少了 \(50\) 次。我们考虑如何减少这个次数。

首先你可以发现一次询问可以覆盖到两个数，也就是说所有的数都被覆盖时只需要询问 \(500\) 次。

我们考虑把不同的对拉出来，然后把它剩下相同的对留下，最坏的情况是所有都被留下了。

此时继续重复上述操作，并把每个对看成一个整体，也就是说按照 \(2,4,8,...,2^n\) 的方式不断进行分组，你会发现，最坏的情况下至少在每 \(4\) 个为一组时至少会查出一组大小为 \(2\) 的不同类型组，因为 \(M=10\)。而在每 \(16\) 个为一组时就可以查出所有的不同组，所以我们只要分到 \(16\) 为一组时就不用再分了，这里总共使用了至多 \(937\) 次询问，请自行计算。

当然这样有个问题，就是在分的时候会出现末尾每办法分进去，我们就直接将其单独提出，这样的单独最多有 \(3\) 组。

最后剩下的相同组一定都是真币，所以只要单独提出其中一个然后与每个不同组比较，若不同组的前半与其不同，则前半为假币，若相同，则后半为假币，这里至多比 \(5\) 次。

对于单独组，它也可能是假币，所以也要比较，但是如果相同就不做处理，这里最多会比较 \(3\) 次。

最后询问次数将严格低于 \(937+3+5=945\) 次。比较劣，但是可过。

还要注意不要读错题，比如说看错 \(1\) 和 \(0\) 的意义之类的，否则你会像我一样调一个多小时。

赛时码风，丑陋轻喷。

#include <bits/stdc++.h>
#include <bits/extc++.h>
#define ll long long
#define ull unsigned long long
#define m_p make_pair
#define m_t make_tuple
#define N 1010
using namespace std;
using namespace __gnu_pbds;
bool ask(int x, int y)
{
	cout << "? " << x << " " << y << "\n";
	fflush(stdout);
	bool ans;
	cin >> ans;
	return (!ans);
}
int m, cnt;
bitset<N> vis;
vector<pair<vector<int>, vector<int>>> ns;
vector<vector<int>> ss;
void solve(vector<vector<int>> a)
{
	if (cnt >= m || a.size() <= 70)
		return;
	int x, y, z, n = a.size();
	vector<vector<int>> a1;
	vector<int> vec1, vec2, vec;
	for (int i = 1; (i << 1) <= n; i++)
	{
		y = i << 1;
		x = y - 1;
		--x;
		--y;
		vec1 = a[x];
		vec2 = a[y];
		if (ask(vec1.front(), vec2.front()))
		{
			vec = vec1;
			for (auto val : vec2)
				vec.push_back(val);
			a1.push_back(vec);
		}
		else
		{
			cnt += vec1.size();
			ns.push_back(m_p(vec1, vec2));
			for (auto val : vec1)
				vis[val] = 1;
			for (auto val : vec2)
				vis[val] = 1;
		}
	}
	if (n & 1)
	{
		ss.push_back(a.back());
		for (auto val : a.back())
			vis[val] = 1;
	}
	return solve(a1);
}
signed main()
{
	int n, q, x, y, los = 1;
	cin >> n >> m >> q;
	vector<vector<int>> a;
	vector<int> vec;
	vec.resize(1);
	for (int i = 1; i <= n; i++)
	{
		vec[0] = i;
		a.push_back(vec);
	}
	solve(a);
	if (cnt == m)
	{
		for (auto vec1 : ss)
			for (auto val : vec1)
				vis[val] = 0;
		ss.clear();
	}
	for (int i = 1; i <= n; i++)
		if (!vis[i])
		{
			los = i;
			break;
		}
	vec.clear();
	for (auto [vec1, vec2] : ns)
	{
		if (ask(los, vec1.front()))
			for (auto val : vec2)
				vec.push_back(val);
		else
			for (auto val : vec1)
				vec.push_back(val);
	}
	for (auto vec1 : ss)
		if (!ask(los, vec1.front()))
			for (auto val : vec1)
				vec.push_back(val);
	sort(vec.begin(), vec.end());
	cout << "!";
	for (auto val : vec)
		cout << " " << val;
	cout << "\n";
	fflush(stdout);
	return 0;
}

话说这道题真的只普及吗？

还是我菜了。