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

Scratch编程一级 题库

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

输出整数部分

输入一个双精度浮点数f, 输出其整数部分。

时间限制:1000

内存限制:65536

输入

一个双精度浮点数f(0 < f < 100000000)。

输出

一个整数,表示浮点数的整数部分。

样例输入

3.8889

样例输出

3
答案与解析
参考答案
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
  double a;
  cin >> a;
  int b;
  b = a;
  cout << b;
  return 0;
}
题目详情
1122 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 7.1 逻辑推理

疫情集中隔离

A同学12月初从国外回来,按照防疫要求,需要进行14天集中隔离,请你实现一个程序,根据回国的时间计算集中隔离结束的日期。

比如,12月1号回来,1号当天开始隔离,14号是隔离的最后一天,因此14号是集中隔离结束的日期。

时间限制:1000

内存限制:65536

输入

一个整数x,表示A同学12月x号回国。(1 ≤ x ≤ 15)

输出

一个整数y,表示A同学结束集中隔离的日期(即12月y号A结束集中隔离)。

样例输入

1

样例输出

14
答案与解析
参考答案
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
  int a, b = 1, c = 1;
  cin >> a;
  if (a <= 18) {
    b = a + 13;
  } else {
    b = a - 18;
  }
  cout << b;
  return 0;
}
题目详情
1123 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 2.4 大小设置

字符判断

对于给定的字符,如果该字符是大小写字母或者数字,输出YES, 否则输出NO

时间限制:1000

内存限制:65536

输入

一个字符

输出

按照题目要求输出YES或者NO

样例输入

样例1输入

A

样例2输入

a

样例3输入

1

样例4输入

*

样例输出

样例1输出

YES

样例2输出

YES

样例3输出

YES

样例4输出

NO

提示

【样例输入】、【样例输出】里的多组数据只是给大家提供尽量多的参考,”样例1输入“、”样例1输出“等提示文字也只是为了区别不同的数据,输入输出中不会出现。输入输出的格式按照题目里【输入】【输出】的描述为准。

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

统计数

给定一个数的序列S,以及一个区间[L, R], 求序列中介于该区间的数的个数,即序列中大于等于L且小于等于R的数的个数。

时间限制:1000

内存限制:65536

输入

第一行3个整数n、L、R,分别表示序列的长度,区间的左端点,区间的右端点。(0 < n ≤ 10000, 1 ≤ L ≤ R ≤ 1000000) 第二行n个正整数,表示序列里的每一个数,每个数小于等于10000000

输出

输出一个整数,表示序列中大于等于L且小于等于R的数的个数。

样例输入

5 1 10
11 8 1 10 16

样例输出

3
答案与解析
参考答案
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
  int a, b, c, d, e, g = 0;
  cin >> a >> b >> c;
  for (e = 1; e <= a; e++) {
    cin >> d;
    if (d >= b && d <= c) {
      g++;
    }
  }
  cout << g;
  return 0;
}
题目详情
1125 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

最大质因子

质因子是指能整除给定正整数的质数。而最大质因子是指一个整数的所有质因子中最大的那个。

比如30的质因子有2,3, 5,所以最大质因子就是5。

时间限制:1000

内存限制:65536

输入

一个整数N( 2 ≤ N ≤ 10000)

输出

N的最大质因子

样例输入

30

样例输出

5

提示

质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。

答案与解析
参考答案
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
  int a;
  bool b = true;
  cin >> a;
  for (int i = a; i >= 1; i--) {
    if (a % i == 0) {
      for (int j = 2; j < i; j++) {
        if (i % j == 0)
          b = false;
      }
      if (b == true) {
        cout << i;
        break;
      } else {
        b = true;
      }
    }
  }
  return 0;
}
题目详情
1126 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

双端队列

定义一个双端队列,进队操作与普通队列一样,从队尾进入。出队操作既可以从队头,也可以从队尾。编程实现这个数据结构。

时间限制:1000

内存限制:65535

输入

