P16408 [Algo Beat Contest 004 D] Displaced Permutation 题解

简单题。

首先容易想到对整个序列询问 次即可还原出整个排列，于是只需要在剩下 次询问以内将排列排序。

发现左移不太好做，容易想到对一个区间操作后第一个元素跑到了最后，因此按照 到 的顺序复原即可。

询问次数 ，边询问边模拟即可，时间复杂度 。

Code

#include <bits/stdc++.h>
using namespace std;

int n, p[1005], x;
string s;

int main() {
	cin >> n;
	for(int _ = 1; _ <= n; ++_) {
		cout << "? 1 " << n << endl;
		x = p[1];
		for(int i = 1; i < n; ++i) {
			p[i] = p[i + 1];
		}
		p[n] = x;
		cin >> s;
		for(int i = 1; i <= n; ++i) {
			if(s[i - 1] == '1') {
				p[i] = i;
			}
		}
	}
	for(int i = n; i; --i) {
		x = -1;
		for(int j = 1; j <= i; ++j) {
			if(p[j] == i) {
				x = j;
				break;
			}
		}
		cout << "? " << x << ' ' << i << endl;
		cin >> s;
		for(int j = x; j < i; ++j) {
			p[j] = p[j + 1];
		}
		p[i] = i;
	}
	cout << "!" << endl;
	return 0;
}