宁波市第29届中小学生程序设计竞赛复赛试题（初中组）解题报告
                                第一题 战马列队
题意不难理解，因为n<=1000，我们可以枚举将战马替换后，最后一匹白马在队列中的位置，这样只需统计这匹马之前（包括这匹马）棕马的数量s1，这匹马之后（不包括这匹马）白马的数量s2，将它们替换就能达到我们需要的队列，那么以这个位置作为最后一匹白马的答案就是替换的马匹数即ans=s1+s2。最终答案即为所有ans中的最小值。别忘了n<=1000，string存不下，要用ansistring。
代码如下：
var
  s:ansistring;
  i,j,n,ans,cnt:integer;
begin
  readln(n);
  readln(s);
  ans:=n;
  for i:=1 to n do begin // i即为枚举的最后一匹白马的位置
    cnt:=0;
    for j:=1 to i do
      if s[j]='B' then inc(cnt);
    for j:=i+1 to n do
      if s[j]='W' then inc(cnt);
宁波学编程哪里好    if ans>cnt then ans:=cnt;
  end;
  writeln(ans);
end.
                          第二题 马农
这道题首先需要一个常用的小技巧，我们开一个二维数组s[i,j]，表示左上角为（1,1），右下角为（i,j）的子矩形中所有数字的和，我们可以用一个递推公式快速求出s数组，即    s[i,j] = s[i-1,j]+s[i,j-1]-s[i-1,j-1]+a[i,j] ， 其中a[i,j] 表示（i,j）这个格子上的数字。
那么求出s数组有什么用呢？利用s数组，可以迅速求出左上角为（x,y)，右下角为（z,u)的子矩形中所有数字的和，公式为ans=s[z,u]-s[z,y-1]-s[x-1,u]+s[x-1,y-1]。
其实上述技巧，在前几年的宁波赛中出现过，即为小学组的题目《方格稿纸》，当然我们是初中组，自然难度要比小学组大，了解上述小技巧后，我们开始来解决这道题目。
题目要求求两个有一个公共点的子矩形，那么我们就来枚举这个公共点。枚举公共点需要的时间复杂度为O（n^2)。这是第一层枚举，那么第二层呢，难道我们知道这个公共点后，向
左（右）上角枚举矩形，同时向右（左）下角枚举矩形，并判断两个矩形是否符合题意？不行，这样就要超时了，知道公共点后，向左（右）上角枚举的时间复杂度为O（n^2), 向右（左）下角枚举的复杂度也为O(n^2)，再加上最外面一层， 有O（n^6)，只能过40%的数据了。
那么我们想一个方法来优化一下，题目只是让我们求出符合要求的矩形个数，并不用求出每一对符合要求的矩形。首先，公共点的枚举是必不可少的，那么在枚举矩形时，我们可以先向左（右）上角枚举矩形，并用一个数组记录下一些信息，什么信息呢？b[x]表示在当前公共点下，左（右）上角的矩形中，数字和为x的矩形的个数，记录下这个值后，我们再去枚举右（左）下角，对于右（左）下角的每一个矩形，算出数字和y，那么在当前公共点下，在左（右）上角，就有b[y]个矩形与此矩形符合条件，我们就可以将答案加上b[y]，至此，题目就解决了，时间复杂度为O（n^4)。
请注意，对于每一个公共点，我们先算左上角与右下角配对，再算右上角与左下角配对，而不要混在一起计算。（也就是说，先将b数组清零，然后计算左上角与右下角配对，再将b数组清零，接着计算右上角与左下角配对）。另外，由于每个格子里的数可正可负，b数组的下标要包括负数在内。
还有一点，公共点一共有n^2，对于每个公共点，左（右）上角最多有n^2个矩形，右（左）下角最多有n^2个矩形，那么合在一起，最多会有n^6对矩形符合题意，当n=50时，这个数的范围已经超出了longint，保险起见，我们还是应当用qword来保存答案。而且，两个longint相乘，结果还是longint，所以部分中间变量也得改成qword。
考虑到每次将如此大的b数组清零，容易超时，我们在清零时用到一个小技巧，每一次将b数组中，b[x]发生改变的x记录在一个数组中，不会超过n^2个，每次清零时，将数组中保存的每一个x，执行b[x]:=0，就可将整个b数组清零，这样绝对不会超时了。
以上属于细节问题，虽然不是题目要考我们的内容，但是不可忽略。
代码如下：
var
  a,s:array[0..50,0..50] of longint;
  b:array[-250000..250000] of integer;
  c:array[1..10000] of longint;              //  c数组用于记录b数组哪些下标要清零
  n,i,j,k,u,x,cnt:integer;
  ans:qword;
