首页 › 题库 › Scratch编程考级 › 1 熟悉编程软件

Scratch编程一级 题库

共 678 道题 ,第 34 / 34 页 · 按题型筛选,点「查看答案」核对解析
章节 1 熟悉编程软件 清除
661 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

成绩判定

给定一门课的考试分数,如果分数大于等于60,则该门课成绩合格,记为"P", 否者成绩不合格,记为"F"。

时间限制:1000

内存限制:65536

输入

一个整数s,表示这门课的分数.(0 ≤ s ≤ 100)

输出

如果成绩合格,输出字母P,否者输出字母F。

样例输入

59

样例输出

F
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
  int s;
  scanf("%d", &s);
  if (s >= 60) {
    printf("P");
  } else {
    printf("F");
  }
  return 0;
}
题目详情
662 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

简单排序

依次输入3个整数a、b、c,将他们从小到大的顺序输出。

时间限制:1000

内存限制:65536

输入

一行3个整数a、b、c,以空格分隔。 0 < a,b,c < 108

输出

一行3个整数,即将a、b、c从小到大排序的3个整数,整数之间以一个空格分隔。

样例输入

10 5 20

样例输出

5 10 20
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a[3];
  scanf("%d%d%d", &a[0], &a[1], &a[2]);
  sort(a, a + 3); // 从小到大排序
  printf("%d %d %d", a[0], a[1], a[2]);
  return 0;
}
题目详情
663 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

数字求和

给定一个正整数a,以及另外的5个正整数,问题是:这5个整数中,小于a的整数的和是多少?

时间限制:3000

内存限制:65536

输入

输入一行,只包括6个小于100的正整数,其中第一个正整数就是a。

输出

输出一行,给出一个正整数,是5个数中小于a的数的和。

样例输入

10 1 2 3 4 11

样例输出

10
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a;
  scanf("%d", &a);
  int sum = 0;
  for (int i = 0; i < 5; i++) {
    int t;
    scanf("%d", &t);
    if (t < a) {
      sum = sum + t;
    }
  }
  printf("%d", sum);
  return 0;
}
题目详情
664 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

数1的个数

给定一个十进制正整数n,写下从1到n的所有整数,然后数一下其中出现的数字“1”的个数。

例如当n=2时,写下1,2。这样只出现了1个“1”;当n=12时,写下1,2,3,4,5,6,7,8,9,10,11,12。这样出现了5个“1”。

时间限制:1000

内存限制:65536

输入

正整数n。1 <= n <= 10000。

输出

一个正整数,即“1”的个数。

样例输入

12

样例输出

5
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
// 把数字转字符串,统计字符串中有多少个'1'的字符
int count_1(int x) {
  char m[20];
  int r = 0;
  int num = sprintf(&m[0], "%d", x);
  for (int i = 0; i < num; i++) {
    if (m[i] == '1') {
      r = r + 1;
    }
  }
  return r;
}
int main() {
  int sum = 0;
  int max_x = 0;
  scanf("%d", &max_x);
  for (int i = 1; i <= max_x; i++) {
    sum = sum + count_1(i);
  }
  printf("%d", sum);
  return 0;
}
题目详情
665 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

迷宫问题

定义一个二维数组:

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一个迷宫, 其中的 1 表示墙壁, 0 表示可以走的路, 只能横着走或竖着走, 不能斜着走, 要求编程序找出从左上角到右下角的最短路线。

时间限制: 1000

内存限制: 65536

输入

一个 5 × 5 的二维数组, 表示一个迷宫。 数据保证有唯一解。

输出

左上角到右下角的最短路径, 格式如样例所示。

样例输入

0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

样例输出

