2023年7月30日发(作者：)

1、潜伏者

program spy;

var

v: array['A'..'Z'] of boolean;

p, q: array['A'..'Z'] of char;

a, b: string;

j: char;

i: integer;

procedure stop;

begin

writeln('Failed');

close(input);

close(output);

halt;

end;

begin

assign(input, '');

reset(input);

assign(output, '');

rewrite(output);

readln(a);

readln(b);

fillchar(v, sizeof(v), 0);

for i := 1 to length(a) do

begin

v[a[i]] := true;

p[a[i]] := b[i];

q[b[i]] := a[i];

end;

for j := 'A' to 'Z' do

if not v[j] then stop;

for i := 1 to length(a) do

begin

if p[a[i]] <> b[i] then stop;

if q[b[i]] <> a[i] then stop;

end;

readln(a);

for i := 1 to length(a) do

write(p[a[i]]);

writeln;

close(input);

close(output);

end. 2、Hankson的趣味题

思路1：

根据最大公约数的定义，X必定为最大公约数的倍数，那么我们可以去枚举a1的倍数，然后去验证最大公约数和最小公倍数是否符合条件。期待分数：50。

程序1：

var

a0,a1,b0,b1,i,j,n,k,x,tot:longint;

function gcd(a,b:longint):longint;

begin

if b=0 then exit(a) else exit(gcd(b,a mod b));

end;

begin

readln(n);

for k:=1 to n do

begin

tot:=0;

readln(a0,a1,b0,b1);

for i:=1 to (b1 div a1) do

begin

x:=i*a1;

if b1 mod x=0 then

if gcd(a0,x)=a1 then

if (b0*x) div (gcd(b0,x))=b1 then begin inc(tot); end;

end;

writeln(tot);

end;

end.

思路2：

根据最小公倍数和最大公约数分解质因数指数的特殊关系进行优化。比如两个数，分解质因数可以得到以下的式子

A=p1^a1+p2^a2+p3^a3……

B=p1^b1+p2^b2+p3^a3……

例如6和21就可以分解成

6=2^1+3^1+5^0+7^0……

21=2^0+3^1+5^0+7^1……

则最大公约数=2^(min(a1,b1))+3^(min(a2,b2))+5^(min(a3,b3))+7^(min(a4,b4))…

最小公倍数=2^(max(a1,b1))+3^(max(a2,b2))+5^(max(a3,b3))+7^(max(a4,b4))…

那么我们可以先将b1分解质因数，在根据最大公约数和最小公倍数在指数上的关系，进行搜索。期待分数：100

程序2：

var

p,x,c:array[0..1000] of longint;

a0,a1,b0,b1,i,j,k,m,tot,t,n:longint;

function gcd(a,b:longint):longint;

begin

if b=0 then exit(a) else exit(gcd(b,a mod b));

end;

procedure dfs(i,sum:longint);

var

max,j:longint;

begin

if i>m then

begin

inc(tot);

p[tot]:=sum;

exit;

end;

max:=sum;

dfs(i+1,max);

for j:=1 to c[i] do

begin

max:=max*x[i];

dfs(i+1,max);

end;

end;

procedure work(b:longint);

var i,p:longint;

begin

i:=2;

p:=b;

while i<=sqrt(p) do

begin

if p mod i=0 then

begin

inc(m);

x[m]:=i;

c[m]:=0;

repeat inc(c[m]);

p:=p div i;

until p mod i<>0;

end;

inc(i);

end;

if p<>1 then

begin

inc(m);

x[m]:=p;

c[m]:=1;

end;

dfs(1,1);

end;

begin

readln(n);

for i:=1 to n do

begin

readln(a0,a1,b0,b1);

fillchar(p,sizeof(p),0);

fillchar(x,sizeof(x),0);

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

m:=0;

tot:=0;

t:=0;

work(b1);

for j:=1 to tot do

if (gcd(p[j],a0)=a1) and ((p[j] div gcd(p[j],b0) * b0)=b1) then inc(t);

writeln(t);

end;

end.

思路三：

和思路二有异曲同工之妙。我们可以先预处理trunc(sqrt(2000000000))以内的质数，然后每读入一组数据，初始答案ans=1,然后我们循环质数，看a0、a1、b0、b1里面有多少个该质数因子，并且将这四个数分别消去所有该质数因子。我们设求出来的该因子个数分别是t1、t2、t3、t4。如果数据合法，那么t1>=t2,t3<=t4。根据最大公约数和最小公倍数的定义，我们要求的数所拥有的该质因子个数s必须要同时满足以下限制条件：

