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

Scratch编程一级 题库

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

小写字母的判断

输入一个字符,判断是否是英文小写字母,即是否是a-z中的一个。

时间限制:1000

内存限制:65536

输入

一个字符。

输出

如果是英文小写字母,则输出yes,否者输出no。

样例输入

k

样例输出

yes
答案与解析
参考答案
#include <iostream>
using namespace std;
int main() {
  char name;
  cin >> name;
  if (name >= 'a' && name <= 'z')
    cout << "yes";
  else
    cout << "no";
  return 0;
}
题目详情
642 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

与7无关的数

一个正整数,如果它能被7整除,或者它的十进制表示法中某一位上的数字为7,则称其为与7相关的数.现求所有小于等于n(n < 100)的与7无关的正整数的平方和.

时间限制:1000

内存限制:65536

输入

输入为一行,正整数n(n < 100)

输出

输出一行,包含一个整数,即小于等于n的所有与7无关的正整数的平方和。

样例输入

21

样例输出

2336
答案与解析
参考答案
#include <iostream>
using namespace std;
int main() {
  int n;
  cin >> n;
  int m = 0;
  for (int i = 1; i <= n; i++) {
    if (i % 7 != 0 && i / 10 % 10 != 7 && i % 10 != 7) {
      m = m + i * i;
    }
  }
  cout << m;
  return 0;
}
题目详情
643 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

发现它,抓住它

一个城市中有两个犯罪团伙A和B,你需要帮助警察判断任意两起案件是否是同一个犯罪团伙所为,警察所获得的信息是有限的。假设现在有N起案件(N<=100000),编号为1到N,每起案件由团伙A或团伙B所为。你将按时间顺序获得M条信息(M<=100000),这些信息分为两类:

D [a] [b]

其中[a]和[b]表示两起案件的编号,这条信息表明它们属于不同的团伙所为

A [a] [b]

其中[a]和[b]表示两起案件的编号,这条信息需要你回答[a]和[b]是否是同一个团伙所为

注意你获得信息的时间是有先后顺序的,在回答的时候只能根据已经接收到的信息做出判断。

时间限制:1000

内存限制:65536

输入

第一行是测试数据的数量T(1<=T<=20)。 每组测试数据的第一行包括两个数N和M,分别表示案件的数量和信息的数量,其后M行表示按时间顺序收到的M条信息。

输出

对于每条需要回答的信息,你需要输出一行答案。如果是同一个团伙所为,回答"In the same gang.“,如果不是,回答"In different gangs.”,如果不确定,回答”Not sure yet."。

样例输入

1
5 5
A 1 2
D 1 2
A 1 2
D 2 4
A 1 4

样例输出

Not sure yet.
In different gangs.
In the same gang.
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
template <class T> struct DisjointSet {
  int *parent;
  T *data;
  map<T, int> m;
  int capacity;
  int size;
  DisjointSet(int max = 1000) {
    capacity = max;
    size = 0;
    parent = new int[max + 1];
    data = new T[max + 1];
  }
  ~DisjointSet() {
    delete[] parent;
    delete[] data;
  }
  bool insert(T x) {
    if (size == capacity)
      return false;
    size++;
    data[size] = x;
    parent[size] = -1;
    m[x] = size;
    return true;
  }
  int getIndex(T x) {
    for (int i = 1; i <= size; i++)
      if (data[i] == x)
        return i;
    return -1;
  }
  int find(T x) {
    typename map<T, int>::iterator it;
    it = m.find(x);
    if (it == m.end())
      return -1;
    int i, rt;
    i = rt = it->second;
    while (parent[rt] > 0)
      rt = parent[rt];
    return rt;
  }
  void unionSet(T x, T y) {
    int rx, ry;
    rx = find(x);
    ry = find(y);
    if (rx == -1 || ry == -1)
      return;
    if (rx == ry)
      return;
    if (parent[rx] < parent[ry]) {
      parent[rx] += parent[ry];
      parent[ry] = rx;
    } else {
      parent[ry] += parent[rx];
      parent[rx] = ry;
    }
    find(x);
    find(y);
  }
};
int main() {
  int t;
  cin >> t;
  while (t--) {
    DisjointSet<int> s;
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
      s.insert(i);
    for (int i = 1; i <= m; i++) {
      int a, b;
      char c;
      cin >> c >> a >> b;
      if (c == 'D')
        s.unionSet(a, b);
      else {
        if (s.find(a) != s.find(b))
          cout << "Not sure yet.";
        else if (s.parent[a] == s.parent[b])
          cout << "In the same gang.";
        else
          cout << "In different gangs.";
        cout << endl;
      }
    }
  }
  return 0;
}
题目详情
644 简答题 偏难 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;
}
题目详情
645 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

