首页 › 题库 › Scratch编程考级 › Scratch编程一级

Scratch编程一级 题库

共 1277 道题 ,第 59 / 64 页 · 按题型筛选,点「查看答案」核对解析
1161 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

小白鼠再排队2

N只小白鼠(1 < N < 100),每只鼠头上戴着一顶有颜色的帽子。现在称出每只白鼠的重量,要求按照白鼠重量从小到大的顺序输出它们头上帽子的颜色。帽子的颜色用 “red”,“blue”等字符串来表示。不同的小白鼠可以戴相同颜色的帽子。白鼠的重量用整数表示。

时间限制:1000

内存限制:65536

输入

输入第一行为一个整数N,表示小白鼠的数目。 下面有N行,每行是一只白鼠的信息。第一个为正整数,表示白鼠的重量,不超过整型范围;第二个为字符串,表示白鼠的帽子颜色,字符串长度不超过10个字符。 注意:白鼠的重量各不相同。

输出

按照白鼠的重量从小到大的顺序输出白鼠的帽子颜色。

样例输入

3
30 red
50 blue
40 green

样例输出

red
green
blue
答案与解析
参考答案
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <vector>

using namespace std;
struct sb {
  int z;
  char s[15];
} a[105];
bool cmp(sb a, sb b) { return a.z < b.z; }
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].z >> a[i].s;
  }
  sort(a + 1, a + 1 + n, cmp);
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < strlen(a[i].s); j++) {
      cout << a[i].s[j];
    }
    cout << endl;
  }
  return 0;
}
题目详情
1162 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 3.3 背景与角色区别

队列和栈

队列和栈是两种重要的数据结构,它们具有push k和pop操作。push k是将数字k加入到队列或栈中,pop则是从队列和栈取一个数出来。队列和栈的区别在于取数的位置是不同的。

队列是先进先出的:把队列看成横向的一个通道,则push k是将k放到队列的最右边,而pop则是从队列的最左边取出一个数。

栈是后进先出的:把栈也看成横向的一个通道,则push k是将k放到栈的最右边,而pop也是从栈的最右边取出一个数。

假设队列和栈当前从左至右都含有1和2两个数,则执行push 5和pop操作示例图如下:

          push 5          pop

队列 1 2  ------->  1 2 5 ------>  2 5

          push 5          pop

栈   1 2  ------->  1 2 5 ------>  1 2

现在,假设队列和栈都是空的。给定一系列push k和pop操作之后,输出队列和栈中存的数字。若队列或栈已经空了,仍然接收到pop操作,则输出error。

时间限制:1000

内存限制:65536

输入

第一行为m,表示有m组测试输入,m<100。 每组第一行为n,表示下列有n行push k或pop操作。(n<150) 接下来n行,每行是push k或者pop,其中k是一个整数。 (输入保证同时在队列或栈中的数不会超过100个)

输出

对每组测试数据输出两行,正常情况下,第一行是队列中从左到右存的数字,第二行是栈中从左到右存的数字。若操作过程中队列或栈已空仍然收到pop,则输出error。输出应该共2*m行。

样例输入

2
4
push 1
push 3
pop
push 5
1
pop

样例输出

3 5
1 5
error
error
答案与解析
参考答案
#include <stdio.h>
#include <string.h>
#define N 150
int stack[N], ps;
int queue[N], qh, qt;
char cmd[5];
int main(void) {
  int m, n, sflag, qflag, a, i;
  scanf("%d", &m);
  while (m--) {
    scanf("%d", &n);
    sflag = qflag = 0;
    ps = 0, qh = 0;
    qt = 0;
    while (n--) {
      scanf("%s", cmd);
      if (cmd[1] == 'u') {
        scanf("%d", &a);
        stack[ps++] = a;
        queue[qt++] = a;
      } else if (cmd[1] == 'o') {
        if (ps == 0)
          sflag = 1;
        if (qt - qh == 0)
          qflag = 1;
        ps--;
        qh++;
      }
    }
    if (qflag)
      printf("error\n");
    else {
      for (i = qh; i < qt; i++)
        printf("%d ", queue[i]);
      printf("\n");
    }
    if (sflag)
      printf("error\n");
    else {
      for (i = 0; i < ps; i++)
        printf("%d ", stack[i]);
      printf("\n");
    }
  }
  return 0;
}
题目详情
1163 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 7.1 逻辑推理

出栈序列统计

栈是常用的一种数据结构,有n个元素在栈顶端一侧等待进栈,栈顶端另一侧是出栈序列。你已经知道栈的操作有两种:push和pop,前者是将一个元素进栈,后者是将栈顶元素弹出。现在要使用这两种操作,由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n,计算并输出由操作数序列1,2,…,n,经过一系列操作可能得到的输出序列总数。

时间限制:1000

内存限制:65536

输入

就一个数n(1≤n≤15)。

输出

一个数,即可能输出序列的总数目。

样例输入

3

样例输出

5

提示

先了解栈的两种基本操作,进栈push就是将元素放入栈顶,栈顶指针上移一位,等待进栈队列也上移一位,出栈pop是将栈顶元素弹出,同时栈顶指针下移一位。    用一个过程采模拟进出栈的过程,可以通过循环加递归来实现回溯:重复这样的过程,如果可以进栈则进一个元素,如果可以出栈则出一个元素。就这样一个一个地试探下去,当出栈元素个数达到n时就计数一次(这也是递归调用结束的条件)。

答案与解析
参考答案
#include <cstdio>
#include <iostream>