若t1>t2,则s=t2

若t1=t2，则s>=t2

若t3

这样，我们或者求出了s的范围，要么证明了不存在合法数字。如果s存在合法取值，我们就将ans乘上s的合法取值个数，否则直接输出0。

注意：如果循环结束后，a0>1或b1>1，那么此时a0或b1一定是超过我们枚举的数字范围的质数。这时我们特殊判断一下就行了。我们的时间复杂度是循环质数复杂度+分解因数复杂度。分解因数最坏是该数为2的若干次方，所以复杂度的上限是log(2000000000)，很小。最慢的点在0.3秒以内出解。

程序3

program son;

var i,j,k,l,m,n,p,q,l2,r2,r,s,t,a0,a1,b0,b1,ans:longint;

prime:array[0..60000] of longint;

need:array[0..60000] of longint;

pd:boolean;

function pri(x:longint):boolean;

var g:longint;

begin

for g:=2 to trunc(sqrt(x)) do

if x mod g=0 then exit(false);

exit(true);

end;

begin

p:=1;prime[1]:=2;

for i:=3 to 50000 do if pri(i) then

begin

inc(p);

prime[p]:=i;

end;

read(n);

for t:=1 to n do

begin

read(a0,a1,b0,b1);

ans:=1;

fillchar(need,sizeof(need),255);

q:=p;

pd:=true;

for i:=1 to p do

begin

l:=0;r:=0;l2:=0;r2:=0;

while a0 mod prime[i]=0 do begin

inc(l);a0:=a0 div prime[i];

end;

while a1 mod prime[i]=0 do

begin

inc(r);a1:=a1 div prime[i];

end;

while b0 mod prime[i]=0 do

begin

inc(l2);b0:=b0 div prime[i];

end;

while b1 mod prime[i]=0 do

begin

inc(r2);b1:=b1 div prime[i];

end;

if l>r then need[i]:=r;

if l2

begin

if (need[i]>-1)and(need[i]<>r2) then

begin

pd:=false;break;

end;

need[i]:=r2;

end;

if need[i]=-1 then

if r2

begin

pd:=false;break;

end else ans:=ans*(r2-r+1);

end;

if i=p then

if a0>1 then

begin

inc(i);prime[i]:=a0;

l:=0;r:=0;l2:=0;r2:=0;

while a0 mod prime[i]=0 do

begin

inc(l);a0:=a0 div prime[i];

end;

while a1 mod prime[i]=0 do

begin

inc(r);a1:=a1 div prime[i];

end; while b0 mod prime[i]=0 do

begin

inc(l2);b0:=b0 div prime[i];

end;

while b1 mod prime[i]=0 do

begin

inc(r2);b1:=b1 div prime[i];

end;

if l>r then need[i]:=r;

if l2

begin

if (need[i]>-1)and(need[i]<>r2) then

begin

pd:=false;

end;

need[i]:=r2;

end;

if need[i]=-1 then

if r2

begin

pd:=false;

end else ans:=ans*(r2-r+1);

dec(i);

end;

if i=p then

if b1>1 then

begin

inc(i);prime[i]:=b1;

l:=0;r:=0;l2:=0;r2:=0;

while a0 mod prime[i]=0 do

begin

inc(l);a0:=a0 div prime[i];

end;

while a1 mod prime[i]=0 do

begin

inc(r);a1:=a1 div prime[i];

end;

while b0 mod prime[i]=0 do

begin

inc(l2);b0:=b0 div prime[i];

end;

while b1 mod prime[i]=0 do

begin

inc(r2);b1:=b1 div prime[i]; end;

if l>r then need[i]:=r;

if l2

begin

if (need[i]>-1)and(need[i]<>r2) then

begin

pd:=false;

end;

need[i]:=r2;

end;

if need[i]=-1 then

if r2

begin

pd:=false;

end else ans:=ans*(r2-r+1);

dec(i);

end;

if not pd then writeln(0) else writeln(ans);

end;

end.

程序4

program son;

var

p, x, c: array[1..10000] of longint;

n, m, t, i, j, k, a0, a1, b0, b1: longint;

function gcd(m, n: longint): longint;

var

r: longint;

begin

while n <> 0 do

begin

r := m mod n;

m := n;

n := r;

end;

gcd := m;

end;

procedure dfs(const i: longint; s: longint);

var

j: longint;

begin

if i > m then begin

inc(k);

p[k] := s;

exit;

end;

dfs(i + 1, s);

for j := 1 to c[i] do

begin

s := s * x[i];

dfs(i + 1, s);

end;

end;

procedure get(b: longint);

var

i: longint;

