题意
这是一个交互题 有n×m的矩阵,里面有两个宝藏,你可以进行两种操作:
第一个是SCAN(x,y),返回两个宝藏到点(x,y)的曼哈顿距离(|x-x|+|y-y|)
第二个是DIG(x,y),如果有坐标有宝藏,返回1,否则返回0,当返回两个1时,成功找到两个宝藏
你最多可以操作7次
吐槽
这个题是一次多的机会也不给,七次都是要跑满的,但是感觉这个题也是挺套路的,绝对值一般都是找两个锻炼就可以去掉了,然后分析就很简单了。
提示
1. 首先需要询问四个端点中的相邻两个,然后就可以推出另外两个端点的值
2. 当行,或者列固定时,沿着一个方向移动,曼哈顿距离的变化趋势一定如下:
3. 因此我们只需要询问上图平面的中点即可,解方程就可以解出x1,x2
4 .同理,对于y坐标,也需要询问一次,即可得到y1,y2,那么现在的总次数为 4
5. 由于不知道x,y两两如何对应,因此,需要DIG测试一次,因此最多需要DIG三次,最少DIG两次,总数6-7次
代码
#include<bits/stdc++.h>
using namespace std;
int n, m;
int f[10];
int X1, Y1, X2, Y2;//X1<X2,Y1<Y2
void run() {
cin >> n >> m;
cout << "SCAN " << 1 << ' ' << 1 << endl;
cin >> f[1];
cout << "SCAN " << 1 << ' ' << m << endl;
cin >> f[2];
f[3] = (f[1] + f[2] - 2 * m + 6) / 2;//a+c
f[4] = (f[1] - f[2] + 2 + 2 * m) / 2;//b+d
f[5] = 2 * n - f[3] + f[4] - 2;
int res = (f[2] - f[1]) / 2;
int mid = (m - res + 1) / 2;
cout << "SCAN " << 1 << ' ' << mid << endl;
cin >> f[6];//中点
Y1 = (f[1] - f[6]) / 2 + 1;
Y2 = f[4] - Y1;
res = (f[5] - f[1]) / 2;
mid = (n - res + 1) / 2;
cout << "SCAN " << mid << ' ' << 1 << endl;
cin >> f[7];//中点
X1 = (f[1] - f[7]) / 2 + 1;
X2 = f[3] - X1;
cout << "DIG " << X1 << ' ' << Y1 << endl;
cin>>res;
if(res){
cout << "DIG " << X2 << ' ' << Y2 << endl;
cin>>res;
}
else{
cout << "DIG " << X1 << ' ' << Y2 << endl;
cin>>res;
cout << "DIG " << X2 << ' ' << Y1 << endl;
cin>>res;
}
}
int main() {
int t;
cin >> t;
while (t--)
run();
return 0;
}
原文地址:http://www.cnblogs.com/4VDP/p/16851478.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性