2015NOIP模拟赛(二) 试题及解析

时间:2022-06-01 18:42:29

题目名称

输入文件

输入输出

时间限制

空间限制

路灯改建计划

light.in

Light.out

1S

128M

数独

shudu.in

shudu.out

10S

128 M

Aim Netbar

netbar.in

netbar.out

1S

128M

 

路灯改建计划(light.pas/c/cpp)

【问题描述】

在康杰中学的道路上,新建了若干漂亮的路灯,这给同学们晚上的出行带来很大的方便。但是,问题随之出现了。

一天晚上,我们信息学竞赛班的Z同学正往校门外走,忽然眼前一片漆黑,于是直接把眼镜都摔掉了,再也找不到。后来Z同学从学校管理处了解到昨晚路灯突然熄灭是因为电路不堪重负,导致空气开关跳闸。

善于思考的Z 同学考虑将路灯进行改建,以避免再次出现类似的问题。Z同学仔细了解每盏路灯的耗电量a[i]与照明度z[i],已知共有N盏电灯,并且每盏电灯都可能有不同的耗电量与照明度,现在的问题是要把这N盏电灯分为M组,新分出的每组灯的耗电量(即是该组所有打开电灯的耗电量之和)不能超过该组的电灯数目的T倍,在满足这样的前提下使得照明度尽可能的大,最后算出M组的最大照明度的和。由于每组耗电量的限制,该组中的某些电灯可能不被使用,但是仍然应该算作该组灯的数目。

特别注意的是电灯按顺序给出,只能把相邻的几盏灯分在一组。由于计算较为复杂,Z同学经过反复的计算仍然不能确定结果,现在就请你为他编写一个程序来解决这个问题。

【输入文件】

文件*有N+1行,第一行三个整数分别为NMT

接下来的N 行每行两个整数,分别为a[i]z[i],所有数据之间以一个空格分开。

【输出文件】

文件仅包含一个数,即输出M组的最大照明度的和。

【输入样例1

2 1 2

2 1

3 2

【输出样例1

2

【输入样例2

5 2 2

1 1

2 2

3 3

4 4

5 5

【输出样例2

10

【数据规模】

对于70%的数据,保证有2<=N<=801<=M<=351<=Ta[i]z[i]<=35

对于全部的数据,保证有2<=N<=1601<=M<=501<=Ta[i]z[i]<=50

数独(shudu.pas/c/cpp)

襄樊开展了数独大赛,明明和红红参加了比赛,比赛分数与时间有关。明明和红红想在别人前面做出来一得到更高的分数。他们想到了作弊,利用掌上电脑解决问题。由于题目较难,请你用计算机帮忙做个程序,解决这个问题。由于输入需要时间,掌上电脑不是很快。

你的程序需要在一秒内解决上百个这样的问题。

数独游戏规则

数独游戏在9x9的方格内进行,分为3x3的小方格,被称为

 

 

 

 

数独游戏首先从已经填入数字的格子开始:

- 数独游戏的目的是根据下列规则,用19之间的数字填满空格,一个格子只能填入一个数字: 
     1.
每个数字在每一行只能出现一次
     2. 每个数字在每一列只能出现一次
     3. 每个数字在每一区只能出现一次
- 总结这些规则,即每个数字在每一行、每一列和每一区只能出现一次。

格式

【输入格式】

数独的个数n(n<=300)
下面n行,每行81个数(ai),当ai=0是未知数,否则为数独里面的已知数。

注意,每2个数之间没有空格。

【输出格式】

输出有n行,每行有81个数为最终的结果。

【样例1

【样例输入1

1005000600080701040700060003090205060008040900060109080500090002040308010006000700

【样例输出1

415923678683751249729864153194285367358647921267139485571496832942378516836512794

【限制】

根据数据的困难程度定时间最多10s最少1s

【提示】

【样例的输入转为表】:
005000600

080701040
700060003
090205060
008040900
060109080
500090002
040308010
006000700
输出转为表:
415923678
683751249
729864153
194285367
358647921
267139485
571496832
942378516
836512794

 

Aim Netbar(netbar.pas/c/cpp)

【问题背景】

M同学都热衷于大型3D网游,可学校的机子配置相当差,根本不能玩大型3D网游,那就只有去网吧。星期一到星期五都是晚上1000才下晚自习,几乎没时间玩。

然而星期六下午放假是绝好的时间,但是学校人多啊,一放学去网吧的人就开始狂奔,竞争之激烈,抢到机子的难度非常之大。往往在我们到达网吧之前都坐满了。