第一行输入一个整数t,代表测试数据的组数。 每组数据的第一行输入一个整数n,表示操作的次数。 接着输入n行,每行对应一个操作,首先输入一个整数type。

 当type=1,进队操作,接着输入一个整数x,表示进入队列的元素。

 当type=2,出队操作,接着输入一个整数c,c=0代表从队头出队,c=1代表从队尾出队。

n <= 1000

输出

对于每组测试数据,输出执行完所有的操作后队列中剩余的元素,元素之间用空格隔开,按队头到队尾的顺序输出,占一行。如果队列中已经没有任何的元素,输出NULL。

样例输入

2
5
1 2
1 3
1 4
2 0
2 1
6
1 1
1 2
1 3
2 0
2 1
2 0

样例输出

3
NULL
答案与解析
参考答案
//解法1
//用deque模拟一下即可
#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{	
	int n,m,type,x;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>m;
		deque<int> q;
		for(int j=1;j<=m;j++){
			cin>>type>>x;
			if(type==1){
				q.push_back(x);
			}else {
				if(x==0)q.pop_front();
				else q.pop_back();
			}
		}
		if(q.empty()){
			cout<<"NULL";continue;
		}
		while(!q.empty()){
			cout<<q.front()<<" ";
			q.pop_front();
		}
		cout<<endl;
	}
	return 0;
}
//解法2
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>

using namespace std;
int n, t, type, c;
int a[1005] = {0};
int Top = 0, Back = 0;
int main() {
  cin >> t;
  while (t--) {
    Top = 0;
    Back = 0;
    cin >> n;
    while (n--) {
      cin >> type >> c;
      if (type == 1) {
        a[Back++] = c;
      } else {
        if (c == 0) {
          Top++;
        } else {
          Back--;
        }
      }
    }
    if (Top == Back) {
      cout << "NULL" << endl;
    } else {
      for (int i = Top; i < Back; ++i) {
        cout << a[i] << " ";
      }
      cout << endl;
    }
  }
  return 0;
}


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

区间合并

给定 n 个闭区间 [ai; bi],其中i=1,2,...,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如,[1;2] 和 [2;3] 可以合并为 [1;3],[1;3] 和 [2;4] 可以合并为 [1;4],但是[1;2] 和 [3;4] 不可以合并。

我们的任务是判断这些区间是否可以最终合并为一个闭区间,如果可以,将这个闭区间输出,否则输出no。

时间限制:1000

内存限制:65536

输入

第一行为一个整数n,3 ≤ n ≤ 50000。表示输入区间的数量。 之后n行,在第i行上(1 ≤ i ≤ n),为两个整数 ai 和 bi ,整数之间用一个空格分隔,表示区间 [ai; bi](其中 1 ≤ ai ≤ bi ≤ 10000)。

输出

输出一行,如果这些区间最终可以合并为一个闭区间,输出这个闭区间的左右边界,用单个空格隔开;否则输出 no。

样例输入

5
5 6
1 5
10 10
6 9
8 10

样例输出

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

using namespace std;
int t, n, min1, max1;
struct node {
  int x, y;
} a[101000];
int N;
int cmp(const node &w, const node &e) {
  if (w.x > e.x)
    return 0;
  return 1;
}
bool f(int i) {
  min1 = a[1].x;
  if (i == t)
    return 1;
  if (a[i + 1].x >= a[i].x && a[i + 1].x <= max1) {
    max1 = max(max1, a[i + 1].y);
    f(i + 1);
  } else
    return 0;
}
int main() {
  int i = 1;
  cin >> n;
  t = n;
  while (n--) {
    cin >> a[i].x >> a[i].y;
    i++;
  }
  sort(a + 1, a + t + 1, cmp);
  max1 = a[1].y;
  if (f(1))
    printf("%d %d\n", min1, max1);
  else
    printf("no\n");
  return 0;
}
题目详情
1128 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

奇怪的括号

某天小A和同学在课堂上讨论到:“栈这种数据结构真是太优美了,既简单用途又广泛。”小B仰慕小A许久,于是他拿出了自己在网上抄写的一道题问小A,如何判断括号是否匹配呢

时间限制:1000

内存限制:65536

输入

多组数据,每组数据占一行,且都是由(、)、[、]、*、/这六种字符组成。