using namespace std;
int n, ans;
void dfs(int in, int out) {
  if (out == 0)
    ans++;
  else if (in == 0) {
    dfs(in + 1, out - 1); // 进栈
  } else {
    dfs(in + 1, out - 1); // 进栈
    dfs(in - 1, out);     // 出栈
  }
}
int main() {
  while (scanf("%d", &n) != EOF) {
    ans = 0;
    dfs(0, n);
    printf("%d\n", ans);
  }
  return 0;
}
题目详情
1164 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.4 新建保存与语言选择

词典

你旅游到了一个国外的城市。那里的人们说的外国语言你不能理解。不过幸运的是,你有一本词典可以帮助你。

时间限制:3000

内存限制:65536

输入

首先输入一个词典,词典中包含不超过100000个词条,每个词条占据一行。每一个词条包括一个英文单词和一个外语单词,两个单词之间用一个空格隔开。而且在词典中不会有某个外语单词出现超过两次。词典之后是一个空行,然后给出一个由外语单词组成的文档,文档不超过100000行,而且每行只包括一个外语单词。输入中出现单词只包括小写字母,而且长度不会超过10。

输出

在输出中,你需要把输入文档翻译成英文,每行输出一个英文单词。如果某个外语单词不在词典中,就把这个单词翻译成“eh”。

样例输入

dog ogday
cat atcay
pig igpay
froot ootfray
loops oopslay

atcay
ittenkay
oopslay

样例输出

cat
eh
loops

提示

输入比较大,推荐使用C语言的I / O函数。

答案与解析
参考答案
#include <algorithm>
#include <stdio.h>
#include <string.h>

#define MAXSTR 11
#define MAXWORD 100010
using namespace std;
typedef struct {
  char foreign[MAXSTR];
  char english[MAXSTR];
} m_word;
m_word m_dic[MAXWORD];
int compare(const void *elem1, const void *elem2) {
  return strcmp(((m_word *)elem1)->foreign, ((m_word *)elem2)->foreign);
}
int main() {
  int count = 0;

  char chs[30];
  while (fgets(chs, 29, stdin), chs[0] != '\n') {
    sscanf(chs, "%s%s", m_dic[count].english, m_dic[count].foreign);
    count++;
  }
  qsort(m_dic, count, sizeof(m_word), compare);
  m_word tmp;
  m_word *ans;
  while (scanf("%s", tmp.foreign) != EOF) {
    ans = (m_word *)bsearch(&tmp, m_dic, count, sizeof(m_word), compare);
    if (ans != NULL)
      printf("%s\n", ans->english);
    else
      printf("eh\n");
  }
  return 0;
}
题目详情
1165 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 4.1 移动

逃离迷宫

你在一个地下迷宫中找到了宝藏,但是也触发了迷宫机关,导致迷宫将在T分钟后坍塌,为此你需要在T分钟内逃离迷宫,你想知道你能不能逃离迷宫。迷宫是一个边长为m的正方形,其中"S"表示你所在的位置,"E"表示迷宫出口,"."是可以随意走动的区域,"#"是不可穿行的墙壁,每次你可以耗费1分钟在区域间移动(上下左右四个方向)。

时间限制:1000

内存限制:65536

输入

输入包含多组数组,第一行是一个整数K(1 <= K <= 10),表示有K组数据。接下来每组数组包含整数m(2<=m<=10)和整数T,m表示正方形迷宫的边长,T表示坍塌时间。其后是一个m*m的字符矩阵,包含字符"S", "E", "."和"#"。

输出

每组数据输出一行,输出“YES"或者"NO",表示是否可以在坍塌之前逃离(也就是说移动次数是否可以不超过T)。

样例输入

2
4 7 
S...
###.
.#E.
..#.
3 4
S..
..#
.#E

样例输出

YES
NO
答案与解析
参考答案
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX_M 12
 
struct node {
    int x, y;
    int tcnt;
};
 
int m, t;
char mat[MAX_M][MAX_M];
 
int bfs(int x0, int y0, int x1, int y1) {
    if (x0 == x1 && y0 == y1) {
        return 0;
    }
    struct node nd = {x0, y0, 0};
    int x, y;
    struct node q[MAX_M * MAX_M];
    int front = 0, rear = 0;
    q[rear++] = nd;
    while (front < rear) {
        nd = q[front++];
        x = nd.x;
        y = nd.y;
        if (x < m - 1) {
            if (mat[x + 1][y] == 'E') {
                return nd.tcnt + 1;
            } else if (mat[x + 1][y] == '.') {
                struct node newNode = {x + 1, y, nd.tcnt + 1};
                q[rear++] = newNode;
                mat[x + 1][y] = '*';
            }
        }
        if (x > 0) {
            if (mat[x - 1][y] == 'E') {
                return nd.tcnt + 1;
            } else if (mat[x - 1][y] == '.') {
                struct node newNode = {x - 1, y, nd.tcnt + 1};
                q[rear++] = newNode;
                mat[x - 1][y] = '*';
            }
        }
        if (y < m - 1) {
            if (mat[x][y + 1] == 'E') {
                return nd.tcnt + 1;
            } else if (mat[x][y + 1] == '.') {
                struct node newNode = {x, y + 1, nd.tcnt + 1};
                q[rear++] = newNode;
                mat[x][y + 1] = '*';
            }
        }
        if (y > 0) {
            if (mat[x][y - 1] == 'E') {
                return nd.tcnt + 1;
            } else if (mat[x][y - 1] == '.') {
                struct node newNode = {x, y - 1, nd.tcnt + 1};
                q[rear++] = newNode;
                mat[x][y - 1] = '*';
            }
        }
    }
    return -1;
}
 
