首页 > 其他分享 >题解:AT_arc184_a [ARC184A] Appraiser

题解:AT_arc184_a [ARC184A] Appraiser

时间:2024-09-23 15:45:57浏览次数:10  
标签:10 arc184 一组 硬币 int 题解 假币 cp Appraiser

题意

\(1000\) 个硬币中有 \(10\) 个假币,你每次可以询问两个位置的硬币类型是否相同,你需要用不超过 \(950\) 次询问找出所有假币的位置。

思路

将前 \(990\) 个硬币每 \(11\) 个分一组,共 \(90\) 组,余 \(10\) 个单独分一组。

询问每组第 \(1\) 个硬币和这组后面硬币的关系。因为只有 \(10\) 个假币,所以如果含有 \(11\) 个硬币的一组全部相同,那么这一组就全是真币,挑出一个真币跟含有假币的组(即含有不同硬币的一组)的第 \(1\) 个硬币比较,即可判断出这一组硬币的真假情况,最多 \(90\times 10+9+10=919\) 次询问,可以通过。

注意因为最后一组只有 \(10\) 个,所以当每组的硬币都相同时,\(10\) 个假币就都在最后一组。

代码

#include <bits/stdc++.h>
using namespace std;
int n,m,q,nst;
bool ys[1005][1005],ist[1005];
vector<int> fk;
bool cp;
signed main() {
	cin>>n>>m>>q;
	for(int i=1;i<=1000;i+=11){
		for(int x,j=i+1;j<=min(1000,i+10);j++){
			cout<<"? "<<i<<" "<<j<<endl;
			cin>>x;
			if(x==1)
				ys[i][j]=true,ist[i]=true,cp=true;
		}
		if(!ist[i])
			nst=i;
	}
	if(!cp){
		cout<<"! ";
		for(int i=991;i<=1000;i++)
			cout<<i<<" ";
		cout<<endl;
		return 0;
	}
	for(int x,i=1;i<=1000;i+=11){
		if(!ist[i]) continue;
		cout<<"? "<<nst<<" "<<i<<endl;
		cin>>x;
		if(x) fk.push_back(i);
		for(int j=i+1;j<=min(1000,i+10);j++){
			if(ys[i][j]^x)
				fk.push_back(j);
		}
	}
	cout<<"! ";
	for(int v:fk)
		cout<<v<<" ";
	cout<<endl;
	return 0; 
}

标签:10,arc184,一组,硬币,int,题解,假币,cp,Appraiser
From: https://www.cnblogs.com/WuMin4/p/18427162

相关文章

  • CF1270H Number of Components 题解
    Description给一个长度为\(n\)的数组\(a\),\(a\)中的元素两两不同。对于每个数对\((i,j)(i<j)\),若\(a_i<a_j\),则让\(i\)向\(j\)连一条边。求图中连通块个数。支持\(q\)次修改数组某个位置的值,每次修改后输出图中连通块个数。\(n,q\le5\times10^5,1\lea_i\le10^......
  • 2024ICPC网络赛第二场题解(部分)
    前言这场相对作用大一点,最后顶着队友的怀疑压力乱搞出了C,但是后面看题解发现似乎是数据弱了跑过去,其实复杂度是队友分析的那样,是不正确的,但是毕竟是打名额的比赛,过了就是过了,这里分享一下C题的乱搞做法,以及其他题的我们队赛时代码。下面的顺序按过题顺序(也差不多是难度递增顺序)......
  • 网站程序打不开数据库错误等常见问题解决方法
    当遇到网站打不开或者数据库错误等问题时,可以按照以下步骤来诊断并解决问题:检查网站根目录:如果上传数据后显示“主机开设成功!”或“恭喜,lanmp安装成功!”,这通常是因为服务器默认放置了一个index.htm文件。此时应检查wwwroot目录内是否有自己的程序文件,并考虑删除默认的index.h......
  • 题解:AT_arc184_a [ARC184A] Appraiser
    本质上还是官方题解的分组并利用\(M\)不大的思路。询问次数\(Q\)离最简单的每个扫一遍就可以知道答案的做法少了\(50\)次。我们考虑如何减少这个次数。首先你可以发现一次询问可以覆盖到两个数,也就是说所有的数都被覆盖时只需要询问\(500\)次。我们考虑把不同的对拉出......
  • 网站打不开数据库错误等常见问题解决方法
    当遇到网站打不开且出现数据库错误等问题时,可以采取以下步骤进行排查和解决:检查默认页面:如果网站显示“主机开设成功!”或者“恭喜,lanmp安装成功!”这样的信息,这可能是服务器默认放置的页面。检查wwwroot目录下是否有自己的程序文件,如果没有,上传正确的文件,并删除默认的index.ht......
  • [ABC371F] Takahashi in Narrow Road 题解
    洛谷题目链接Atcoder题目链接前言这道题我赛时想到了正解并打了出来,然后因为把\(l\)打成了\(1\)导致WA\(\times23\),然后又没场切六道题(悲。然后赛后有人说正解是珂朵莉树/线段树,然而我是珂朵莉树\(+\)线段树,呵。题意数轴上有\(n\)个人,第\(i\)个人初始在\(X_i\)处,每一次操作......
  • CF1239E Turtle 题解
    Description一只乌龟从\(2\timesn\)的棋盘的左上角走到右下角,只能往下或往右,需要给出一种方案来分配\(2n\)个数字使得乌龟走过的路径上的数之和的最大值最小。\(2\leqn\leq25,0\leqa_{1,i},a_{2,i}\leq5\times10^4\)。Solution设\(pre_{i}=\sum_{j=1}^{i}{a_{1,i}......
  • P5975 photo 题解
    Solution先离散化,记\(f(l,r,p)\)为覆盖了\([l,r]\)区间内纵坐标\(\gep\)的点最少矩形个数。则:\[f(l,r,p)=\min(f(l,r,p),f(l,mid,p)+f(mid+1,r,p))\]\[f(l,r,p)=\min(f(l,r,p),f(l,r,res)+1)\]令\(h\)为用面积为\(S\)的矩形去覆盖\([l,r]\)区间的高度,即\(S/(r......
  • P9192 Pareidolia 题解
    Statement给串\(t\),定义\(B(s)\)为\(s\)删一些字符后能出现最多多少个bessie,\(A(t)\)表示对\(t\)的所有子串\(s\)求\(B(s)\)的和,有\(q\)次单点修改,每次改完输出\(B(s)\).Solution动态dp,但是带矩乘\(6^3\)常数,不好.还是考虑分治咋做.现在有区间\([l,mid],......
  • P3703 树点涂色 题解
    Statement树,每个点有一个颜色,初始每个点颜色互不相同到根链涂上新颜色链颜色数\(u\)子树内点\(v\)到根路径的最多颜色数Solution首先,相同颜色的点一定构成一条从下往上的链考虑LCT,维护一个性质:一条实链的点的颜色相同.于是\(u\)到根的颜色数\(=\)\(u\)到根的虚......