【交互题】CF864div2 C. Li Hua and Chess

￡神魔★判官ぃ 2024-03-22 10:38 84阅读 0赞

**感觉交互题就是不断地去缩小答案范围，得注意观察它的询问次数，询问次数是特殊条件**

[  
Problem - C - Codeforces][Problem - C - Codeforces]

题意：

给定一个棋盘，在棋盘上某个位置放置了一个棋子，**你可以问不超过3个问题**，每次问题query(x,y)都会回答从(x,y)出发到目标点最少要走的距离，试确定目标点的位置

![b3ccc347c984492e983adce5bd64157c.png][]

思路：

构造题，选定一个特殊的点进行提问

选定(1,1)，得到目标点离(1,1)的距离

这样目标点的范围就缩小到如下位置：

![format_png][]

然后对(1,k+1),(k+1,1)提问，可以进一步缩小答案范围

对(1,k+1)询问，如果离(1,1)的距离小于(1,k+1)的距离，那么就在最底下那根线上

![format_png 1][]

否则就在右边的线上

![format_png 2][]

Code：

#include <bits/stdc++.h>
    
    //#define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int Inf=0x3f3f3f3f;
    
    int n,m;
    
    int query(int x,int y){
    	if(x>n||y>m) return Inf;
    	int ans;
    	cout<<"?"<<" "<<x<<" "<<y<<'\n';
    	cin>>ans;
    	return ans;
    }
    void output(int x,int y){
    	cout<<"!"<<" "<<x<<" "<<y<<'\n'; 
    }
    void solve(){
    	cin>>n>>m;
    	int x=query(1,1);
    	int y=query(1,x+1);
    	int z=query(x+1,1);
    	if(y<x) output(y+1,x+1);
    	else output(x+1,z+1);
    }
    signed main(){
    	//cout.flush();
    	//ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1797/problem/C
[b3ccc347c984492e983adce5bd64157c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/20861c936bae44e4976979c0bc7aa2d2.png
[format_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/455d772946df4db99697788e44ed9405.png
[format_png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/d5fa72d472ce4703a2d8bd30430174f8.png
[format_png 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/9aa1de852ceb491487693a4753f4ec02.png