输出

每组数据输出一行,如果括号能匹配成功,输出True,否则输出False。括号匹配规则是: ( 和 ) 匹配 [ 和 ] 匹配 /* 和 */ 匹配 如果含有冗余字符也算匹配失败,例如 /***/ 是匹配失败的因为中间多了一个*。

样例输入

()/*[()]*/
*/**/

样例输出

True
False
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
  while (cin >> s) {
    stack<char> st;
    for (int i = 0; i < s.size(); i++) {
      if (st.empty()) {
        st.push(s[i]);
      } else {
        if (s[i] == ')' && st.top() == '(')
          st.pop();
        else if (s[i] == ']' && st.top() == '[')
          st.pop();
        else if (s[i] == '/' && st.top() == '*' && st.size() >= 3) {
          st.pop();
          char a = st.top();
          st.pop();
          char b = st.top();
          st.pop();
          if (!(a == '*' && b == '/')) {
            st.push(b);
            st.push(a);
            st.push('*');
          }
        } else
          st.push(s[i]);
      }
    }
    if (st.empty())
      cout << "True" << endl;
    else
      cout << "False" << endl;
  }
  return 0;
}
题目详情
1129 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

合法出栈序列

给定一个由不同小写字母构成的长度不超过8的字符串x,现在要将该字符串的字符依次压入栈中,然后再全部弹出。

要求左边的字符一定比右边的字符先入栈,出栈顺序无要求。

再给定若干字符串,对每个字符串,判断其是否是可能的x中的字符的出栈序列。

时间限制:1000

内存限制:65536

输入

第一行是原始字符串x 后面有若干行,每行一个字符串

输出

对除第一行以外的每个字符串,判断其是否是可能的出栈序列。如果是,输出"YES",否则,输出"NO"

样例输入

abc
abc
bca
cab

样例输出

YES
YES
NO
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
string a, b;
int main() {
  cin >> a;
  while (cin >> b) {
    stack<char> st;
    int j = 0;
    for (int i = 0; i < a.size(); i++) {
      if (!st.empty())
        if (st.top() == b[j]) {
          st.pop();
          j++;
        }
      st.push(a[i]);
    }
    while (!st.empty() && st.top() == b[j] && j < b.size()) {
      st.pop();
      j++;
    }
    if (st.empty())
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }
  return 0;
}
题目详情
1130 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 4.1 移动

抓牛

农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=100000)。农夫有两种移动方式:

1、从X移动到X-1或X+1,每次移动花费一分钟

2、从X移动到2*X,每次移动花费一分钟

假设牛没有意识到农夫的行动,站在原地不动。农夫最少要花多少时间才能抓住牛?

时间限制:2000

内存限制:65536

输入

两个整数,N和K

输出

一个整数,农夫抓到牛所要花费的最小分钟数

样例输入

5 17

样例输出

4
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int b[200100];
int a[10];
queue<int> q;
int n, k;
void bfs(int x) {
  q.push(x);
  b[x] = 1;
  while (!q.empty()) {
    int s = q.front();
    a[1] = s - 1;
    a[2] = s + 1;
    a[3] = 2 * s;
    for (int i = 1; i < 4; i++) {
      if (b[a[i]] == 0 && a[i] >= 0 && a[i] < 100100) {
        b[a[i]] = b[s] + 1;
        q.push(a[i]);
        if (a[i] == k) {
          cout << b[k] - 1 << endl;
        }
      }
    }
    q.pop();
  }
}
int main() {
  cin >> n >> k;
  bfs(n);
  return 0;
}
题目详情
1131 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 4.1 移动

泳池

学校是 N x N 的坐标方格 grid 中,每一个方格的值 grid(i,j)表示在位置 (i,j) 的高度。现在开始下雨了。当时间为 t 时,此时雨水导致方格中任意位置的水位为 t 。你可以从一个方格游向四周相邻的任意一个方格,但是前提是此时水位必须同时淹没这两个方格。假定小C的游动是不耗时的。

现在小C从坐标方格的左上(0,0)出发。最少耗时多久他才能到达坐标方格的右下平台 (N-1, N-1)?

