题解 - Vijos

0

freefly LV 10 @ 2009-09-04 17:18:13

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var

tw,n,i,j,k,s:longint;

w:array[0..100]of longint;

dp:array[0..100000]of longint;

f:array[0..100000]of longint;

ans:array[0..100]of longint;

begin

readln(tw);

readln(n); s:=0;

for i:=1 to n do

begin

readln(w[i]);

s:=s+w[i];

end;

fillchar(dp,sizeof(dp),0);

fillchar(f,sizeof(f),0);

dp[0]:=1;

for i:=1 to n do

begin

for j:=s downto w[i] do

begin

if (dp[j]0)and(dp[j-w[i]]0) then f[j]:=1;

if (dp[j]=0)and(dp[j-w[i]]0) then dp[j]:=i;

if f[j-w[i]]=1 then f[j]:=1;

end;

end;

fillchar(ans,sizeof(ans),0);

for i:=1 to s do

//if dp[i]0 then writeln(i,' ',dp[i]);

dp[0]:=1;

if dp[tw]=0 then

begin writeln(0); exit; end;

k:=0;

if f[tw]=1 then

begin

writeln(-1);

exit;

end;

if (dp[tw]0)and(f[tw]=0) then

begin

while tw0 do

begin

j:=0;

//writeln(tw);

for i:=1 to dp[tw] do

if tw>=w[i] then

begin