Sequence

给定m个数字序列,每个序列包含n个非负整数。我们从每一个序列中选取一个数字组成一个新的序列,显然一共可以构造出nm个新序列。接下来我们对每一个新的序列中的数字进行求和,一共会得到nm个和,请找出最小的n个和

时间限制:3000

内存限制:65536

输入

输入的第一行是一个整数T,表示测试用例的数量,接下来是T个测试用例的输入 每个测试用例输入的第一行是两个正整数m(0 < m <= 100)和n(0 < n <= 2000),然后有m行,每行有n个数,数字之间用空格分开,表示这m个序列 序列中的数字不会大于10000

输出

对每组测试用例,输出一行用空格隔开的数,表示最小的n个和

样例输入

1
2 3
1 2 3
2 2 3

样例输出

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

using namespace std;
priority_queue<int> que;
int a[2005];
int b[2005]; // 用作中间数组
int main() {
  int T;
  cin >> T;
  int m, n;
  while (T--) {
    cin >> m >> n;
    for (int i = 0; i < n; i++) {
      scanf("%d", &a[i]);
    }
    sort(a, a + n);             // 用a做总的和数组
    for (int i = 1; i < m; i++) // 轮接下来的序列
    {
      for (int j = 0; j < n; j++) {
        scanf("%d", &b[j]);
        que.push(a[0] + b[j]);
      }
      for (int j = 1; j < n; j++) {
        for (int k = 0; k < n; k++) {
          if (a[j] + b[k] < que.top()) {
            que.pop();
            que.push(a[j] +
                     b[k]); // 比最大值小就顶了它,想要得到ab两个里面最小的n个数
          }
        }
      }
      for (int i = 0; i < n; i++) {
        a[n - i - 1] = que.top(); // 由于是最大值堆,要反过来让a有序
        que.pop();                // 队列已经被清空了,轮下一次
      }
    }
    for (int i = 0; i < n - 1; i++)
      printf("%d ", a[i]);
    printf("%d\n", a[n - 1]);
  }
  return 0;
}
题目详情
646 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

stack or queue

栈和队列都是常用的线性结构,它们都提供两个操作:

Push:加入一个元素。

Pop:弹出一个元素。

不同的是,栈是”先进后出”,而队列则是”先进先出”。

给出一个线性结构的进出顺序,判定这个结构是栈还是队列。

时间限制:1000

内存限制:65535

输入

第一行输入一个整数t,代表有t组测试数据 对于每组测试数据,第一行输入一个整数n,代表操作的次数。 随后输入n行,每行包含两个整数 type val。 当type = 1时,表示该次操作为push操作,val表示进入的数字。当type=2时,表示该次操作为pop操作,val代表出来的数字。 3<=n<=2000

输出

每组测试数据输出一行。 输出该组数据对应的线性结构,”Stack” 或者 “Queue”。 题目保证是栈或者队列的一种。

样例输入

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

样例输出

Stack
Queue
答案与解析
参考答案
#include <deque>
#include <iostream>

using namespace std;
int main() {
  int t;
  scanf("%d", &t);
  deque<int> ds; // imitating stack
  for (int i = 0; i < t; i++) {
    int n;
    bool tag = false;
    scanf("%d", &n);
    for (int j = 0; j < n; j++) {
      int type, val;
      scanf("%d%d", &type, &val);
      if (tag)
        continue;
      if (type == 1) {
        ds.push_back(val);
      } else {
        int s = ds.back();
        ds.pop_back();
        if (s != val) {
          printf("Queue\n");
          tag = true;
        }
      }
    }
    if (!tag)
      printf("Stack\n");
    ds.clear();
  }
}
题目详情
647 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