学校到网吧的路是错综复杂的,以致于到一个自己想去的网吧都有非常多的路线可以选择,而路线的长度又不相同,这样就决定了要花费的时间,因此想要尽快到达,选择一条最佳的线路是很有必要的。

【问题描述】

为了简化问题,我们把学校与周边的网吧看做图中的顶点,学校与网吧,网吧与网吧之间的路线看做边,每个边都有一个权,表示我们走完这条路的时间,由于放学人流量大,如果反向走会有危险,因此这是一个有向图。

学校在S点,想要去的网吧在T点。你的任务就是选择一条最佳路线,使得从学校到目的地网吧的时间最短,你只需要输出最短到达时间即可。

【输入文件】

netbar.in *有M+2行数据

第一行两个整数NM,表示点数和边数。

然后M行每行3个正整数(uvt),表示有一条可由uv耗时为t的边。

最后一行两个正整数ST

【输出文件】

netbar.out 中,只有一行,一个整数表示最短时间。如果ST之间不存在通路则输

出“No Solution!(双引号不输出,“!”为西文标点)

【输入样例】

4 4

1 2 3

2 4 10

1 3 5

3 4 5

1 4

【输出样例】

10

【数据规模】

对于30%的数据保证有1<N<=10001<=M<=1000

对于全部的数据保证有1<N<=100001<=M<=100000

解析:

 

路灯改建计划(light.pas/c/cpp)

Vijos  1488

【问题描述】

在康杰中学的道路上,新建了若干漂亮的路灯,这给同学们晚上的出行带来很大的方便。但是,问题随之出现了。

一天晚上,我们信息学竞赛班的Z同学正往校门外走,忽然眼前一片漆黑,于是直接把眼镜都摔掉了,再也找不到。后来Z同学从学校管理处了解到昨晚路灯突然熄灭是因为电路不堪重负,导致空气开关跳闸。

善于思考的Z 同学考虑将路灯进行改建,以避免再次出现类似的问题。Z同学仔细了解每盏路灯的耗电量a[i]与照明度z[i],已知共有N盏电灯,并且每盏电灯都可能有不同的耗电量与照明度,现在的问题是要把这N盏电灯分为M组,新分出的每组灯的耗电量(即是该组所有打开电灯的耗电量之和)不能超过该组的电灯数目的T倍,在满足这样的前提下使得照明度尽可能的大,最后算出M组的最大照明度的和。由于每组耗电量的限制,该组中的某些电灯可能不被使用,但是仍然应该算作该组灯的数目。

特别注意的是电灯按顺序给出,只能把相邻的几盏灯分在一组。由于计算较为复杂,Z同学经过反复的计算仍然不能确定结果,现在就请你为他编写一个程序来解决这个问题。

【输入文件】

文件*有N+1行,第一行三个整数分别为NMT

接下来的N 行每行两个整数,分别为a[i]z[i],所有数据之间以一个空格分开。

【输出文件】

文件仅包含一个数,即输出M组的最大照明度的和。

【输入样例1

2 1 2

2 1

3 2

【输出样例1

2

【输入样例2

5 2 2

1 1

2 2

3 3

4 4

5 5

【输出样例2

10

【数据规模】

对于70%的数据,保证有2<=N<=801<=M<=351<=Ta[i]z[i]<=35

对于全部的数据,保证有2<=N<=1601<=M<=501<=Ta[i]z[i]<=50

 

算法动归+01背包

U[I,j]表示从第I个灯到第j个灯的最大照明度;(用01背包求)

 g[i,j]表示前j个路灯分i份;(用DP求)

方程

 g[i,j]:=max(g[i,j],g[i-1,k]+u[k+1,j]);

{j个分i组可以是前k个分i-1组,后面的分一组}

 

program light;

var o:array[0..10000] of longint;

    a,z:array[0..165] of longint;

    u:array[0..165,0..165] of longint;

    g:array[0..55,0..165] of longint;

    n,m,q,i:longint;

function max(x,y:longint):longint;

begin if x>y then exit(x)else exit(y);end;

procedure main;

var

  i,j,k,mmm:longint;

begin

  for i:=1 to n do

    begin

     fillchar(o,sizeof(o),0);

      for j:=i to n do

      begin

       mmm:=(n-i+1)*q;

       for k:=mmm downto a[j] do

        if o[k-a[j]]+z[j]>o[k] then o[k]:=o[k-a[j]]+z[j];  {一个建造u[i,j]01背包}

      u[i,j]:=o[(j-i+1)*q];

      end;

    end;

 

