Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 呵呵

Posted by yu179121 at 2014-10-06 17:08:40 on Problem 1417
```var
n,i,j,p1,p2,x,y,z,k,s,tx,ty:longint;
f,b,a:array[0..2000] of longint;
q:array[0..2000,0..1] of longint;
p:array[0..2000,0..1] of boolean;
dp:array[0..2000,0..500] of longint;
st:string;
fl:boolean;
function find(x:longint):longint;
var
t:longint;
begin
if f[x]<>x then
begin
t:=find(f[x]);
b[x]:=b[x] xor b[f[x]];
f[x]:=t;
end;
exit(f[x]);
end;
function max(x,y:longint):longint;
begin
if x>y then exit(x)
else exit(y);
end;
function pd(i,x:longint):boolean;
begin
if i=0 then exit(true);
if (x>=q[i,0]) and (x>=q[i,1]) and (dp[i-1,x-q[i,0]]+q[i,0]=dp[i-1,x-q[i,1]]+q[i,1]) then exit(false);
if (x>=q[i,0]) and (dp[i-1,x-q[i,0]]+q[i,0]=x) then
begin
p[i,0]:=true;
exit(pd(i-1,x-q[i,0]))
end
else
begin
p[i,1]:=true;
if (dp[i-1,x-q[i,1]]+q[i,1]=x) then exit(pd(i-1,x-q[i,1]));
end;
end;
begin
while not seekeof do
begin
if (n=0) and (p1=0) and (p2=0) then break;
k:=p1+p2;
for i:=1 to k do
begin
f[i]:=i; b[i]:=0;
end;
for i:=1 to n do
begin
if pos('no',st)>0 then z:=1
else z:=0;
tx:=find(x);ty:=find(y);
if tx<>ty then
begin
f[tx]:=ty;
b[tx]:=b[x] xor b[y] xor z;
end;
end;
fillchar(a,sizeof(a),0);
s:=0;
for i:=1 to k do
begin
f[i]:=find(i);
if a[f[i]]=0 then
begin
inc(s);
a[f[i]]:=s;
q[s,1]:=0; q[s,0]:=0;
p[s,1]:=false; p[s,0]:=false;
end;
inc(q[a[f[i]],b[i]]);
end;
dp[0,0]:=0;
fl:=true;
for i:=1 to s do
for j:=0 to k do
begin
dp[i,j]:=0;
if (j>=q[i,0]) then dp[i,j]:=max(dp[i,j],dp[i-1,j-q[i,0]]+q[i,0]);
if (j>=q[i,1]) then dp[i,j]:=max(dp[i,j],dp[i-1,j-q[i,1]]+q[i,1]);
end;
if dp[s,p1]<>p1 then fl:=false;
if (p1>=q[s,1]) and (p1>=q[s,0]) and (dp[s-1,p1-q[s,0]]+q[s,0]=dp[s-1,p1-q[s,1]]+q[s,1]) then fl:=false;
if fl and (pd(s,p1)) then
begin
for i:=1 to k do
if p[a[f[i]],b[i]] then writeln(i);
writeln('end');
end
else writeln('no');
end;
end.```

Followed by: