NOIP1997 提高组题目、题解、程序

这是我整理的信息学资料的一部分，包含1996-2008年信息学联赛的题目、题解和程序。希望能够对大家有一定的帮助。所写的程序使用 Free Pascal 编译。这些程序都是我一年或两年前所写，所以分析和代码难免会出现不优美或有问题，如果你发现这样的问题，请及时和我联系。如果你需要其它年份的资料，本站提供这些资料的目录。

一.在N*N的棋盘上(1<=N<=10)填入1,2,...N*N共N*N个数,使得任意两个相邻的数之和为素数. 例如,当N=2时,有

1	2
4	3

其相邻数的和为素数的有:1+2,1+4,4+3,2+3
当N=4时,一种可以填写的方案如下:

1	2	11	12
16	15	8	5
13	4	9	14
6	7	10	3

在这里我们约定:左上角的格子里必须放数字1
程序要求:
输入:N
输出:若有多种解,则需输出第一行,第一列之和均为最小的排列方案;若无解,则输出"NO!"

简析：这是一个搜索题目，需要注意判断素数的方法。

program noip1997_1;
type integer=longint;
var ss:array[1..200]of boolean;
    a,c:array[1..10,1..10]of integer;
    b:array[1..100]of boolean;
    i,n,minh,minl,j,pp:integer;
procedure get(var h,l:integer;i,j:integer);
var ii,p:integer;
begin
    h:=0;
    p:=n;
    if (i=1) then p:=j;
    for ii:=1 to p do
      h:=h+a[1,ii];
    l:=0;
    for ii:=1 to i do
      l:=l+a[ii,1];
end;
procedure sou(i,j,h,l:integer);
var k,yh,yl,p:integer;
    change,can:boolean;
begin
   p:=pp;
   if (i=j)and(j=1) then begin p:=1; end;
   k:=0;
   while k+1<=p do
   begin
       k:=k+1;
       if k=0 then k:=1;
       if b[k] then continue;
       if (i>1)and(ss[a[i-1,j]+k]=false)then continue;
       if (j>1)and(ss[a[i,j-1]+k]=false)then continue;
       b[k]:=true;
       a[i,j]:=k;
       yh:=h; yl:=l;
       if i=1 then yh:=yh+k;
       if j=1 then yl:=yl+k;
       if (yh>=minh)or(yl>=minl) then begin b[k]:=false; break; end;
       if (i=j)and(i=n) then begin  minh:=h; minl:=l; c:=a; end
                              else begin
                                if j=n
                                then sou(i+1,1,yh,yl)
                                else
                                     sou(i,j+1,yh,yl);
                              end;
      b[k]:=false;
   end;
end;
procedure init;
var i,j:integer;
begin
   for i:=1 to 200 do
   begin
     ss[i]:=true;
     for j:=2 to trunc(sqrt(i))+1 do
        if (i mod j=0)and(j<>i) then begin ss[i]:=false; break; end;
   end;
   ss[1]:=false;
end;
begin
   init;
   readln(n);
   minh:=999999;
   minl:=999999;
   pp:=n*n;
   sou(1,1,0,0);
   if minh=999999 then begin writeln('No!'); exit; end;
   for i:=1 to n do
   begin
     for j:=1 to n do
       write(c[i,j]:3);
     writeln;
   end;
end.

二.代数表达式的定义如下:

代数表达式:

项:

因子:

字母:

例如,下面式子是合法的代数表达式:

a+b*(a+c);

a*a/(b+c);

下列式子是不合法的代数表达式:

ab;

a+b*(c+d); {因子中无字母d}

程序要求:

输入:输入一个字符串,以";"结束,(";"本身不是代数表达式中字符,仅作为结束符号)

输出:若表达式正确,则输出:"OK";

若表达式不正确,则输出"ERROR",及错误类型

错误类型约定:

1.式子中出现不允许的字符;

2.括号不配对;

3.其他错误

例如:输入a+(b);

输出:OK