int main() {
    int k, i, j, x0, y0, x1, y1, ans;
    scanf("%d", &k);
    while (k--) {
        scanf("%d %d", &m, &t);
        for (i = 0; i < m; i++) {
            for (j = 0; j < m; j++) {
                scanf(" %c", &mat[i][j]);
                if (mat[i][j] == 'S') {
                    x0 = i;
                    y0 = j;
                } else if (mat[i][j] == 'E') {
                    x1 = i;
                    y1 = j;
                }
            }
        }
        ans = bfs(x0, y0, x1, y1);
        if (ans <= t && ans >= 0) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
    return 0;
}
题目详情
1166 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

夺宝探险

你无意中发现了装满了宝藏的迷宫,你想要获得尽可能多的宝藏,但是迷宫里的机关阻碍了你的计划。迷宫的地面是M行N列的矩形网格,每格是一块带有机关且放置了1个宝藏的地砖,宝藏一共有K种,用1-K表示其种类,迷宫的入口只有一个,为迷宫的第一行第一列。地砖的机关如下:

1. 每次你只能踏到你与你所在地砖相邻的地砖上(即前后左右4块);

2. 当你踏上某块地砖后,其上的宝藏(假设种类为k)自动归属你,同时所有放置了种类为k的宝藏的地砖碎裂,你无法踏上,你当前所在的地砖在你离开后也会立刻碎裂;

3. 当你无路可走的时候,你会被传送回迷宫出口,无法再进入迷宫。

你想知道你最多能获得多少宝藏。

时间限制:1000

内存限制:65536

输入

输入的第一行是三个用空格隔开的整数,分别是M、N和K(1 <= M,N <= 20, 1 <= K <= 100) 之后是M行,每行包含N个范围为1-K的整数,用空格隔开,表示放置的宝藏种类

输出

只有一行,为一个整数,表示最多能获得的宝藏个数。

样例输入

3 4 5
1 2 3 3
2 1 4 3
1 5 1 2

样例输出

4
答案与解析
参考答案
#include <iostream>
using namespace std;
int m, n, k;
int a[22][22];
bool jewel[101];
int have = 0; // 获得的宝石数
int ans = 0;
int dirx[4] = {0, 0, 1, -1};
int diry[4] = {1, -1, 0, 0};
void dfs(int x, int y) {
  for (int i = 0; i < 4; i++) {
    int nx = x + dirx[i];
    int ny = y + diry[i];
    if (!jewel[a[nx][ny]]) {
      jewel[a[nx][ny]] = true;
      have++;
      dfs(nx, ny);
      have--;
      jewel[a[nx][ny]] = false;
    }
  }
  ans = max(ans, have);
}
int main() {
  cin >> m >> n >> k;
  int i, j;
  for (i = 1; i <= m; i++)
    for (j = 1; j <= n; j++)
      cin >> a[i][j];
  jewel[a[1][1]] = true;
  jewel[0] = true;
  have = 1;
  dfs(1, 1);
  cout << ans;
  return 0;
}
题目详情
1167 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

晶矿的个数

在某个区域发现了一些晶矿,已经探明这些晶矿总共有分为两类,为红晶矿和黑晶矿。现在要统计该区域内红晶矿和黑晶矿的个数。假设可以用二维地图m[][]来描述该区域,若m[i][j]为#表示该地点是非晶矿地点,若m[i][j]为r表示该地点是红晶矿地点,若m[i][j]为b表示该地点是黑晶矿地点。一个晶矿是由相同类型的并且上下左右相通的晶矿点组成。现在给你该区域的地图,求红晶矿和黑晶矿的个数。

时间限制:1000

内存限制:65536

输入

第一行为k,表示有k组测试输入。 每组第一行为n,表示该区域由n*n个地点组成,3 <= n<= 30 接下来n行,每行n个字符,表示该地点的类型。

输出

对每组测试数据输出一行,每行两个数字分别是红晶矿和黑晶矿的个数,一个空格隔开。

样例输入

2
6
r##bb#
###b##
#r##b#
#r##b#
#r####
######
4
####
#rrb
#rr#
##bb

样例输出

2 2
1 2
答案与解析
参考答案
#include <bits/stdc++.h>

using namespace std;

const int N = 30;
char b[N][N + 1];
int n;

void dfs(int r, int c, char type) {
  if (r < 0 || r >= n || c < 0 || c >= n)
    return;
  if (b[r][c] != type)
    return;
  b[r][c] = '#';
  dfs(r - 1, c, type);
  dfs(r + 1, c, type);
  dfs(r, c - 1, type);
  dfs(r, c + 1, type);
}

int main() {
  int k;
  scanf("%d", &k);
  while (k--) {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
      scanf("%s", b[i]);

    int rcnt = 0, bcnt = 0;
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (b[i][j] == 'r') {
          rcnt++;
          dfs(i, j, 'r');
        } else if (b[i][j] == 'b') {
          bcnt++;
          dfs(i, j, 'b');
        }

    printf("%d %d\n", rcnt, bcnt);
  }

  return 0;
}
题目详情
1168 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 2.4 大小设置

冠军之路

当训练师眼神对上的那一刻,就会开始对战。

lxz来到了冠军之路的山洞中。山洞的地图是一个N*M的矩形。在地图中,'.'代表可以行走的地面,'#'代表无法行走的岩石。'I'代表山洞的入口,即lxz现在所在的位置。'O'表示冠军之路的出口。lxz可以向上下左右四个方向行走。矩形的四周都是山洞的岩石,无法行走。

冠军之路中有一些精英训练师,他们可能面向上、下、左、右四个方向,在地图上用'w','a','s','d'表示,其中'w'表示向上。's'表示向下。'a'表示向左。'd'表示向右(这些位置不可行走)。如果lxz出现在精英训练师正对方向的一条线上,且没有被岩石或其他精英训练师阻挡,那么lxz就会与这个精英训练师进行对战。每位训练师只会与lxz对战一次。

为了通过冠军之路,lxz必须击败所有精英训练师。lxz希望找到一条击败所有精英训练师并走到冠军之路出口的最短路径。

时间限制:1000

内存限制:65536

输入

第一行是两个整数,N, M表示地图的大小。 0 < N, M <= 100 接下来是N行,每行M个字符,代表冠军之路的地图。训练师的个数不超过8

输出

一个整数,表示击败所有精英训练师并走到冠军之路出口的最短路径的长度。如果无法击败所有精英训练师或者无法到达出口,输出-1。

样例输入

3 3
Id.
...
Oa#

样例输出

8
答案与解析
参考答案
#include <algorithm>
#include <iostream>
#include <limits>
#include <queue>
#include <vector>

using namespace std;
/*
3 3
Id.
...
Oa#
*/
struct point {
  int x, y;
  point(int x, int y) : x(x), y(y) {}
  point() : x(0), y(0) {}
  bool operator==(const point &p) const { return x == p.x && y == p.y; }
  bool operator<(const point &p) const {
    if (x == p.x)
      return y < p.y;
    return x < p.x;
  }
};
struct item {
  point pt;
  char c;
  item(point p, char c) {
    pt.x = p.x;
    pt.y = p.y;
    this->c = c;
  }
};
int direct[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int a[105][105];
char d[105][105];
int pass[105][105];
vector<vector<point>> pts;
vector<item> base;
point bp, ep;
int n, m;

int bfs(point from, point to) {
  queue<point> q;
  char path[105][105] = {0};
  q.push(from);
  int ans = 0;
  while (q.size()) {
    // TODO
    int size = q.size();
    for (int k = 0; k < size; k++) {
      point cur = q.front();
      q.pop();
      path[cur.x][cur.y] = 1;
      if (cur == to) {
        return ans;
      }
      for (int i = 0; i < 4; i++) {
        point dst;
        dst.x = cur.x + direct[i][0];
        dst.y = cur.y + direct[i][1];
        if (dst.x >= n || dst.x < 0)
          continue;
        if (dst.y > m || dst.y < 0)
          continue;
        if (path[dst.x][dst.y] == 0 &&
            (d[dst.x][dst.y] == '.' || d[dst.x][dst.y] == 'O' ||
             d[dst.x][dst.y] == 'I')) {
          q.push(dst);
        }
      }
    }
    ans++;
  }
  return 0;
}
vector<point> getpoints(char pos, point p) {
  vector<point> res;
  string ss = ".IO";
  if (pos == 'w') {
    for (int i = p.x - 1; i >= 0; i--)
      if (ss.find(d[i][p.y]) != string::npos)
        res.push_back(point(i, p.y));
      else
        break;
  }
  if (pos == 's') {
    for (int i = p.x + 1; i < m; i++)
      if (ss.find(d[i][p.y]) != string::npos)
        res.push_back(point(i, p.y));
      else
        break;
  }
  if (pos == 'a') {
    for (int i = p.y - 1; i >= 0; i--)
      if (ss.find(d[p.x][i]) != string::npos)
        res.push_back(point(p.x, i));
      else
        break;
  }
  if (pos == 'd') {
    for (int i = p.y + 1; i < n; i++)
      if (ss.find(d[p.x][i]) != string::npos)
        res.push_back(point(p.x, i));
      else
        break;
  }
  return res;
}
/*
void showpath(int i, int j) {
    if (i == j) return;
    if (pass[i][j] == 0) {
        printf("%d -> %d \n",i , j);
        route.push_back(j);
    } else {
        showpath(i, pass[i][j]);
        showpath(pass[i][j], j);
    }
}
*/
int getMinBfs(point pt, vector<int> &idx, vector<int> &p,
              vector<vector<point>> pts) {
  int minval = INT32_MAX;
  for (uint32_t i = 0; i < pts.size(); i++) {
    for (uint32_t j = 0; j < pts[i].size(); j++) {
      int dis = bfs(pt, pts[i][j]);
      if (minval > dis) {
        minval = dis;
        idx.clear(), p.clear();
        idx.push_back(i), p.push_back(j);
      } else if (minval == dis) {
        idx.push_back(i), p.push_back(j);
      }
    }
  }
  return minval;
}
vector<point> getMinPoints(point pt, vector<vector<point>> pts) {
  vector<point> res;
  int idx, p;
  for (uint32_t i = 0; i < pts.size(); i++) {
    int minval = INT32_MAX;
    for (uint32_t j = 0; j < pts[i].size(); j++) {
      int dis = bfs(pt, pts[i][j]);
      if (minval > dis) {
        minval = dis;
        idx = i, p = j;
      }
    }
    res.push_back(pts[idx][p]);
  }
  return res;
}
// 贪心法+bfs搜索计算最小路径
int getMinPath(point bp, point ep, vector<vector<point>> points) {
  int sum = 0, minSum = INT32_MAX;
  vector<int> idx, p;
  vector<point> ap;
  vector<vector<point>> apt;
  point pt;
  ap = getMinPoints(bp, points); // 获取与bp点距离最近的所有点
  for (int x = 0; x < ap.size(); x++) {
    pt = bp;
    sum = bfs(pt, ap[x]);
    apt = points;
    apt.erase(apt.begin() + x);
    pt = ap[x]; // 设置为当前点
    if (apt.size() > 0) {
      sum += getMinBfs(pt, idx, p, apt);
      while (1) {
        if (idx.size() > 1) { // 有多个并列最近点的情况
          int tmin = INT32_MAX, ts, k;
          for (int i = 0; i < idx.size(); i++) {
            vector<vector<point>> tp = apt;
            tp.erase(tp.begin() + idx[i]);
            ts = getMinPath(apt[idx[i]][p[i]], ep,
                            tp); // 计算以并列点为起点的路径
            if (tmin > ts) {
              tmin = ts;
              k = i;
            } // 记录最小路径
          }
          idx[0] = idx[k], p[0] = p[k]; // 更新最小路径
        }
        pt = apt[idx[0]][p[0]];
        apt.erase(apt.begin() + idx[0]);
        if (apt.size() == 0)
          break;
        sum += getMinBfs(pt, idx, p, apt);
      }
    }
    sum += bfs(pt, ep); // 加上到出口点的距离
    if (minSum > sum)
      minSum = sum;
  }
  return minSum;
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
      cin >> d[i][j];
      if (d[i][j] != '#' && d[i][j] != '.') {
        base.push_back(item(point(i, j), d[i][j]));
      }
      if (d[i][j] == 'I')
        bp = point(i, j);
      if (d[i][j] == 'O')
        ep = point(i, j);
    }
  // 扩展点,增加同方向的
  for (int i = 0; i < base.size(); i++) {
    vector<point> vp;
    if (base[i].c != 'I' && base[i].c != 'O') {
      vp = getpoints(base[i].c, base[i].pt);
      pts.push_back(vp);
    }
  }
  int sum1 = getMinPath(bp, ep, pts);          // 正向计算
  int sum2 = getMinPath(ep, bp, pts);          // 反向计算
  cout << (sum1 > sum2 ? sum2 : sum1) << endl; // 取最小值
  return 0;
}
题目详情
1169 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

小白鼠再排队

N只小白鼠(1 < N < 100),每只鼠头上戴着一顶有颜色的帽子。现在称出每只白鼠的重量,要求按照白鼠重量从小到大的顺序输出它们头上帽子的颜色。帽子的颜色用 “red”,“blue”等字符串来表示。不同的小白鼠可以戴相同颜色的帽子。白鼠的重量用整数表示。

时间限制:1000

内存限制:65536

输入

输入第一行为一个整数N,表示小白鼠的数目。 下面有N行,每行是一只白鼠的信息。第一个为正整数,表示白鼠的重量,不超过整型范围;第二个为字符串,表示白鼠的帽子颜色,字符串长度不超过10个字符。 注意:白鼠的重量各不相同。

输出

按照白鼠的重量从小到大的顺序输出白鼠的帽子颜色。

样例输入

3
30 red
50 blue
40 green

样例输出

red
green
blue
答案与解析
参考答案
#include <iostream>
using namespace std;
int main() {
  int a[100];    // 体重
  string b[100]; // 帽子颜色
  int n;
  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> a[i] >> b[i];
  for (int i = n - 1; i > 0; i--) // 冒泡排序
    for (int j = 0; j < i; j++) {
      if (a[j] > a[j + 1]) {
        swap(a[j], a[j + 1]);
        swap(b[j], b[j + 1]);
      }
    }
  for (int i = 0; i < n; i++)
    cout << b[i] << endl;
  return 0;
}
题目详情
1170 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 7.1 逻辑推理

多余的数

小A同学在完成一个数学题:求给定的10个整数的和。小A同学在求完之后发现和参考答案对不上,检查后发现在求和过程中多计算了一个数,其他过程没有问题。现给出小A计算用的11个数,以及正确的参考答案,请算出小A同学多计算的那一个数。

时间限制:1000

内存限制:65536

输入

第一行11个正整数,每个数小于等于1000000 第二行一个整数,表示参考答案

输出

一个整数,表示多计算的那一个数。

样例输入

2 4 6 8 1 3 5 7 9 5 11
54

样例输出

7

提示

样例中原有的10个数为2 4 6 8 1 3 5 9 5 11,和为54,多余的数为7。

答案与解析
参考答案
#include <iostream>
using namespace std;
int main() {
  int sum = 0, a, t;
  for (int i = 1; i <= 11; i++) {
    cin >> a;
    sum = sum + a; // 11个数总和
  }
  cin >> t;
  cout << sum - t; // 11个数总和-10个数总和=多加的数
  return 0;
}
题目详情
1171 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 2.4 大小设置

打字员

有一个打字员,他打字的时候有个习惯,从来不用 Shift 来切换大小写,只用 Caps Lock。 现在给他一个地铁站的名字,你需要写一个程序来告诉他,他需要敲击多少下键盘才能打出 这个地铁站名。

时间限制:1000

内存限制:65536

输入

第一行输入一个数字 n (n<1000),表示共有多少个需要处理的车站名。从第 2 到第 n+1 行是这 n 个车站名。车站名由英文字母构成,名字的长度不会超过 100 个字符。已知开始时 键盘是输入小写字母的状态。

输出

这个打字员敲击键盘的次数。

样例输入

5
BeiJingDaXueDongMen
AAAaaaBBBbbbABAB
AmericanRAILWAY
AaAaAa
DFjfkdaB

样例输出

31
21
18
12
11
答案与解析
参考答案
#include <iostream>
using namespace std;
int pd(char c) {
  if (c >= 'a' && c <= 'z')
    return 1;
  return 2;
}
int main() {
  int n;
  string s[1000];
  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> s[i];
  for (int i = 0; i < n; i++) {
    int len = s[i].size(), t = 0;
    if (pd(s[i][0]) == 1) // 第一个字母单独处理
      t++;
    else
      t += 2;
    for (int j = 1; j < len; j++) {
      if (pd(s[i][j]) == pd(s[i][j - 1])) // 是否与前一个字母相同
        t++;                              // 相同直接打
      else
        t += 2; // 不相同先切换大小写再打
    }
    cout << t << endl;
  }
  return 0;
}
题目详情
1172 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 7.1 逻辑推理

最好的草

奶牛Bessie计划好好享受柔软的春季新草。新草分布在R行C列的牧场里。它想计算一下牧场中的草丛数量。

在牧场地图中,每个草丛要么是单个“#”,要么是有公共边的相邻两个“#”。给定牧场地图,计算有多少个草丛。

例如,考虑如下5行6列的牧场地图

. # . . . .

. . # . . .

. . # . . #

. . . # # .

. # . . . .

这个牧场有5个草丛:一个在第一行,一个在第二列横跨了二、三行,一个在第三行,一个在第四行横跨了四、五列,最后一个在第五行。

时间限制:10000

内存限制:65536

输入

第一行包含两个整数R和C,中间用单个空格隔开。 接下来R行,每行C个字符,描述牧场地图。字符只有“#”或“.”两种。(1 <= R, C <= 100 )

输出

输出一个整数,表示草丛数。

样例输入

5 6
.#....
..#...
..#..#
...##.
.#....

样例输出

5
答案与解析
参考答案
#include <iostream>
using namespace std;

int R, C, cnt = 0;
string grass[100];

void dfs(int x, int y) {
  int step[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 记录当前位置的四个方向
  for (int i = 0; i < 4; ++i) {
    int xx = x + step[i][0], yy = y + step[i][1];
    if (xx < 0 || xx >= R || yy < 0 || yy >= C) // 判断边界
      continue;
    if (grass[xx][yy] == '#') {
      grass[xx][yy] = '.'; // 标记
      dfs(xx, yy);
    }
  }
}

int main() {
  cin >> R >> C;
  for (int i = 0; i < R; ++i)
    cin >> grass[i];
  for (int i = 0; i < R; ++i)
    for (int j = 0; j < C; ++j)
      if (grass[i][j] == '#') {
        cnt++;
        dfs(i, j);
      }
  cout << cnt;
  return 0;
}
题目详情
1173 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

字符串中最长的连续出现的字符

求一个字符串中最长的连续出现的字符,输出该字符及其出现次数。字符串中无空白字符(空格、回车和tab),如果这样的字符不止一个,则输出出现最早的字符。

时间限制:1000

内存限制:65536

输入

一行,一个不包含空白字符的字符串,字符串长度小于200。

输出

一行,输出最长的连续出现的字符及其最长的连续出现次数,中间以一个空格分开。

样例输入

aaaaadbbbbbcccccccdddddddddd

样例输出

d 10
答案与解析
参考答案
#include <iostream>
using namespace std;
int main() {
  string s;
  int n = 1, maxn = 1;
  char maxc;
  cin >> s;
  int len = s.size(); // 字符串长度
  maxc = s[0];
  for (int i = 1; i < len; i++) {
    if (s[i] == s[i - 1]) { // 与前一个字符相同,将n累加
      n++;
      if (n > maxn) { // 当前字符连续出现次数超过存储的最大值
        maxn = n;
        maxc = s[i];
      }
    } else
      n = 1;
  }
  cout << maxc << " " << maxn;
  return 0;
}
题目详情
1174 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

公共子序列

我们称序列Z = < z1, z2, ..., zk >是序列X = < x1, x2, ..., xm >的子序列当且仅当存在 严格上升 的序列< i1, i2, ..., ik >,使得对j = 1, 2, ... ,k, 有xij = zj。比如Z = < a, b, f, c > 是X = < a, b, c, f, b, c >的子序列。 现在给出两个序列X和Y,你的任务是找到X和Y的最大公共子序列,也就是说要找到一个最长的序列Z,使得Z既是X的子序列也是Y的子序列。

时间限制:3000

内存限制:65536

输入

输入包括多组测试数据。每组数据包括一行,给出两个长度不超过200的字符串,表示两个序列。两个字符串之间由若干个空格隔开。

输出

对每组输入数据,输出一行,给出两个序列的最大公共子序列的长度。

样例输入

abcfbc         abfcab
programming    contest 
abcd           mnp

样例输出

4
2
0
答案与解析
参考答案
#include <bits/stdc++.h>
#include <string>
using namespace std;
int f[1000][1000];
int main() {
  string a, b;
  while (cin >> a >> b) {
    int n = a.size();
    int m = b.size();
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; i++) {
      for (int k = 1; k <= m; k++) {
        if (a[i - 1] == b[k - 1]) {
          f[i][k] = max(f[i][k], f[i - 1][k - 1] + 1);
        } else {
          f[i][k] = max(f[i][k - 1], f[i - 1][k]);
        }
      }
    }
    cout << f[n][m] << endl;
  }
  return 0;
}
题目详情
1175 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

硬币问题

有N(不大于100)种硬币,编号为1至N,已知每种硬币的重量(不超过100的正整数)和面额(不超过100的正整数),每种硬币数量不限。选取总重量不超过C(不大于1000的正整数)的硬币,最多能获得多少总面额?

时间限制:1000

内存限制:65536

输入

第一行输入N 第二行输入C 第三行输入各硬币重量,用空格隔开 第四行输入各硬币价值,用空格隔开

输出

最大总面额

样例输入

3
5
1 2 5
1 3 6

样例输出

7
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int t[105], v[105];
int dp[1005];
int main() {
  int n, c;
  cin >> n >> c;
  for (int i = 1; i <= n; i++)
    cin >> t[i];
  for (int i = 1; i <= n; i++)
    cin >> v[i];
  for (int i = 1; i <= n; i++) {
    for (int j = t[i]; j <= c; j++) {
      dp[j] = max(dp[j], dp[j - t[i]] + v[i]);
    }
  }
  cout << dp[c];
  return 0;
}
题目详情
1176 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

田忌赛马

你一定听过田忌赛马的故事吧?

如果3匹马变成1000匹,齐王仍然让他的马按从优到劣的顺序出赛,田忌可以按任意顺序选择他的赛马出赛。赢一局,田忌可以得到200两银子,输一局,田忌就要输掉200两银子,平局的话不输不赢。

请问田忌最多能赢多少银子?

时间限制:5000

内存限制:65536

输入

输入包含多组测试数据. 每组测试数据的第一行是一个整数n(1<=n<=1000),表示田忌和齐王都拥有n匹马。接下来一行是n个整数,表示田忌的马的速度,下一行也是n个整数,表示齐王的马的速度。 输入的最后以一个0表示结束。

输出

对每组数据,输出一个整数,表示田忌至多可以赢多少银子,如果田忌赢不了,就输出一个负数,表示田忌最少要输多少银子。

样例输入

3
92 83 71
95 87 74
2
20 20
20 20
2
20 19
22 18
0

样例输出

200
0
0
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int h1, h2, t1, t2, n, i, ans = 0;
int t[100001], k[100001];
int cmp(int a, int b) { return a > b; }
int main() {
  while (cin >> n && n) {
    for (i = 1; i <= n; i++)
      cin >> t[i];
    for (i = 1; i <= n; i++)
      cin >> k[i];
    sort(t + 1, t + n + 1, cmp);
    sort(k + 1, k + n + 1, cmp);
    h1 = h2 = 1;
    t1 = t2 = n;
    while (h1 <= t1) {
      if (t[h1] > k[h2])
        ans += 200, h1++, h2++;
      else {
        if (t[h1] < k[h2])
          ans -= 200, t1--, h2++;
        else {
          if (t[t1] > k[t2])
            ans += 200, t1--, t2--;
          else {
            if (t[t1] < k[h2])
              ans -= 200;
            t1--, h2++;
          }
        }
      }
    }
    cout << ans << endl;
    ans = 0;
  }
}
题目详情
1177 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

上机

又到周末了,同学们陆陆续续开开心心的来到机房上机。jbr也不例外,但是他到的有点晚,发现有些机位上已经有同学正在做题,有些机位还空着。细心的jbr发现,一位同学来到机房,坐在机位i上,如果他的左右两边都空着,他将获得能力值a[i];如果当他坐下时,左边或者右边已经有一个人在上机了,他将获得能力值b[i];如果当他坐下时,他的左边右边都有人在上机,他将获得能力值c[i]。

同时他发现,已经在上机的同学不会受到刚要坐下的同学的影响,即他们的能力值只会在坐下时产生,以后不会发生变化;第一个机位左边没有机位,最后一个机位右边没有机位,无论何时坐在这两个机位上将无法获得c值。

这时jbr发现有一排机器还空着,一共有N个机位,编号1到N。这时有N位同学们陆陆续续来到机房,一个一个按照顺序坐在这排机位上。聪明的jbr想知道怎么安排座位的顺序,可以使这N位同学获得能力值的和最大呢?

时间限制:1000

内存限制:65536

输入

第一行一个整数N(1<= N <= 10000)

第二行N个数,表示a[i]

第三行N个数,表示b[i]

第四行N个数,表示c[i]

(1<= a[i],b[i],c[i] <=10000)

输出

一个整数,表示获得最大的能力值和

样例输入

4
1 2 2 4
4 3 3 1
2 1 1 2

样例输出

14

提示

第一位同学坐在第四个机位上,获得能力值4; 第二位同学坐在第三个机位上,获得能力值3; 第三位同学坐在第二个机位上,获得能力值3; 第四位同学坐在第一个机位上,获得能力值4; 总和为14。

答案与解析
参考答案
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

using namespace std;
int a[10005];
int b[10005];
int c[10005];
int d
    [10005]
    [4]; // 考虑前i的座位已经坐好的前i个座位最大值,0-第i个人坐下的时候两边没人,1-左边有人,2-右边有人,3-都有人
int main() {
  int n;
  cin >> n;
  int i;
  for (i = 1; i <= n; i++)
    cin >> a[i];
  for (i = 1; i <= n; i++)
    cin >> b[i];
  for (i = 1; i <= n; i++)
    cin >> c[i];
  d[1][0] = a[1];
  d[1][2] = b[1];
  for (i = 2; i <= n; i++) {
    d[i][0] =
        max(d[i - 1][3], d[i - 1][2]) +
        a[i]; // 第i个位置坐下的时候两边没人,要求它先于第i-1个人被坐,也就是说第i-1个人坐下的时候一定是右边有人
    d[i][1] = max(d[i - 1][0], d[i - 1][1]) + b[i];
    d[i][2] = max(d[i - 1][3], d[i - 1][2]) + b[i];
    d[i][3] = max(d[i - 1][0], d[i - 1][1]) + c[i];
  }
  cout << max(d[n][0], d[n][1]);
  return 0;
}
// 参考答案2
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 10000 + 1;
int a[N], b[N], c[N], dp[N][4];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    scanf("%d", &a[i]);
  for (int i = 1; i <= n; i++)
    scanf("%d", &b[i]);
  for (int i = 1; i <= n; i++)
    scanf("%d", &c[i]);
  dp[1][0] = a[1];
  dp[1][1] = -INF;
  dp[1][2] = b[1];
  dp[1][3] = -INF;
  for (int i = 2; i <= n; i++) {
    dp[i][0] = a[i] + max(dp[i - 1][2], dp[i - 1][3]);
    dp[i][1] = b[i] + max(dp[i - 1][0], dp[i - 1][1]);
    dp[i][2] = b[i] + max(dp[i - 1][2], dp[i - 1][3]);
    dp[i][3] = c[i] + max(dp[i - 1][0], dp[i - 1][1]);
  }
  printf("%d\n", max(dp[n][0], dp[n][1]));
  return 0;
}


