欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

NOIP普及组题解

程序员文章站 2024-03-18 21:20:10
...

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.
相关标签: 2017noip 普及组

上一篇: 问题 F: 成绩统计

下一篇: