专栏文章

题解：CF1354G Find a Gift

lltl0825
CF1354G题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miouq69k
此快照首次捕获于
2025/12/03 01:28
3 个月前
此快照最后确认于
2025/12/03 01:28
3 个月前
查看原文
更好的阅读体验
题目传送门

题意简述

TT 组数据。
给定 nn 个盒子，n≤103n\le 10^3，每个盒子可能有石头或礼物，已知石头的重量严格大于礼物重量且石头重量都相等，礼物的重量可能不同，礼物数量 kk 严格小于 n2\frac{n}{2}。
现在你可以与机器交互，每次向其询问两段交集为空的区间 机器会告诉你那段区间里盒子总重更重或相等。
对于每组数据，你最多询问 5050 次，要找出第一个装有礼物的盒子。

题目思路

首先，我们可以从1号位置下手。
分类讨论：
  • 若 11 号盒子是礼物，答案就是 11。
  • 若 11 号盒子是石头，我们可以倍增的向后找，具体见下。
倍增：
每次询问 1∼len1 \sim len 和 len+1∼2×lenlen+1 \sim 2\times len，若前一段重，则礼物在 len+1∼2×lenlen+1 \sim 2\times {len}，若是相等，1∼2×len1 \sim 2\times {len} 都是石头，len{len} 每次乘 22 这些询问是 log⁡2n\log_2 n 的。
举个例子：
一开始，我们问 11 和 22 若相同，因为石头一样重，长度一样长，我们又确定了 11 是石头，所以 22 也是石头。接着问 11，22 和 33，44，若重量不同，所以礼物肯定在 3∼43 \sim 4 中，因为 1∼21\sim 2 都是石头。
我们找到一段区间中有礼物了，接着去二分找礼物位置。
设礼物在 l∼rl \sim r 中。
我们二分长度 le{le} 每次询问 1∼le1 \sim {le} 和 l∼l+le−1 l \sim l+{le}-1，若前者重，礼物在 l∼l+le−1 l \sim l + {le} -1 中，否则在 l+le−1∼r l + {le} -1 \sim r 中，因为前者我们已经确定都是石头了。
二分询问次数：log⁡2n\log_2 n。
11 号是石头消耗总次数：2×log⁡2n2\times \log_2 n。
现在最重要的是如何确定：11 是否是石头。
我们知道现在除去 11 号是石头消耗总次数外还有大约 3030 次机会，每次我们可以随机一个除 11 以外的位置，判断两个东西的重量，若 11 更轻，则我们可以知道 11 一定是礼物，因为没有比石头更重的东西，判断 3030 次后，若没有比 11 更重的东西，我们可以认为 11 是石头。 错误概率约为 (12)30(\frac{1}{2})^{30} 因为 k≤n2k \le \frac{n}{2}。

注意：

  1. 边界问题，倍增时可能没有完全倍增到 nn 位置。
  2. 输出问题，记得刷新缓冲区。

代码：

CPP
#include<bits/stdc++.h>
using namespace std;
int t;
signed main()
{	
//	ios::sync_with_stdio(0);
//	cin.tie(0);
	srand(time(0));
	cin>>t;
	while(t--)
	{
		int n,k;
		cin>>n>>k;
		int tmp=__lg(n)*2;
		int p=1;
		for(int i=1;i<=20;i++)
		{
			cout<<"? 1 1\n";
			fflush(stdout);
			cout<<"1\n";
			fflush(stdout);
			int kk=min(rand()%n+2,n);
			cout<<kk<<'\n';
			fflush(stdout);
			string s;
			cin>>s;
			if(s == "WASTED")
			{
				return 0;
			}
			else
			{
				if(s == "FIRST")
				{
					
				}
				if(s == "SECOND")
				{
					p=0;
					break;
				}
			}
		}
		if(p>0)
		{
			int flag=1;
			int len=1;
			for(len=1;2*len<=n;len*=2)
			{
				int tmpx=1+len;
				cout<<"? "<<len<<' '<<len<<'\n';
				fflush(stdout);
				for(int i=1;i<=tmpx-1;i++)
				{
					cout<<i<<' ';
					fflush(stdout);
				}
				cout<<'\n';
				fflush(stdout);
				for(int i=tmpx;i<=tmpx+len-1;i++)
				{
					cout<<i<<' ';
					fflush(stdout);
				}
				cout<<'\n';
				fflush(stdout);
				string s;
				cin>>s;
				if(s == "FIRST")
				{
					int l=1,r=len,ans=0;
					while(l<=r)
					{
						int mid=(l+r)/2;
						cout<<"? "<<mid<<' '<<mid<<'\n';
						fflush(stdout);
						for(int i=1;i<=mid;i++)
						{
							cout<<i<<' ';
							fflush(stdout);
						}
						cout<<'\n';
						fflush(stdout);
						for(int i=tmpx;i<=tmpx+mid-1;i++)
						{
							cout<<i<<' ';
							fflush(stdout);
						}
						cout<<'\n';
						fflush(stdout);
						string s1;
						cin>>s1;
						if(s1 == "FIRST")
						{
							r=mid-1;
							ans=mid;
						}
						if(s1 == "EQUAL")
						{
							l=mid+1;
						}
					}
					cout<<"! "<<tmpx+ans-1<<'\n';
					fflush(stdout);
					flag=0;
					goto it;
				}
				if(s == "SECOND")
				{
					return 0;
				}
				if(s == "EQUAL")
				{
					continue;
				}
				if(s == "WASTED")
				{
					return 0;
				}
			}
			it:;
			if(flag)
			{
				int l=1,r=n-len,ans=0,tmpx=len+1;
				while(l<=r)
				{
					int mid=(l+r)/2;
					cout<<"? "<<mid<<' '<<mid<<'\n';
					fflush(stdout);
					for(int i=1;i<=mid;i++)
					{
						cout<<i<<' ';
						fflush(stdout);
					}
					cout<<'\n';
					fflush(stdout);
					for(int i=tmpx;i<=tmpx+mid-1;i++)
					{
						cout<<i<<' ';
						fflush(stdout);
					}
					cout<<'\n';
					fflush(stdout);
					string s1;
					cin>>s1;
					if(s1 == "FIRST")
					{
						r=mid-1;
						ans=mid;
					}
					if(s1 == "EQUAL")
					{
						l=mid+1;
					}
				}
				cout<<"! "<<tmpx+ans-1<<'\n';
				fflush(stdout);
			}
		}
		else
		{
			cout<<"! 1\n";
			fflush(stdout);
			continue;
		}
	}
	return 0;
}

评论

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

正在加载评论...