CF1588 B. Guess the Permutation
交互题。第一次写,怪新奇的qwq
题意:给定一个序列a,其中a[i]=i。选择三个数i、j、k,翻转区间[i,j-1],[j,k],你可以询问区间[l,r]内逆序对的数量来确定i,j,k的值,询问不超过40次。
场上捏了组样例,发现两个区间交界处逆序对数量时相等的,还想右边的长度可以由query(l,n)-query(l+1,n)+1算出来,左边的可以找到最大值n(n+1)/2反向解出n。然后致力于找这个位置,最后也没写对。看了别人的解法被自己蠢到了qaq
解:首先二分出i的位置,易得1到i和小于i的数逆序对为0。然后query(l,n)-query(l+1,n)+1算出左边位置。然后算出右边位置。然后没了。
害!代码如下:
#includeusing namespace std; #define ll long long #define maxx 1000005 #define inf 0x7fffffff //#define int long long ll query(int l,int r){ printf("? %d %d\n",l,r); fflush(stdout); ll temp; scanf("%lld",&temp); return temp; } signed main() { int T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); int l=1,r=n,ans; while(l<=r){ int mid=l+(r-l)/2; if(query(1,mid)==0){ ans=mid; l=mid+1; } else r=mid-1; } ll s2=query(ans,n)-query(ans+1,n)+1; ll s3=query(ans+s2,n)-query(ans+s2+1,n)+1; printf("! %d %lld %lld\n",ans,ans+s2,ans+s2+s3-1); fflush(stdout); } return 0; }
以及交互题询问后要fflush(stdout),可以专门写一个函数干这件事情。