50 条题解

  • 3
    @ 2017-06-06 08:10:50

    这不是个BFS嘛。。一脸懵逼
    先对输入的数字排序,就可以保证先生成出0的那个数字一定最小
    最多5000种状态。。BFS秒过

    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <algorithm>
    #include <queue>
    #include <string>
    #include <map>
    #include <cstring>
    #include <ctime>
    #include <vector>
    #define inf 1e9
    #define ll long long
    #define For(i,j,k) for(int i=j;i<=k;i++)
    #define Dow(i,j,k) for(int i=k;i>=j;i--)
    using namespace std;
    int n,m,a[101],q[10001],num[10001],nxt[10001],vis[10001],l=1,r,ans,tot,ANS[10001];
    int main()
    {
        scanf("%d%d",&n,&m);
        For(i,1,m)  scanf("%d",&a[i]);
        sort(a+1,a+m+1);
        For(i,1,m)  if(a[i]&&!vis[a[i]%n])  q[++r]=a[i]%n,vis[a[i]%n]=1,num[r]=a[i],nxt[r]=-1;
        while(l<=r)
        {
            int t=q[l];
            if(t==0){ans=l;break;}
            For(i,1,m)
            {
                int tmp=(t*10+a[i])%n;
                if(!vis[tmp])
                    q[++r]=tmp,num[r]=a[i],nxt[r]=l,vis[tmp]=1;
            }
            l++;
        }
        while(ans!=-1)
        {
            ANS[++tot]=num[ans];
            ans=nxt[ans];
        }
        Dow(i,1,tot)    printf("%d",ANS[i]);
    }
         
    
  • 1
    @ 2008-11-01 16:59:17

    (a*b) mod c=(a mod c*b mod c) mod c

    (a+b) mod c=(a mod c+b mod c) mod c

    因此构图,一个余数对应一个点,对于每一个余数k,若(j*10+a[i]) mod n=l,则k与l连边,权为a[i]

    求最短路即可

  • 1
    @ 2008-11-01 16:29:18

    感谢吴豪..

    令我恍然大虎..

    ``原来余数可以这样转换的..

    好弱的数据..

    我自己写了一组.

    44440

    10

    44

    88

    242

    52

    24

    346

    241

    254

    123

    褂掉..抱着试试的心态交上去..竟然..A了..

  • 1
    @ 2006-05-24 20:42:04

    不用记录前面所有除过的数,只需要记录前面的余数。建一个图,图中的节点表示任意数除以n的余数,利用广搜,假设前一步的节点是x,那么下一步的节点就是(x*10+a[i]) mod n,两点间的权值是a[i],那么从0出发,当走回0的时候,一路上的权值全部连起来,就是所求的数字。其核心思想就是利用余数代表前面的运算结果,避免记录和处理太大的数。注意针对余数进行判重。

  • 0
    @ 2018-07-28 13:34:28

    =<
    题目没说答案范围,我一开始估计是100位数字以内,结果总是WA第一个点,我以为第一个点是小数字的边界问题,结果开成500位就AC了。。

    DP+按模分类

    #include <bits/stdc++.h>
    using namespace std;
    #define FOR(i,n) for (int i=1;i<=n;i++)
    #define REP(i,a,b) for (int i=a;i<=b;i++)
    #define pb push_back
    #define mp make_pair
    #define ll long long
    #define pos(x,y) (x+(y)*n)
    const int N=100000+10;
    const int inf=0x3f3f3f3f;
    const ll mod=1000000007;
    const double eps=1e-8;
    
    int n,m;
    int a[20];
    int f[510][10][5010];
    int ten[510];
    int main() {
        //freopen("in.txt","r",stdin);
        //freopen("out.txt","w",stdout);
        cin>>n>>m;
        FOR(i,m) {
            int t;cin>>t;
            a[t]=1;
        }
        if (n<10) {
            FOR(i,9) {
                if (n*i<10&&a[n*i]) {
                    cout<<n*i<<endl;
                    return 0;
                }
            }
        }
        REP(i,0,9) if (a[i]) f[1][i][i%n]=1;
        ten[0]=1;
        FOR(i,500) ten[i]=ten[i-1]*10%n; 
        FOR(i,500) {
            REP(j,0,9) if (a[j]) REP(j2,0,9) if (a[j2]) {
                REP(k,0,n-1) {
                    f[i+1][j2][(j2*ten[i]+k)%n]|=f[i][j][k];
                }
            }
        }
        REP(i,2,500) FOR(j,9) if (a[j]) {
            if (f[i][j][0]) {
                int s=j;
                cout<<s;
                int t=(n-(j*ten[i-1])%n)%n;
                int now=i-1;
                while (now) {
                    REP(k,0,9) if (a[k]) {
                        if (f[now][k][t]) {
                            cout<<k;
                            t=(n+t-(k*ten[now-1])%n)%n;
                            break;
                        }
                    }
                    now--;
                }
                return 0;
            }
        }
        return 0;
    }
    
  • 0
    @ 2012-08-03 23:43:31

    #01: Accepted (364ms, 644KB)

    #02: Accepted (367ms, 644KB)

    #03: Accepted (102ms, 644KB)

    #04: Accepted (106ms, 644KB)

    #05: Accepted (94ms, 644KB)

    #06: Accepted (110ms, 644KB)

    #07: Accepted (121ms, 644KB)

    #08: Accepted (129ms, 644KB)

    #09: Accepted (129ms, 644KB)

    #10: Accepted (145ms, 644KB)

    Accepted / 100 / 1671ms / 644KB

    o(n)的没秒杀?真心自卑了

  • 0
    @ 2010-07-14 15:34:51

    Accepted 有效得分:100 有效耗时:9ms

    这题用DP好啊~只是被那ansistring恶心到了,速度降了不少……

  • 0
    @ 2009-11-07 14:13:59

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    1次秒杀 呵呵

  • 0
    @ 2009-11-02 19:42:59

    核心代码

    for j:=0 to n-1 do

    if v then

    for k:=1 to m do

    begin

    e:=(a[k]*x+j)mod n;

    if not v then

    begin

    v:=true;

    f:=a[k];

    g:=j;

    end else

    if (a[k]0) then

    if (a[k]

  • 0
    @ 2009-10-30 16:02:25

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    不幸 第299个通过 ……………………………………

  • 0
    @ 2009-10-29 21:20:29

    太囧了,第一次竟然内存溢出...

    我只能说,评测机太萎了,还好最后秒掉了...

  • 0
    @ 2009-10-27 08:41:06

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    orz花了我二十分钟...

    BFS解决~

    不过DP确实没想出来,膜拜想出DP并写出来秒杀的牛们...

    OTL...

  • 0
    @ 2009-09-12 15:27:00

    楼下神牛:

    BFS可以拿余数判重……所以也可以AC

    不过我为啥202了?

  • 0
    @ 2009-10-15 09:27:28

    我第一个点TLE/格式错误

    其他90分……

    真是无语……

    我回楼下的。。。确实这样。。。

    囧了。。。

    谢谢。

  • 0
    @ 2009-08-04 20:43:15

    要用高精吗

  • 0
    @ 2009-07-26 14:58:42

    比较大小要从头比哦.不要像我一样犯低级错误..

  • 0
    @ 2009-07-19 20:25:14

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 9ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:9ms

    呼呼,滚动数组太牛B了!

  • 0
    @ 2009-07-12 23:07:15

    这10个十进制数字,有多少位啊?????????????????????????????????????????????????????????????????

    也就是说,是用以个数字(0,1,2....9)还是任意自然数啊?????????????????????????????????????

  • 0
    @ 2009-05-28 09:58:04

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

    BFS万岁!

    AC第一百题!

  • 0
    @ 2009-03-28 09:36:57

    FT。BFS水题一次AC

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

信息

ID
1065
难度
7
分类
其他 | 数学 点击显示
标签
(无)
递交数
1481
已通过
260
通过率
18%
被复制
6
上传者