题解

39 条题解

  • 1
    @ 2019-08-13 21:38:03

    我也不知道这算什么,记忆化搜索?
    思路有点奇葩,就是统计连续出现的可行解次数,只要次数等于最小木棍长度,那么之后的长度都能通过添加最小木棍来获得。于是向前取最后一个不能组成的数为结果。

    #include <iostream>
    #include <algorithm>
    #define maxl 10000000
    
    using namespace std;
    
    int n,m;
    int len[100];
    bool vis[maxl]={0};
    
    int main()
    {
        cin>>n>>m;
        int i,j,k;
        for(i=0;i<n;i++)
        {
            cin>>len[i];
        }
        sort(len,len+n);
        if(len[0]-m<=1)
        {
            cout<<-1<<endl;
            return 0;
        }
        int acc=0;
        vis[0]=true;
        for(i=0;i<maxl;i++)
        {
            if(vis[i])
            {
                acc++;
                if(acc>=len[0]-m)
                {
                    break;
                }
                for(j=0;j<n;j++)
                {
                    for(k=len[j]-m;k<=len[j];k++)
                    {
                        vis[i+k]=true;
                    }
                }
            }
            else
            {
                acc=0;
            }
        }
        if(i<maxl)
        {
            cout<<i-acc<<endl;
        }
        else
        {
            cout<<-1<<endl;
        }
        return 0;
    }
    
  • 0
    @ 2019-08-13 21:38:03

    我也不知道这算什么,记忆化搜索?
    思路有点奇葩,就是统计连续出现的可行解次数,只要次数等于最小木棍长度,那么之后的长度都能通过添加最小木棍来获得。于是向前取最后一个不能组成的数为结果。

    #include <iostream>
    #include <algorithm>
    #define maxl 10000000
    
    using namespace std;
    
    int n,m;
    int len[100];
    bool vis[maxl]={0};
    
    int main()
    {
        cin>>n>>m;
        int i,j,k;
        for(i=0;i<n;i++)
        {
            cin>>len[i];
        }
        sort(len,len+n);
        if(len[0]-m<=1)
        {
            cout<<-1<<endl;
            return 0;
        }
        int acc=0;
        vis[0]=true;
        for(i=0;i<maxl;i++)
        {
            if(vis[i])
            {
                acc++;
                if(acc>=len[0]-m)
                {
                    break;
                }
                for(j=0;j<n;j++)
                {
                    for(k=len[j]-m;k<=len[j];k++)
                    {
                        vis[i+k]=true;
                    }
                }
            }
            else
            {
                acc=0;
            }
        }
        if(i<maxl)
        {
            cout<<i-acc<<endl;
        }
        else
        {
            cout<<-1<<endl;
        }
        return 0;
    }
    
  • 0
    @ 2017-08-07 18:46:17

    /*
    真的是老泪纵横,这题用多组输入,结果有1 的情况,输出,完了我用continue,结果一直WA在第十个样例,一改回单租输入就AC了,我的内心是绝望的。
    */

    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    #include <algorithm>
    #include <queue>
    #include <vector>
    #define P pair<int,int>

    using namespace std;

    const int ma=3010,INF=0x3f3f3f3f;
    int l[ma],f[ma],cnt;
    bool vis[ma];

    void solve()
    {
    int m=l[1];
    memset(f,INF,sizeof(f));
    f[0]=0;
    priority_queue<P,vector<P>,greater<P> > q;
    q.push(P(0,0));
    int x;
    P t;
    while(!q.empty())
    {
    t=q.top();
    q.pop();
    x=t.second;
    if(f[x]<t.second) continue;
    for(int i=1; i<=cnt; ++i)
    {
    if(f[x]+l[i]<f[(x+l[i])%m])
    {
    f[(x+l[i])%m]=f[x]+l[i];
    q.push(P(f[(x+l[i])%m],(x+l[i])%m));
    }
    }
    }

    for(int i=0; i<m; ++i)
    if(f[i]==INF)
    {
    puts("-1");
    return;
    }

    int ans=0;
    for(int i=0; i<m; ++i)
    ans=max(ans,f[i]-m);
    printf("%d\n",ans);
    }

    int main()
    {
    int n,m;
    scanf("%d%d",&n,&m);
    memset(vis,false,sizeof(vis));
    int x;
    for(int i=0; i<n; ++i)
    {
    scanf("%d",&x);
    for(int j=(x-m>0?x-m:1); j<=x; ++j)
    vis[j]=true;
    }
    if(vis[1])
    {
    puts("-1");
    return 0;
    }

    cnt=0;
    for(int i=1; i<=3000; ++i)
    if(vis[i]) l[++cnt]=i;

    solve();

    return 0;
    }

  • 0
    @ 2016-11-30 14:36:37

    #include <cstdio>
    #include <iostream>
    #include <string>
    #include <algorithm>
    #include <queue>
    #include <vector>

    using namespace std;
    #define debug cout<<"Orzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz"<<endl;
    const int INF = 2047483647;
    int dis[3426];
    int c[422567], vis[5122567];
    int n,m;
    queue <int> q;
    vector <int> v;
    int min_length = INF;
    int max_length = -5;
    int iv[3456];
    int spfa() {
    for(int i = 0; i <= min_length; i++) {
    dis[i] = INF;
    }
    for(int i = 1; i <= c[0]; i++) {
    // cout<<now<<' '<<i<<' '<<c[i]<<' '<<endl;
    int now = c[i] % min_length;
    if(dis[now] == INF || dis[now] > c[i]) {
    dis[now] = c[i];
    q.push(now);
    }
    }
    // debug;

    while(!q.empty()) {
    int now = q.front(); q.pop();
    vis[now] = 0;
    if(!iv[now]) {
    v.push_back(now);
    iv[now] = 1;
    }
    for(int i = 0; i < v.size(); i++) {
    int nn = (dis[v[i]] + dis[now]) % min_length;
    if(dis[nn] > dis[now] + dis[v[i]]) {
    dis[nn] = dis[now] + dis[v[i]];
    // if(nn_mod == 3) {
    // cout<<dis[nn_mod] <<' '<<"dis["<<now_mod<<"] = "<<dis[now_mod] << ' '<<nn<<endl;
    // }
    if(!vis[nn]) {
    vis[nn] = 1;
    q.push(nn);
    }
    }

    }

    }
    for(int i = 0; i < min_length; i++) {
    // cout<<i<<' '<<dis[i]<<' '<<min_length<<' '<<endl;
    if(dis[i] < INF) {
    max_length = max(max_length, dis[i]);
    } else return -1;
    }
    return max_length - min_length;
    }

    int main() {
    cin>>n>>m;
    for(int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    for(int j = 0; j <= m && x - j; j++)
    if(!vis[x - j]) {
    vis[x - j] = 1;
    c[++c[0]] = x - j;
    min_length = min(min_length , c[c[0]]);
    if(x - j == 1) {
    cout<< - 1 <<endl;
    return 0;
    }
    }
    }
    cout<<spfa()<<endl;
    // cout<<spfa();
    return 0;
    }

  • 0
    @ 2016-11-15 19:45:13

    Magic SPFA~
    ```c++
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    using namespace std;

    #define INF (1<<30)
    #define LL long long
    #define f(a,b,c) for(int a=(b);a<=(c);a++)

    #ifdef WIN32
    #define AUTO "%I64d"
    #else
    #define AUTO "%lld"
    #endif

    const int N=3005;

    int n,m;
    int a[N];
    bool b[N];
    int c[N],tot;
    int maxstp=-1;
    int len;

    int dis[N];
    bool vis[N];
    queue<int> q;

    void SPFA()
    {
    memset(dis,127,sizeof(dis));
    q.push(0); vis[0]=1; dis[0]=0;
    while(!q.empty()) {
    int t=q.front(); q.pop(); vis[t]=0;
    f(i,1,tot) {
    if(dis[(t+c[i])%maxstp]>dis[t]+c[i]) {
    dis[(t+c[i])%maxstp]=dis[t]+c[i];
    if(!vis[(t+c[i])%maxstp]) {
    q.push((t+c[i])%maxstp);
    vis[(t+c[i])%maxstp]=1;
    }
    }
    }
    }

    }

    int main()
    {
    freopen("bullpen.in","r",stdin);
    freopen("bullpen.out","w",stdout);

    cin>>n>>m;
    f(i,1,n) {
    scanf("%d",&len);
    a[len-m>=1? len-m:1]++; a[len+1]--;
    }
    int sum=0;
    f(i,1,N-1) {
    sum+=a[i];
    if(sum>0){
    b[i]=1; c[++tot]=i;
    if(i==1) { cout<<-1; return 0; }
    maxstp=max(maxstp,i);
    }
    }

    SPFA();

    int maxpath=-1;
    f(i,0,maxstp-1) {
    if(dis[i]==2139062143) { cout<<-1; return 0; }
    maxpath=max(maxpath,dis[i]);
    }
    if(maxpath/maxstp==0) cout<<-1;
    else cout<<maxpath%maxstp+(maxpath/maxstp-1)*maxstp;
    return 0;
    }
    ```

  • 0
    @ 2016-06-14 19:51:59

    神奇的最短路,学习了~
    ```c++
    #include<cstdio>
    #include<algorithm>
    #include<queue>
    #include<cstring>
    #include<vector>
    using namespace std;
    const int INF = 2147483647;

    struct Po
    {
    int dis,u;
    Po(int a=0,int b=0) : dis(a),u(b) {}
    bool operator > (const Po &a) const { return dis>a.dis || (dis==a.dis && u>a.u); }
    };

    bool vis[3010];
    int dis[3010],n,m,min_length=INF;
    vector<int> done,length;

    int Dijkstra()
    {
    memset(vis,0,sizeof(vis));
    memset(dis,-1,sizeof(dis));
    priority_queue<Po,vector<Po>,greater<Po> > q;
    for(int i=0;i<(int)length.size();i++)
    {
    int now=length[i]%min_length;
    if(dis[now]==-1 || dis[now]>length[i])
    {
    dis[now]=length[i];
    q.push(Po(dis[now],now));
    }
    }

    while(!q.empty())
    {
    int now=(q.top()).u;q.pop();
    if(vis[now]) continue;
    vis[now]=true;
    done.push_back(now);

    for(int i=0;i<(int)done.size();i++)
    {
    int next=(dis[now]+dis[done[i]])%min_length;
    if(!vis[next]&&(dis[next]==-1||dis[next]>dis[now]+dis[done[i]]))
    {
    dis[next]=dis[now]+dis[done[i]];
    q.push(Po(dis[next],next));
    }
    }
    }

    int max_one=-5;
    for(int i=0;i<min_length;i++)
    {
    if(!vis[i]) return -1;
    max_one=max(max_one,dis[i]);
    }
    return max_one-min_length;
    }

    int main()
    {
    /*freopen("in","r",stdin);*/
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
    int k;
    scanf("%d",&k);
    for(int i=0;i<=m&&k-i>0;i++)
    {
    min_length=min(min_length,k-i);
    length.push_back(k-i);
    }
    }

    int ans=Dijkstra();
    printf("%d\n",ans==0 ? -1 : ans);
    return 0;
    }
    ```

  • 0
    @ 2013-08-29 16:41:03

    Accepted, time = 123 ms, mem = 848 KiB, score = 120
    最短路果然强大啊。。。
    强烈膜拜用DP的大牛= =

  • 0
    @ 2010-04-06 16:35:58

    从递推推来推去就推到最短路了~

    这题真有趣~

    Dijk

  • 0
    @ 2009-11-03 19:58:40

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    竟然1A了!!!!!!

    感谢楼下们提供的最短路的思路!如饮醍醐!

  • 0
    @ 2009-11-02 17:05:51

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    好题!!!

    你们不要用那种烂的背包放着乱搞

    那么好的方法还是要想一下

    转化成最短路

  • 0
    @ 2009-09-27 20:58:40

    TLE三个点啊,我的天……

  • 0
    @ 2009-09-07 17:04:27

    数学方法不会..就用dp过了..

    先是把所有可用的木棒长度求出来,若存在长度为1的或者所有木棒长度最小公约数不为0,则输出-1,连续个最小长度的长度可拼凑成的话,则以后一定也都可以..一遇到这个情况..直接输出前面的最优值..

    program mzn;

    var f:array[0..5000000]of boolean;

    now,tem,n,m,i,j,tot,p:longint;

    l:array[0..3000]of longint;

    use:array[0..3000]of boolean;

    function gcd(X,y:longint):longint;

    begin

    if x mod y=0 then exit(y);

    gcd:=gcd(y, x mod y);

    end;

    begin

    readln(n,m);

    for i:=1 to n do

    begin

    readln(l[i]);

    use[l[i]]:=true;

    end;

    for i:=1 to n do

    for j:=1 to m do

    begin

    if l[i]-ji then break;

    if f[i-l[j]] then

    begin

    f[i]:=true;

    break;

    end;

    end;

    if f[i]=false then now:=0

    else inc(now);

    if now=l[1] then

    begin

    writeln(i-now);

    halt;

    end;

    end;

    end.

  • 0
    @ 2009-08-04 10:53:32

    A君:M不会等于0吧,否则我们的优化就错了

    B:题目说了 M>0

    交上去。。第五个WA。。。此时M=0.......

    A君:不会有重复的木材吧。

    B:不会有这么恶心的数据吧

    交上去。。。第9第10个点TLE。。。此时大量重边。。。

    好吧 我们都很弱。。

  • 0
    @ 2009-08-21 20:52:11

    考虑下对于任意的D,若不定方程有解,则必定

    存在a1x1+a2x2..=D

    a1x1=D-a2x2...(mod a1)

    所以有解充要条件是存在a2x2+a3x3...关于D同余且D>=a2x2+a3x3...

    所以可以求出对于每一个i(0

  • 0
    @ 2009-03-16 19:49:06

    猥琐的过了...

    那个数学方法不太明白的说

  • 0
    @ 2009-02-24 17:50:21

    DP到5000000就可以了

  • 0
    @ 2009-02-17 19:07:30

    jkol

  • 0
    @ 2009-02-04 21:40:28

    这是顺推的DP:

    编译通过...

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

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

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

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

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

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

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

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

    ├ 测试数据 09:运行超时...

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

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

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

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

    Unaccepted 有效得分:92 有效耗时:941ms

    这是逆推的DP:

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2008-11-13 13:10:11

    编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • 0
    @ 2009-01-23 11:05:34

    如果一个长度a后b(b:=minl)都能取到,那么a就为所要求的解

    判断无限解:1 能取到长度1的木条

    2 所有木条长度的最大公约数不为1(或当前搜索的长度超过最大的两段木条的最小公倍数)

信息

ID
1054
难度
6
分类
其他 | 数学 点击显示
标签
递交数
775
已通过
213
通过率
27%
被复制
2
上传者