交互題還是很難搞呀~

C. Chocolate Bunny(交互,推導)

$假設a_i\%a_j=x$

$a_j\%a_i=y$

其實就能得到一些東西了

$假設a_i>a_j$

$那么y=a_j$

$那么x<a_j$

$那么x<y且a_j=y$

$所以,經過(i,j)得到x,經過(j,i)得到y$

$x和y的較大值就是a_i和a_j的較小值$

$比如y比較大,那么通過a_j\%a_i=y$

$所以唯一確定a_j=y$

$綜上所訴,2次操作可以求得兩個數中的較小值$

$2n?2次操作得到n?1個數,剩下那個是n(因為n永遠不會當作較小值求出來)$

#include <bits/stdc++.h> using namespace std; int a[10009]; void print(int q,int w){cout << "? " << q << " " << w << '\n'; } int main() {int n;cin >> n;int last=1;for(int i=2;i<=n;i++){int q,w;print(last,i);fflush(stdout);cin >> q;print(i,last);fflush(stdout);cin >> w;if( q<w ) a[i]=w; //較大值不改變 else a[last]=q,last=i;}a[last]=n;cout << "! ";for(int i=1;i<=n;i++)cout << a[i] << " ";fflush(stdout); }

總結

以上是生活随笔為你收集整理的1407C. Chocolate Bunny(交互,推导)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。