栈的基本操作

栈是一种重要的数据结构,它具有push k和pop操作。push k是将数字k加入到栈中,pop则是从栈中取一个数出来。

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

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

      push 5          pop

1

栈 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
4
push 1
push 3
pop
push 5
1
pop

样例输出

1 5
error
答案与解析
参考答案
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define M 1000
typedef struct {
  int num[M];
  int top;
} stack;
void push(stack *p, int i) {
  if (p->top == M - 1)
    return;
  else {
    p->num[++(p->top)] = i;
    return;
  }
}
int pop(stack *p) {
  if (p->top == -1) {
    return 0;
  } else
    return (p->num[(p->top)--]);
}
int main() {
  int m, n, i, j;
  char s[5];
  stack *p;
  scanf("%d", &m);
  while (m--) {
    int t = 0;
    p = (stack *)malloc(sizeof(stack));
    p->top = -1;
    scanf("%d", &n);
    while (n--) {
      scanf("%s", s);
      if (strcmp(s, "push") == 0) {
        scanf("%d", &i);
        push(p, i);
      } else {
        if (p->top == -1)
          t = 1;
        pop(p);
      }
    }
    if (t == 1)
      printf("error\n");
    else {
      if (p->top != -1) {
        for (j = 0; j < (p->top); j++)
          printf("%d ", p->num[j]);
        printf("%d\n", p->num[p->top]);
      }
    }
  }
  return 0;
}
题目详情
648 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

合影效果

小云和朋友们去爬香山,为美丽的景色所陶醉,想合影留念。如果他们站成一排,男生全部在左(从拍照者的角度),并按照从矮到高的顺序从左到右排,女生全部在右,并按照从高到矮的顺序从左到右排,请问他们合影的效果是什么样的(所有人的身高都不同)?

时间限制:1000

内存限制:65536

输入

第一行是人数n(2 <= n <= 40,且至少有1个男生和1个女生)。 后面紧跟n行,每行输入一个人的性别(男male或女female)和身高(浮点数,单位米),两个数据之间以空格分隔。

输出

n个浮点数,模拟站好队后,拍照者眼中从左到右每个人的身高。每个浮点数需保留到小数点后2位,相邻两个数之间用单个空格隔开。

样例输入

6
male 1.72
male 1.78
female 1.61
male 1.65
female 1.70
female 1.56

样例输出

1.65 1.72 1.78 1.70 1.61 1.56
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<float> Men;
  vector<float> Women;
  string gender;
  float height;
  for (int i = 1; i <= n; i++) {
    cin >> gender >> height;
    if (gender == "male") {
      Men.push_back(height);
    } else if (gender == "female") {
      Women.push_back(height);
    }
  }
  sort(Men.begin(), Men.end(), less<float>());        // sort ascending
  sort(Women.begin(), Women.end(), greater<float>()); // sort descending
  cout << setiosflags(ios::fixed);
  copy(Men.begin(), Men.end(),
       ostream_iterator<float>(cout << setprecision(2), " "));
  copy(Women.begin(), Women.end(),
       ostream_iterator<float>(cout << setprecision(2), " "));
  cout << endl;
  return 0;
}
题目详情
649 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

最长上升子序列

一个数的序列bi,当b1 < b2 < … < bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN),我们可以得到一些上升的子序列(ai1, ai2, …, aiK),这里1 <= i1 < i2 < … < iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8). 你的任务,就是对于给定的序列,求出最长上升子序列的长度。

时间限制:11000

内存限制:65536

输入

输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数,这些整数的取值范围都在0到10000。

输出

最长上升子序列的长度。

样例输入

7
1 7 3 5 9 4 8

样例输出

4
答案与解析
参考答案
#include <bits/stdc++.h>
#define fio                                                                    \
  ios::sync_with_stdio(0);                                                     \
  cin.tie(0);                                                                  \
  cout.tie(0);
