NOIP普及组题解

T1

题目描述

牛牛最近学习了C++入门课程，这门课程的总成绩计算方法是：

总成绩=作业成绩×20%+小测成绩×30%+期末考试成绩×50%

牛牛想知道，这门课程自己最终能得到多少分。

输入输出格式

输入格式：
输入文件只有1行，包含三个非负整数A、B、C，分别表示牛牛的作业成绩、小测成绩和期末考试成绩。相邻两个数之间用一个空格隔开，三项成绩满分都是100分。

输出格式：
输出文件只有1行，包含一个整数，即牛牛这门课程的总成绩，满分也是100分。

思路：

这么水的题，还用讲吗。。。

因为a b c满足 mod 10=0
所以输出 (a * 2+b * 3+c * 5) div 10 就可以AC啦！！！

代码：

var x,y,z:longint;
begin
  assign(input,'score.in');
  assign(output,'score.out');
  reset(input);
  rewrite(output);
  read(x,y,z);
  write((x*2+y*3+z*5) div 10);
  close(input);
  close(output);
end.

T2

题目描述

图书馆中每本书都有一个图书编码，可以用于快速检索图书，这个图书编码是一个 正整数。 每位借书的读者手中有一个需求码，这个需求码也是一个正整数。如果一本书的图 书编码恰好以读者的需求码结尾，那么这本书就是这位读者所需要的。 小 D 刚刚当上图书馆的管理员，她知道图书馆里所有书的图书编码，她请你帮她写 一个程序，对于每一位读者，求出他所需要的书中图书编码最小的那本书，如果没有他 需要的书，请输出-1。

输入输出格式

输入格式：
输入文件的第一行，包含两个正整数 n 和 q，以一个空格分开，分别代表图书馆里 书的数量和读者的数量。

接下来的 n 行，每行包含一个正整数，代表图书馆里某本书的图书编码。

接下来的 q 行，每行包含两个正整数，以一个空格分开，第一个正整数代表图书馆 里读者的需求码的长度，第二个正整数代表读者的需求码。

思路

也很水

O(n,m)暴力直接过。
代码并不优，可自己写一个。

代码：

var a,b:array[-11..1111] of longint;
    //b:array[-11..1111] of longint;
    n,m,i,j,k,t,s:longint;
    f:boolean;
procedure qsort(l,r:longint);
var i,j,mid:longint;
begin
  i:=l; j:=r; mid:=a[(i+j) div 2];
  repeat
    while a[i]<mid do inc(i);
    while a[j]>mid do dec(j);
    if i<=j then
    begin
      a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0];
      b[0]:=b[i]; b[i]:=b[j]; b[j]:=b[0];
      inc(i); dec(j);
    end;
  until i>j;
  if j>l then qsort(l,j);
  if i<r then qsort(i,r);
end;
begin
  assign(input,'librarian.in');
  assign(output,'librarian.out');
  reset(input);
  rewrite(output);
  read(n,m);
  for i:=1 to n do
  begin
    read(a[i]); s:=a[i];
    while s>0 do
    begin
      inc(b[i]);
      s:=s div 10;
    end;
  end;
  qsort(1,n);
  for i:=1 to m do
  begin
    read(s);
    read(s);
    for j:=1 to n do
    begin
      t:=1; f:=false;
      for k:=1 to b[j] do
      begin
        t:=t*10;
        if s=a[j] mod t then
        begin
          f:=true; break;
        end;
      end;
      if f then
      begin
        writeln(a[j]); break;
      end;
    end;
    if not f then writeln(-1);
  end;
  close(input);
  close(output);
end.

T3

题目描述

有一个m × m的棋盘，棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。

任何一个时刻，你所站在的位置必须是有颜色的（不能是无色的）， 你只能向上、 下、左、 右四个方向前进。当你从一个格子走向另一个格子时，如果两个格子的颜色相同，那你不需要花费金币；如果不同，则你需要花费 1 个金币。

另外， 你可以花费 2 个金币施展魔法让下一个无色格子暂时变为你指定的颜色。但这个魔法不能连续使用， 而且这个魔法的持续时间很短，也就是说，如果你使用了这个魔法，走到了这个暂时有颜色的格子上，你就不能继续使用魔法； 只有当你离开这个位置，走到一个本来就有颜色的格子上的时候，你才能继续使用这个魔法，而当你离开了这个位置（施展魔法使得变为有颜色的格子）时，这个格子恢复为无色。

现在你要从棋盘的最左上角，走到棋盘的最右下角，求花费的最少金币是多少？

输入输出格式

输入格式：
数据的第一行包含两个正整数 m， n，以一个空格分开，分别代表棋盘的大小，棋盘上有颜色的格子的数量。

接下来的 n 行，每行三个正整数 x， y， c， 分别表示坐标为（ x， y）的格子有颜色 c。

其中 c=1 代表黄色， c=0 代表红色。 相邻两个数之间用一个空格隔开。 棋盘左上角的坐标为（ 1, 1），右下角的坐标为（ m, m）。

棋盘上其余的格子都是无色。保证棋盘的左上角，也就是（ 1， 1） 一定是有颜色的。

输出格式：
输出一行，一个整数，表示花费的金币的最小值，如果无法到达，输出-1。

思路：

有点难度，我才95。

我用的是dp。
先定义一个数组，储存颜色（注意染色之后不要变回来），分几种情况讨论。

特别注意白色，要讨论染成哪种颜色。

代码：

var a,f:array[-11..1111,-11..1111] of longint;
    b:array[-11..1111,-11..1111] of boolean;
    n,m,i,j,t1,t2,x,y,z:longint;
function min(x,y:longint):longint;
begin
  if x>y then exit(y) else exit(x);
