讨论 - 【顶】质疑数据与标程

许烨闻 2011-08-30 15:57:00

点我顶贴收藏删除

我用了两套搜索，评测记录是相同的。

const

two:array[0..40]of int64=(1,2,4,8,16,32,64,128,256,512,1024,

2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,

2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,

2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776);

var

s:string;

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

l,n,i,k,len:longint;

function get(dep:longint;l,n:int64):longint;

var

i,x:longint;w:int64;

begin

if (l>=two[len-dep+1])or(len-dep+1>l)or(n>l)or(l<0)or(n<0) then exit(0);

if dep>len then

if (l=0)and(n=0) then exit(1) else exit(0);

if a[dep]=0 then exit(get(dep+1,l-1,n));

get:=0;w:=0;

for i:=dep to len do

begin

w:=w*2+a[i];

if a[i+1]=0 then get:=get+get(i+1,l-w,n-w);

if get>1 then exit(2);

end;

begin

readln(l,n);

while (l<>0)and(n<>0) do

begin

readln(s);

len:=length(s);

fillchar(a,sizeof(a),0);

for i:=1 to len do a[i]:=ord(s[i])-48;

k:=get(1,l,n);

if k=0 then writeln('NO')

else

if k=1 then writeln('YES')

else

writeln('NOT UNIQUE');

readln(l,n);

end;

end.

这个程序，搜的是解压的每个部分。

状态: Unaccepted

测评机： Xeost[5]

得分： 30分

提交日期： 2011-8-30 13:53:00

有效耗时： 297毫秒

测试结果1: 通过本测试点|有效耗时187ms

测试结果2: 测试结果错误.错误结果为:NOT UNIQUE

NOT UNIQUE

NO

正确结果应为:NOT UNIQUE

NOT UNIQUE

YES

NOT UNIQUE

NO

测试结果3: 测试结果错误.错误结果为:YES

YES

NOT UNIQUE

YES

正确结果应为:NO

YES

NOT UNIQUE

NO

YES

测试结果4: 测试结果错误.错误结果为:NO

NOT UNIQUE

YES

NO

NOT UNIQUE

正确结果应为:NO

NOT UNIQUE

YES

NOT UNIQUE

NO

NOT UNIQUE

测试结果5: 通过本测试点|有效耗时47ms

测试结果6: 测试结果错误.错误结果为:NO

YES

NOT UNIQUE

NO

NOT UNIQUE

正确结果应为:NOT UNIQUE

YES

NOT UNIQUE

NO

测试结果7: 测试结果错误.错误结果为:NOT UNIQUE

NOT UNIQUE

YES

正确结果应为:NOT UNIQUE

NO

NOT UNIQUE

YES

测试结果8: 测试结果错误.错误结果为:NOT UNIQUE

YES

NO

正确结果应为:NOT UNIQUE

YES

NO

测试结果9: 测试结果错误.错误结果为:NOT UNIQUE

NOT UNIQUE

YES

NOT UNIQUE

YES

NOT UNIQUE

正确结果应为:YES

NOT UNIQUE

NO

NOT UNIQUE

测试结果10: 通过本测试点|有效耗时63ms

var

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

s:string;

l,n,i,m,ans,len:longint;

procedure search(dep,now,sum,zero:qword);

var

i:longint;

begin

if ans>1 then exit;

if dep>len then

begin

if sum+now=n then inc(ans);

exit;

end;

if a[dep]=0 then begin

if zero+c[dep]>m then search(dep+1,now*2+a[dep],sum,zero);

if zero+b[dep]<=m then search(dep+b[dep],0,sum+now,zero+b[dep]);

end

else search(dep+1,now*2+a[dep],sum,zero);

end;

begin

readln(l,n);

while (l<>0)and(n<>0) do

begin

readln(s);

len:=length(s);

for i:=1 to len do a[i]:=ord(s[i])-48;

b[len+1]:=0;m:=0;

fillchar(c,sizeof(c),0);

for i:=len downto 1 do

if a[i]=1 then b[i]:=0

else

begin

inc(m);

b[i]:=b[i+1]+1;

c[i]:=m;

end;

m:=l-n-b[1];

ans:=0;

if m>=0 then search(b[1]+1,0,0,0);

if ans=0 then writeln('NO')

else

if ans=1 then writeln('YES')

else

writeln('NOT UNIQUE');

readln(l,n);

end;

end.

这个搜索主要是搜0，0的总个数必定是l-n。

状态: Unaccepted

测评机： Xeond[6]

得分： 30分

提交日期： 2011-8-30 13:21:00

有效耗时： 267毫秒

测试结果1: 通过本测试点|有效耗时157ms

测试结果2: 测试结果错误.错误结果为:NOT UNIQUE

NOT UNIQUE

NO

正确结果应为:NOT UNIQUE

NOT UNIQUE

YES

NOT UNIQUE

NO

测试结果3: 测试结果错误.错误结果为:YES

YES

NOT UNIQUE

YES

正确结果应为:NO

YES

NOT UNIQUE

NO

YES

测试结果4: 测试结果错误.错误结果为:NO

NOT UNIQUE

YES

NO

NOT UNIQUE

正确结果应为:NO

NOT UNIQUE

YES

NOT UNIQUE

NO

NOT UNIQUE

测试结果5: 通过本测试点|有效耗时63ms

测试结果6: 测试结果错误.错误结果为:NO

YES

NOT UNIQUE

NO

NOT UNIQUE

正确结果应为:NOT UNIQUE

YES

NOT UNIQUE

NO

测试结果7: 测试结果错误.错误结果为:NOT UNIQUE

NOT UNIQUE

YES

正确结果应为:NOT UNIQUE

NO

NOT UNIQUE

YES

测试结果8: 测试结果错误.错误结果为:NOT UNIQUE

YES

NO

正确结果应为:NOT UNIQUE

YES

NO

测试结果9: 测试结果错误.错误结果为:NOT UNIQUE

NOT UNIQUE

YES

NOT UNIQUE

YES

NOT UNIQUE

正确结果应为:YES

NOT UNIQUE

NO

NOT UNIQUE

测试结果10: 通过本测试点|有效耗时47ms

希望主席或出题者写一下题解。模拟赛最好还是要有题解，如果有标程更好。

#1 许烨闻@2011-08-30 15:57:00

回复删除

我AC了，想删除此帖。