题解 - Vijos

2

Lifi LV 10 @ 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

HLBhahaqiu LV 8 @ 2020-12-11 21:28:56

#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

Lifi LV 10 @ 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

NOWO LV 4 @ 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

我是神 LV 10 @ 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

Odin. LV 8 @ 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

qig159357 LV 8 @ 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

vcvycy LV 8 @ 2013-08-29 16:41:03

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

0

hahacool LV 10 @ 2010-04-06 16:35:58

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

这题真有趣~

Dijk

0

prince_hao LV 10 @ 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

jacklv LV 10 @ 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

naneux LV 8 @ 2009-09-27 20:58:40

TLE三个点啊，我的天……

0

mznanan LV 10 @ 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

lijian3256 LV 10 @ 2009-08-04 10:53:32

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

B：题目说了 M>0

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

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

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

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

好吧我们都很弱。。

0

fjxmlhx LV 10 @ 2009-08-21 20:52:11

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

存在a1x1+a2x2..=D

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

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

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

0

cgy4ever LV 10 @ 2009-03-16 19:49:06

猥琐的过了...

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

0

voyagec2 LV 10 @ 2009-02-24 17:50:21

DP到5000000就可以了

0

pop542677493 LV 3 @ 2009-02-17 19:07:30

jkol

0

curimit LV 10 @ 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

jimistdponde LV 8 @ 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

题解

40 条题解

牛场围栏

信息

状态

开发

支持

题解

40 条题解

牛场围栏

信息

状态

开发

支持

还没有账户？

登录