时间限制:1000

内存限制:65536

输入

第一行有一个整数N,以下是一个N*N的方阵,代表各处的高度。 

输入范围:

2 ≤ N ≤ 300 

0 ≤ Height ≤ 10000000

输出

输出一个整数,代表最少等待时间T

样例输入

样例输入1:

2
0 2
1 3

样例输入2:

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

样例输出

样例输出1:

3

样例输出2:

16

提示

样例1:时间为3时,才可以游向平台(1,1),此时水位为3。 样例2:时间为16时,水位为16,此时才能保证(0,0)和(4,4)是联通的(请自行找出一条通路)。

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

using namespace std;
int maze[305][305];
bool reach[305][305];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int N;
struct point {
  int x, y;
  point(int a, int b) : x(a), y(b) {}
};
bool canreach(int t) {
  if (maze[0][0] > t)
    return false;
  memset(reach, 0, sizeof(reach));
  reach[0][0] = 1;
  queue<point> myqueues;
  myqueues.push(point(0, 0));
  while (!myqueues.empty()) {
    point top = myqueues.front();
    myqueues.pop();
    if (top.x == N - 1 && top.y == N - 1)
      return true;
    for (int i = 0; i < 4; i++) {
      int tx = top.x + dx[i];
      int ty = top.y + dy[i];
      if (tx < 0 || tx >= N || ty < 0 || ty >= N)
        continue;
      if (reach[tx][ty])
        continue;
      if (maze[tx][ty] > t)
        continue;
      reach[tx][ty] = 1;
      myqueues.push(point(tx, ty));
    }
  }
  return false;
}
int main() {
  memset(maze, 0, sizeof(maze));
  cin >> N;
  int L = 10000000, R = 0;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cin >> maze[i][j];
      L = min(maze[i][j], L);
      R = max(maze[i][j], R);
    }
  }
  int result = 10000000;
  while (L <= R) {
    int mid = (L + R) / 2;
    if (canreach(mid)) {
      R = mid - 1;
      result = min(result, mid);
    } else
      L = mid + 1;
  }
  cout << result << endl;
  return 0;
}
题目详情
1132 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 4.1 移动

问题求解

给定一个正整数N,求最小的M满足比N大且M与N的二进制表示中有相同数目的1。

举个例子,假如给定N为78,二进制表示为1001110,包含4个1,那么最小的比N大的并且二进制表示中只包含4个1的数是83,其二进制是1010011,因此83就是答案。

时间限制:1000

内存限制:65536

输入

输入若干行,每行一个数N(1 ≤ N ≤ 1000000),如果这行为0表示输入结束。

输出

对于每个N,输出对应的M。

样例输入

1
2
3
4
78
0

样例输出

2
4
5
8
83
答案与解析
参考答案
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>

#define INF 999999999
#define N 1001
using namespace std;
int main() {
  int n;
  while (scanf("%d", &n) != EOF && n) {
    int cnt = 0;
    int temp = n;
    while (temp > 0) {
      if (temp % 2)
        cnt++;
      temp /= 2;
    }
    int sum = 0;
    while (1) {
      temp = ++n;
      while (temp > 0) {
        if (temp % 2)
          sum++;
        temp /= 2;
      }
      if (cnt == sum) {
        cout << n << endl;
        break;
      }
      sum = 0;
    }
  }
  return 0;
}
//解法2 样例代码  枚举
using namespace std;
int n;  // 定义变量 n
int tj(int x) {
    int ans = 0;  // 定义变量 ans
    while (x) {  // 当 x 不为0循环执行
        if (x &)
            ans++;  // 如果 x 的最低位为1,则将 ans 加1
        x >>= 1;  // 将 x 右移1位,即将 x 的二进制表示向右移动一位
    }
    return ans;  // 返回 ans
}
int main() {
    while (1) {  // 无限循环
        cin >> n;  // 从标准输入读取一个整数 n
        if (!n)break;  如果 n 为0,则结束循环
        int t = tj(n);  // 调用函数 tj 计算 n 的二进制中的1的个数,并将结果赋值给 t
        for (int i = n + 1;; i++) {  // 从 n+1 开始递增遍历整数 i
            if (t == tj(i)) {
                cout << i << endl;  // 输出第一个满足条件的整数 i,即其二进制表示中的1的个数与 t 相等
                break;  // 结束循环
            }
        }
    }
    return 0;  // 返回 0,表示程序正常结束
}
题目详情
1133 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