例如:输入a+(b+c*a;

输出 error 2

简析：主要注意考虑完全所有的情况。本题也可以用栈的思想解决。

program noip1997_2;
type integer=shortint;
var i:shortint;
    s:string;
function yunsuan(c:char):boolean;
begin
   if (c<>'+')and(c<>'-')and(c<>'*')and(c<>'/') then exit(false) else exit(true);
end;
function getnumber(s:string;c:char):shortint;
var i,p:shortint;
begin
   p:=0;
   for i:=1 to length(s) do
     if s[i]=c then inc(p);
   exit(p);
end;
function jiancha(s:string):shortint;
var i,j,p,z,y:integer;
    s1:string;
begin
    writeln(s);
    if length(s)=0 then exit(0);
    i:=getnumber(s,'(');
    z:=0; y:=0;
    if getnumber(s,')')<>i then exit(2);
    s1:='';
    i:=0;
    if (s[1]<>'-')and(s[1]<>'(')and(s[1]<>')')and(not((s[1]>='a')and(s[1]<='c'))) then exit(3);
    while i+1<=length(s) do
    begin
        i:=i+1;
        if (s[i]<>'(')and(s[i]<>')')and(s[i]<>'+')and(s[i]<>'-')and(s[i]<>'*')and(s[i]<>'/')and(not ((s[i]>='a')and(s[i]<='c'))) then
           exit(1);
        if ((s[i]='+')or(s[i]='-'))and(z=0) then begin {if (s1='')and(length(s)<>1) then exit(3);} if (i=length(s))and(i<>1) then exit(3); p:=jiancha(s1); s1:=''; if p<>0 then exit(p); end;
        if s[i]='(' then
            begin
                inc(z);
                if y=0 then begin
                                y:=i+1;
                                if i=length(s) then exit(3);
                                if (length(s1)=0)or(yunsuan(s1[length(s1)]))
                                then begin p:=jiancha(copy(s1,1,length(s1)-1)); s1:=''; if p<>0 then exit(p); end
                                else exit(3);
                            end;
            end;
        if s[i]=')' then
        begin
             dec(z); if z=0 then begin s1:=copy(s1,2,length(s1)); if s1='' then exit(3); p:=jiancha(s1); s1:=''; if p<>0 then exit(p);  end;
        end;
        if (s[i]<>')')or(z<>0) then s1:=s1+s[i];
        if (i>1)and((s[i-1]='+')or(s[i-1]='-')or(s[i-1]='*')or(s[i-1]='/'))and(not(((s[i]>='a')and(s[i]<='c'))or(s[i]='('))) then exit(3);
        if (i>1)and((s[i-1]>='a')and(s[i-1]<='c'))and((s[i]>='a')and(s[i]<='c'))then exit(3);
    end;
    if (s1<>'')and(s1<>s) then jiancha(s1);
    exit(0);
end;
begin
    write('Input a dai shu biao da shi:'); readln(s);
    i:=jiancha(s);
    if i=0 then writeln('OK')
    else
      writeln('Error ',i:1);
end.

三.骑士游历:

设有一个n*m的棋盘(2<=n<=50,2<=m<=50),如下图,在棋盘上任一点有一个中国象棋马,

马走的规则为:

1.马走日字 2.马只能向右走

即如下图所示:

任务1:当N,M 输入之后,找出一条从左下角到右上角的路径.

例如:输入 N=4,M=4

输出:路径的格式:(1,1)->(2,3)->(4,4)

若不存在路径,则输出"no"

任务2:当N,M 给出之后,同时给出马起始的位置和终点的位置,试找出从起点到终点的所有路径的数目.

例如:(N=10,M=10),(1,5)(起点),(3,5)(终点)

输出:2(即由(1,5)到(3,5)共有2条路径)

输入格式:n,m,x1,y1,x2,y2(分别表示n,m,起点坐标,终点坐标)

输出格式:路径数目(若不存在从起点到终点的路径,输出0)

简析：动态规划可以解决这个问题。设DP[i,j]表示(i,j)点有多少个路径。那么每个可以到达这个点的位置上的DP[x,y]的和就是DP[i,j]。

program noip2007_3;
const b:array[1..4,1..2]of integer=((-2,-1),(-1,-2),(-2,1),(-1,2));
var  m,n,k,i,j:integer;
     a:array[-1..2501,-1..2501]of integer;
     c:array[-1..2501,-1..2501]of integer;
function print(i,j:integer):boolean;
var ii:integer;
begin
   if (i=1)and(j=1) then begin write(' ->(',i,',',j,')'); exit; end;
   if c[i,j]=0 then exit(false);
   if print(i+b[c[i,j],1],j+b[c[i,j],2])=false then exit(false);
   write(' ->(',i,',',j,')');
   exit(true);
end;
begin
     fillchar(a,sizeof(a),0);
     readln(m,n);
     a[1,1]:=1;
     for j:=2 to n do
       for i:=1 to m do
         for k:=1 to 4 do
         begin
              //if (i+b[k,1]>m)or(j+b[k,2]>n)then continue;
              a[i,j]:=a[i,j]+a[i+b[k,1],j+b[k,2]];
              if a[i+b[k,1],j+b[k,2]]>0 then c[i,j]:=k;
         end;
     if print(i,j)=false then write('No answer!');
     i:=1;
end.

NOIP1997 提高组题目、题解、程序

取消回复