for i:=1 to m do

 for j:=i to n do

  for k:=i-1 to j-1 do  {注意是i-1j-1,保证后面KJ中是连续没有分开}

 g[i,j]:=max(g[i,j],g[i-1,k]+u[k+1,j]);

 writeln(g[m,n]);

end;

begin

readln(n,m,q);

for i:=1 to n do readln(a[i],z[i]);

main;

end.

数独(shudu.pas/c/cpp)

Vijos 1345

襄樊开展了数独大赛,明明和红红参加了比赛,比赛分数与时间有关。明明和红红想在别人前面做出来一得到更高的分数。他们想到了作弊,利用掌上电脑解决问题。由于题目较难,请你用计算机帮忙做个程序,解决这个问题。由于输入需要时间,掌上电脑不是很快。

你的程序需要在一秒内解决上百个这样的问题。

数独游戏规则

数独游戏在9x9的方格内进行,分为3x3的小方格,被称为

 

 

 

 

数独游戏首先从已经填入数字的格子开始:

- 数独游戏的目的是根据下列规则,用19之间的数字填满空格,一个格子只能填入一个数字: 
     1.
每个数字在每一行只能出现一次
     2. 每个数字在每一列只能出现一次
     3. 每个数字在每一区只能出现一次
- 总结这些规则,即每个数字在每一行、每一列和每一区只能出现一次。

格式

【输入格式】

数独的个数n(n<=300)
下面n行,每行81个数(ai),当ai=0是未知数,否则为数独里面的已知数。

注意,每2个数之间没有空格。

【输出格式】

输出有n行,每行有81个数为最终的结果。

【样例1

【样例输入1

1

005000600080701040700060003090205060008040900060109080500090002040308010006000700

【样例输出1

415923678683751249729864153194285367358647921267139485571496832942378516836512794

【限制】

根据数据的困难程度定时间最多10s最少1s

【提示】

【样例的输入转为表】:
005000600

080701040
700060003
090205060
008040900
060109080
500090002
040308010
006000700
输出转为表:
415923678
683751249
729864153
194285367
358647921
267139485
571496832
942378516
836512794

源代码:

program p02;

type

 w=record

  x,y,d:integer;

 end;

var

 g,l,h:array[1..9,1..9] of boolean;{分别为区,列,行}

 p:array[1..81] of w;{记录状态}

 n,k,m,i,j:integer;

 s:array[1..9,1..9] of char;

 ok:boolean;

 r:char;

procedure print;

var

 ii,jj:integer;

begin

 for ii:=1 to 9 do

  for jj:=1 to 9 do

   write(s[ii,jj]);

 writeln;

end;

function get(i,j:integer):integer;{取得格子号}

begin

 if i<=3 then begin case j of

                     1..3 :exit(1); 4..6: exit(2); 7..9: exit(3); end; end

          else

           if i<=6 then begin case j of

                     1..3 :exit(4); 4..6: exit(5); 7..9: exit(6); end; end

                      else begin case j of

                     1..3 :exit(7); 4..6: exit(8); 7..9: exit(9); end; end;

end;

procedure dfs(v:integer);{深搜}

var

 t:integer;

begin

 if ok=true then exit;

 if v>m then begin print; ok:=true; exit; end;

 for t:=1 to 9 do

  if h[p[v].x,t]=false then

   if l[p[v].y,t]=false then

    if g[p[v].d,t]=false then

     begin

      r:=chr(ord(t)+48);

      s[p[v].x,p[v].y]:=r;

      h[p[v].x,t]:=true;

      l[p[v].y,t]:=true;

      g[p[v].d,t]:=true;

      dfs(v+1);

      s[p[v].x,p[v].y]:='0';

      h[p[v].x,t]:=false;

      l[p[v].y,t]:=false;

      g[p[v].d,t]:=false;

     end;

end;

procedure init;{读入}

begin

 m:=0; ok:=false;

 fillchar(s,sizeof(s),'0');

 fillchar(g,sizeof(g),false);

 fillchar(h,sizeof(h),false);

 fillchar(l,sizeof(l),false);

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

 for i:=1 to 9 do

  for j:=1 to 9 do

   begin

    read(s[i,j]);

    case s[i,j] of

    '1'..'9': begin

               h[i,ord(s[i,j])-48]:=true; l[j,ord(s[i,j])-48]:=true;

               g[get(i,j),ord(s[i,j])-48]:=true;

              end;

    '0': begin inc(m); p[m].x:=i; p[m].y:=j; p[m].d:=get(i,j); end;

    end;

  end;  readln;

