自动搬运

查看原文

来自洛谷，原作者为

	Da_un Rome was not built in a day

搬运于2025-08-24 22:33:22，当前版本为作者最后更新于2021-08-17 13:46:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题在比赛中是第一题，所以理论上讲并不算很难，但看到题面，心中不免有些颤动。再看测试数据，一个测试点 $2$ 分，另一个有 $98$ 分，目测应该是一个规律题，但写了半天就是写不出来，直到赛后看了公开的题解才恍然大悟，所以我在这里更通俗的说一下解法，也是弥补一下当时的遗憾~~

题目传送门

思路

• 对于第一个测试点，考虑了一下，直接暴力搜索，可以很轻松地拿到 $2$ 分。

• 对于第二个测试点，很显然第一种策略肯定是不行的，所以要换一种思维方式，因为字符串 $S$ 和 $T$ 都只是由 $7$ 或 $9$ 组成的，所以对于任意一个长度大于 $2$ 的字符串，串中一定存在一个数的出现次数大于 $1$，所以不难发现，两个重复出现的数的最大公约数一定等于这个这个数，这两个重复出现的数字也可以看做长度为 $1$ 的区间。因此，可以把串中所有满足最大公约数为 $7$ 和 $9$ 并且长度为 $1$ 的区间对拿出来组成两个集合，这两个集合就可以唯一确定这个串(不明白的可以自己举个例子写一下)。

所以对于一个长度小于 $2$ 的字符串，它不满足第二种方法，推一下的话都只有一对字符串无法识别。所以直接判断 $n$ 的范围直接输出对应答案即可。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline long long read()
{
	long long s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') w=-1;
		ch=getchar();
	} 
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*w;
}
long long n,t;
void work()
{
	n=read();
	if(n>2)
		cout<<0<<endl;
	if(n<=2)	
		cout<<1<<endl; //推出的结果
}
int main()
{
	t=read();
	while(t--)
		work();
	return 0;
}

对于这道题，收获还是蛮多的~~