(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
答案与解析
参考答案
/*#include <iostream>*/
#include <bits/stdc++.h>
using namespace std;
const int idata = 50 + 5;
int maps[idata][idata];
bool judge[idata][idata];
int change[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int nx, ny;
int x[idata], y[idata];
int show[30];
bool flag;
void print(int tail) {
  if (show[tail])
    print(show[tail]);
  cout << "(" << x[tail] << ", " << y[tail] << ")" << endl;
}
int main() {
  int head, tail;
  register int i, j;
  for (i = 0; i < 5; i++) {
    for (j = 0; j < 5; j++) {
      cin >> maps[i][j];
      if (maps[i][j] == 1)
        judge[i][j] = 1;
    }
  }
  head = 0;
  tail = 1;
  judge[0][0] = 1;
  show[tail] = head;
  while (tail > head) {
    head++;
    for (i = 0; i < 4; i++) {
      nx = x[head] + change[i][0];
      ny = y[head] + change[i][1];
      if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && !judge[nx][ny]) {
        tail++;
        x[tail] = nx;
        y[tail] = ny;
        judge[nx][ny] = 1;
        show[tail] = head;

        if (nx == 4 && ny == 4) {
          flag = 1;
          print(tail);
          break;
        }
      }
    }
    if (flag)
      break;
  }
  return 0;
}

>>试试在线提交?季卡以上会员请联系客服,免费开通OJ账号

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

二叉树的深度

给定一棵二叉树,求该二叉树的深度

二叉树深度定义:从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的节点个数为树的深度

时间限制:1000

内存限制:65535

输入

第一行是一个整数n,表示二叉树的结点个数。二叉树结点编号从1到n,根结点为1,n <= 10 接下来有n行,依次对应二叉树的n个节点。 每行有两个整数,分别表示该节点的左儿子和右儿子的节点编号。如果第一个(第二个)数为-1则表示没有左(右)儿子

输出

输出一个整型数,表示树的深度


样例输入

3
2 3
-1 -1
-1 -1

样例输出

2
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 7;
struct node {
  int left, right;
} t[MAXN];
int n;
void build() {
  for (int i = 1; i <= n; i++) {
    cin >> t[i].left >> t[i].right;
  }
}
#define rep1(i, n) for (int i = 1; i <= n; i++)
inline int dfs(int x) {
  if (x == -1)
    return 0;
  return max(dfs(t[x].left), dfs(t[x].right)) + 1;
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  build();
  cout << dfs(1);
  return 0;
}
//题解2
#include <algorithm>
#include <iostream>

using namespace std;
int meng[102][30]; /*a[i][0]表示节点i的左孩子节点编号,
a[i][1]表示节点i的右孩子节点编号,a[i][2]表示i节点的父节点编号。*/
int a, b;
int dfs(int root) {
  if (meng[root][0] == -1 && meng[root][1] == -1)
    return 1;
  else {
    int left = 0, right = 0;
    if (meng[root][0] >= 0)
      left = dfs(meng[root][0]);
    /*如果该节点满足不为-1证明它有父节点,
    递归回去去证明它的父节点上面是否也有父节点*/
    if (meng[root][1] >= 0) {
      right = dfs(meng[root][1]);
    }
    return max(right, left) + 1;
  }
}
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a >> b;
    // 二维是为了更好的判断左孩子还是右孩子,父节点
    meng[i][0] = a; // i的左孩子是a
    meng[i][1] = b; // i的右孩子是b
  }
  cout << dfs(1) << endl;
  return 0;
}
题目详情
667 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.4 新建保存与语言选择

表达式· 表达式树· 表达式求值

众所周知, 任何一个表达式, 都可以用一棵表达式树来表示。 例如,

表达式 a+b*c, 可以表示为如下的表达式树:

+

/ \

a *

/ \

 b c

现在, 给你一个中缀表达式, 这个中缀表达式用变量来表示(不含数字), 请你将这个中缀表达式用表达式二叉树的形式输出出来。

时间限制: 1000

内存限制: 65535

输入

输入分为三个部分。 第一部分为一行,即中缀表达式(长度不大于50)。中缀表达式可能含有小写字母代表变量(a-z),也可能含有运算符(+、-、*、/、小括号),不含有数字,也不含有空格。 第二部分为一个整数n(n < 10),表示中缀表达式的变量数。 第三部分有n行,每行格式为C x,C为变量的字符,x为该变量的值。

输出

输出分为三个部分,第一个部分为该表达式的逆波兰式,即该表达式树的后根遍历结果。占一行。 第二部分为表达式树的显示,如样例输出所示。如果该二叉树是一棵满二叉树,则最底部的叶子结点,分别占据横坐标的第1、3、5、7……个位置(最左边的坐标是1),然后它们的父结点的横坐标,在两个子结点的中间。如果不是满二叉树,则没有结点的地方,用空格填充(但请略去所有的行末空格)。每一行父结点与子结点中隔开一行,用斜杠(/)与反斜杠(\)来表示树的关系。/出现的横坐标位置为父结点的横坐标偏左一格,\出现的横坐标位置为父结点的横坐标偏右一格。也就是说,如果树高为m,则输出就有2m-1行。 第三部分为一个整数,表示将值代入变量之后,该中缀表达式的值。需要注意的一点是,除法代表整除运算,即舍弃小数点后的部分。同时,测试数据保证不会出现除以0的现象。


