gggo


私信TA

用户名:dotcpp0646213

访问量:642

签 名:

等  级
排  名 2719
经  验 2178
参赛次数 2
文章发表 6
年  龄 0
在职情况 学生
学  校
专  业

  自我简介:

解题思路:
题目给出了初始的两个值a、b,进行线性的组合,让我们求解求最大不能组合出的数字;假设该数字是n,那么从n+1一直到无穷都必须能够由a、b进行组合。

可以很容易的想到(后面的通过前面的+a、+b得到),这串组合数字最小的正周期为T=min(a,b),那么只要我们求得的第一个数字x ,其后连续T位都能由a、b组合即可得到答案为x-1。


注意事项:

  1. 使用数组visit[i]表示是否由a、b组合得到,初始值visit[a]=visit[b]=1,visit数组空间必须足够大。

  2. 设置变量con记录连续次数,且当visit[i]值为1时,则该数可以再+a、+b,即visit[i+a]=visit[i+b]=1;若不为1,则变量con重置为0;当con=min(a,b)时,结束循环。


参考代码:

#include

using namespace std;

int main(){

     int  i,a,b,con=0,temp;//con表示当前连续次数

     int visit[100000]={0};

     cin>>a>>b;

     if(a>b){

         temp=a;

         a=b;

         b=temp;

     }

    visit[a]=visit[b]=1;

     for(i=1;con<a;i++){

         if(visit[i]) {

              visit[i+a]=visit[i+b]=1;

              con++;

          }else{

              con=0;

          }

     }

    cout<<i-a-1;

    return 0;

}


 

0.0分

1 人评分

  评论区

  • «
  • »