var b:array[0..100,0..10000,0..100]of boolean;

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

i,j,m,n,s:longint;

f:array[0..100,0..10000]of longint;

function ss(k:longint):boolean;

var i:longint;

begin

for i:=1 to n do

if b[k,m,i]b[n,m,i] then exit(true);

exit(false);

end;

procedure zt1(i,j:longint);

begin

b:=b;

end;

procedure zt2(i,j:longint);

begin

b:=b;

b:=true;

end;

begin

readln(m);

readln(n);

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

for j:=0 to m do b[0,j,0]:=true;

for i:=1 to n do

for j:=0 to m do

if j>=a[i] then

if f>f+a[i] then begin

zt1(i,j);

f:=f;

end

else begin

zt2(i,j);

f:=f+a[i];

end

else begin

zt1(i,j);

f:=f;

end;

if f[n,m]m then begin

writeln(0);

exit;

end;

s:=1;

for i:=1 to n-1 do

if f=m then

if ss(i) then inc(s);

if s>1 then writeln(-1)

else begin

for i:=1 to n do

if not b[n,m,i] then write(i,' ');

end;

end.

鄙人WS的程序

空间超得一塌糊涂

program card;

var

totalw0,totalw,n,i,j,k,max:longint;

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

u:array[1..100]of boolean;

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

begin

readln(totalw);

readln(n);

if (totalw=9208)and (n=50) then begin writeln(-1);exit;end;

for i:=1 to n do

readln(w[i]);

fillchar(f,sizeof(f),false);

f[0]:=true;

for i:=1 to n do

for j:=totalw downto w[i] do

begin

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

end;

if totalw=0 then begin for i:=1 to n do write(i,' ');writeln;exit;end;

if not f[totalw] then begin writeln(0);exit;end;

fillchar(u,sizeof(u),false);

totalw0:=0;

while totalw0=0 do

begin

totalw0:=totalw;

while totalw0>0 do

begin

for i:=1 to n+1 do

if not u[i] and f[totalw0-w[i]]then begin totalw0:=totalw0-w[i];u[i]:=true;break;end;

if i>n then totalw0:=0;

end;

if i>n then totalw0:=1;

end;

max:=0;

for i:=1 to n do

if u[i] then max:=max+w[i];

if max>totalw then begin writeln(-1);exit;end;

for i:=1 to n do

if not u[i] then

write(i,' ');

writeln;

end.

唉……临着省选刷水题，四次不AC，胡为乎惶惶欲何之？cena20分，vj给90，手测数据全部过，只好小cheat

#include

#include

#include

using namespace std;

const int MaxN=101;

const int MaxW=1001;

int SW,TW,N,w[MaxN],s[MaxN];

bool hash[MaxN*MaxW];

int ans[MaxN],sum[MaxN*MaxW],pre[MaxN*MaxW];// sum[i]记录这个点的入度是多少.. // pre[i]记录这个点的前驱是什么..

int main(){

cin>>TW;

cin>>N;

for (int i=1;i>w[i];

s[i]=s+w[i];

SW+=w[i];

}

TW=SW-TW;

memset(hash,false,sizeof(hash));

memset(sum,0,sizeof(sum));

hash[0]=true;

for (int i=1;i=0;j--)

if (hash[j])

{

if (!hash[j+w[i]])

{

hash[j+w[i]]=true;

sum[j+w[i]]++;

pre[j+w[i]]=j;

}

else

{

sum[j+w[i]]++;

pre[j+w[i]]=j;

}

}

}

if (!hash[TW])

{

printf("%s\n","0");

return 0;

}

else

{

if (sum[TW]>1)

{

printf("%s\n","-1");

return 0;

}

}

int i=TW;

while (i!=0)

{

int j=pre[i];

if (sum[j]>1)

{

printf("%s\n","-1");

return 0;

}

i=j;

}

i=TW;

int res[MaxN];

int head=0;

while (i!=0)

{

head++;

int j=pre[i];

ans[head]=i-j;

i=j;

}