交易市场

市场里面一共有n种物品,有m种交易途径,每个交易途径可以由(x,y,z)表示,意思是可以用第x种物品换成第y种物品,并且得到z元的收益(z均大于0)。最开始你只有第一种物品,请问最多可以赚取多少收益。

时间限制:1000

内存限制:65536

输入

第一行两个正整数n和m(n ≤ 1000,m ≤ 4000) 接下来m行,每行三个正整数x, y, z,意思是可以用第x种物品换成第y种物品,并且得到z元的收益。(1 ≤ x,y ≤ n, 1 ≤ z ≤ 100)

输出

一个整数表示最大收益,如果可以赚取无穷多的收益则输出1000000000

样例输入

3 3
1 2 2
2 3 3
1 3 4

样例输出

5
答案与解析
参考答案
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#define INF 1000000000
using namespace std;
struct exchangeTo {
  int target;
  int p;
  exchangeTo(int a, int b) : target(a), p(b) {}
};
struct path {
  int pre;
  int val;
} dp[1005];
map<int, vector<exchangeTo>> tables;
bool inPath(int n, int k) {
  while (k != -1) {
    if (n == k)
      return true;
    k = dp[k].pre;
  }
  return false;
}
int main() {
  memset(dp, -1, sizeof(dp));
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    tables[x].push_back(exchangeTo(y, z));
  }
  dp[1].val = 0, dp[1].pre = 0;
  bool done = false;
  int result = 0;
  queue<int> myqueues;
  myqueues.push(1);
  while (!myqueues.empty()) {
    int top = myqueues.front();
    myqueues.pop();
    if (!tables[top].empty()) {
      vector<exchangeTo>::iterator ii;
      for (ii = tables[top].begin(); ii != tables[top].end(); ii++) {
        if (inPath(ii->target, top)) {
          result = INF;
          done = true;
          break;
        }
        if (dp[top].val + ii->p > dp[ii->target].val) {
          dp[ii->target].val = dp[top].val + ii->p;
          dp[ii->target].pre = top;
          myqueues.push(ii->target); // 注意这里的更新
        }
        result = max(result, dp[ii->target].val);
      }
      if (done)
        break;
    }
  }
  cout << result << endl;
  return 0;
}
题目详情
1134 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

最佳路径

如下所示的由正整数数字构成的三角形:

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。

注意:路径上的每一步只能从一个数走到下一层上和它最近的下边(正下方)的数或者右边(右下方)的数。

时间限制:1000

内存限制:65536

输入

第一行为三角形高度100>=h>=1,同时也是最底层边的数字的数目。 从第二行开始,每行为三角形相应行的数字,中间用空格分隔。

输出

最佳路径的长度数值。

样例输入

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

样例输出

30
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int n, a[1001][1001] = {};
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) {
      cin >> a[i][j];
    }
  }
  for (int i = n; i >= 1; i--) {
    for (int j = i; j >= 1; j--) {
      a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
    }
  }
  cout << a[1][1];
  return 0;
}
题目详情
1135 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 7.1 逻辑推理

数字构造

火山宝打算造一个 n 位的十进制数字出来。

对于 1 到 n 中的每一个 i,火山宝可以从 xi,1, ..., xi,ki 这 ki 个 0-9 的数字中选择一个作为 ai。

在选择结束后,a1a2...an 形成了一个 n 位的十进制数——这就是火山宝造出来的数。

你需要帮火山宝计算他能造出的数中,有多少个是 3 的倍数。

时间限制:1000

内存限制:65536

输入

第一行输入一个整数 n(1 ≤ n ≤ 18),表示数字的位数。 接下来 n 行,每行第一个整数 ki (1 ≤ ki ≤ 10),表示第 i 中候选的数字数量。接着是 ki 个两两不同的 0-9 范围内的数字 xi,1, ..., xi,ki。 输入保证 0 不是第一位的可选项。

