求余数……
Program P3980;
var
a,b:longint;
begin
while not seekeof do
begin
read(a,b);
writeln(a mod b);
end;
end.
POJ 1856(海战）
搜索 此题数据小，不需要状压
Program P1856;
var
n,m,i,j,ans:longint;
c:char;
f:array[0..1010,0..1010] of boolean;
function find(x,y:longint):boolean;
var
i,j,k,l:longint;
begin
i:=x;j:=y;
while f[x,j] do inc(j);
dec(j);
while f[i,y] do inc(i);
dec(i);
for k:=x to i do
for l:=y to j do
begin
if not(f[k,l]) then exit(false);
f[k,l]:=false;
end;
for k:=x-1 to i+1 do
if f[k,j+1] or f[k,y-1] then exit(false);
for l:=y to j do
if f[i+1,l] or f[x-1,l] then exit(false);
exit(true);
end;
function main:boolean;
var
i,j:longint;
begin
ans:=0;
for i:=1 to n do
for j:=1 to m do
if f[i,j] then
begin
if not(find(i,j)) then exit(false)
else inc(ans);
end;
exit(true);
end;
begin
while not seekeof do
begin
fillchar(f,sizeof(f),false);
readln(n,m);
if (n+m=0) then break;
for i:=1 to n do
begin
for j:=1 to m do
begin
read(c);
if c='#' then f[i,j]:=true;
end;
readln;
end;
if main then writeln('There are ',ans,' ships.')
else writeln('Bad placement.');
end;
end.
POJ 1523（求割点）
求割点入门题！
……死调一下午+晚上才发现把‘node'打成’nodes'了……
Program P1523;
const
maxedge=999000;
maxn=10000;
var
edge,tail:array[1..maxedge] of longint;
size:longint;
head:array[1..maxn] of longint;
n,i,j,ans,k:longint;
b,cut:array[1..maxn] of boolean;
time,root:longint;
a,d,ancestor,c:array[1..maxn] of longint;
procedure addedge(u,v:longint);
begin
inc(size);
edge[size]:=v;
tail[size]:=head[u];
head[u]:=size;
end;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
procedure Dfs(k,father,deep:longint);
var
i,j,p,tot:longint;
begin
tot:=0;
c[k]:=1;
d[k]:=deep;
ancestor[k]:=deep;
p:=head[k];
while (p>0) do
begin
i:=edge[p];
if (i<>father) and (c[i]=1) then ancestor[k]:=min(ancestor[k],d[i]);
if (c[i]=0) then
begin
dfs(i,k,deep+1);
inc(tot);
ancestor[k]:=min(ancestor[k],ancestor[i]);
if (k=root) and (tot>=2) then cut[k]:=true;
if (k<>root) and (ancestor[i]>=d[k]) then cut[k]:=true;
end;
p:=tail[p];
end;
c[k]:=2;
inc(time);
a[k]:=time;
end;
procedure Dfs2(k:longint);
var
i,p:longint;
begin
b[k]:=true;
p:=head[k];
while (p>0) do
begin
i:=edge[p];
if not(b[i]) then
begin
dfs2(i);
end;
p:=tail[p];
end;
end;
function main:boolean;
var
i,j,p,ans:longint;
begin
time:=0;
main:=false;
for i:=1 to maxn do
if (head[i]>0) and (c[i]=0) then
begin
root:=i;
dfs(root,0,1);
end;
for i:=1 to maxn do
if cut[i] then
begin
main:=true;
ans:=0;
fillchar(b,sizeof(b),false);
b[i]:=true;
p:=head[i];
while (p>0) do
begin
if not(b[edge[p]]) then
begin
dfs2(edge[p]);
inc(ans);
end;
p:=tail[p];
end;
writeln(' SPF node ',i,' leaves ',ans,' subnets');
end;
end;
begin
{ assign(input,'p1523.in');
reset(input);
}
k:=1;
while not seekeof do
begin
size:=0;
fillchar(head,sizeof(head),0);
fillchar(edge,sizeof(edge),0);
fillchar(tail,sizeof(tail),0);
fillchar(cut,sizeof(cut),false);
fillchar(c,sizeof(c),0);
fillchar(d,sizeof(d),0);
fillchar(ancestor,sizeof(ancestor),0);
read(i);
if i=0 then break;
read(j);
while (i>0) do
begin
addedge(i,j);
addedge(j,i);
read(i);
if i=0 then break;
read(j);
end;
ans:=0;
writeln('Network #',k);
if not(main) then writeln(' No SPF nodes');
writeln;
inc(k);
end;
end.
POJ 2777(涂点问线）
线段树……
Program p2777;
const
maxl=100000;
maxt=30;
maxo=100000;
var
l,t,o,i,j,k:longint;
col:array[1..maxl*10] of longint;
c:char;
x,y,color:longint;
visit:array[1..maxt] of boolean;
procedure build(l,r,root:longint);
var
mid:longint;
begin
if l=r then
begin
col[root]:=1;
exit;
end;
mid:=(l+r) shr 1;
build(l,mid,root shl 1);
build(mid+1,r,root shl 1+1);
col[root]:=1;
end;
procedure swap(var a,b:longint);
var
p:longint;
begin
p:=a;a:=b;b:=p;
end;
procedure detate(l,r,sonl,sonr,root,color:longint);
var
i,j,mid:longint;
begin
mid:=(l+r) shr 1;
if l=r then
begin
col[root]:=color;
exit;
end;
if (sonl<=l) and (r<=sonr) then
begin
col[root]:=color;
exit;
end;
if col[root]>0 then
begin
col[root*2]:=col[root];
col[root*2+1]:=col[root];
col[root]:=-1;
end;
if not((mid<sonl) or (sonr<l)) then detate(l,mid,sonl,sonr,root shl 1,color);
if not((r<sonl) or (sonr<mid+1)) then detate(mid+1,r,sonl,sonr,root shl 1+1,color);
end;
function quere(l,r,sonl,sonr,root:longint):longint;
var
mid,i,j:longint;
begin
quere:=0;
mid:=(l+r) shr 1;
if col[root]>0 then
begin
if not(visit[col[root]]) then
begin
visit[col[root]]:=true;
exit(1);
end;
exit(0);
end;
if not((mid<sonl) or (sonr<l)) then inc(quere,quere(l,mid,sonl,sonr,root shl 1));
if not((r<sonl) or (sonr<mid+1)) then inc(quere,quere(mid+1,r,sonl,sonr,root shl 1+1));
end;
begin
readln(l,t,o);
build(1,l,1);
for i:=1 to o do
begin
read(c);
if c='C' then
begin
readln(x,y,color);
if x>y then swap(x,y);
detate(1,l,x,y,1,color);
end
else
begin
readln(x,y);
if x>y then swap(x,y);
fillchar(visit,sizeof(visit),false);
writeln(quere(1,l,x,y,1));
end;
end;
end.
POJ 3100(非二分不合作）
这题的数据太水……
居然不需要2分Log n查找……尽管我也不知道上限是多少……
Program P3100;
var
a,b,n,i,j,dis:longint;
function pow(a,b:longint):longint;
var
i:longint;
begin
if a=0 then exit(0);
if a=1 then exit(1);
if b=0 then exit(0);
if b=1 then exit(a)
else
begin
pow:=pow(a,b shr 1);
if (b mod 2=0) then
begin
exit(pow*pow);
end
else exit(pow*pow*a);
end;
end;
begin
read(b,n);
while (b+n>0) do
begin
i:=0;
while (pow(i,n)<b) do
begin
dis:=b-pow(i,n);
inc(i);
end;
if (pow(i,n)-b>dis) then writeln(i-1) else writeln(i);
read(b,n);
end;
end.
HYSBZ 1079(着色方案）
Dp 神奇的状态转移……
Program fd;
const
mo=1000000007;
var
n,i,j:longint;
c,tot:array[1..15] of longint;
f:array[0..15,0..15,0..15,0..15,0..15,0..15] of int64;
function dfs(a1,a2,a3,a4,a5,last:longint):int64;
var
i,j:longint;
ans,q:int64;
a:array[1..5] of longint;
begin
if f[a1,a2,a3,a4,a5,last]>0 then exit(f[a1,a2,a3,a4,a5,last]);
a[1]:=a1;a[2]:=a2;a[3]:=a3;a[4]:=a4;a[5]:=a5;
ans:=0;
for i:=1 to 5 do
if (a[i]>0) then
begin
if (last=i+1) and (a[i]=1) then continue;
// if (last=i+1) then dec(a[i]);
dec(a[i]);
if i>1 then inc(a[i-1]);
q:=dfs(a[1],a[2],a[3],a[4],a[5],i);
inc(a[i]);
if i>1 then dec(a[i-1]);
if last=i+1 then ans:=(ans+(a[i]-1)*q) mod mo
else ans:=(ans+a[i]*q) mod mo;
// if (last=i+1) then inc(a[i]);
end;
f[a1,a2,a3,a4,a5,last]:=ans;
exit(ans);
end;
begin
read(n);
fillchar(tot,sizeof(tot),0);
for i:=1 to n do
begin
read(c[i]);
inc(tot[c[i]]);
end;
fillchar(f,sizeof(f),0);
for i:=1 to n do f[0,0,0,0,0,i]:=1;
writeln(dfs(tot[1],tot[2],tot[3],tot[4],tot[5],0));
end.
POJ 1818(贪心）
让每个人每局都与可战胜的人中最强的打,看有无可行解……
Program p1818;
var
n,x,k,i,j,mid:longint;
q:array[1..5100] of longint;
f:array[1..5100] of longint;
function max(a,b:longint):longint;
begin
if a<b then exit(b) else exit(a);
end;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
function is_ac(person:longint):boolean;
var
i,j,l,h,t:longint;
size:longint;
begin
fillchar(f,sizeof(f),0);
fillchar(q,sizeof(q),0);
q[1]:=person;
size:=1;
f[person]:=1;
h:=1;t:=1;
for l:=2 to x+1 do
begin
for i:=h to t do
begin
for j:=max(1,q[i]-k) to n do
begin
if f[j]=0 then
begin
inc(size);
q[size]:=j;
f[j]:=l;
break;
end;
end;
end;
t:=size;
end;
if (size<n) then exit(false)
else exit(true);
end;
begin
read(n,k);
x:=0;
i:=1;
while (i<n) do
begin
inc(x);
i:=i shl 1;
end;
i:=1;j:=n;
if is_ac(j) then i:=j;
while (j-i>1) do
begin
mid:=(i+j) shr 1;
if is_ac(mid) then i:=mid else j:=mid;
end;
writeln(i);
end.
POJ 1363(栈）
此题纯模拟也能过……
我更懒，直接记栈尾元素和已出元素……
Program P1363;
var
n,i:longint;
a:array[1..1000] of longint;
b:array[0..1000] of boolean;
t:longint;
tag:boolean;
begin
read(n);
while (n>0) do
begin
read(a[1]);
while (a[1]>0) do
begin
fillchar(b,sizeof(b),false);
for i:=2 to n do read(a[i]);
t:=a[1];
b[t]:=true;
dec(t);
tag:=false;
for i:=2 to n do
begin
if not(b[a[i]]) then
begin
if a[i]>t then
begin
t:=a[i];
b[t]:=true;
dec(t);
while b[t] do dec(t);
end
else if a[i]=t then
begin
b[t]:=true;
dec(t);
while b[t] do dec(t);
end
else
begin
writeln('No');
tag:=true;
break;
end;
end
else
begin
writeln('No');
tag:=true;
break;
end;
end;
if not(tag) then writeln('Yes');
read(a[1]);
end;
writeln;
read(n);
end;
end.
POJ 2828（卡时线段树）
本题乍一看链表，实际上肯定超时%……
故用线段树 LogN查找……
Program P2828;
const
maxn=200000;
var
n,i,j:longint;
pos,val:array[1..maxn] of longint;
sum:array[1..maxn*10] of longint;
ans:array[1..maxn] of longint;
procedure pushup(root:longint);
begin
sum[root]:=sum[root*2]+sum[root*2+1];
end;
procedure build(l,r,root:longint);
var
mid:longint;
begin
if l=r then
begin
sum[root]:=1;
exit;
end;
mid:=(l+r) shr 1;
build(l,mid,root*2);
build(mid+1,r,root*2+1);
pushup(root);
end;
procedure decr(l,r,root,node:longint);
var
mid:longint;
begin
if l=r then
begin
dec(sum[root]);
exit;
end;
mid:=(l+r) shr 1;
if (node<=mid) then decr(l,mid,root shl 1,node)
else decr(mid+1,r,root shl 1+1,node);
pushup(root);
end;
function find(l,r,root,value:longint):longint;
var
mid:longint;
begin
mid:=(l+r) shr 1;
if l=r then
begin
decr(1,n,1,l);
exit(l);
end;
if (sum[root shl 1]>=value) then exit(find(l,mid,root shl 1,value))
else exit(find(mid+1,r,root shl 1+1,value-sum[root shl 1]));
end;
begin
while not seekeof do
begin
read(n);
for i:=1 to n do read(pos[i],val[i]);
build(1,n,1);
for i:=n downto 1 do
begin
ans[find(1,n,1,pos[i]+1)]:=val[i];
end;
for i:=1 to n-1 do write(ans[i],' ');
writeln(ans[n]);
end;
end.
POJ 2528（数据有误的线段树）
此题数据有误……
是我英文太差，还是答案出错……
Program P2528;
const
maxn=10000;
maxr=10000000;
var
t,n,i,j,k:longint;
a,b,v:array[1..maxn*2] of longint;
h:array[1..maxr] of longint;
col:array[1..maxn*100] of longint;
visit:array[1..maxn*2] of boolean;
procedure qsort(l,r:longint);
var
i,j,m,p:longint;
begin
i:=l;
j:=r;
m:=v[(l+r) div 2];
repeat
while v[i]<m do inc(i);
while v[j]>m do dec(j);
if i<=j then
begin
p:=v[i];
v[i]:=v[j];
v[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
procedure update(l,r,sonl,sonr,root,color:longint);
var
i,j,k,mid:longint;
begin
mid:=(l+r) shr 1;
if (sonl<=l) and (r<=sonr) then
begin
col[root]:=color;
exit;
end;
if (col[root]>=0) then
begin
col[root*2]:=col[root];
col[root*2+1]:=col[root];
col[root]:=-1;
end;
if not((mid<sonl) or (sonr<l)) then update(l,mid,sonl,sonr,root*2,color);
if not((r<sonl) or (sonr<mid+1)) then update(mid+1,r,sonl,sonr,root*2+1,color);
end;
function dfs(l,r,root:longint):longint;
var
i,j,mid:longint;
begin
mid:=(l+r) shr 1;
if col[root]=0 then exit(0);
if col[root]>0 then
begin
if not(visit[col[root]]) then
begin
visit[col[root]]:=true;
exit(1);
end
else exit(0);
end;
exit(dfs(l,mid,root*2)+dfs(mid+1,r,root*2+1));
end;
begin
read(t);
while t>0 do
begin
dec(t);
read(n);
for i:=1 to n do
begin
read(a[i],b[i]);
v[i]:=a[i];
v[n+i]:=b[i];
end;
qsort(1,2*n);
j:=1;
for i:=2 to 2*n do
if v[i]<>v[i-1] then
begin
inc(j);
v[j]:=v[i];
end;
for i:=1 to j do h[v[i]]:=i;
fillchar(col,sizeof(col),0);
for i:=1 to n do
begin
update(1,j,h[a[i]],h[b[i]],1,i);
end;
fillchar(visit,sizeof(visit),false);
writeln(dfs(1,j,1));
end;
end.