样例输入

a+b*c
3
a 2
b 7
c 5

样例输出

abc*+
   +
  / \
 a   *
    / \
    b c
37
答案与解析
参考答案
#include <cmath>
#include <cstring>
#include <iostream>
#include <stack>
#include <string>

#define OK 1
#define ERROR 0
#define MAXSIZE 50
using namespace std;
struct number {
  char ch;
  int value;
};
number a[10];

// 定义二叉树类型
typedef struct BiNode {
  char date;
  struct BiNode *lchild, *rchild;
} BiNode;

// 定义栈类型
typedef struct SqStack {
  char *base;
  char *top;
  int stacksize;
} SqStack;

// 初始化栈
int InitStack(SqStack &S) {
  S.base = new char[MAXSIZE];
  if (!S.base)
    exit(ERROR);
  S.top = S.base;
  S.stacksize = MAXSIZE;
  return OK;
}

// 出栈
char Pop(SqStack &S) {
  if (S.top == S.base)
    return ERROR;
  char e = *(--S.top);
  return e;
}

// 入栈
int Push(SqStack &S, char e) {
  if (S.top - S.base == S.stacksize)
    return ERROR;
  *(S.top++) = e;
  return OK;
}
// 将中缀表达式转化为后缀表达式
string Change(string str) {
  // str为中缀表达式,str2为后缀表达式
  string str2 = "";
  char ch, e; // e用于保存栈中弹出的元素
  SqStack S1; // S1用于存放操作符(为辅助栈),S用于存放后续表达式
  InitStack(S1);
  for (int i = 0; i < str.size(); i++) {
    ch = str[i];
    if (ch >= 'a' && ch <= 'z') {
      str2 += ch;
    }
    if (ch == '(')
      Push(S1, ch);
    if (ch == ')') {
      while (*(S1.top - 1) != '(') {
        e = Pop(S1);
        str2 += e;
      }
      Pop(S1); // 左括号出栈但不入S2栈中
    }
    // 遇到+或-时
    // 栈空/栈顶为左括号:直接入栈
    // 否则一直出栈,直到栈空/栈顶为左括号,再入栈
    if (ch == '+' || ch == '-') {
      while (*(S1.top - 1) != '(' && S1.base != S1.top) {
        e = Pop(S1);
        str2 += e;
      }
      Push(S1, ch);
    }
    // 遇到*或/时
    // 栈空/栈顶为左括号/栈顶操作符为+ or -:直接入栈
    // 否则一直出栈,直到满足上述条件,再入栈
    if (ch == '*' || ch == '/') {
      while (S1.base != S1.top && *(S1.top - 1) != '(' &&
             *(S1.top - 1) != '-' && *(S1.top - 1) != '+') {
        e = Pop(S1);
        str2 += e;
      }
      Push(S1, ch);
    }
  }
  // 中缀表达式遍历完成,还需检查栈中是否有未输出字符
  // 判断栈空,非空则直接出栈
  while (S1.base != S1.top) {
    e = Pop(S1);
    if (e != '(')
      str2 += e;
  }
  return str2;
}
struct BiNode *s[MAXSIZE]; // 定义栈,该栈用于存放树
int top = -1;

// 建立二叉树
BiNode *CreatTree(string str) {
  // str为后缀表达式
  BiNode *T, *T2;
  SqStack S;
  BiNode *e1, *e2;
  int i;
  InitStack(S);
  for (i = 0; i < str.size() - 1; i++) {
    if (str[i] >= 'a' && str[i] <= 'z') {
      T = new BiNode;
      T->date = str[i];
      T->lchild = T->rchild = NULL;
      s[++top] = T;
    } else {
      T = new BiNode;
      T->date = str[i];
      e1 = s[top--];
      e2 = s[top--];
      T->lchild = e2;
      T->rchild = e1;
      s[++top] = T;
    }
  }
  T = new BiNode;
  T->date = str[i];
  T->rchild = s[top--];
  T->lchild = s[top--];
  s[++top] = T;
  T2 = new BiNode;
  T2 = s[top];
  return T2;
}

int Seek(char e, int n) {
  for (int i = 0; i < n; i++) {
    if (a[i].ch == e)
      return a[i].value;
  }
}