输出

你需要输出一行一个整数,表示火山宝能造出的数字中,3 的倍数的数量。

样例输入

样例输入1:

2
5 5 6 7 8 9
5 0 1 2 3 4

样例输入2:

5
9 1 2 3 4 5 6 7 8 9
10 0 1 2 3 4 5 6 7 8 9
10 0 1 2 3 4 5 6 7 8 9
10 0 1 2 3 4 5 6 7 8 9
10 0 1 2 3 4 5 6 7 8 9

样例输出

样例输出1:

9

样例输出2:

30000

提示

样例1能造出来的 3 的倍数有 51, 54,60,63,72,81,84,90, 93。

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

using namespace std;
int num[20][10];
int k[20];
int mod[20][3] = {};
int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> k[i];
    for (int j = 0; j < k[i]; j++) {
      cin >> num[i][j];
      mod[i][num[i][j] % 3]++;
    }
  }
  long result[3] = {};
  for (int i = 0; i < 3; i++)
    result[i] = mod[0][i];
  for (int i = 1; i < n; i++) {
    long temp0 = result[0], temp1 = result[1], temp2 = result[2];
    result[0] = temp0 * mod[i][0] + temp1 * mod[i][2] + temp2 * mod[i][1];
    result[1] = temp0 * mod[i][1] + temp1 * mod[i][0] + temp2 * mod[i][2];
    result[2] = temp0 * mod[i][2] + temp1 * mod[i][1] + temp2 * mod[i][0];
  }
  cout << result[0] << endl;
  return 0;
}
题目详情
1136 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

奶牛散步

从一个无限大的矩阵的中心点出发,一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法? 

输入

一个数字,代表N,N<=1000

输出

输出有多少方案数模12345

样例输入

2

样例输出

7
答案与解析
参考答案
// 上一步向上走,下一步可以向左、右、上
// 上一步向左走,下一步可以向左、上
// 上一步向右走,下一步可以向右、上

#include <iostream>
using namespace std;
int main() {
  int n;
  cin >> n;
  long long lr = 2, up = 1;
  int i = 0;
  long long tmplr = 0, tmpup = 0;
  if (n == 1) {
    cout << 3;
  } else {
    for (i = 2; i <= n; i++) {
      tmplr = lr;
      tmpup = up;
      lr = (tmpup * 2 + tmplr) % 12345;
      up = (tmpup + tmplr) % 12345;
    }
    cout << (up + lr) % 12345;
  }
  return 0;
}
题目详情
1137 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

吃奶酪

Jerry准备偷吃Tom的奶酪。所有的奶酪排成了一条直线,每块奶酪都有不同的美味程度。然而,如果有相邻两块奶酪都被Jerry偷吃,Tom就会发现这一点并迅速抓住Jerry。Jerry当然希望在不被Tom发现的条件下吃到的奶酪美味度总和最大。当然,他也可以选择一块奶酪都不吃。请你帮助他规划一下偷吃的方案,告诉他最多能偷吃到多少的美味度吧。

时间限制:1000

内存限制:65536

输入

第一行一个整数T (T<=100),表示测试数据组数。 接下来,每组测试数据包含两行。其中,第一行一个整数n (1 <= n <= 100,000) ,表示奶酪的数量;第二行n个整数,表示这一排直线上奶酪的美味程度,请注意,美味度保证能够被int类型存储,且可能是负数。

输出

对于每组测试数据,输出一个整数,表示Jerry可以吃到的最大美味度总和。请注意,美味度总和可能超过int存储范围

样例输入

2
4
1 2 3 1
5
2 7 9 3 1

样例输出

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

using namespace std;
long long d[100005];
int a[100005];
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    memset(d, 0, sizeof(d));
    memset(a, 0, sizeof(a));
    cin >> n;
    for (int i = 1; i <= n; i++)
      cin >> a[i];
    d[1] = max(0, a[1]);
    d[2] = max(int(d[1]), a[2]);
    for (int i = 3; i <= n; i++) {
      d[i] = max(d[i - 1], a[i] + d[i - 2]);
    }
    cout << d[n] << endl;
  }
  return 0;
}
题目详情
1138 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