begin

m := 0;

i := 2;

while i <= sqrt(b) + 1e-6 do

begin

if b mod i = 0 then

begin

inc(m);

x[m] := i;

c[m] := 0;

repeat

inc(c[m]);

b := b div i;

until b mod i <> 0;

end;

inc(i);

end;

if b <> 1 then

begin

inc(m);

x[m] := b;

c[m] := 1;

end;

k := 0;

dfs(1, 1);

end;

begin

assign(input, '');

reset(input); assign(output, '');

rewrite(output);

read(n);

for i := 1 to n do

begin

read(a0, a1, b0, b1);

get(b1);

t := 0;

for j := 1 to k do

if (gcd(p[j], a0) = a1) and (p[j] div gcd(p[j], b0) * b0 = b1) then

inc(t);

writeln(t);

end;

close(input);

close(output);

end.

3、最优贸易

两次SPFA，用a[i]表示从起点开始到i结点能经过的最小值，用b[i]表示从终点延反向边到达i结点能经过的最大值。Ans=max(b[i]-a[i])。

const

maxn=100010;

maxm=1000010;

type

data=record

t,f,next:longint;

end;

var

n,m,ls:longint;

a,c,d,stack,v:axn]of longint;

f:axn]of boolean;

seg:axm]of data;

procedure insert_e(s,t,f1,f2:longint);

begin

inc(ls);

seg[ls].t:=t;

seg[ls].f:=f1;

seg[ls].next:=a[s];

a[s]:=ls;

inc(ls);

seg[ls].t:=s;

seg[ls].f:=f2;

seg[ls].next:=a[t];

a[t]:=ls; end;

procedure init;

var

i,j,k,l:longint;

begin

readln(n,m);

fillchar(a,sizeof(a),255);

ls:=0;

for i:=1 to n do read(v[i]);

for i:=1 to m do

begin

readln(j,k,l);

if l=1 then insert_e(j,k,1,2)

else insert_e(j,k,3,3);

end;

end;

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

end;

procedure spfa1;

var

i,k,open,closed:longint;

begin

fillchar(c,sizeof(c),127);

fillchar(f,sizeof(f),0);

f[1]:=true;

open:=0;

closed:=1;

stack[1]:=1;

c[1]:=v[1];

while open

begin

inc(open);

k:=stack[open mod maxn];

f[k]:=false;

i:=a[k];

while i<>-1 do

begin

if (seg[i].f and 1=1)and(min(c[k],v[seg[i].t])

c[seg[i].t]:=min(c[k],v[seg[i].t]);

if not f[seg[i].t] then

begin

f[seg[i].t]:=true;

inc(closed);

stack[closed mod maxn]:=seg[i].t;

end;

end;

i:=seg[i].next;

end;

end;

end;

procedure spfa2;

var

i,k,open,closed:longint;

begin

fillchar(d,sizeof(d),0);

fillchar(f,sizeof(f),0);

f[n]:=true;

open:=0;

closed:=1;

stack[1]:=n;

d[n]:=v[n];

while open

begin

inc(open);

k:=stack[open mod maxn];

f[k]:=false;

i:=a[k];

while i<>-1 do

begin

if (seg[i].f and 2=2)and(max(d[k],v[seg[i].t])>d[seg[i].t]) then

begin

d[seg[i].t]:=max(d[k],v[seg[i].t]);

if not f[seg[i].t] then

begin

f[seg[i].t]:=true;

inc(closed);

stack[closed mod maxn]:=seg[i].t;

end;

end;

i:=seg[i].next;

end; end;

end;

procedure main;

var

i,ans:longint;

begin

spfa1;

spfa2;

ans:=0;

for i:=1 to n do

ans:=max(ans,d[i]-c[i]);

writeln(ans);

end;

begin

assign(input,'');

reset(input);

assign(output,'');

rewrite(output);

init;

main;

close(input);

close(output);

end.

程序2：

program trade;

const

maxn = 100005;

var

e1, e2: array[1..1000010] of record

t, next: longint;

end;

a, b, g1, g2, q: axn] of longint;

v: axn] of boolean;

n, i, f, r, k, p, s: longint;

procedure init;

var

m, s, i, j, k, z: longint;

procedure link(const i, j: longint);

begin

inc(s);

with e1[s] do

begin t := j;

next := g1[i];

end;

g1[i] := s;

with e2[s] do

begin

t := i;

next := g2[j];

end;

g2[j] := s;

end;

begin

read(n, m);

for i := 1 to n do read(b[i]);

fillchar(g1, sizeof(g1), 0);

