AI Summary
如何用有限次询问还原被反转的01序列？二分找出交换区间，reverse即可。
P15303 『NFC-OI R1』序列陆
我们首先观察数据范围。
对于前四个点，我们可以直接简单解决，这里不再赘述。
对于特殊性质2，实际上就是将序列的所有 移动到了中间，形成了如下图的结构：
我们可以通过简单的二分来找到任意一个 的位置，并求出其前后各有多少 ，之后输出即可。
这里给一份所有特殊性质的代码（45 pts）：
/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
void ask (int l,int r) {
cout<<"? "<<l<<" "<<r<<endl;
}
int n,k,c;
signed main() {
Cios;
cin>>n>>k>>c;
if (k==n) {
vector <int> _res;
for (int i=1;i<=n;i++) {
ask(i,i);
int r;
cin>>r;
_res.push_back(r);
}
cout<<"! ";
for (int r:_res) cout<<r<<" ";
return 0;
}
if (c==1) {
ask(1,n);
int rg;
cin>>rg;
cout<<"! ";
for (int i=1;i<=n;i++) {
if (n-i+1<=rg) cout<<"1 ";
else cout<<"0 ";
}
return 0;
}
if (c==2) {
ask(1,n);
int tot;
cin>>tot;
int nw=tot;
int l=1,r=n;
int id=-1;
while (l<r&&nw==tot) {
int mid=(l+r)>>1;
ask(l,mid);
int tmp;
cin>>tmp;
if (tmp==0) l=mid+1;
else if (tmp==tot) r=mid;
else id=mid,nw=tmp;
}
cout<<"! ";
for (int i=1;i<=n;i++) {
if (i<=id) {
if (id-i+1<=nw) cout<<"1 ";
else cout<<"0 ";
}
else {
if (i-id<=tot-nw) cout<<"1 ";
else cout<<"0 ";
}
}
return 0;
}
return 0;
}解决完特殊性质，我们来考虑正解。
考虑原序列 ，形如下：
我们进行第一次询问 ask(1,n) ，求出的答案记作 ，表示整个序列中 的总数。
那么我们可以考虑查询 序列中原本 序列中全为 的部分现在有多少 ，即查询区间 ，记作 。
之后怎么考虑呢？我们看下图：
这是两种不同的情况。我们需要想办法区分。
容易想到，我们可以查询区间 。为什么呢？
若所有的左侧的 全部紧贴分界线，中间没有 的情况下，这个区间总和应该为 。
那我们查询，若为 ，则说明是情况 ，反之为情况 。
若为情况 ，我们可以算出置换左端点 ；
若为情况 ，我们可以算出置换右端点
固定了端点和情况之后，我们可以使用剩下的 次查询找到另一个端点，之后手动reverse就好了。具体可以看代码。
/*---------------------
by DRheEheAM (awa)-----
love hanser forever!---
---------------------*/
#include<bits/stdc++.h>
using namespace std;
#define intc constexpr int
#define intl long long
#define Cios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
void ask (int l,int r) {
cout<<"? "<<l<<" "<<r<<endl;
}
int n,k,c;
int a[100005];
signed main() {
Cios;
cin>>n>>k>>c;
if (k==n) {
vector <int> _res;
for (int i=1;i<=n;i++) {
ask(i,i);
int r;
cin>>r;
_res.push_back(r);
}
cout<<"! ";
for (int r:_res) cout<<r<<" ";
return 0;
}
if (c==1) {
ask(1,n);
int rg;
cin>>rg;
cout<<"! ";
for (int i=1;i<=n;i++) {
if (n-i+1<=rg) cout<<"1 ";
else cout<<"0 ";
}
return 0;
}
if (c==2) {
ask(1,n);
int tot;
cin>>tot;
int nw=tot;
int l=1,r=n;
int id=-1;
while (l<r&&nw==tot) {
int mid=(l+r)>>1;
ask(l,mid);
int tmp;
cin>>tmp;
if (tmp==0) l=mid+1;
else if (tmp==tot) r=mid;
else id=mid,nw=tmp;
}
cout<<"! ";
for (int i=1;i<=n;i++) {
if (i<=id) {
if (id-i+1<=nw) cout<<"1 ";
else cout<<"0 ";
}
else {
if (i-id<=tot-nw) cout<<"1 ";
else cout<<"0 ";
}
}
return 0;
}
ask(1,n);
int tot;
cin>>tot;
for (int i=1;i<=n;i++) {
if (n-i+1<=tot) a[i]=1;
else a[i]=0;
}
int li=n-tot+1;
ask(1,li-1);
int k;
cin>>k;
if (tot==0||tot==n||k==0) {
cout<<"! ";
for (int i=1;i<=n;i++) cout<<a[i]<<" ";
return 0;
}
int l=-1,r=-1;
int res1=0;
if (li-k-1>=1) {
ask(1,li-k-1);
cin>>res1;
}
if (res1==0) {
l=li-k;
int lf=li,rg=n;
while (lf<=rg) {
int mid=lf+rg>>1;
ask(li,mid);
int tmp;
cin>>tmp;
if (mid-li+1-tmp==k) {
r=mid;
rg=mid-1;
}
else lf=mid+1;
}
}
else {
r=li+k-1;
int lf=1,rg=li-1;
while (lf<=rg) {
int mid=lf+rg>>1;
ask(mid,li-1);
int tmp;
cin>>tmp;
if (tmp==k) {
l=mid;
lf=mid+1;
}
else rg=mid-1;
}
}
reverse(a+l,a+r+1);
cout<<"! ";
for (int i=1;i<=n;i++) cout<<a[i]<<" ";
return 0;
}
评论（0）
暂无评论