ACM_送气球（规律题）

送气球

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

为了奖励近段时间辛苦刷题的ACMer，会长决定给正在机房刷题的他们送气球。N位ACMer的围成了一个圈，会长分别间隔1,2,3,4.......个ACMer送一个气球，请问是不是所有的ACMer都有气球呢？

Input:

输入一个数字N（2≤N<1000000000），代表ACMer的人数。

Output:

如果所有人都有，输出‘YES’，否则输出‘NO’。

Sample Input:

Sample Output:

YES

NO

NO

NO

Hint:

N = 5,首先会长给一号和二号ACMer一个糖果，之后给四号一个糖果，按照循环，再给二号一个糖果，再给一号一个糖果，再给一号一个糖果......
解题思路：咋看这道题给的数据n最大是10的9次方，再结合题意，纯找规律题啊。但是菜鸡比赛时测试代码下标写错了，结果半天跑不出结果，比赛完后修改了一下并A了这水题。
给出的提示意思是，先给1号一个糖果，间隔1到2号再给2号糖果，间隔2到4号给其糖果，就这样子循环给。
测试代码找规律：

 #include<bits/stdc++.h>

 using namespace std;

 int main()

 {

     for(int N=;N<;++N){

         int j=,t=;

         bool a[N],flag=false;

         memset(a,false,sizeof(a));

         a[]=a[]=true;//下标从0开始

         while(t<){

             j=(j+t)%N;//j：0~N-1

             if(!a[j])a[j]=true;

             t++;

         }

         for(int i=;i<N;++i){

             if(!a[i]){flag=true;break;}

         }

         if(!flag)cout<<N<<endl;

         //else cout<<N<<":0"<<endl;

     }

     return ;

 }

由于间隔t给的是10的6次方，所以找N个ACMer是否都分到糖果只枚举到1000个，这样不用等太久。运行结果是 4  8  16  32   64 。。。熟悉吧！！！这就是规律！！！接下来就好办了，题目给的N最大为10的9次方在int范围内，所以先打表2^i次方，再枚举判断N是否在这里面即可。
AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 int main()

 {

     int a[]={},n;

     bool flag;

     for(int i=;i<;i++)

         a[i]=*a[i-];

     while(cin>>n){

         flag=false;

         for(int i=;i<;++i){

             if(n==a[i]){flag=true;break;}

         }

         if(flag)cout<<"YES"<<endl;

         else cout<<"NO"<<endl;

     }

     return ;

 }

巴特西

ACM_送气球（规律题）

送气球

Time Limit: 2000/1000ms (Java/Others)

Problem Description:

Input:

Output:

Sample Input:

Sample Output:

最新文章

热门文章