P7817 [RC-05] 迷失自我 题解

Da_un · 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;
}

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