end;
begin
  assign(input,'chess.in');
  assign(output,'chess.out');
  reset(input);
  rewrite(output);

  read(n,m);
  for i:=1 to n do for j:=1 to n do a[i,j]:=-1;
  fillchar(b,sizeof(b),false);
  for i:=1 to m do
  begin
    read(x,y,z);
    a[x,y]:=z; b[x,y]:=true;
  end;
  fillchar(f,sizeof(f),$7f div 3);
  f[1,1]:=0;
  for i:=1 to n do for j:=1 to n do if (i<>1)or(j<>1) then
  begin
    t1:=maxlongint div 3; t2:=t1;
    case a[i,j] of
      -1:
      begin
        if b[i-1,j] then t1:=f[i-1,j]+2;
        if b[i,j-1] then t2:=f[i,j-1]+2;
        if t1<t2 then
        begin
          a[i,j]:=a[i-1,j];
          f[i,j]:=t1;
        end else
        if t1>t2 then
        begin
          a[i,j]:=a[i,j-1];
          f[i,j]:=t2;
        end else
        if t1=t2 then
        begin
          if a[i-1,j]<>a[i,j-1] then a[i,j]:=2 else
          a[i,j]:=a[i-1,j];
          f[i,j]:=t1;
        end;
      end;
      0,1:
      begin
        if (a[i-1,j]<>2)and(a[i-1,j]<>a[i,j]) then
          t1:=f[i-1,j]+1 else t1:=f[i-1,j];
        if (a[i,j-1]<>2)and(a[i,j-1]<>a[i,j]) then
          t2:=f[i,j-1]+1 else t2:=f[i,j-1];
        f[i,j]:=min(t1,t2);
      end;
    end;
  end;
  if f[n,n]>=n*n*2 then write(-1) else write(f[n,n]);

  close(input); close(output);
end.

T4

题目描述

跳房子，也叫跳飞机，是一种世界性的儿童游戏，也是中国民间传统的体育游戏之一。

跳房子的游戏规则如下：

在地面上确定一个起点，然后在起点右侧画 n 个格子，这些格子都在同一条直线上。每个格子内有一个数字（ 整数），表示到达这个格子能得到的分数。玩家第一次从起点开始向右跳， 跳到起点右侧的一个格子内。第二次再从当前位置继续向右跳，依此类推。规则规定：

玩家每次都必须跳到当前位置右侧的一个格子内。玩家可以在任意时刻结束游戏，获得的分数为曾经到达过的格子中的数字之和。

现在小 R 研发了一款弹跳机器人来参加这个游戏。但是这个机器人有一个非常严重的缺陷，它每次向右弹跳的距离只能为固定的 d。小 R 希望改进他的机器人，如果他花 g 个金币改进他的机器人，那么他的机器人灵活性就能增加 g， 但是需要注意的是，每次弹跳的距离至少为 1。 具体而言， 当g < d时， 他的机器人每次可以选择向右弹跳的距离为 d-g, d-g+1,d-g+2， …， d+g-2， d+g-1， d+g； 否则（ 当g ≥ d时），他的机器人每次可以选择向右弹跳的距离为 1， 2， 3， …， d+g-2， d+g-1， d+g。

现在小 R 希望获得至少 k 分，请问他至少要花多少金币来改造他的机器人。

输入输出格式

输入格式：
第一行三个正整数 n， d， k， 分别表示格子的数目， 改进前机器人弹跳的固定距离， 以及希望至少获得的分数。 相邻两个数之间用一个空格隔开。

接下来 n 行，每行两个正整数x_i, s_i，分别表示起点到第i个格子的距离以及第i个格子的分数。 两个数之间用一个空格隔开。 保证x_i按递增顺序输入。

输出格式：
共一行，一个整数，表示至少要花多少金币来改造他的机器人。若无论如何他都无法获得至少 k 分，输出-1。

思路：

才40分

代码：

type rec=record
        x:longint;
        y:longint;
     end;
var n,d,k,i,s,ans:longint;
    a:array[-11..500111] of rec;
    f:array[-11..500111] of longint;
function max(x,y:longint):longint;
begin
  if x>y then exit(x) else exit(y);
end;
function min(x,y:longint):longint;
begin
  if x>y then exit(y) else exit(x);
end;
function find(l,r:longint):longint;
var i,t,mid:longint;
begin
  if l>=r then exit(r);
  ans:=0;
  mid:=(l+r) div 2; fillchar(f,sizeof(f),0); f[0]:=0;
  for i:=1 to n do
  begin
    for t:=i-1 downto 0 do
    if (a[i].y-a[t].y<=d+mid)and(a[i].y-a[t].y>=d-mid) then
      if (f[t]>0)or(t=0) then f[i]:=max(f[i],f[t]+a[i].x);
    ans:=max(f[i],ans);
  end;
  if ans>=k then exit(find(l,mid));
  if ans<k then exit(find(mid+1,r));
end;
procedure quit;
begin
  close(input);
  close(output);
  halt;
end;
begin
  assign(input,'jump.in');
  assign(output,'jump.out');
  reset(input);
  rewrite(output);
  read(n,d,k);
  for i:=1 to n do
  begin
    read(a[i].y,a[i].x);
    if a[i].x>0 then s:=s+a[i].x;
  end;
  ans:=maxlongint;
  if s<k then
  begin
    write(-1); quit;
  end;
  if (n>=5000) then
  begin
    for i:=d-1 downto 1 do
      if a[i].x>0 then
      begin
        s:=a[d].y-a[i].y; break;
      end;
    for i:=d+1 to n do
      if a[i].x>0 then
      begin
        s:=min(s,a[i].y-a[d].y);
      end;
    write(s); quit;
  end;
  write(find(0,max(d-1,n-d)));
  //if n=1 then write(0) else write(ans);
  quit;
end.