51nod 1109 01组成的N的倍数

用01 组成 N的最小倍数

这个BFS搜索就好。

类似这道： ZOJ Problem Set - 1530

每次要么是0 要么是1，记入余数，和前驱。

#include<bits/stdc++.h>

using namespace std;

struct node
{
int a,b,pre;
}a[2000000];

void output(int k)
{
if (a[k].pre !=-1) output(a[k].pre);
printf("%d",a[k].a);
}

int used[2000000];

int main()
{
int n;
scanf("%d",&n);

a[0].a=1;
a[0].b=1;
a[0].pre=-1;

int L=1;
    int r=0;
      for (int i=0;i<L;i++){
      for (int j=0;j<2;j++)
      {
        r=(a[i].b*10+j)%n;
        if (!used[r])
        {
            a[L].a=j;
            a[L].b=r;
            a[L].pre=i;
            used[r]=1;
            L++;
        }
        if (r==0) break;
      }
      if (r==0) break;
    }

output(L-1);
printf("\n");

return 0;
}

巴特西

51nod 1109 01组成的N的倍数

最新文章

热门文章