int Count(string str, int n) {
  // str为后缀表达式数组,n变量个数
  int sum = 0;
  stack<int> S;
  int x, x1, x2;
  for (int i = 0; i < n; i++) {
    cin >> a[i].ch >> a[i].value;
  }
  for (int i = 0; i < str.size(); i++) {
    if (str[i] >= 'a' && str[i] <= 'z') {
      x = Seek(str[i], n);
      S.push(x);
    } else {
      x2 = S.top();
      S.pop(); // 左操作数
      x1 = S.top();
      S.pop(); // 右操作数
      switch (str[i]) {
      case '+':
        sum = x1 + x2;
        break;
      case '-':
        sum = x1 - x2;
        break;
      case '*':
        sum = x1 * x2;
        break;
      case '/':
        sum = x1 / x2;
        break;
      }
      S.push(sum);
    }
  }
  sum = S.top();
  return sum;
}
char arr[1000][1000];
// 打印二叉树
void PrintTree(int tag, BiNode *T, int x, int m, int y) {
  arr[2 * tag - 1][(x + m) / 2] = T->date;
  if (tag != 1) {
    if (y == 1)
      arr[2 * tag - 2][m] = '/';
    else
      arr[2 * tag - 2][x] = '\\';
  }
  if (T->lchild != NULL)
    PrintTree(tag + 1, T->lchild, x, (x + m) / 2 - 1, 1);
  if (T->rchild != NULL)
    PrintTree(tag + 1, T->rchild, (x + m) / 2 + 1, m, 0);
}

// 计算二叉树的深度
int Depth(BiNode *T) {
  int m, n;
  if (T == NULL)
    return 0;
  else {
    m = Depth(T->lchild);
    n = Depth(T->rchild);
    if (m > n)
      return (m + 1);
    else
      return (n + 1);
  }
}

bool Judge(int i, int j, int n) {
  for (int k = j + 1; k <= n; k++) {
    if (arr[i][k] != ' ')
      return 1;
  }
  return 0;
}

int main() {
  string str1; // 中序表达式
  cin >> str1;
  int n; // 变量个数
  cin >> n;
  string str2 = Change(str1); // str2为后序表达式
  BiNode *T = CreatTree(str2);
  int sum = Count(str2, n);
  int dp = Depth(T);
  cout << str2 << endl;
  memset(arr, ' ', sizeof(arr));
  PrintTree(1, T, 1, pow(2.0, dp) - 1, 0);
  for (int i = 1; i <= 2 * dp - 1; i++) {
    for (int j = 1; j <= pow(2.0, dp) - 1; j++) {
      cout << arr[i][j];
      if (arr[i][j] != ' ') {
        if (Judge(i, j, pow(2.0, dp) - 1))
          continue;
        else
          break;
      }
    }
    cout << endl;
  }
  cout << sum << endl;
  return 0;
}
题目详情
668 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

拼写检查

现在有一些英语单词需要做拼写检查, 你的工具是一本词典。 需要检查的单词, 有的是词典中的单词, 有的与词典中的单词相似, 你的任务是发现这两种情况。 单词 A 与单词 B 相似的情况有三种:

1、 删除单词 A 的一个字母后得到单词 B;

2、 用任意一个字母替换单词 A 的一个字母后得到单词 B;

3、 在单词 A 的任意位置增加一个字母后得到单词 B。

你的任务是发现词典中与给定单词相同或相似的单词。

时间限制: 2000

内存限制: 65536

输入

第一部分是词典中的单词, 从第一行开始每行一个单词, 以"#"结束。

词典中的单词保证不重复, 最多有 10000 个。 第二部分是需要查询的单词, 每行一个, 以"#"结束。 最多有 50 个需要查询的单词。 词典中的单词和需要查询的单词均由小写字母组成, 最多包含 15 个字符。

输出

按照输入的顺序, 为每个需要检查的单词输出一行。 如果需要检查的单词出现在词典中, 输出“?x is correct", ?x 代表需要检查的单词。

如果需要检查的单词没有出现在词典中, 则输出"?x: ?x1 ?x2 ...?xn",其中?x 代表需要检查的单词, ?x1...?xn 代表词典中与需要检查的单词相似的单词, 这些单词中间以空格隔开。 如果没有相似的单词, 输出"?x:"即可。

样例输入

i
is
has
have
be
my
more
contest
me
too
if
award
#
me
aware
m
contest
hav
oo
or
i
fi
mre
#

