这题题目看不懂……用谷歌翻译完，更看不懂……
对A此题不看Discuss的神语言流表示膜拜
Program P2209;
var
n,p,s,ans,i:longint;
begin
read(n,p);
ans:=0;
for i:=1 to n do
begin
read(s);
if p=2 then s:=s*s;
if p=3 then s:=s*s*s;
if s>0 then inc(ans,s);
end;
writeln(ans);
end.
这题考双端队列……好偏门的数据结构……
Program c;
const
maxn=1000000;
type
node=record
num,d:longint;
end;
douq=record
d:array[1..maxn] of node;
l,r:longint;
end;
var
n,k,i,j:longint;
a:array[1..maxn] of longint;
ans1,ans2:array[1..maxn] of longint;
minq,maxq:douq;
procedure push(var q:douq;num2,d2:longint);
begin
with q do
begin
inc(r);
d[q.r].num:=num2;
d[q.r].d:=d2;
end;
end;
procedure popl(var q:douq;i:longint);
begin
with q do
begin
if d[l].num=i then inc(l);
end;
end;
procedure popr(up,i:longint);
var
j:longint;
begin
if up=1 then
begin
with minq do
begin
while (l<r) and (d[r].d>i) do dec(r);
if l=r then
if d[r].d>i then dec(r);
end;
end
else
begin
with maxq do
begin
while (l<r) and (d[r].d<i) do dec(r);
if l=r then
if d[r].d<i then dec(r);
end;
end;
end;
begin
read(n,k);
for i:=1 to n do read(a[i]);
fillchar(minq,sizeof(minq),0);
minq.l:=1;
fillchar(maxq,sizeof(maxq),0);
maxq.l:=1;
if k=1 then
begin
for i:=1 to n-1 do write(a[i],' ');
writeln(a[n]);
for i:=1 to n-1 do write(a[i],' ');
writeln(a[n]);
end
else
begin
for i:=1 to k do
begin
popr(1,a[i]);
push(minq,i,a[i]);
popr(0,a[i]);
push(maxq,i,a[i]);
end;
ans1[1]:=minq.d[minq.l].d;
ans2[1]:=maxq.d[maxq.l].d;
for i:=k+1 to n do
begin
popl(minq,i-k);
popl(maxq,i-k);
popr(1,a[i]);
push(minq,i,a[i]);
popr(0,a[i]);
push(maxq,i,a[i]);
ans1[i-k+1]:=minq.d[minq.l].d;
ans2[i-k+1]:=maxq.d[maxq.l].d;
end;
for i:=1 to n-k do write(ans1[i],' ');
writeln(ans1[n-k+1]);
for i:=1 to n-k do write(ans2[i],' ');
writeln(ans2[n-k+1]);
end;
end.
这题 居然一次就过了^_^
Program P2195;
const
maxn=200;
maxm=200;
maxh=200;
maxd=1000;
var
n,m,i,j,k,ut,vt:longint;
s:string;
form:array[1..maxn,1..maxm] of longint;
u,v:array[1..maxh,1..2] of longint;
map,f,cost:array[0..maxd,0..maxd] of longint;
b:array[0..maxd] of boolean;
q:array[1..maxd*5] of longint;
d,pre:array[0..maxd] of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure spfa;
var
i,j,h,t,now:longint;
begin
fillchar(d,sizeof(d),127);
fillchar(b,sizeof(b),false);
fillchar(pre,sizeof(pre),0);
d[0]:=0;
b[0]:=true;
h:=1;t:=1;
q[1]:=0;
while h<=t do
begin
now:=q[h];
for i:=0 to 2*ut+1 do
if (map[now,i]-f[now,i]>0) then
if (d[now]+cost[now,i]<d[i]) then
begin
d[i]:=d[now]+cost[now,i];
pre[i]:=now;
if not(b[i]) then
begin
b[i]:=true;
inc(t);
q[t]:=i;
end;
end;
b[now]:=false;
inc(h);
end;
end;
function hllp:longint;
var
i,j,k,flow,totalcost,nowcost:longint;
begin
hllp:=0;
totalcost:=0;
while (true) do
begin
spfa;
if d[ut*2+1]=2139062143 then exit(totalcost);
flow:=maxlongint;
i:=ut*2+1;
repeat
flow:=min(map[pre[i],i]-f[pre[i],i],flow);
i:=pre[i];
until i=0;
i:=ut*2+1;
nowcost:=0;
repeat
inc(f[pre[i],i],flow);
f[i,pre[i]]:=-f[pre[i],i];
inc(nowcost,cost[pre[i],i]);
i:=pre[i];
until i=0;
inc(totalcost,nowcost*flow);
end;
end;
function main:longint;
var
i,j,k:longint;
begin
main:=0;
fillchar(map,sizeof(map),0);
fillchar(f,sizeof(f),0);
fillchar(cost,sizeof(cost),0);
for i:=1 to ut do map[0,i]:=1;
for i:=ut+1 to ut+vt do map[i,ut+vt+1]:=1;
for i:=1 to ut do
for j:=ut+1 to ut+vt do
begin
map[i,j]:=1;
cost[i,j]:=abs(u[i,1]-v[j-ut,1])+abs(u[i,2]-v[j-ut,2]);
cost[j,i]:=-cost[i,j];
end;
main:=hllp;
end;
begin
while not eof do
begin
readln(n,m);
if (n=0) and (m=0) then break;
ut:=0;
vt:=0;
for i:=1 to n do
begin
readln(s);
for j:=1 to m do
if s[j]='m' then
begin
inc(ut);
u[ut,1]:=i;
u[ut,2]:=j;
end
else if s[j]='H' then
begin
inc(vt);
v[vt,1]:=i;
v[vt,2]:=j;
end;
end;
writeln(main);
end;
end.
一开始居然忘添反向边……
Program P2516;
const
maxn=100;
maxm=100;
maxk=100;
var
n,m,k,i,j,l,maxflow:longint;
need,prod:array[1..maxn,1..maxk] of longint;
needk,prodk:array[1..maxk] of longint;
fee:array[1..maxk,1..maxn,1..maxm] of longint;
cost,map,f:array[0..200,0..200] of longint;
b:array[0..200] of boolean;
d,pre:array[0..200] of longint;
q:array[1..500000] of longint;
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 spfa;
var
i,j,l,h,t,now:longint;
begin
fillchar(d,sizeof(d),127);
fillchar(b,sizeof(b),false);
fillchar(pre,sizeof(pre),0);
d[0]:=0;
b[0]:=true;
q[1]:=0;
h:=1;t:=1;
while h<=t do
begin
now:=q[h];
for i:=0 to n+m+1 do
if (map[now,i]-f[now,i]>0) then
if (d[now]+cost[now,i]<d[i]) then
begin
d[i]:=d[now]+cost[now,i];
pre[i]:=now;
if not(b[i]) then
begin
b[i]:=true;
inc(t);
q[t]:=i;
end;
end;
b[now]:=false;
inc(h);
end;
end;
function hllp:longint;
var
i,j,l,flow,totalflow,p:longint;
totalcost,nowcost:longint;
begin
hllp:=0;
totalflow:=0;
totalcost:=0;
while (true) do
begin
spfa;
if d[n+m+1]=2139062143 then exit(totalcost);
flow:=maxlongint;
i:=n+m+1;
repeat
flow:=min(flow,map[pre[i],i]-f[pre[i],i]);
i:=pre[i];
until i=0;
nowcost:=0;
i:=n+m+1;
repeat
inc(f[pre[i],i],flow);
f[i,pre[i]]:=-f[pre[i],i];
inc(nowcost,cost[pre[i],i]);
i:=pre[i];
until i=0;
inc(totalcost,nowcost*flow);
end;
end;
function main:longint;
var
i,j,l,s,t:longint;
begin
main:=0;
for i:=1 to k do if prodk[i]<needk[i] then exit(-1);
for i:=1 to k do
begin
fillchar(cost,sizeof(cost),0);
fillchar(map,sizeof(map),0);
fillchar(f,sizeof(f),0);
s:=0;
t:=n+m+1;
for j:=1 to m do map[s,j]:=prod[j,i];
for j:=1 to n do map[m+j,t]:=need[j,i];
for j:=1 to m do
for l:=1 to n do
begin
map[j,m+l]:=prod[j,i];
cost[j,m+l]:=fee[i,l,j];
cost[m+l,j]:=-cost[j,m+l];
end;
main:=main+hllp;
end;
end;
begin
while not seekeof do
begin
read(n,m,k);
if (n=0) and (m=0) and (k=0) then break;
fillchar(needk,sizeof(needk),0);
fillchar(prodk,sizeof(prodk),0);
for i:=1 to n do
for j:=1 to k do
begin
read(need[i,j]);
inc(needk[j],need[i,j]);
end;
for i:=1 to m do
for j:=1 to k do
begin
read(prod[i,j]);
inc(prodk[j],prod[i,j]);
end;
for i:=1 to k do
for j:=1 to n do
for l:=1 to m do
begin
read(fee[i,j,l]);
end;
writeln(main);
end;
end.
这题是exgcd……
我居然连wa了2天……
至少知道DIV函数的性质了 （-x) div t =-(x div t)
(-x) div (-t) = (x div t)
发现自己数论蒟蒻……
Program p1061;
var
x,y,n,m,l,t:int64;
a,b,c,c2:int64;
function exgcd(a,b:int64):int64;
var
x1,y1:longint;
begin
if b=0 then
begin
x:=1;
y:=0;
exit(a);
end;
exgcd:=exgcd(b,a mod b);
x1:=y;
y1:=x-(a div b)*y;
x:=x1;
y:=y1;
end;
begin
read(x,y,m,n,l);
a:=n-m;
c:=x-y;
b:=l;
c2:=exgcd(a,b);
if (c mod c2<>0) then writeln('Impossible')
else
begin
x:=x*(c div c2);
y:=y*(c div c2);
t:=b div c2;
if t<0 then
while (x<0) do
begin
x:=x-t*abs(x div t)-t;
end;
if t>0 then while (x<0) do x:=x+t*abs(x div t)+t;
x:=x mod (b div c2);
writeln(x);
end;
end.
哪为朋友帮我看看多关键字排序哪儿错了……
Program P1018;
type
product=record
b,id:longint;
p:longint;
end;
var
t,n,i,j,total,count,maxb,mintb,price:longint;
visit:array[1..100] of longint;
m:array[1..100] of longint;
a:array[1..100000] of product;
ans:double;
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(b) else exit(a);
end;
procedure qsort(l,r:longint);
var
i,j:longint;
m,p:product;
begin
i:=l;
j:=r;
m:=a[(l+r) div 2];
repeat
while a[i].b<m.b do inc(i);
// while (a[i].p<m.p) and (a[i].b=m.b) do inc(i);
// while (a[i].id<m.id) and (a[i].b=m.b) and (a[i].p=m.p) do inc(i);
while a[j].b>m.b do dec(j);
// while (a[j].p>m.p) and (a[j].b=m.b) do dec(j);
// while (a[j].id>m.id) and (a[j].b=m.b) and (a[j].p=m.p) do dec(j);
if i<=j then
begin
p:=a[i];
a[i]:=a[j];
a[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;
begin
{ assign(input,'p1018.in');
assign(output,'p1018.out');
reset(input);
rewrite(output);
}read(t);
while t>0 do
begin
total:=0;
read(n);
mintb:=maxlongint;
for i:=1 to n do
begin
read(m[i]);
maxb:=0;
for j:=1 to m[i] do
begin
inc(total);
a[total].id:=i;
read(a[total].b,a[total].p);
maxb:=max(a[total].b,maxb);
end;
mintb:=min(maxb,mintb);
end;
qsort(1,total);
ans:=0;
for i:=1 to total-n+1 do
begin
if a[i].b>mintb then break;
count:=0;
fillchar(visit,sizeof(visit),0);
visit[a[i].id]:=a[i].p;
for j:=i+1 to total do
begin
if a[j].b<a[i].b then write('x');
if (visit[a[j].id]=0) then
begin
inc(count);
visit[a[j].id]:=a[j].p;
end;
visit[a[j].id]:=min(visit[a[j].id],a[j].p);
end;
if count<n-1 then break;
price:=0;
for j:=1 to n do inc(price,visit[j]);
if ans<(a[i].b/price) then ans:=a[i].b/price;
end;
writeln(ans:3:3);
dec(t);
end;
{
close(input);
close(output); }
end.
注意普通路径是双向的
program P3259;
var
f,n,m,w,i,j:longint;
s,e,t:longint;
map:array[1..2500,1..3] of longint;
wmap:array[1..300,1..3] of longint;
d:array[1..2500] of longint;
flag:boolean;
procedure relax(u,v,w:longint);
begin
if (d[v]>d[u]+w) then
begin
d[v]:=d[u]+w;
flag:=false;
end;
end;
procedure bellman_ford;
var
i,j:longint;
begin
for i:=1 to n do
begin
flag:=true;
for j:=1 to m do
begin
relax(map[j,1],map[j,2],map[j,3]);
relax(map[j,2],map[j,1],map[j,3]);
end;
for j:=1 to w do relax(wmap[j,1],wmap[j,2],-wmap[j,3]);
if flag then break;
end;
if flag then writeln('NO') else writeln('YES');
end;
begin
read(f);
while f>0 do
begin
fillchar(map,sizeof(map),0);
fillchar(wmap,sizeof(wmap),0);
fillchar(d,sizeof(d),0);
read(n,m,w);
for i:=1 to m do
begin
read(map[i,1],map[i,2],map[i,3]);
end;
for i:=1 to w do read(wmap[i,1],wmap[i,2],wmap[i,3]);
bellman_ford;
dec(f);
end;
end.
别问我……我也不知道怎么证明
Program p2505;
var
n:double;
begin
while not seekeof do
begin
read(n);
while n>18 do n:=n/18;
if n<=9 then writeln('Stan wins.')
else writeln('Ollie wins.');
end;
end.
高精Dp
Program P2506;
type
arr=record
a:array[1..10000] of longint;
len:longint;
end;
const
base=1000;
var
i,j,n:longint;
f:array[0..250] of arr;
function max(a,b:longint):longint;
begin
if a<b then exit(b) else exit(a);
end;
Procedure add(a,b:arr;var c:arr);
var
i,j,len:longint;
begin
fillchar(c,sizeof(c),0);
for i:=1 to max(a.len,b.len) do
begin
inc(c.a[i],a.a[i]+2*b.a[i]);
inc(c.a[i+1],c.a[i] div base);
c.a[i]:=c.a[i] mod base;
end;
i:=max(a.len,b.len);
while (c.a[i+1]>0) do
begin
inc(i);
inc(c.a[i+1],c.a[i] div base);
c.a[i]:=c.a[i] mod base;
end;
while (i>1) and (c.a[i]=0) do dec(i);
c.len:=i;
end;
begin
fillchar(f,sizeof(f),0);
for i:=0 to 250 do f[i].len:=1;
f[1].a[1]:=1;
f[0].a[1]:=1;
for i:=2 to 250 do add(f[i-1],f[i-2],f[i]);
while not eof do
begin
readln(n);
write(f[n].a[f[n].len]);
for i:=f[n].len-1 downto 1 do
begin
if f[n].a[i]<100 then write('0');
if f[n].a[i]<10 then write('0');
write(f[n].a[i]);
end;
writeln;
end;
end.
格雷码做
0要特判
答案 就是读入的两个数充格雷码转为2进制的差的绝对值的十进制
Program P1832;
Type
arr=record
a:array[1..500] of longint;
len:longint;
end;
var
n,m,i:longint;
a,b,c,d:arr;
node2:array[1..1000] of arr;
function max(a,b:longint):longint;
begin
if a<b then exit(b) else exit(a);
end;
function compare:boolean;
var
i,j:longint;
begin
while (a.len>1) and (a.a[a.len]=0) do dec(a.len);
while (b.len>1) and (b.a[b.len]=0) do dec(b.len);
if a.len<b.len then exit(true)
else if a.len>b.len then exit(false);
i:=a.len;
while (i>1) and (a.a[i]=b.a[i]) do
begin
dec(i);
end;
if (a.a[i]<=b.a[i]) then exit(true) else exit(false);
end;
Procedure Subtract(a,b:arr;var c:arr);
var
i,j:longint;
pa:arr;
begin
if (compare) then
begin
pa:=a;
a:=b;
b:=pa;
end;
fillchar(c,sizeof(c),0);
for i:=1 to a.len do
begin
inc(c.a[i],a.a[i]-b.a[i]);
if c.a[i]<0 then
begin
inc(c.a[i],2);
dec(c.a[i+1]);
end;
end;
c.len:=a.len;
while (c.len>1) and (c.a[c.len]=0) do dec(c.len);
end;
procedure add(a,b:arr;var c:arr);
var
i,j:longint;
begin
fillchar(c,sizeof(c),0);
for i:=1 to max(a.len,b.len) do
begin
inc(c.a[i],a.a[i]+b.a[i]);
inc(c.a[i+1],c.a[i] div 10);
c.a[i]:=c.a[i] mod 10;
end;
c.len:=max(a.len,b.len)+1;
while (c.len>1) and (c.a[c.len]=0) do dec(c.len);
end;
begin
fillchar(node2,sizeof(node2),0);
node2[1].len:=1;
node2[1].a[1]:=1;
for i:=2 to 500 do
begin
add(node2[i-1],node2[i-1],node2[i]);
end;
{ assign(input,'P1832.in');
assign(output,'P1832.out');
reset(input);
rewrite(output);
}
read(m);
while m>0 do
begin
fillchar(a,sizeof(a),0);
fillchar(b,sizeof(b),0);
read(n);
if n=0 then
begin
writeln('0');
dec(m);
continue;
end;
for i:=n downto 1 do read(a.a[i]);
for i:=n downto 1 do read(b.a[i]);
for i:=n-1 downto 1 do
begin
a.a[i]:=(a.a[i] xor a.a[i+1]);
end;
for i:=n-1 downto 1 do
b.a[i]:=b.a[i] xor b.a[i+1];
a.len:=n;
b.len:=n;
subtract(a,b,c);
// for i:=n downto 1 do write(c.a[i]);
// writeln;
fillchar(d,sizeof(d),0);
d.len:=1;
for i:=n downto 1 do
if c.a[i]>0 then add(node2[i],d,d);
for i:=d.len downto 1 do write(d.a[i]);
writeln;
dec(m);
end;
{ close(input);
close(output);
}
end.