fillchar(g2, sizeof(g2), 0);

s := 0;

for k := 1 to m do

begin

read(i, j, z);

link(i, j);

if z = 2 then link(j, i);

end;

end;

begin

assign(input, '');

reset(input);

assign(output, '');

rewrite(output);

init;

fillchar(v, sizeof(v), 0);

a[1] := b[1];

for i := 2 to n do a[i] := 100000;

f := 0;

r := 1;

q[1] := 1;

while f <> r do

begin

if f = maxn then f := 1 else inc(f);

k := q[f];

v[k] := false;

p := g1[k];

while p <> 0 do

begin with e1[p] do

if a[t] > a[k] then

begin

a[t] := a[k];

if a[t] > b[t] then a[t] := b[t];

if not v[t] then

begin

if r = maxn then r := 1 else inc(r);

q[r] := t;

v[t] := true;

end;

end;

p := e1[p].next;

end;

end;

s := 0;

fillchar(v, sizeof(v), 0);

f := 1;

r := 1;

q[1] := n;

v[n] := true;

if s < b[n] - a[n] then s := b[n] - a[n];

while f <= r do

begin

p := g2[q[f]];

while p <> 0 do

begin

with e2[p] do

if not v[t] then

begin

v[t] := true;

if s < b[t] - a[t] then s := b[t] - a[t];

inc(r);

q[r] := t;

end;

p := e2[p].next;

end;

inc(f);

end;

writeln(s);

close(input);

close(output);

end. 4、靶形数独

program d_1;

var usei,usej,usex:array[0..10,0..10] of boolean;

usep:array[0..100] of boolean;

maxi,a:array[0..10,0..10] of longint;

t,s,max,tot,i,j,k,n,m,p:longint;

x,y:array[0..100] of longint;

function solve(i,J:longint):longint;

var s,s1:longint;

begin

if (i<=j) then s:=i else s:=j;

if (10-i<=10-j) then s1:=10-i else s1:=10-j;

if (s=1) or (s1=1) then begin solve:=6; exit;end;

if (s=2) or (s1=2) then begin solve:=7; exit;end;

if (s=3) or (s1=3) then begin solve:=8; exit;end;

if (s=4) or (s1=4) then begin solve:=9; exit;end;

if (s=5) or (s1=5) then begin solve:=10;exit;end;

end;

function pr(i,j:longint):longint;

begin

pr:=(i-1) div 3*3+(j-1) div 3+1;

end;

procedure tryit(pp,now:longint);

var t,min,w,j:longint;

begin

if pp=s+1 then

begin

if now>max then

begin

max:=now;

maxi:=a;

end

end

else

begin

t:=0; min:=999999;

for i:=1 to s do

if (a[x[i],y[i]]=0) and (not(usep[i])) then

begin

w:=0;

for j:=1 to 9 do

if (usei[x[i],j]) and (usej[y[i],j]) and

(usex[pr(x[i],y[i]),j]) then

begin inc(w);

if w>=min then break;

end;

if w

begin

min:=w;

t:=i;

end;

end;

if min=0 then exit;

usep[t]:=true;

for j:=1 to 9 do

if (usei[x[t],j]) and (usej[y[t],j]) and

(usex[pr(x[t],y[t]),j]) then

begin

usei[x[t],j]:=false;

usej[y[t],j]:=false;

usex[pr(x[t],y[t]),j]:=false;

a[x[t],y[t]]:=j;

tryit(pp+1,now+solve(x[t],y[t])*j);

a[x[t],y[t]]:=0;

usei[x[t],j]:=true;

usej[y[t],j]:=true;

usex[pr(x[t],y[t]),j]:=true;

end;

usep[t]:=false;

end;

end;

begin

assign(input,'');

assign(output,'');

reset(input);

rewrite(output);

fillchar(usei,sizeof(usei),true);

fillchar(usej,sizeof(usej),true);

fillchar(usex,sizeof(usex),true);

tot:=0; max:=0; s:=0;

for i:=1 to 9 do

begin

for j:=1 to 9 do

begin

read(a[i,j]);

if a[i,j]<>0 then

begin usei[i,a[i,j]]:=false;

usej[j,a[i,j]]:=false;

usex[pr(i,j),a[i,j]]:=false;

t:=solve(i,j);

tot:=tot+t*a[i,j];

end;

if (a[i,j]=0) then

begin

inc(s);

x[s]:=i; y[s]:=j;

end;

end;

readln;

end;

fillchar(usep,sizeof(usep),false);

tryit(1,tot);

if max=0 then writeln('-1') else writeln(max);

close(input);

close(output);

end.