「MCOI-03」金牌
题意
只告诉有长度 \(n\) 的数列。
每个\(i\) 有一个值 \(a_i\),你只能问任意两个 \(x,y\) 的值 \(a_x, a_y\) 是否相同。
求能否构造出一个排列, 满足排列中任意相邻的 \(i, j\) 使得 \(a_i \neq a_j\)。
摩尔投票法
首先思考无解情况,只有存在一个数出现次数 \(\geq \lceil \frac{n}{2} \rceil\) 时无解。
那么众数是出现次数最多的,这时就能想到摩尔投票法,能 只通过比较相等 求出众数。
单纯的摩尔投票法只能花费 \(n - 1\) 次比较,来求出一个众数,来判断是否有解。
改编
考虑对单纯的摩尔投票法进行思考,可以时刻记录的信息是众数出现的所有位置,它们都是 相同的数。
每次出现不同的数,就会对当前众数个数减一,就可以看成两个不同的数组成一对。
- 考虑众数个数减到 \(0\) 的过程,设众数是 \(x\),那么这几对数就可以这样表示:
它们能保证相邻的数不同。
- 如果在下一个数是 \(y\),那么现在的众数就是 \(y\),记录位置。 假设众数个数又减到 \(0\),那么每次减掉的数对可以表示为 :
可以调换顺序,
\[(z,y),(c,y),\dots \]这样就可以和前面接上:
\[(x, y),(x,z),\dots,(x,y),(z,y),(c,y),\dots \]这样相邻的数总不会相同。
- 如果下一个数不是 \(y\), 而是 \(z\),那么直接加入 \(z\), 即可保证不同。
可以发现,当众数是 \(y\) 时,那么上一次最后一个数也是 \(y\),那么只要有不跟 \(y\) 相同的数 \(z\) 出现,
按照 \(y, z\) 的顺序加入答案序列,即可保证相邻不同。
那么最后可能多出很多个相同的数,直接暴力判断答案序列中能插入的位置,插入在两个和它不同的数中间,要特判开头结尾。
如果还是有数插不进,就说明无解。
代码
#include
using namespace std;
using ll = long long;
const int MAXN = 200010;
const ll INF = 1e18;
const int mod = 1000000007;
//#define ll long long
template
void Read(T &x) {
x = 0; T f = 1; char a = getchar();
for(; a < '0' || '9' < a; a = getchar()) if (a == '-') f = -f;
for(; '0' <= a && a <= '9'; a = getchar()) x = (x * 10) + (a ^ 48);
x *= f;
}
int ask(int x, int y) {
cout << x << ' ' << y << endl;
int ans;
cin >> ans;
return ans;
}
int main() {
int t;
cin >> t;
while(t --) {
int n, Q;
cin >> n >> Q;
queue q;
vector ans(1, 0);
for (int i = 1; i < n; i ++) {
if (q.empty()) {
if (ask(i, ans.back()))
ans.emplace_back(i);
else
q.push(i);
} else {
if (ask(i, q.front())) {
ans.emplace_back(i);
ans.emplace_back(q.front());
q.pop();
} else {
q.push(i);
}
}
}
vector pd = ans;
if (!q.empty()) {
int cnt = 0;
for (auto & i : pd)
i = ask(i, q.front());
if (pd.size() && pd[0]) cnt ++;
if (pd.size() && pd[pd.size() - 1]) cnt ++;
for (int i = 1; i < (int) pd.size(); i ++)
if (pd[i] && pd[i - 1])
cnt ++;
if (cnt < q.size()) {
cout << -1 << endl;
continue;
}
}
cout << n << endl;
if (pd.size() && pd[0] && !q.empty()) cout << q.front() << ' ', q.pop();
for (int i = 0; i < (int) ans.size(); i ++) {
cout << ans[i] << ' ';
if (i < ans.size() - 1 && pd[i] && pd[i + 1] && !q.empty()) {
cout << q.front() << ' ';
q.pop();
}
}
if (pd.size() && pd[pd.size() - 1] && !q.empty()) cout << q.front() << ' ', q.pop();
cout << endl;
}
return 0;
}