using namespace std;
const int maxn = 1010;
int a[maxn];
int maxLen[maxn];
int main() {
  fio int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    maxLen[i] = 1;
  }
  for (int i = 2; i <= n; i++) {
    for (int j = 1; j < i; j++) {
      if (a[i] > a[j]) {
        maxLen[i] = max(maxLen[i], maxLen[j] + 1);
      }
    }
  }
  cout << *max_element(maxLen + 1, maxLen + n + 1) << endl;
}
题目详情
650 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

神奇的口袋

有一个神奇的口袋,总的容积是40,用这个口袋可以变出一些物品,这些物品的总体积必须是40。John现在有n个想要得到的物品,每个物品的体积分别是a1,a2……an。John可以从这些物品中选择一些,如果选出的物体的总体积是40,那么利用这个神奇的口袋,John就可以得到这些物品。现在的问题是,John有多少种不同的选择物品的方式。

时间限制:10000

内存限制:65536

输入

输入的第一行是正整数n (1 <= n <= 20),表示不同的物品的数目。接下来的n行,每行有一个1到40之间的正整数,分别给出a1,a2……an的值。

输出

输出不同的选择物品的方式的数目。

样例输入

3
20
20
20

样例输出

3
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int goods[30];
// 从前k种物品中选择一些,凑成体积w的做法数目
int ways(int w, int k) {
  if (w == 0)
    return 1; // 没有需要凑的体积了,刚好凑满
  if (k <= 0)
    return 0; // 还差体积或者体积过了,但是没有物品可以选了。

  if (w >= goods[k]) {
    return ways(w, k - 1) +
           ways(w - goods[k], k - 1); // 体积:选择第k种物品 + 不选第k种物品
  } else {
    return ways(w, k - 1);
  }
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &goods[i]);
  }
  printf("%d", ways(40, n));
  return 0;
}
题目详情
651 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.4 新建保存与语言选择

滑雪

Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子

1 2 3 4 5

16 17 18 19 6

15 24 25 20 7

14 23 22 21 8

13 12 11 10 9

一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上,这是最长的一条。

时间限制:1000

内存限制:65536

输入

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。

输出

输出最长区域的长度。

样例输入

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

样例输出

25
答案与解析
参考答案
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
// 控制方向的常用方法
int n, m, a[205][205], s[205][205], ans;
int dfs(int x, int y) {
  if (s[x][y])
    return s[x][y];
  s[x][y] = 1; // 自身算一个距离
  for (int i = 0; i < 4; i++) {
    int tx = dx[i] + x, ty = dy[i] + y;
    if (tx > 0 && tx <= n && ty >= 1 && ty <= m && a[x][y] > a[tx][ty]) {
      dfs(tx, ty);
      s[x][y] = max(s[x][y], s[tx][ty] + 1);
      // 记忆化
    }
  }
  return s[x][y];
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      scanf("%d", &a[i][j]);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
      ans = max(ans, dfs(i, j)); // 将每个点当成起点做dfs
  printf("%d", ans);
  return 0;
}

解题思路

采用递推的动态规划方式求解

先用结构体保存每个点对应的原本坐标位置和高度;

将所有点按高度从小到大排序;

用一个二维数组保存输入的原本数据,

再用一个二维数组保存对应位置的最大滑行距离;

从第二个点开始求解(因为第一个点高度最低,显然滑行距离为1)

依次和它在原本坐标里的上下左右四个方向进行判断,

如果它比某一方向上的高度高,则它的滑行距离就应该是相比较的最大滑行距离+1和它保存的最大滑行距离中的最大值。

最后求完总共的点,进行遍历,得到最终最大值。

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

课程冲突

小 A 修了 n 门课程, 第 i 门课程是从第 ai 天一直上到第 bi 天。

定义两门课程的冲突程度为 : 有几天是这两门课程都要上的。

例如 a1=1,b1=3,a2=2,b2=4 时, 这两门课的冲突程度为 2。

现在你需要求的是这 n 门课中冲突程度最大的两门课的冲突程度。

时间限制:1000

内存限制:65536

输入