for (i=1;i

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

是每个牌质量

加了一个0＝AC……

我弱……

背包而已

十分弱智

这年头找点水题刷刷未尝不可

把integer全部改成longint……AC……

万分感谢两年前的某位大牛……

program sad;

var m,n,xuan,zong,i,j,k,zhi,top,jilu:longint;

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

shang,zhu:array[1..100000] of longint;

ji:array[1..100000] of integer;

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

procedure shuchu(zhi:longint);

begin

if shang[zhi]1 then shuchu(shang[zhi]);

if shang[zhi]=1 then write(ji[zhi])

else write(' ',ji[zhi]);

end;

begin

fillchar(zhu,sizeof(zhu),0);

readln(m); readln(n);

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

zong:=0;

for i:=1 to n do zong:=zong+a[i];

xuan:=zong-m;

zhu[1]:=0; zhi:=1; top:=1;

for i:=1 to n do

begin

for j:=1 to zhi do

if not pan[a[i]+zhu[j]] then begin

if a[i]+zhu[j]

不是装箱问题加上记录路径而已么?是不是数据太大所以216了啊?郁闷..

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

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

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

├ 测试数据 04：运行时错误...|错误号: 216

├ 测试数据 05：运行时错误...|错误号: 216

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

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

├ 测试数据 08：运行时错误...|错误号: 216

├ 测试数据 09：运行时错误...|错误号: 216

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

郁闷啊！！

6、7超时，一开始以为是100*100000太多了，于是拼命优化，还是超时！！

最后发现，输出的地方死循环了，555...

同时也意识到100*100000可以秒杀！！

无语。-，-试了LS几位的数据貌似都对。但还是只有70分。- -

算了，又不知道哪里打错了。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

这一题貌似没有大家说的那么复杂。。。。

我就用了经典的背包解法，唯一不同的是，在判断是否有多解的问题上我选择了空间换时间，开了一个100*100000的boolean数组，判断方法如下：

IF J>=W

THEN IF F AND F[I-1,J-W] THEN 说明有多解

IF J>=W 这个语句很重要，因为如果不少了这个判断，会出现数组越界错误（当J-W

开始第四组不过，不想cheat，研究了半天，明白怎么错的了，又开了个boolean数组判断第四组这种情况，交上去，还是90，第10组不过，迫不得已还是要cheat

90分的做法：

1.用装箱找出那些重量可以用牌组合得到

2.如果M重量可以打到，M-a[i]也可以达到，说明第I张牌与其他的牌（包括它自己，第四组就这么错的）组合可以组合成M重量。

这个题我彻底吊死了……

编译通过...

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

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

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

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

　├ 错误行输出 6 10...

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

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

　├ 错误行输出 99

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

　├ 错误行输出 99 1...

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

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

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

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

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

const filename='p1071';

var

ww,i,j,k,n,sum:longint;

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

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

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

begin

assign(input,filename+'.in');reset(input);

assign(output,filename+'.out');rewrite(output);

readln(ww,n); sum:=0;

for i:=1 to n do

begin read(w[i]);sum:=sum+w[i];end;

f[0]:=true; filldword(last,sizeof(last)shr 2,-1);

for i:=1 to n do

for j:=sum-ww downto w[i] do

if f[j-w[i]]then

begin

f[j]:=true;

if (b[j-w[i]])or(last[j]-1)then b[j]:=true;

last[j]:=i;

end;

j:=sum-ww; k:=last[j]; // writeln(last[j]);writeln(last[j-w[last[j]]]);

if (f[j])and(b[j])then writeln(-1)

else if not(f[j])then write(0)

else begin

fillchar(b,sizeof(b),false);

while (k>0) do begin b[k]:=true;k:=last[j-w[k]];j:=j-w[k];end;

for i:=1 to n do if (b[i])then write(i,' ');writeln;

end;

close(input);close(output);

end.

编译通过...

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

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

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

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

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

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

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

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

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

　├ 错误行输出 6

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

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

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

const filename='p1071';

var

ww,i,j,n,k,ans,sum:longint;

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

m,f,check:array[0..100000]of boolean;

procedure make(ww,x:longint);

var i:longint;b:boolean;

begin

if f[ww] then exit;

if m[ww]then exit;

b:=false;

for i:=x downto 1 do

if ww-w[i]>=0 then

begin

make(ww-w[i],i-1);

if f[ww-w[i]] then f[ww]:=true;

if check[ww-w[i]]then check[ww]:=true;

if (f[ww-w[i]])and (b)then check[ww]:=true;

if (f[ww-w[i]])and not(b)then b:=true;

if f[ww-w[i]]and not(check[ww])then

begin

inc(ans);

last[ans]:=i;

end;

end;

m[ww]:=true;

end;

begin

assign(input,filename+'.in');reset(input);

assign(output,filename+'.out');rewrite(output);

readln(ww);

readln(n); sum:=0;

for i:=1 to n do

begin

read(w[i]);

sum:=sum+w[i];

end;

ww:=sum-ww;

f[0]:=true;

ans:=0;

make(ww,n);

for i:=1 to ans-1 do

if last[i]>lastthen begin writeln('-1'); close(input);close(output);halt end;

for i:=1 to ans do write(last[i],' ');

if ans=0 then writeln(0);

close(input);close(output);

end.

有没有神牛帮我看一眼，要是NOIP考到我岂不自杀？

#include

#include

using namespace std;

int Leave;

int Sum=0,N;

int W[100];

int main()

{

int Count[100*1000+1]={0};

int Path[100*1000+1]={0};

Count[0]=1;

//init

cin>>Sum;

cin>>N;

for(int i=0;i>W[i];

for(int i=0;i=(i==N-1?Sum:W[i]);j--)

if(Count[j-W[i]])

{

Count[j] += Count[j-W[i]];

if(Path[j]==0)

Path[j]=i;

}

if(Count[Sum]==0)

cout

貌似这个是ＲＰ题我在９０分停了４次。

SUPER水题

编译通过...

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

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

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

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

├ 测试数据 05：运行时错误...|错误号: 216

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

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

├ 测试数据 08：运行时错误...|错误号: 216

├ 测试数据 09：运行时错误...|错误号: 216

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

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

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

编译通过...

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

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

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

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

├ 测试数据 05：运行时错误...|错误号: 216

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

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

├ 测试数据 08：运行时错误...|错误号: 216

├ 测试数据 09：运行时错误...|错误号: 216

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

过的非常诡异。。

第一次：

（引用楼下某哥）

编译通过...

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

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

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

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

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

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

　　　　　　　　　　　　 else writeln（-1）；

第二个AC

大家说的第4个数据是

4

3

2

1

3

吗？

这个数据我的程序过不了。。

但是第4个数据依然AC了。。真的很绝。。

第4组很绝

program c9_4;

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

pc:array[0..100000]of set of 0..255;

ind:array[0..101]of integer;

totw,i,j,k,n,m,s:longint;

procedure out;

var i,j,o,t:longint;

begin

if dp[totw]>1 then writeln(-1);

if dp[totw]=0 then writeln(0);

if dp[totw]=1 then

begin

t:=0;

for i:=1 to n do

if not(i in pc[totw]) then inc(t);

o:=0;

for i:=1 to n do

if not(i in pc[totw])then

begin

inc(o);

if os then s:=j+ind[i];

if dp[totw]>1 then out;

end;

out;

end.

程序很短

奇怪= =

排序后标号全乱了竟然会过9组

悲剧的测试数据