2009年信息学奥赛（我是高一的）的四道题目及解法

Question

跪求，有一道题是间谍有一道题是公约数那次（pascal语言）

Answer 1

1．潜伏者
(spy.pas/c/cpp)
【问题描述】
R 国和S 国正陷入战火之中，双方都互派间谍，潜入对方内部，伺机行动。
历尽艰险后，潜伏于 S 国的R 国间谍小C 终于摸清了S 国军用密码的编码规则：
1． S 国军方内部欲发送的原信息经过加密后在网络上发送，原信息的内容与加密后所
得的内容均由大写字母‘A’-‘Z’构成（无空格等其他字符）。
2． S 国对于每个字母规定了对应的“密字”。加密的过程就是将原信息中的所有字母替
换为其对应的“密字”。
3． 每个字母只对应一个唯一的“密字”，不同的字母对应不同的“密字”。“密字”可以
和原字母相同。
例如，若规定‘A’的密字为‘A’，‘B’的密字为‘C’（其他字母及密字略），则原信
息“ABA”被加密为“ACA”。
现在，小 C 通过内线掌握了S 国网络上发送的一条加密信息及其对应的原信息。小C
希望能通过这条信息，破译S 国的军用密码。小C 的破译过程是这样的：扫描原信息，对
于原信息中的字母x（代表任一大写字母），找到其在加密信息中的对应大写字母y，并认为
在密码里y 是x 的密字。如此进行下去直到停止于如下的某个状态：
1． 所有信息扫描完毕，‘A’-‘Z’ 所有 26 个字母在原信息中均出现过并获得了相应
的“密字”。
2． 所有信息扫描完毕，但发现存在某个（或某些）字母在原信息中没有出现。
3． 扫描中发现掌握的信息里有明显的自相矛盾或错误（违反S 国密码的编码规则）。例
如某条信息“XYZ”被翻译为“ABA”就违反了“不同字母对应不同密字”的规则。
在小 C 忙得头昏脑涨之际，R 国司令部又发来电报，要求他翻译另外一条从S 国刚刚
截取到的加密信息。现在请你帮助小C：通过内线掌握的信息，尝试破译密码。然后利用破
译的密码，翻译电报中的加密信息。
【输入】
输入文件名为 spy.in，共3 行，每行为一个长度在1 到100 之间的字符串。
第 1 行为小C 掌握的一条加密信息。
第 2 行为第1 行的加密信息所对应的原信息。
第 3 行为R 国司令部要求小C 翻译的加密信息。
输入数据保证所有字符串仅由大写字母‘A’-‘Z’构成，且第1 行长度与第2 行相等。
【输出】
输出文件 spy.out 共1 行。
若破译密码停止时出现 2，3 两种情况，请你输出“Failed”（不含引号，注意首字母大
写，其它小写）。
否则请输出利用密码翻译电报中加密信息后得到的原信息。
【输入输出样例 1】
spy.in spy.out
AA
AB
EOWIE
Failed
全国信息学奥林匹克联赛（NOIP2009）复赛提高组
第 3 页共 7 页
【输入输出样例 1 说明】
原信息中的字母‘A’和‘B’对应相同的密字，输出“Failed”。
【输入输出样例 2】
spy.in spy.out
QWERTYUIOPLKJHGFDSAZXCVBN
ABCDEFGHIJKLMNOPQRSTUVWXY
DSLIEWO
Failed
【输入输出样例2 说明】
字母‘Z’在原信息中没有出现，输出“Failed”。
【输入输出样例 3】
spy.in spy.out
MSRTZCJKPFLQYVAWBINXUEDGHOOILSMIJFRCOPPQCEUNYDUMPP
YIZSDWAHLNOVFUCERKJXQMGTBPPKOIYKANZWPLLVWMQJFGQYLL
FLSO
NOIP
2．Hankson 的趣味题
(son.pas/c/cpp)
【问题描述】
Hanks 博士是BT (Bio-Tech，生物技术) 领域的知名专家，他的儿子名叫Hankson。现
在，刚刚放学回家的Hankson 正在思考一个有趣的问题。
今天在课堂上，老师讲解了如何求两个正整数c1 和c2 的最大公约数和最小公倍数。现
在Hankson 认为自己已经熟练地掌握了这些知识，他开始思考一个“求公约数”和“求公
倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数a0,a1,b0,b1，设某未知正整
数x 满足：
1． x 和a0 的最大公约数是a1；
2． x 和b0 的最小公倍数是b1。
Hankson 的“逆问题”就是求出满足条件的正整数x。但稍加思索之后，他发现这样的
x 并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的x 的个数。请你帮
助他编程求解这个问题。
【输入】
输入文件名为 son.in。第一行为一个正整数n，表示有n 组输入数据。接下来的n 行每
行一组输入数据，为四个正整数a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入
数据保证a0 能被a1 整除，b1 能被b0 整除。
【输出】
输出文件 son.out 共n 行。每组输入数据的输出结果占一行，为一个整数。
对于每组数据：若不存在这样的 x，请输出0；
若存在这样的 x，请输出满足条件的x 的个数；
全国信息学奥林匹克联赛（NOIP2009）复赛提高组
第 4 页共 7 页
【输入输出样例】
son.in son.out
2
41 1 96 288
95 1 37 1776
6
2
【说明】
第一组输入数据，x 可以是9、18、36、72、144、288，共有6 个。
第二组输入数据，x 可以是48、1776，共有2 个。
【数据范围】
对于 50%的数据，保证有1≤a0，a1，b0，b1≤10000 且n≤100。
对于 100%的数据，保证有1≤a0，a1，b0，b1≤2,000,000,000 且n≤2000。
3．最优贸易
(trade.pas/c/cpp)
【问题描述】
C 国有n 个大城市和m 条道路，每条道路连接这n 个城市中的某两个城市。任意两个
城市之间最多只有一条道路直接相连。这m 条道路中有一部分为单向通行的道路，一部分
为双向通行的道路，双向通行的道路在统计条数时也计为1 条。
C 国幅员辽阔，各地的资源分布情况各不相同，这就导致了同一种商品在不同城市的价
格不一定相同。但是，同一种商品在同一个城市的买入价和卖出价始终是相同的。
商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息
之后，便决定在旅游的同时，利用商品在不同城市中的差价赚回一点旅费。设C 国n 个城
市的标号从1~ n，阿龙决定从1 号城市出发，并最终在n 号城市结束自己的旅行。在旅游的
过程中，任何城市可以重复经过多次，但不要求经过所有n 个城市。阿龙通过这样的贸易方
式赚取旅费：他会选择一个经过的城市买入他最喜欢的商品——水晶球，并在之后经过的另
一个城市卖出这个水晶球，用赚取的差价当做旅费。由于阿龙主要是来C 国旅游，他决定
这个贸易只进行最多一次，当然，在赚不到差价的情况下他就无需进行贸易。
假设 C 国有5 个大城市，城市的编号和道路连接情况如下图，单向箭头表示这条道路
为单向通行，双向箭头表示这条道路为双向通行。
假设 1~n 号城市的水晶球价格分别为4，3，5，6，1。
阿龙可以选择如下一条线路：1->2->3->5，并在2 号城市以3 的价格买入水晶球，在3
号城市以5 的价格卖出水晶球，赚取的旅费数为2。
阿龙也可以选择如下一条线路 1->4->5->4->5，并在第1 次到达5 号城市时以1 的价格
买入水晶球，在第2 次到达4 号城市时以6 的价格卖出水晶球，赚取的旅费数为5。
全国信息学奥林匹克联赛（NOIP2009）复赛提高组
第 5 页共 7 页
现在给出 n 个城市的水晶球价格，m 条道路的信息（每条道路所连接的两个城市的编号
以及该条道路的通行情况）。请你告诉阿龙，他最多能赚取多少旅费。
【输入】
输入文件名为 trade.in。
第一行包含 2 个正整数n 和m，中间用一个空格隔开，分别表示城市的数目和道路的
数目。
第二行 n 个正整数，每两个整数之间用一个空格隔开，按标号顺序分别表示这n 个城
市的商品价格。
接下来 m 行，每行有3 个正整数，x，y，z，每两个整数之间用一个空格隔开。如果z=1，
表示这条道路是城市x 到城市y 之间的单向道路；如果z=2，表示这条道路为城市x 和城市
y 之间的双向道路。
【输出】
输出文件 trade.out 共1 行，包含1 个整数，表示最多能赚取的旅费。如果没有进行贸易，
则输出0。
【输入输出样例】
trade.in trade.out
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
5
【数据范围】
输入数据保证 1 号城市可以到达n 号城市。
对于 10%的数据，1≤n≤6。
对于 30%的数据，1≤n≤100。
对于 50%的数据，不存在一条旅游路线，可以从一个城市出发，再回到这个城市。
对于 100%的数据，1≤n≤100000，1≤m≤500000，1≤x，y≤n，1≤z≤2，1≤各城市
水晶球价格≤100。
4．靶形数独
(sudoku.pas/c/cpp)
【问题描述】
小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他
们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向Z 博士请教，
Z 博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。
靶形数独的方格同普通数独一样，在 9 格宽×9 格高的大九宫格中有9 个3 格宽×3 格
高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些
全国信息学奥林匹克联赛（NOIP2009）复赛提高组
第 6 页共 7 页
数字，利用逻辑推理，在其他的空格上填入1 到9 的数字。每个数字在每个小九宫格内不能
重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即
每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）
上图具体的分值分布是：最里面一格（黄色区域）为 10 分，黄色区域外面的一圈（红
色区域）每个格子为9 分，再外面一圈（蓝色区域）每个格子为8 分，蓝色区域外面一圈（棕
色区域）每个格子为7 分，最外面一圈（白色区域）每个格子为6 分，如上图所示。比赛的
要求是：每个人必须完成一个给定的数独（每个给定数独可能有不同的填法），而且要争取
更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字
的乘积的总和。如图，在以下的这个已经填完数字的靶形数独游戏中，总分数为2829。游
戏规定，将以总分数的高低决出胜负。
由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能
够得到的最高分数。
全国信息学奥林匹克联赛（NOIP2009）复赛提高组
第 7 页共 7 页
【输入】
输入文件名为 sudoku.in。
一共 9 行。每行9 个整数（每个数都在0—9 的范围内），表示一个尚未填满的数独方
格，未填的空格用“0”表示。每两个数字之间用一个空格隔开。
【输出】
输出文件 sudoku.out 共1 行。
输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数-1。
【输入输出样例 1】
sudoku.in sudoku.out
7 0 0 9 0 0 0 0 1
1 0 0 0 0 5 9 0 0
0 0 0 2 0 0 0 8 0
0 0 5 0 2 0 0 0 3
0 0 0 0 0 0 6 4 8
4 1 3 0 0 0 0 0 0
0 0 7 0 0 2 0 9 0
2 0 1 0 6 0 8 0 4
0 8 0 5 0 4 0 1 2
2829
【输入输出样例 2】
sudoku.in sudoku.out
0 0 0 7 0 2 4 5 3
9 0 0 0 0 8 0 0 0
7 4 0 0 0 5 0 1 0
1 9 5 0 8 0 0 0 0
0 7 0 0 0 0 0 2 5
0 3 0 5 7 9 1 0 8
0 0 0 6 0 1 0 0 0
0 6 0 9 0 0 0 0 1
0 0 0 0 0 0 0 0 6
2852
【数据范围】
40%的数据，数独中非0 数的个数不少于30。
80%的数据，数独中非0 数的个数不少于26。
100%的数据，数独中非0 数的个数不少于24。

答案：
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, 'spy.in');
reset(input);
assign(output, 'spy.out');
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的趣味题
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, 'son.in');
reset(input);
assign(output, 'son.out');
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、最优贸易
program trade;
const
maxn = 100005;
var
e1, e2: array[1..1000010] of record
t, next: longint;
end;
a, b, g1, g2, q: array[1..maxn] of longint;
v: array[1..maxn] 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, 'trade.in');
reset(input);
assign(output, 'trade.out');
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<min then
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,'sudoku.in');
assign(output,'sudoku.out');
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.