专栏文章

题解：CF1666I Interactive Treasure Hunt

TTH_HaZel
CF1666I题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minh4gzl
此快照首次捕获于
2025/12/02 02:19
3 个月前
此快照最后确认于
2025/12/02 02:19
3 个月前
查看原文
666 先打完双倍经验才来的。
upd:
[2025/10/28 17:06] 发现了代码中的错误，糖丸了。

思路

数学题。
其实理论上 n,mn,m 可以开到很大。
下文令 x1≥x2x_1\ge x_2，y1≥y2y_1\ge y_2。
对于两个点的坐标，我们可以把它看成一个四元一次方程组求解，现在的问题是如何找到四个方程。
因为有绝对值，所以我们可以想到取一些极值点来消除绝对值的影响。我们可以想到取 (1,1)(1,1)，(1,m)(1,m)，(n,1)(n,1)，(n,m)(n,m) 中的两个点。
其中不难发现，(1,1)(1,1)，(n,m)(n,m) 是等价的；(1,m)(1,m)，(n,1)(n,1) 是等价的，我们这里取 (1,1)(1,1)，(1,m)(1,m)。
设 (1,1)(1,1) 的询问答案为 aa，(1,m)(1,m) 的询问答案为 bb，
则有：
{x1+x2+y1+y2=a+4x1+x2−y1−y2=b+2−2m\begin{cases} x_1+x_2+y_1+y_2=a+4\\ x_1+x_2-y_1-y_2=b+2-2m \end{cases}
于是，我们能求出：
{x1+x2=a+b2+3−my1+y2=a−b2+1+m\begin{cases} x_1+x_2=\frac{a+b}{2}+3-m\\ y_1+y_2=\frac{a-b}{2}+1+m \end{cases}
现在我们考虑如何求出 x1−x2x_1-x_2，这样就可以根据 x1+x2x_1+x_2 求出它们的值（y1−y2y_1-y_2 同理）。
不难注意到，根据绝对值的性质，我们设询问为 (x,y)(x,y)，答案为 c=∣x1−x∣+∣x2−x∣+∣y1−y∣+∣y2−y∣c=|x_1-x|+|x_2-x|+|y_1-y|+|y_2-y|。
首先，我们先排除 yy 对答案的影响，所以 yy 取 11，答案为 ∣x1−x∣+∣x2−x∣+y1−1+y2−1=c|x_1-x|+|x_2-x|+y_1-1+y_2-1=c。解得 ∣x1−x∣+∣x2−x∣=c+1−a−b2−m|x_1-x|+|x_2-x|=c+1-\frac{a-b}{2}-m。
我们要求 x1−x2x_1-x_2，只要令 x1≥x≥x2x_1\ge x\ge x_2 即可。 那么，如何找出符合条件的 xx 呢？
注意到当 xx 为中点时，满足上方的式子。又因为我们已经求出了 x1+x2=a+b2+3−mx_1+x_2=\frac{a+b}{2}+3-m，根据中点公式，得 x=a+b+6−2m4x=\frac{a+b+6-2m}{4}。
所以，答案为 x1−a+b+6−2m4+a+b+6−2m4−x2=c+1−a−b2−mx_1-\frac{a+b+6-2m}{4}+\frac{a+b+6-2m}{4}-x_2=c+1-\frac{a-b}{2}-m，解得 x1−x2=c+1−a−b2−mx_1-x_2=c+1-\frac{a-b}{2}-m.
于是，我们有如下式子：
{x1+x2=a+b2+3−mx1−x2=c+1−a−b2−m\begin{cases} x_1+x_2=\frac{a+b}{2}+3-m\\ x_1-x_2=c+1-\frac{a-b}{2}-m \end{cases}
解得：
{x1=a+c2+2−mx2=b−c2−1\begin{cases} x_1=\frac{a+c}{2}+2-m\\ x_2=\frac{b-c}{2}-1 \end{cases}
y1−y2y_1-y_2 同理，不做赘述。
我们发现最后 x1,x2,y1,y2x_1,x_2,y_1,y_2 的搭配不确定，所以先试一次 (x1,y1)(x_1,y_1)，如果有宝藏那么另一个就是 (x2,y2)(x_2,y_2)，否则两个宝藏就是 (x1,y2)(x_1,y_2) 和 (x2,y1)(x_2,y_1)，总询问次数刚好 77 次。

代码

CPP
//哈哈哈这次我终于记得改注释了
//嘻嘻我又改代码了
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	cin>>t;
	cout<<flush;
	while(t--)
	{
		int n,m;
		cin>>n>>m;
		
		cout<<"SCAN 1 1"<<endl;
		int su;
		cin>>su;
		su+=4;//x1+x2+y1+y2
		
		int sub;
		cout<<"SCAN 1 "<<m<<endl;
		cin>>sub;
		sub=-m-m+2+sub;//x1+x2-y1-y2
		
		int sux,suy;
		sux=su+sub>>1;//x1+x2
		suy=su-sub>>1;//y1+y2
		
		int xmid,ymid;
		xmid=sux>>1;//中点
		ymid=suy>>1;
		
		int subx,suby;
		cout<<"SCAN "<<xmid<<' '<<1<<endl;
		cin>>subx;
		subx=abs(2+subx-suy);//x1-x2
		
		cout<<"SCAN "<<1<<' '<<ymid<<endl;
		cin>>suby;
		suby=abs(2+suby-sux);//y1-y2
		
		int x1,y1,x2,y2;
		x1=sux+subx>>1;
		x2=sux-subx>>1;
		y1=suy+suby>>1;
		y2=suy-suby>>1;
		bool f;
		cout<<"DIG "<<x1<<' '<<y1<<endl;
		cin>>f;
		if(f==1)
		{
			cout<<"DIG "<<x2<<' '<<y2<<endl;
			cin>>f;
			continue;
		}
		else
		{
			cout<<"DIG "<<x1<<' '<<y2<<endl;
			cin>>f;
			cout<<"DIG "<<x2<<' '<<y1<<endl;
			cin>>f;
			continue;
		}
	}
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...