end;

begin

 assign(input,'shudu.in'); reset(input);

 assign(output,'shudu.out'); rewrite(output);

 readln(n);

 for k:=1 to n do

  begin

   init;

   if m=0 then begin print; continue; end;{根据数据,其实可以再稍微优化一下,就是把每组的解都记录一下,如果出现重复的数据,直接输出即可,事实证明它是可以过的}

   dfs(1);

  end;

 close(input); close(output);

end.

第三题解析:

解题思路:

题目可以抽象为输入n个顶点,e条边的有向图,再读入源点S和目标点T,求ST的最短路。输入规模:1<N<=100001<=M<=100000

 最短路有三种方法:floyd,dijsktra,spfa。如果用floyd,时间性能为O(n3) , 只能通过1000以内的数据;用dijkstra,时间性能为O(n2),只能通过10000以内的数据,且用邻接矩阵存储时,10000*10000*4个字节,总内存达到380MB,会超内存。用spfa算法,时间性能为O(kM),能通过所有测试数据,k的值平均为2,表示顶点入队的平均次数。此时,可以采用数组模拟链表的存边方法,开一个边的一维数组,把所有边存储起来。如对于如下输入数据:

5 7

1 2 2

1 5 8

1 3 1

1 4 3

2 5 3

3 5 1

4 3 2

1 5

下面这个图的数组模拟链表的形式存储边,把从某个顶点出来的所有边通过链表的形式,链接起来,就象存储普通有序树一样,右儿子挂到左儿子下面。这里的操作原理是,处理某个顶点出来的边时,下一条边挂到前一条边,如下图,第一条边指向0,后面的边都指向前一条边,所以,在处理某个顶点相连的边的松驰操作时,可以很方便的处理以该顶点连出去的边,当指向0时,则以该顶点出去的松驰操作完成。

 

program netbar;

  var

    list,dis:array [0..10000] of longint; //list存储当前边的指针,dis存储各点到源点的最短路

    next,toit,cost,q:array [0..100000] of longint;//next存储当前边指向前一条边的位置,toit表示当前边的出点,cost表示当前边的边权

    n,m,i,a,b,c,s,e,tot:longint;

    flag:array [0..10000] of boolean;

  procedure add(a,b,c:longint);//数组模拟链表的添边的方法

    begin

      inc(tot); //边的数目

toit[tot]:=b; //当前边的出点顶点标号

cost[tot]:=c; //当前边的权值

next[tot]:=list[a]; //当前边指向前一条边的位置,如果当前边是顶点a的读入的第一条边,则它指向前面第0条边,表示next[tot]:=0

list[a]:=tot; //从入点a引出的边的编号存储给lsit[a]

    end;

  procedure SPFA;

    var

      i,head,tail,v,k:longint;

    begin

      fillchar(flag,sizeof(flag),true);

      for i:=1 to n do dis[i]:=maxlongint;

      head:=1; tail:=1; q[1]:=s; dis[s]:=0; flag[s]:=false;//源点s入队

      repeat

        v:=q[head]; k:=list[v]; //队列头出队,k存储当前v顶点的边的编号

        while k<>0 do //处理v的所有边,直至边指向0,即第一条边也处理了

          begin

            if dis[v]+cost[k]<dis[toit[k]] then  //松驰操作

              begin

                dis[toit[k]]:=dis[v]+cost[k]; //松驰成功

                if flag[toit[k]] then  //入队

                  begin

                    inc(tail); q[tail]:=toit[k]; flag[toit[k]]:=false;

                  end;

              end;

            k:=next[k]; //处理顶点v的前一条边

          end;

        flag[v]:=true;

        inc(head);

      until head>tail;

    end;

  begin

    assign(input,'netbar.in'); reset(input);

    assign(output,'netbar.out'); rewrite(output);

    fillchar(list,sizeof(list),0);

    fillchar(next,sizeof(next),0);

    fillchar(toit,sizeof(toit),0);

    fillchar(cost,sizeof(cost),0);

    tot:=0;

    readln(n,m);

    for i:=1 to m do

      begin readln(a,b,c); add(a,b,c); end;

    readln(s,e);

    SPFA;

    if dis[e]<maxlongint then writeln(dis[e])

                         else writeln('No Solution!');

    close(input); close(output);

  end.

 

N的顶点规模达到10000时,如果用邻接矩阵存储图,容易超内存,且1个亿的运算次数在1S的时限内不一定出得来。