样例输出

me is correct
aware: award
m: i my me
contest is correct
hav: has have
oo: too
or:
i is correct
fi: i
mre: more me
答案与解析
参考答案
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>

using namespace std;
bool IsSame(string a, string b) {
  char drop;
  // a短
  int mi = min(a.length(), b.length());
  string a1 = a;
  string b1 = b;
  sort(a1.begin(), a1.end());
  sort(b1.begin(), b1.end());
  bool exis = false;
  for (int i = 0; i < mi; i++) {
    if (a1[i] != b1[i]) {
      drop = b1[i];
      exis = true;
      break;
    }
  }

  if (!exis) {
    drop = b1[b1.length() - 1];
  }
  string ti;
  bool ex = false;
  for (int i = 0; i < a.length(); i++) {
    if (a[i] != b[i]) {
      ex = true;
      ti = a.substr(0, i);
      ti = ti + drop;
      ti = ti + a.substr(i, 1000);
      break;
    }
  }
  if (!ex) {
    ti = a + drop;
  }
  if (ti != b) {
    return false;
  } else {
    return true;
  }
}
int main() {
  string dictionary[10010];
  string words[60];
  string a, b;
  int dic = 0;
  int m = 0;
  while (1) {
    cin >> a;
    if (a == "#") {
      break;
    } else {
      dictionary[dic++] = a;
    }
  }
  while (1) {
    cin >> b;
    if (b == "#") {
      break;
    } else {
      words[m++] = b;
    }
  }
  for (int i = 0; i < m; i++) {
    bool you = false;
    for (int j = 0; j < dic; j++) {
      if (dictionary[j] == words[i]) {
        cout << words[i] << " is correct" << endl;
        you = true;
        break;
      }
    } // 判断是否完全相同。

    if (you != true) {
      cout << words[i] << ": ";
      for (int j = 0; j < dic; j++) {
        int somewhat = words[i].length() - dictionary[j].length();
        if (somewhat == 0) {
          for (int k = 0; k < words[i].length(); k++) {
            if (words[i][k] != dictionary[j][k]) {
              string tishen = words[i];
              tishen[k] = dictionary[j][k];
              if (tishen == dictionary[j]) {
                cout << dictionary[j] << " ";
              }
            }
          }
        }
        if (abs(somewhat) == 1) {
          if (words[i].length() > dictionary[j].length()) {
            if (IsSame(dictionary[j], words[i])) {
              cout << dictionary[j] << " ";
            }
          } else {
            if (IsSame(words[i], dictionary[j])) {
              cout << dictionary[j] << " ";
            }
          }
        }
      }
      cout << endl;
    }
  }
  system("pause");
}
题目详情
669 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

数字变换

给定一个包含 5 个数字(0-9)的字符串, 例如 “02943”, 请将“12345”变换到它。 你可以采取 3 种操作进行变换

1. 交换相邻的两个数字

2. 将一个数字加 1。 如果加 1 后大于 9, 则变为 0

3. 将一个数字加倍。 如果加倍后大于 9,则将其变为加倍后的结果除以 10 的余数。

最多只能用第 2 种操作 3 次, 第 3 种操作 2 次 求最少经过多少次操作可以完成变换。

时间限制: 1000

内存限制: 65536

输入

有最多 100,000 组数据 每组数据就是包含 5 个数字的字符串

输出

对每组数据, 输出将"12345"变换到给定字符串所需要的最少操作步数。 如果无法变换成功, 输出-1

样例输入

12435
99999
12374

样例输出

1
-1
3

提示

由于测试数据太多, 如果对每组数据都从头进行搜索, 就会超时。 建议先做预处理, 即以“12345” 作为初始状态做一遍彻底的广搜, 找出“12345” 经合法变换能够到达的所有字符串, 并记录到达这些字符串各需要多少步操作。 然后对读入的每组数据, 在上述预处理记录的结果中进行查询即可。

答案与解析
参考答案
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>

using namespace std;
#define _init(x, v) memset(x, v, sizeof(x))

int rcd[100000];
bool vis[100000][5][5];

struct node {
  int a[5], d, o2, o3;
};
queue<node> q;

void in() {
  _init(rcd, -1);
  node s = {1, 2, 3, 4, 5, 0, 3, 2};
  q.push(s);
  vis[12345][3][2] = 1;
  rcd[12345] = 0;
}