第一行一个正整数 n 表示课程数量。接下来 n 行,每行两个正整数 ai,bi。 2 ≤ n≤ 1000, 1 ≤ai ≤bi ≤ 1000。

输出

输出一个整数表示最大的冲突程度。

样例输入

3
1 3
2 4
5 5

样例输出

2
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
// #define PPYDEBUG
struct lesson {
  int no; // 课程编号
  int a;  // 课程开始a天
  int b;  // 课程结束b天
};
int max_chongtu(lesson x, lesson y) {
  int r = min(x.b, y.b) - max(x.a, y.a) + 1;
  if (r < 0) {
    r = 0;
  }
#ifdef PPYDEBUG
  printf("%d = x[%d,%d] - y[%d,%d]\n", r, x.a, x.b, y.a, y.b);
#endif
  return r;
}
int main() {
#ifdef LOCAL
  freopen("202209_3_1.in", "r", stdin);
#endif
  int n;
  scanf("%d", &n);
  lesson le[1010];
  for (int i = 0; i < n; i++) {
    le[i].no = i + 1;
    scanf("%d%d", &le[i].a, &le[i].b);
  }
  int r = 0;
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      r = max(r, max_chongtu(le[i], le[j]));
    }
  }
  printf("%d", r);
  return 0;
}
题目详情
653 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

最长下坡

小明天天沿着未名湖环湖路跑,有时候也觉得蛮累。

累的时候跑下坡就很开心。小明想知道最长的一段下坡有多长。

环湖路是个圆形,周长n米。每隔一米测一下路面高度,两个测高点之间的高度是单调变化或不变的。

问最长的一段下坡有多少米长。小明只能顺时针跑。下坡必须高度单调减少。

时间限制:1000

内存限制:65536

输入

第一行是整数n,表示环湖路一共n米长(2<=n<=100)。 第二行是n个整数,每个整数范围[0,10000],按顺时针顺序给出了n个测高点的高度。

输出

最长下坡路段的长度。

样例输入

样例输入1:

5
2 1 5 6 3

样例输入2:

5
2 1 5 4 3

样例输入3:

4
1 1 1 1

样例输出

样例输出1:

3

样例输出2:

4

样例输出3:

0

提示

这是个简单枚举题,枚举起点即可

答案与解析
参考答案
#include <stdio.h>
int main() {
  int n, i, max = 0, t = 0, s;
  int a[100];
  scanf("%d", &n);
  for (i = 0; i < n; i++)
    scanf("%d", &a[i]);

  s = a[0];
  for (i = 1; i < n; i++) {
    if (a[i] < s)
      t++;
    else {
      if (t > max)
        max = t;
      t = 0;
    }
    s = a[i];
  }
  for (i = 0; i < n; i++) {
    if (a[i] < s)
      t++;
    else {
      if (t > max)
        max = t;
      break;
    }
    s = a[i];
  }
  printf("%d", max);
  return 0;
}
题目详情
654 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

放苹果

把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。

时间限制:1000

内存限制:65536

输入

第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10。

输出

对输入的每组数据M和N,用一行输出相应的K。

样例输入

1
7 3

样例输出

8
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int dp(int m, int n) {
  if (m == 0 or n == 1) {
    // 如果,碟子只有1个,无论苹果有多少个都只有一种放法
    return 1;
  }
  if (n > m) {
    // 如果,碟子的个数大于苹果的个数
    return dp(m, m);
  } else {
    return dp(m, n - 1) + dp(m - n, n);
  }
}
int main() {
#ifdef LOCAL
  freopen("202209_3_5.in", "r", stdin);
#endif
  int t;
  scanf("%d", &t);
  int n, m;
  for (int i = 0; i < t; i++) {
    scanf("%d%d", &m, &n);
    printf("%d", dp(m, n));
  }
  return 0;
}
题目详情
655 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

统计误差范围内的数

统计一个整数序列中与指定数字m误差范围小于等于X的数的个数。

时间限制:5000

内存限制:65536

输入

输入包含三行:

第一行为N,表示整数序列的长度(N <= 100);

第二行为N个整数,整数之间以一个空格分开;