题目详情
1178 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

制作蛋糕

小A擅长制作香蕉蛋糕和巧克力蛋糕。制作一个香蕉蛋糕需要2个单位的香蕉,250个单位的面粉,75个单位的糖,100个单位的黄油。制作一个巧克力蛋糕需要75个单位的可可粉,200个单位的面粉,150个单位的糖,150个单位的黄油。一个香蕉蛋糕可以卖出400元,而一个巧克力蛋糕可以卖出450元。为了避免蛋糕变质,每种蛋糕至多只能制作100个。

现已知每种原料的数量,求小A至多可以卖出多少元的蛋糕。

时间限制:1000

内存限制:65536

输入

依次输入面粉、香蕉、糖、黄油、可可粉的数量,每种原料数量均为不超过100000的整数。

输出

输出一个整数,表示最多卖出的钱数。

样例输入

4000
6
2000
500
500

样例输出

1700
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
  int mf, xj, t, hy, kkf, xjcake = 0, kkcake = 0, msum = 0, sum = 0;
  cin >> mf >> xj >> t >> hy >> kkf;
  for (int i = 0; i <= xj / 2; i++)
    for (int j = 0; j <= kkf / 75; j++) {
      if ((i * 250 + j * 200) <= mf && (i * 75 + j * 150) <= t &&
          (i * 100 + j * 150) <= hy && i <= 100 && j <= 100) {
        sum = i * 400 + j * 450;
        if (sum > msum)
          msum = sum;
      }
    }
  cout << msum;
  return 0;
}
题目详情
1179 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