int toNum(node &n) {
  int t = 0;
  for (int i = 0; i < 5; ++i) {
    t *= 10;
    t += n.a[i];
  }
  return t;
}

void bfs() {
  while (!q.empty()) {
    node s = q.front();
    int t = toNum(s);
    if (rcd[t] == -1 || rcd[t] > s.d)
      rcd[t] = s.d;
    // printf("n = %d, d = %d, o2 = %d, o3 = %d\n", toNum(s), s.d, s.o2, s.o3);
    ++s.d;
    q.pop();
    for (int i = 0; i < 5; ++i) {
      // o1
      if (i < 4 && s.a[i] != s.a[i + 1]) {
        swap(s.a[i], s.a[i + 1]);
        if (!vis[toNum(s)][s.o2][s.o3]) {
          vis[toNum(s)][s.o2][s.o3] = 1;
          q.push(s);
        }
        swap(s.a[i], s.a[i + 1]);
      }
      // o2
      if (s.o2 > 0) {
        --s.o2;
        s.a[i] = (s.a[i] + 1) % 10;
        if (!vis[toNum(s)][s.o2][s.o3]) {
          vis[toNum(s)][s.o2][s.o3] = 1;
          q.push(s);
        }
        s.a[i] = (s.a[i] + 10 - 1) % 10;
        ++s.o2;
      }
      // o3
      if (s.o3 > 0) {
        --s.o3;
        int bak = s.a[i];
        s.a[i] = (2 * s.a[i]) % 10;
        if (!vis[toNum(s)][s.o2][s.o3]) {
          vis[toNum(s)][s.o2][s.o3] = 1;
          q.push(s);
        }
        s.a[i] = bak;
        ++s.o3;
      }
    }
  }
}

int main() {
  in();
  bfs();
  int n;
  while (cin >> n) {
    cout << rcd[n] << endl;
  }
  system("pause");
  return 0;
}
题目详情
670 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

神奇的数列

一个正整数数列, 可以将它切割成若干个数据段, 每个数据段由值相同的相邻元素构成。 该数列的神奇之处在于, 每次切除一个数据段后,该数据段前后的元素自动连接在一起成为邻居。 例如从数列“2 8 9 77 6 9 4” 中切除数据段“7 7 ” 后, 余下的元素会构成数列“2 8 9 6 94”

请问若要将该数列切割成若干个数据段, 则至少会切出来几个数据段?

样例: 按下列顺序切割数列“2 8 9 7 7 6 9 4” , 只要切割成 6 段

切割出“7 7” , 余下 “2 8 9 6 9 4”

切割出 “6” , 余下 “2 8 9 9 4”

切割出 “9 9” , 余下 “2 8 4”

切割出 “2” , 余下 “8 4”

切割出 “8” , 余下 “4”

时间限制: 1000

内存限制: 65536

输入

第一行是一个整数, 示共有多少组测试数据。 每组测试数据的输入包括两行: 第一行是整数 N, N<=200,表示数列的长度, 第二行是 N 个正整数。

输出

每个测试案例的输出占一行, 是一个整数。 格式是: Case n: x n 是测试数据组编号, x 是答案

样例输入

2
8
2 8 9 7 7 6 9 4
16
2 8 9 7 7 6 9 4 4 2 8 4 2 7 6 9

样例输出

Case 1: 6
Case 2: 11
答案与解析
参考答案
#include <cstring>
#include <iostream>

using namespace std;
int score[202][202];
int N;
int num[202];
int main() {
  int T;
  // cin >> T;
  // freopen("C:\\Users\\csctest\\Desktop\\slin.txt", "r", stdin);
  // freopen("C:\\Users\\csctest\\Desktop\\sloutx.txt", "w", stdout);
  scanf("%d", &T);
  int T0 = T;
  while (T--) {
    /*for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                    score[i][j] = 256;
            }
    }*/
    memset(score, 1, sizeof(score));
    memset(num, 0, sizeof(num));
    int N;
    scanf("%d", &N); // cin >> N;
    for (int i = 0; i < N; ++i) {
      scanf("%d", &num[i]); // cin >> num[i];
      score[i][i] = 1;
    }
    for (int i = 0; i < N; ++i) {
      for (int j = 0; j < i; ++j) {
        score[i][j] = 0;
      }
    }
    for (int i = 0; i < N - 1; ++i) {
      if (num[i] == num[i + 1])
        score[i][i + 1] = 1;
      else
        score[i][i + 1] = 2;
    }
    for (int i = N - 2; i >= 0; --i) {
      for (int j = i + 1; j < N; ++j) {
        for (int k = i; k < j; ++k) {
          if (num[k] == num[j]) {
            score[i][j] = min(score[i][j], score[i][k] + score[k + 1][j - 1]);
          }
          score[i][j] = min(score[i][j], score[i][k] + score[k + 1][j]);
        }
      }
    }
    /*
    for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                    if (score[i][j] < 10000 ) printf("%d ", score[i][j]);//cout
    << score[i][j] << " "; else printf("%d ", -1); //cout << -1 << " ";
            }
            printf("\n");//cout << endl;
    }*/
    printf("Case %d: %d\n", T0 - T, score[0][N - 1]);
    // cout << "Case " << T0-T << ": " <<score[0][N-1] << endl;
  }
  return 0;
}
题目详情
671 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