第三行包含2个整数,为指定的整数m,误差范围X。

输出

输出为N个数中与指定数字m误差范围小于等于X的数的个数。

样例输入

5
1 2 3 4 5
3 1

样例输出

3

提示

样例中2,3,4都满足条件,故答案为3

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef LOCAL
  freopen("1.in", "r", stdin);
#endif
  int N;
  scanf("%d", &N);
  int *a = new int[N + 1];
  for (int i = 0; i < N; i++) {
    scanf("%d", &a[i]);
  }
  int m, X;
  scanf("%d%d", &m, &X);
  int count = 0;
  for (int i = 0; i < N; i++) {
    if (abs(a[i] - m) <= X) {
      count = count + 1;
    }
  }
  printf("%d", count);
  return 0;
}
题目详情
656 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

全在其中

你设计了一个新的加密技术,可以用一种聪明的方式在一个字符串的字符间插入随机的字符串从而对信息进行编码。由于专利问题,我们将不会详细讨论如何在原有信息中产生和插入字符串。不过,为了验证你的方法,有必要写一个程序来验证原来的信息是否全在最后的字符串之中。

给定两个字符串s和t,你需要判断s是否是t的“子列”。也就是说,如果你去掉t中的某些字符,剩下字符将连接而成为s。

时间限制:1000

内存限制:65536

输入

输入包括多个测试样例。每一个都是由空格分隔的由字母数字ASCII字符组成的两个特定的字符串s和t。s和t的长度不超过100000

输出

对于每个测试样例,如果s是t的“子列”,则输出”Yes”,否则输出”No”

样例输入

sequence subsequence
person compression
VERDI vivaVittorioEmanueleReDiItalia
caseDoesMatter CaseDoesMatter

样例输出

Yes
No
Yes
No
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
bool isok(string a, string b) {
  int b_start = 0;
  int count = 0;
  for (int i = 0; i < a.length(); i++) {
    for (int j = b_start; j < b.length(); j++) {
      b_start = j + 1;
      if (b[j] == a[i]) {
        count++;
        break;
      }
    }
  }
  if (count == a.length()) {
    return true;
  }
  return false;
}
int main() {
#ifdef LOCAL
  freopen("202209_2_2.in", "r", stdin);
#endif
  string a;
  string b;
  while (cin >> a) {
    cin >> b;
    bool r = isok(a, b);
    if (r == true) {
      printf("Yes\n");
    } else {
      printf("No\n");
    }
  }
  return 0;
}
题目详情
657 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

Lab杯

“Lab杯”乒乓球赛就要在PKU的实验室之间举行了。人工智能实验室的学生都是乒乓球的狂热分子,都强烈希望代表实验室去比赛。但是由于名额限制,他们之中只能由一个人被选作代表。

为了让选择的过程公平,他们决定打一次单循环赛,每一对学生之间都打一场五局三胜的比赛。赢得最多比赛的人就将代表实验室去比赛。现在Ava手里有一份表,表里面记录了每一场比赛的比分。她应该让谁去比赛?

时间限制:5000

内存限制:131072

输入

输入包含一组测试数据。第一行包含n(2 ≤ n ≤ 100),实验室里学生的数目。接下来给出一个n × n矩阵A。矩阵的每一个元素都是0、1、2、3中的一个。第i行第j列的元素aij是第i个学生在和第j个学生的比赛中赢的局数。aij和aji(i ≠ j)正好有一个是3,另外一个小于3。矩阵的所有对角线元素都是0。

输出

输出赢了最多比赛的学生的编号。如果有平分,选择编号最小的。

样例输入

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

样例输出

4
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef LOCAL
  freopen("202209_2_3.in", "r", stdin);
#endif
  int n;
  scanf("%d", &n);

  int a[110][110];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      scanf("%d", &a[i][j]);
    }
  }
  int max_score = 0;
  int no = 1;
  for (int i = 0; i < n; i++) {
    int t = 0;
    for (int j = 0; j < n; j++) {
      t = t + a[i][j];
    }
    if (t > max_score) {
      max_score = t;
      no = i + 1;
    }
  }
  printf("%d", no);
  return 0;
}
题目详情
658 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