余数相同问题

已知三个正整数 a,b,c。

现有一个大于1的整数x,将其作为除数分别除a,b,c,得到的余数相同。

请问满足上述条件的x的最小值是多少?

数据保证x有解。

输入

一行,三个不大于1000000的正整数a,b,c,两个整数之间用一个空格隔开。

输出

一个整数,即满足条件的x的最小值。

样例输入

300 262 205

样例输出

19
答案与解析
参考答案
#include <iostream>
using namespace std;
int min(int a, int b, int c) {
  int min = a;
  if (b < min)
    min = b;
  if (c < min)
    min = c;
  return min;
}
int ys(int a, int b, int c) {
  int i;
  for (i = 2; i <= min(a, b, c); i++) {
    int y1 = a % i, y2 = b % i, y3 = c % i;
    if (y1 == y2 && y1 == y3 && y2 == y3)
      break;
  }
  return i;
}
int main() {
  int a, b, c;
  cin >> a >> b >> c;
  cout << ys(a, b, c) << endl;
}
题目详情
1139 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 7.1 逻辑推理

生成括号

Paul是一名数学专业的同学,在课余选修了C++编程课,现在他能够自己写程序判断判断一个给定的由'('和')'组成的字符串是否是正确匹配的。可是他不满足于此,想反其道而行之,设计一个程序,能够生成所有合法的括号组合,请你帮助他解决这个问题。

时间限制:1000

内存限制:65536

输入

输入只有一行N,代表生成括号的对数(1 ≤ N ≤ 10)。

输出

输出所有可能的并且有效的括号组合,按照字典序进行排列,每个组合占一行。

样例输入

3

样例输出

((()))
(()())
(())()
()(())
()()()
答案与解析
参考答案
#include <bitset>
#include <ctime>
#include <iostream>

using namespace std;
int N;
bool judge(bitset<20> temp) {
  int numL = 0, numR = 0; // numL 表0 左括号数 numR表1 右括号数
  for (int i = 2 * N - 1; i >= 0; i--) {
    if (temp[i])
      numR++;
    else
      numL++;
    if (numL - numR < 0)
      return false; // 在任何一个位置所得的前缀中0的个数不少于1的个数。
  }
  if (numL != numR)
    return false; // 有相同个数的0和1,都是N个
  return true;
}
int main() {
  cin >> N;
  int max = 1 << (2 * N - 1); // 2的2*N-1次方
  // cout<<max<<endl;

  for (int i = 1; i <= max; i++) {
    bitset<20> temp;
    // 开始枚举每种可能
    for (int j = 0; j < 2 * N; j++) {
      temp[j] = (i >> j) & 1; // 这里是反着取的 如000111,先取个位的1
    }
    // 对每种可能进行判断
    if (judge(temp)) {
      for (int j = 2 * N - 1; j >= 0; j--) {
        if (temp[j])
          cout << ")"; // 所以这要反过来输出
        else
          cout << "(";
      }
      cout << endl;
    }
  }

  return 0;
}
题目详情
1140 简答题 偏难 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 <algorithm>
#include <iostream>
#include <vector>

using namespace std;
struct project {
  int start;
  int end;
  project(int a, int b) : start(a), end(b) {}
  bool operator<(const project A) const {
    if (start == A.start)
      return end < A.end;
    else
      return start < A.start;
  }
};
int main() {
  int n;
  cin >> n;
  vector<project> alls;
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    alls.push_back(project(a, b));
  }
  sort(alls.begin(), alls.end());
  int result = 0;
  for (int i = 0; i < n; i++) {
    if (alls[i].end - alls[i].start < result) // 剪枝
      continue;
    for (int j = i + 1; j < n; j++) {
      if (alls[j].start > alls[i].end)
        break;
      int t = min(alls[i].end, alls[j].end) - alls[j].start + 1;
      result = max(t, result);
    }
  }
  cout << result << endl;
  return 0;
}
题目详情