硬币

宇航员 Bob 有一天来到火星上, 他有收集硬币的习惯。 于是他将火星上所有面值的硬币都收集起来了, 一共有 n 种, 每种只有一个: 面值分别为 a1,a2… an。 Bob 在机场看到了一个特别喜欢的礼物, 想买来送给朋友 Alice, 这个礼物的价格是 X 元。 Bob 很想知道为了买这个礼物他的哪些硬币是必须被使用的, 即 Bob 必须放弃收集好的哪些硬币种类。 飞机场不提供找零, 只接受恰好 X 元。

时间限制: 1000

内存限制: 262144

输入

第一行包含两个正整数 n 和 x。 (1 <= n <= 200, 1 <= x <= 10000) 

第二行从小到大为 n 个正整数 a1, a2, a3 … an (1 <= ai <= 10000)

输出

第一行是一个整数, 即有多少种硬币是必须被使用的。 第二行是这些必须使用的硬币的面值(从小到大排列) 。

样例输入

5 18
1 2 3 5 10

样例输出

2
5 10

提示

输入数据将保证给定面值的硬币中至少有一种组合能恰好能够支付 X元。 如果不存在必须被使用的硬币, 则第一行输出 0, 第二行输出空行。

答案与解析
参考答案
#include <iostream>
using namespace std;
int val[210] = {0};
int ways[10000] = {0};
int ans[210] = {0};

int cal(int x, int y) {
  if (x < 0)
    return 0;
  return ways[x] - cal(x - y, y);
}

int main() {
  int N, Max;
  cin >> N >> Max;
  for (int i = 1; i <= N; ++i)
    cin >> val[i];
  ways[0] = 1;
  for (int i = 1; i <= N; ++i)
    for (int j = Max; j >= val[i]; --j)
      ways[j] += ways[j - val[i]];
  int cnt = 0;
  for (int i = 1; i <= N; ++i)
    if (cal(Max, val[i]) == 0)
      ans[cnt++] = val[i];
  cout << cnt << endl;
  if (cnt == 0)
    cout << ' ' << endl;
  else {
    cout << ans[0];
    for (int i = 1; i < cnt; ++i)
      cout << ' ' << ans[i];
  }
  return 0;
}
题目详情
672 简答题 偏难 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 <stdio.h>
#include <string.h>
int max(int a, int b) {
  if (a > b)
    return a;
  else
    return b;
}
int main() {
  char s1[201], s2[201];
  while (scanf("%s %s", s1, s2) != EOF) {
    int dp[201][201];
    memset(dp, 0, sizeof(dp));
    int m = strlen(s1), n = strlen(s2);
    for (int i = 1; i <= m; i++) {
      for (int j = 1; j <= n; j++) {
        if (s1[i - 1] == s2[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1] + 1;
        } else {
          dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
      }
    }
    printf("%d\n", dp[m][n]);
  }
  return 0;
}
题目详情
673 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

和数

给定一个正整数序列,判断其中有多少个数,等于数列中其他两个数的和。 比如,对于数列1 2 3 4, 这个问题的答案就是2, 因为3 = 2 + 1, 4 = 1 + 3。

时间限制:10000

内存限制:65536

输入

共两行,第一行是数列中数的个数n ( 1 <= n <= 100),第二行是由n个不大于10000的正整数组成的数列,相邻两个整数之间用单个空格隔开。

输出

一个整数,即数列中等于其他两个数之和的数的个数。

样例输入

4

1 2 3 4

样例输出

2

答案与解析
参考答案
#include <cstdio>
#include <iostream>
using namespace std;
int a[105];
int main() {
  int n, ans = 0;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    bool f = false;
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < n; k++) {
        if (i != j && i != k && j != k && a[i] == a[j] + a[k]) {
          f = true;
        }
      }
    }
    if (f == true)
      ans++;
  }
  cout << ans;
  return 0;
}
题目详情
674 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

