题解 P5887 【Ringed Genesis】

· · 题解

作为2020年的第2道比赛题，还是比较简单的。

思路

这题代码并不难写，重点在于思路。

先举几个例子。如果环长8，步长2，会出现这样的情况：

可以发现，当初始点是红点时，蓝色的4块永远跳不到，否则红色的4块永远跳不到。

如果环长8，步长6，会出现这样的情况：

和上面效果是一样的。

再如果环长8，步长4，又会出现这样的情况：

出现了4种颜色。

综上，不难发现颜色的个数就是环长和步长的最大公约数。

只要一种颜色有一个格子上有兔子，那么所有这种颜色上都能够跳到。

答案就是跳不到的颜色个数乘以每个颜色有多少格。

这样，代码就呼之欲出了。

代码

相信没有多少人喜欢上面的一通分析吧，那么，你们喜欢的代码来了——

#include<cstdio>
using namespace std;
const int MAXN=1e6+10;
bool s[MAXN];//s[i]表示有没有兔子在颜色i上
int gcd(int num1,int num2){//标准gcd求最大公约数
    if(num2==0) return num1;
    return gcd(num2,num1%num2);//辗转相除法
}
int main(){
    int n,m,d,a,ans=0;
    scanf("%d%d%d",&n,&m,&d);
    int gc=gcd(n,d);//求出颜色个数
    for(int i=1;i<=m;i++){
        scanf("%d",&a);
        s[a%gc]=1;//标记
    }
    for(int i=0;i<gc;i++)
        if(!s[i]) ans+=(n/gc);//跳不到就加上每个颜色的格数
    printf("%d",ans);
    return 0;//华丽结束
}

看我这么辛苦画了这么些个图，总得点个赞再走呀！