if (dp[tw-w[i]]0)and((dp[tw-w[i]]

0

BlackS LV 8 @ 2009-08-28 14:09:50

编译通过...

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

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

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

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

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

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

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

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

├ 测试数据 09：答案错误...程序输出比正确答案长

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

如果有第9个点爆的话是因为在需要的路径中有一组数据的重量相同

如果有类似于

if f[j-w[i]]-2 then begin

if f[j]=-2 then begin

f[j]:=j-w[i];

a[j]:=i; end

else

if f[j]j-w[i] then f[j]:=-1;

可以将最后一句改成

if f[j]-2 then f[j]:=-1;

-2表示无解

第九个点是什么？

0

363059129 LV 10 @ 2009-08-22 14:07:14

第四个点cheat~~~~

我也不想啊……

0

hj363059129 LV 9 @ 2009-08-22 13:39:28

编译通过...

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

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

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

├ 测试数据 04：答案错误...程序输出比正确答案长

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

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

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

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

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

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

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

Unaccepted 有效得分：90 有效耗时：0ms

第四个貌似不是永恒の灵魂提供的数据...

难不成改过了...

郁闷

过不去

第四个点答案是3 6 10

……

0

broken-boat LV 7 @ 2009-08-18 09:14:18

70---|80---|90---|100

OMG kill me

注意这个数据..

4

1

1

1

1

ans 1 2 3 4

0

SecretAgent LV 10 @ 2009-08-17 08:54:16

一种DP是

f表示前i个物品能否到达j的重量,很容易写

但是不能这样解,大约要要计算10^7次

于是改成递推

longint完全没问题

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

LP.Fighting LV 10 @ 2009-08-14 23:38:32

字符串记路径

循环别乱加break...WA了2次...

0

zhqc LV 9 @ 2009-08-14 11:51:04

这题太恶性^做了N次^

0

LX11111 LV 10 @ 2009-08-07 13:31:19

编译通过...

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

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

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

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

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

├ 测试数据 06：运行超时|格式错误...

├ 测试数据 07：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 08：答案正确... 41ms

├ 测试数据 09：答案正确... 41ms

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

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

Unaccepted 有效得分：80 有效耗时：82ms

var

w:array[1..100]of longint;

f:array[0..100000]of string;

a:array[0..100000]of integer;

n,i,j,tw,rw:longint;

s:string;

procedure print;

var

i,j,k,l:longint;

s,s1:string;

c:array[1..100000]of boolean;

begin

l:=length(f[tw]);

j:=2;s:='';

fillchar(c,sizeof(c),false);

while j

0

wzc1995 LV 10 @ 2009-08-05 17:57:58

谁有我耗时长？

编译通过...

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

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

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

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

├ 测试数据 05：答案正确... 259ms

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

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

├ 测试数据 08：答案正确... 259ms

├ 测试数据 09：答案正确... 244ms

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

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

Accepted 有效得分：100 有效耗时：762ms

谁有我程序短？

#include

using namespace std;

bool lu[10100][105];

int main()

{

long f[10100]={0};

int i,j,n,m,v,x;

long long k;

cin >> n >> m;

k=0;

for(i=1;i> v;

for(j=n-v;j>=0;j--)

if(f[j+v]

0

xjx8599 LV 10 @ 2009-08-05 02:21:28

program p1071;

var w,n,i,j,k,t:longint;

v:array[1..1000] of longint;

f:array[0..100000] of boolean;

g:array[1..100000,0..1000] of longint;

xx:array[1..1000] of boolean;

flag:boolean;

begin

readln(w);

readln(n);

for i:=1 to n do readln(v[i]);

f[0]:=true;

for i:=1 to n do

for j:=w downto v[i] do

if f[j-v[i]] then

begin

if (j=w) and f[w] then begin writeln(-1);exit;end;

if not f[j] then

begin

f[j]:=true;

flag:=false;

for k:=1 to g[j-v[i],0] do

begin

inc(g[j,0]);

g[j,g[j,0]]:=g[j-v[i],k];

if g[j-v[i],k]=i then flag:=true;

end;

if not flag then

begin

inc(g[j,0]);

g[j,g[j,0]]:=i;

end;

end;

end;

if not f[w] then writeln(0)

else

begin

for i:=1 to g[w,0] do

xx[g[w,i]]:=true;

for i:=1 to n do

if not xx[i] then begin write(i);break;end;

t:=i;

for i:=t+1 to n do

if not xx[i] then write(' ',i);

writeln;

end;

end.

一次AC

程序很丑贴一下

O(∩_∩)O~

0

340508965 LV 10 @ 2009-08-04 10:13:09

第一次提交

编译通过...

├ 测试数据 04：答案错误...程序输出比正确答案长

├ 测试数据 09：答案错误...程序输出比正确答案长

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

Unaccepted 有效得分：80 有效耗时：0ms

郁闷！然后去调查了第四组（永恒灵魂提供的）

4

3

2

3

1

标准输出 1

错误输出 2

注意：（如果你用类似01背包解法且第四组wa了的很肯能就是这个错误了）

如果f[m]代表能不能称出重量m(boolean类型) w[i]表示第i张纸牌重量

for i:=1 to n do

for m:= totw(总重量) downto w[i] do

if f[m-w[i]] then

begin

f[m]:=true;

row[m]:=i; //记录了当前重量为m时用到最后一个物品为i

end;

那为什么第四组会错了?

然后我就一直想不明白....

最后原始方法...人工模拟了一遍

首先第一次循环后

f[2]:=true; row[2]:=1;

第二次循环后

f[2]:=true; row[2]:=1;

f[3]:=true; row[3]:=2;

第三次循环(错误就出现在这里！！！)

f[4]:=true; row[4]:=3; //因为 f[4-w[3]]=f[3]=true

（可以看出答案已经得出来了但是根据上面的循环程序继续做了下去!!）

f[3]:=true; row[3]:=3; //因为前面的两重循环中f[3-w[3]]=f[2]=true

f[2]:=true; row[2]:=1; //没有改变

所以说本来重量totw=3, f[3]可以由w[2]=3 直接构成

但是后来继续循环会把它更新掉因为f[3]也可以由w[1]+w[3]=3构成

所以此时

totw=f[3]的方案重量+w[3] f[3]的方案重量=f[2]的方案重量+w[3]

我们已经把w[3]使用了2次.....

所以会挂掉

...........诶.........

所以遇到最优解相等时不要更新掉

后来修改了我再次提交

编译通过...

├ 测试数据 09：答案错误...程序输出比正确答案长

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

Unaccepted 有效得分：90 有效耗时：0ms

....郁闷看了大家的题解说法就去把数组改成longint了

可是没想到再次提交的结果（我要暴怒了！！！）

编译通过...

├ 测试数据 05：答案错误...程序输出比正确答案长

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

Unaccepted 有效得分：90 有效耗时：0ms

天要亡我........（打字很累人啊吐血了！！）

最后看到别人的题解说第五组可能会>maxlongint

sum[totw]表示重量为totw时的方案数

如果你写 if sum[totw]>1 then writeln(-1);是会挂的

你应该写 if sum[totw]=1 then 输出剩下纸牌

else writeln（-1）；

就这样

...我吐血了n升 n>maxlongint(不能活了！！)

总算Ac 掉了

第一次觉得ac好难啊啊啊啊啊啊

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

0

makaida LV 8 @ 2009-08-02 21:12:11

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var i,j,k,l,m,n:integer;

s0,v:longint;

a,b:array[1..100] of integer;

c:array[0..100000] of boolean;

d:array[0..100000,0..100] of boolean;

begin

readln(v);

readln(n);

for i:=1 to n do

begin

read(a[i]);b[i]:=i;

end;

for i:=1 to n-1 do

for j:=i+1 to n do

if a[i]>a[j] then

begin l:=a[i];a[i]:=a[j];a[j]:=l;l:=b[i];b[i]:=b[j];b[j]:=l;end;

c[0]:=true;s0:=0;

for i:=1 to n do

begin

for j:=s0 downto 0 do

begin

if (c[j]) then

begin

if c[j+a[i]] then

begin if j+a[i]=v then begin writeln(-1);halt;end; end

else

begin

for l:=1 to 100 do

if d[j,l] then d[j+a[i],l]:=true;

d[j+a[i],b[i]]:=true;

c[j+a[i]]:=true;

end;

end;

end;

s0:=s0+a[i];

end;

if c[s0-v]=false then writeln(0)

else

begin

for i:=1 to 100 do

if d[s0-v,i] then write(i,' ');

end;

end.

这个题目用c[i]记录i是否达到，用d记录重量i的组成里是否有j号牌

最后输出d[s0-v,j]{d[s0-v,j]=true} 简单的DP

0

YY_0227 LV 8 @ 2009-08-02 15:51:24

编译通过...

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

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

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

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

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

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

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

├ 测试数据 08：答案正确... 41ms

├ 测试数据 09：答案正确... 9ms

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

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

Accepted 有效得分：100 有效耗时：50ms

类似01背包的操作。。。

我下面是初二就得了夏令营金牌的同志-的小号。。。

0

贾君鹏 LV 7 @ 2009-07-21 08:49:27

编译通过...

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

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

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

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

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

├ 测试数据 06：答案错误...　├ 标准行输出

　├ 错误行输出

├ 测试数据 07：答案错误...　├ 标准行输出

　├ 错误行输出

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

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

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

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

Unaccepted 有效得分：80 有效耗时：0ms

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

很奇怪，为什么第一次交上去错误的程序错了两个点，但是却没错你们传说中的第五个点。。。

0

suning LV 9 @ 2009-07-16 19:25:51

气死我了~~~

第五组的数据竟然有超过maxlongint种的方法，要用int64啊！！！！

不过话说这vj也太搞笑了，竟然说我超时，害我盯了屏幕半天，愣是没看出来，视力又下降了，555~~

凸-_-凸

0

dreamy LV 10 @ 2009-07-16 13:50:47

怎么回事啊，那个totalw怎么没范围的

害我wa 了n 回！

崩溃的啊！

0

lelouch1 LV 8 @ 2009-07-12 13:13:03

var

a:array[1..100]of integer;

f:array[0..100000]of boolean;

g:array[0..100000]of integer;{lujin}

h:array[0..100000]of boolean;{whether duojie}

q:array[0..100000]of boolean;

i,j,k,p,n,m:longint;

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

begin

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

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

end;

procedure out(x:integer);

begin

writeln(x);halt;

end;

begin

readln(m);

readln(n);

for i:=1 to n do

read(a[i]);

k:=gcd(m,a[1]);

for i:=2 to n do

k:=gcd(k,a[i]);

m:=m div k;

for i:=1 to n do

a[i]:=a[i] div k;

f[0]:=true;

for i:=1 to n do

for j:=m downto a[i] do

if f[j-a[i]] then

begin

if f[j] then

begin

h[j]:=true;continue;

end;

f[j]:=true;

if h[j-a[i]] then h[j]:=true;

g[j]:=i;

end;

if h[m] then out(-1);

if g[m]=0 then out(0);

k:=m;

while k>0 do

begin

q[g[k]]:=true;dec(k,a[g[k]]);

end;

for i:=1 to n do

if not q[i] then

write(i,' ');

end.

第7个点输出0 啊

0

飓风音速 LV 10 @ 2009-07-12 09:37:33

背包！

数组开到1000000最保险！

感谢notblack提供的数据:

614

13

627

861

527

911

751

658

568

846

998

188

923

426

685

ANS=1 2 3 4 5 6 7 8 9 11 13

0

skyhacker LV 7 @ 2009-07-12 00:27:48

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

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

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

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

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

├ 测试数据 06：运行时错误...|错误号: 2293572

├ 测试数据 07：运行时错误...|错误号: 2293572

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

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

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

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

Unaccepted 有效得分：80 有效耗时：0ms

6,7怎么那么奇怪？？？

#include

int TW,WW=0,N,S[100001]={0},L[100001]={0},w[101];

int fun()

{

int i,j;

for(i=N;i>=1;i--)

for(j=WW-w[i];j>=0;j--){

if(S[j]){S[j+w[i]]++;L[j+w[i]]=i;}

if(S[WW]>1) return;

}

}

int main()

{

int i,j;

scanf("%d %d",&TW,&N);

for(i=1;i1) printf("-1");

else

{

i=WW;

while(i>0)

{printf("%d ",L[i]);i-=w[L[i]];}

}

}

题解

200 条题解

新年趣事之打牌

信息

状态

开发

支持

题解

200 条题解

新年趣事之打牌

信息

状态

开发

支持

还没有账户？

登录