分解因数

给出一个正整数a,要求分解成若干个正整数的乘积,即a = a1 * a2 * a3 * ... * an,并且1 < a1 <= a2 <= a3 <= ... <= an,问这样的分解的种数有多少。注意到a = a也是一种分解。

时间限制:1000

内存限制:65536

输入

第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数a (1 < a < 32768)

输出

n行,每行输出对应一个输入。输出应是一个正整数,指明满足要求的分解的种数

样例输入

2
2
20

样例输出

1
4
答案与解析
参考答案
#include <iostream>
using namespace std;
int cnt;
void fenjie(int x, int y) {
  if (x == 1) {
    cnt++;
    return;
  }
  for (int i = y; i <= x; i++) {
    if (x % i == 0) {
      fenjie(x / i, i);
    }
  }
  return;
}
int main() {
  int n, m;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> m;
    cnt = 0;
    fenjie(m, 2);
    cout << cnt << endl;
  }
  return 0;
}
题目详情
675 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

丛林探险

一、准备工作

(1)删除默认小猫角色,添加角色:Avery&nbsp;Walking;

(2)添加背景:Bedroom 3、Jungle。

二、功能实现

(1)点击绿旗,初始背景为Bedroom 3,小女孩初始造型为avery walking-a,初始位置在舞台左侧,面向右方;

题干图片

(2) 1秒后,小女孩从舞台左侧切换着造型移动到舞台右侧;

题干图片

(3) 舞台切换为Jungle背景。

题干图片

答案与解析
参考答案

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

小鸟展翅

1.准备工作

(1)删除默认小猫角色,添加角色:Parrot;

(2)添加背景:Woods And Bench、Blue Sky。

2.功能实现

(1)点击绿旗,鹦鹉初始位置在舞台左侧,初始造型为“parrot-a”,初始背景为“Woods And Bench”;

(2)1秒后,播放声音Bird的同时,小鸟扇动翅膀向右侧飞行,一直飞行到舞台最右侧;

(3)背景切换为“Blue Sky”,鹦鹉重新回到左侧;

(4)继续飞行到舞台中间位置。

答案与解析
参考答案

题目详情
677 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.3 造型与背景标签

大棕熊的冬去春来

1.准备工作     

(1)添加背景:Winter、Forest;

(2)删除默认小猫角色,添加角色:Bear-walking。

2.功能实现     

(1)点击绿旗,初始背景为Winter,棕熊初始造型为bear-walk-a,它初始位置在舞台左侧,面向右;

(2)棕熊从舞台左侧向右走,每走20步,切换下一个造型,等待1秒;

(3)当棕熊走到100步时停止走动,切换成下一个背景。

答案与解析
参考答案

参考程序:

Bear-walking  

评分标准: 

(1)能正确添加背景角色;(3分)

(2)角色初始造型、位置及背景设置正确;(3分)

(3)角色Bear-walking从舞台左侧向右走,每走20步,切换下一个造型,等待1秒;(6分)

(4)当Bear-walking走到100步时,切换成下一个背景。(3分)

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

乌鸦喝水

1.准备工作

(1)添加背景:Desert;

(2)删除默认小猫角色,添加角色:Toucan、Glass Water。

2.功能实现

(1)乌鸦的初始位置在舞台左下角,面向右,水杯的初始位置在舞台右下角,如下图所示;

(2)乌鸦播放声音pop;

(3)乌鸦移动到水杯的位置,注意能看到移动过程;

(4)乌鸦到达水杯边上后,水杯切换为空造型。

答案与解析
参考答案

答案解析:

乌鸦

水杯

评分标准:

(1)背景添加正确,角色添加正确;(2分)

(2)乌鸦和水杯的初始位置正确;(2分)

(3)水杯初始造型正确;(1分)

(4)能播放pop声音;(3分)

(5)乌鸦能水平向右移到水杯旁边,能看到移动过程;(5分)(看不到移动过程扣3分)

(6)乌鸦到达水杯旁边后,水杯切换为空杯造型。(2分)

题目详情