有趣的跳跃

一个长度为n(n>0)的序列中存在“有趣的跳跃”当且仅当相邻元素的差的绝对值经过排序后正好是从1到(n-1)。例如,1 4 2 3存在“有趣的跳跃”,因为差的绝对值分别为3,2,1。当然,任何只包含单个元素的序列一定存在“有趣的跳跃”。你需要写一个程序判定给定序列是否存在“有趣的跳跃”。

时间限制:1000

内存限制:65536

输入

一行,第一个数是n(0 < n < 3000),为序列长度,接下来有n个整数,依次为序列中各元素,各元素的绝对值均不超过1,000,000,000

输出

一行,若该序列存在“有趣的跳跃”,输出"Jolly",否则输出"Not jolly"

样例输入

4 1 4 2 3

样例输出

Jolly
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef LOCAL
  freopen("202209_2_4.in", "r", stdin);
#endif
  int n;
  scanf("%d", &n);
  int *a = new int[n + 1]; // 元素列表
  int *b = new int[n + 2]; // 元素差绝对值列表
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 0; i < n - 1; i++) {
    b[i] = abs(a[i] - a[i + 1]);
  }
  // 元素差绝对值列表从小到大排序
  sort(b, b + n - 1);
  for (int i = 0; i < n - 1; i++) {
    if (b[i] != i + 1) {
      printf("Not jolly");
      return 0;
    }
  }
  printf("Jolly");
  return 0;
}
题目详情
659 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

 反反复复

Mo和Larry发明了一种信息加密方法。他们首先决定好列数,然后将信息(只包含字母)从上往下依次填入各列,并在末尾补充一些随机字母使其成为一个完整的字母矩阵。例如,若信息是“There's no place like home on a snowy night”并且有5列,Mo会写成:

t o i o y

h p k n n

e l e a i

r a h s g

e c o n h

s e m o t

n l e w x

注意Mo只会填入字母,且全部是小写形式。在这个例子中,Mo用字母“x”填充了信息使之成为一个完整的矩阵,当然他使用任何字母都是可以的。

Mo根据这个矩阵重写信息:首先从左到右写下第一行,然后从右到左写下第二行,再从左到右写下第三行……以此左右交替地从上到下写下各行字母,形成新的字符串。这样,例子中的信息就被加密为:toioynnkpheleaigshareconhtomesnlewx。

你的工作是帮助Larry从加密后的信息中还原出原始信息(包括填充的字母)。

时间限制:1000

内存限制:65536

输入

第一行包含一个整数(范围2到20),表示使用的列数。 第二行是一个长度不超过200的字符串。

输出

一行,即原始信息。

样例输入

5

toioynnkpheleaigshareconhtomesnlewx

样例输出

theresnoplacelikehomeonasnowynightx
答案与解析
参考答案
#include <stdio.h>
#include <string.h>
char sz[300], a[30][30], b[30][30];
int main() {
  int n, i, j, mm, m, k = 0;
  scanf("%d", &n);
  scanf("%s", sz);
  mm = strlen(sz);
  m = mm / n;

  for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++) {
      a[i][j] = sz[k++];
    }
  }
  for (i = 0; i < m; i++) {
    if (i % 2 == 0) {
      for (j = 0; j < n; j++) {
        b[i][j] = a[i][j];
      }
    }
    if (i % 2 != 0) {
      for (j = 0; j < n; j++) {
        b[i][j] = a[i][n - j - 1];
      }
    }
  }
  for (j = 0; j < n; j++) {
    for (i = 0; i < m; i++) {
      printf("%c", b[i][j]);
    }
  }
}
题目详情
660 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

指定顺序输出

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

时间限制:1000

内存限制:65536

输入

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

输出

一行3个整数c、a、b,整数之间以一个空格分隔。

样例输入

1 2 3

样例输出

3 1 2
答案与解析
参考答案
#include <iostream>
using namespace std;
int main() {
  int a, b, c;
  cin >> a >> b >> c;
  cout << c << " " << a << " " << b;
}
题目详情