begin
  readln(n);
  fillchar(s,sizeof(s),0);
  for i:=1 to n do
    for j:=1 to n do begin
      read(a[i,j]);
      s[i,j]:=s[i-1,j]+s[i,j-1]-s[i-1,j-1]+a[i,j];              //计算s数组
    end;
  ans:=0;
  fillchar(b,sizeof(b),0);
  for i:=1 to n do
    for j:=1 to n do begin
      cnt:=0;
      for k:=1 to i do
        for u:=1 to j do begin
          x:=s[i,j]-s[i,u-1]-s[k-1,j]+s[k-1,u-1];
          inc(b[x]);
          inc(cnt);
          c[cnt]:=x;
        end;
      for k:=i+1 to n do
        for u:=j+1 to n do begin
          x:=s[k,u]-s[k,j]-s[i,u]+s[i,j];
          inc(ans,b[x]);
        end;
      for k:=1 to cnt do
        b[c[k]]:=0;                            //寻左上角与右下角配对
      cnt:=0;
      for k:=1 to i do
        for u:=j to n do begin
          x:=s[i,u]-s[k-1,u]-s[i,j-1]+s[k-1,j-1];
          inc(b[x]);
          inc(cnt);
          c[cnt]:=x;
        end;
      for k:=i+1 to n do
        for u:=1 to j-1 do begin
          x:=s[k,j-1]-s[k,u-1]-s[i,j-1]+s[i,u-1];
          inc(ans,b[x]);
        end;
      for k:=1 to cnt do
        b[c[k]]:=0;                        //寻右上角与左下角配对
    end;
  writeln(ans);
end.
                          第三题  马语翻译
此题为图论最短路，但是数据规模中n<= 100 000，M<=1000, k<=1000如果把每一种语言看成一个点，而两种语言能够通过一台机器直接翻译则连一条边，那么不用说最短路算法超时不超时了，我们一共需要连k*k*M条边，连存都存不下，更不用说做最短路算法了。
那么把每种语言看成点是不可行了，但是我们可以把每一台机器看成一个点，两台机器之间连边当且仅当这两台机器能够翻译的语言中有相同的，那么题目就转换成，将能够翻译语言1的机器看做起点，能够翻译语言n的机器看做终点，求起点到终点的最短路。注意，可能不止一台机器能够翻译语言1（语言n），因此起点和终点可能有多个。（最短路的算法可以用
dijkstra算法进行，为了节省时间，这里采用spfa算法。不要觉得spfa算法很高深，在本题中，此算法就类似一个宽搜。）可以忽略括号里面的话，我们就采用宽搜的方法来做最短路，效率是很高的，但与宽搜稍有区别，我们的起点有多个，具体处理时，我们用dist[x]表示点x到起点的最短距离，一开始将所有起点的dist[x]设为1，而所有非起点的dist[x]都设为一个很大的数，并将起点全都加入到一个队列里。更新时，我们从队列里依次取出每一个点，并用这个点去更新与它相邻的所有点。当用点u更新点v时，若dist[u]+1<dist[v]，则dist[v]=dist[u]+1，并将点v加入队列，继续更新其他的点。
那么我们仅剩一个问题，就是将机器连边。该怎样进行枚举连边才不会超时呢？我们可以枚举每一台机器，对于每一台机器枚举每一种语言，比如机器a能翻译语言b，我们就在语言b的后面添加机器a，这样的实现我们可以用一根链将它们连起来，具体怎么做呢？我们开一个数组head[x]表示“语言x下连接的第一台机器”的数组下标，再开数组value[y]与next[y]，value[y]中，y就是前面所说数组下标，value[y]就是这一个下标所存的机器的编号，next[y]表示这一个机器所连接的下一个机器的数组下标，当这个机器向下没有连其他机器时，next[y]就等于0。每当有机器a能翻译语言b时，我们可以采用以下方式实现“在语言b的后面添加机器a”：inc(cnt); value[cnt]:=a; next[cnt]:=head[b]; head[b]:=cnt; 其中cnt就是数组下标，我们
添加的时候是反向添加的，也就是说语言b下后添加的机器反而在前面。
如果我们要枚举语言b下所有的机器，该怎么做呢？可采用以下语句: j:=head[b]; while j<>0 do begin v:=value[j]; j:=next[j]; end; 语句中的v就是语言b下连接的机器a，我们可以将语言b下的所有机器保存下来，然后分别两两连边。至此连边工作就完成了。
那么，题目到此也就解决了。不过这个算法还是存在欠缺，因为无法保证在极端的数据下，此算法不会超时。
以上所述的算法是求最短经过几步能够从语言1翻译到语言n，那如何判断无解？那就是在求最短路时，从起点无法到达终点。
代码如下：
var
  n,k,m,x,cnt,cnt1,i,j,u,v,i1,hd,tl,ans:longint;
  g:array[1..1000,1..1000] of integer;
  head:array[1..100000] of longint;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。