找和最接近但不超过K的两个元素

在一个长度为n(1 < n < 1000)的整数(0至1000之间)序列中,选出两个元素使得它们的和最接近但不超过K(0 <= K < 2000)。保证一定存在不超过K的两元素和。<n<1000)的整数(0至1000之间)序列中,选出两个元素使得它们的和最接近但不超过k(0<=k<2000)。保证一定存在不超过k的两元素和。<n<1000)的整数(0至1000之间)序列中,选出两个元素使得它们的和最接近但不超过k(0<=k<2000)。保证一定存在不超过k的两元素和。

<n<1000)的整数(0至1000之间)序列中,选出两个元素使得它们的和最接近但不超过k(0<=k<2000)。保证一定存在不超过k的两元素和。

时间限制:1000

内存限制:65536

输入

第一行输入一个整数n 第二行输入一个整数K 第三行输入序列,用空格分开

输出

最接近但不超过K的和

样例输入

4
7
1 2 2 8

样例输出

4
答案与解析
参考答案
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

using namespace std;
int a[10005];
int main() {
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  sort(a, a + n);
  int l = 0, r = n - 1;
  int ans = a[0] + a[1];
  while (l < r) {
    int sum = a[l] + a[r];
    if (sum <= k) {
      if (k - sum < k - ans)
        ans = sum;
    }
    if (sum == k) {
      cout << k << endl;
      return 0;
    } else if (sum < k)
      l++;
    else
      r--;
  }
  cout << ans << endl;
}
题目详情
1180 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

数根

树根可以通过把一个数的各个位上的数字加起来得到。如果得到的数是一位数,那么这个数就是数根。如果结果是两位数或者包括更多位的数字,那么再把这些数字加起来。如此进行下去,直到得到是一位数为止。比如,对于24来说,把2和4相加得到6,由于6是一位数,因此6是24的数根。再比如39,把3和9加起来得到12,由于12不是一位数,因此还得把1和2加起来,最后得到3,这是一个一位数,因此3是39的数根。

输入

一个正整数(小于10^1000)

输出

一个数字,即输入数字的数根

样例输入

24

样例输出

6
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int sg(int n) {
  int sum = 0;
  while (n) {
    sum += n % 10;
    n /= 10;
  }
  if (sum >= 10)
    return sg(sum);
  return sum;
}
int main() {
  string s;
  int len, ans = 0;
  cin >> s;
  len = s.size();
  for (int i = 0; i < len; i++) {
    ans = ans + s[i] - '0';
  }
  cout << sg(ans);
  return 0;
}
题目详情