题目链接: 洛谷 https://www.luogu.org/problemnew/show/CF1153E
这道题是很久以前 NTF 跟我说的, 现在想起来把它做了...
我们发现, 如果蛇的两头都在矩形里或矩形外, 则询问为偶数, 否则为奇数.
所以我们询问每一行和每一列, 就能知道蛇的两头的横纵坐标了.
但是有一种情况不行, 那就是两头在同一行或列上 (以下只考虑同一行的), 但是它们一定不在同一列, 所以可以找到它们所在的列, 然后通过二分找出它们所在的行.
具体实现可以看代码.
- #include<bits/stdc++.h>
- #define Rint register int
- using namespace std;
- inline int read(){
- int ch = getchar(), res = 0;
- while(ch <'0' || ch> '9') ch = getchar();
- while(ch>= '0' && ch <= '9'){
- res = res * 10 + ch - '0';
- ch = getchar();
- }
- return res;
- }
- int n, cnt;
- pair<int, int> res[4];
- inline int query(int a1, int b1, int a2, int b2){
- printf("? %d %d %d %d\n", a1, b1, a2, b2);
- fflush(stdout);
- return read() & 1;
- }
- inline int solve1(int x){
- int l = 1, r = n, mid;
- while(l <r){
- mid = l + r>> 1;
- if(query(x, l, x, mid)) r = mid;
- else l = mid + 1;
- }
- return l;
- }
- inline int solve2(int x){
- int l = 1, r = n, mid;
- while(l <r){
- mid = l + r>> 1;
- if(query(l, x, mid, x)) r = mid;
- else l = mid + 1;
- }
- return l;
- }
- int main(){
- n = read();
- for(Rint i = 1;i <= n;i ++)
- if(query(i, 1, i, n)) res[cnt ++] = make_pair(i, solve1(i));
- if(!cnt){
- for(Rint i = 1;i <= n;i ++)
- if(query(1, i, n, i)){
- if(!cnt) res[cnt ++] = make_pair(solve2(i), i);
- else res[cnt ++] = make_pair(res[0].first, i);
- }
- }
- printf("! %d %d %d %d\n", res[0].first, res[0].second, res[1].first, res[1].second);
- fflush(stdout);
- }
- CF1153E
来源: http://www.bubuko.com/infodetail-3108411.html