首页 › 题库 › Scratch编程考级 › 1.1 舞台区与角色区

Scratch编程一级 题库

共 432 道题 ,第 16 / 22 页 · 按题型筛选,点「查看答案」核对解析
章节 1.1 舞台区与角色区 清除
301 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

奇数单增序列

给定一个长度为N(不大于500)的正整数序列,请将其中的所有奇数取出,并按升序输出。

时间限制:1000

内存限制:65536

输入

共2行: 第1行为 N; 第2行为 N 个正整数,其间用空格间隔。

输出

增序输出的奇数序列,数据之间以逗号间隔。数据保证至少有一个奇数。

样例输入

10
1 3 2 6 5 4 9 8 7 10

样例输出

1,3,5,7,9
答案与解析
参考答案
#include <stdio.h>
int main() {
  int N;
  int a[501];
  int b[501];
  int sum = 0;
  scanf("%d", &N);
  for (int i = 0; i < N; i++)
    scanf("%d", &a[i]);
  for (int i = 0, j = 0; i < N; i++)
    if (a[i] % 2 == 1) {
      b[j] = a[i];
      j++;
      sum++;
    }
  for (int i = 0; i < sum - 1; i++)
    for (int j = 0; j < sum - 1 - i; j++)
      if (b[j] > b[j + 1]) {
        int temp = b[j];
        b[j] = b[j + 1];
        b[j + 1] = temp;
      }
  for (int i = 0; i < sum; i++) {
    if (i == 0)
      printf("%d", b[0]);
    else
      printf(",%d", b[i]);
  }
}

      

//解法2
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,a[505],k=0;
  	cin>>n;
  	for(int i=1,x;i<=n;i++){
  		cin>>x;
  		if(x&1)a[k++]=x;
  	}
	sort(a,a+k);
	cout<<a[0];
	for(int i=1;i<k;i++) cout<<","<<a[i];
  	return 0;
}
题目详情
302 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

话题焦点人物

微博提供了一种便捷的交流平台。一条微博中,可以提及其它用户。例如Lee发出一条微博为:“期末考试顺利 @Kim @Neo”,则Lee提及了Kim和Neo两位用户。

我们收集了N(1 < N < 10000)条微博,并已将其中的用户名提取出来,用小于等于100的正整数表示。

通过分析这些数据,我们希望发现大家的话题焦点人物,即被提及最多的人(题目保证这样的人有且只有一个),并找出那些提及它的人。

时间限制:1000

内存限制:65536

输入

输入共两部分: 第一部分是微博数量N,1 < N < 10000。 第二部分是N条微博,每条微博占一行,表示为: 发送者序号a,提及人数k(0 < = k < = 20),然后是k个被提及者序号b1,b2...bk; 其中a和b1,b2...bk均为大于0小于等于100的整数。相邻两个整数之间用单个空格分隔。

输出

输出分两行: 第一行是被提及最多的人的序号; 第二行是提及它的人的序号,从小到大输出,相邻两个数之间用单个空格分隔。同一个序号只输出一次。

样例输入

5
1 2 3 4
1 0
90 3 1 2 4
4 2 3 2
2 1 3

样例输出

3
1 2 4
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  int counter[105] = {0};
  int a[10005][25] = {0};
  int result[10005] = {0}, p = 0;
  int maxnum = 0, maxtime = 0;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i][0] >> a[i][1];
    for (int j = 2; j <= a[i][1] + 1; j++) {
      cin >> a[i][j];
      counter[a[i][j]]++;
      if (counter[a[i][j]] > maxtime) {
        maxtime = counter[a[i][j]];
        maxnum = a[i][j];
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 2; j <= a[i][1] + 1; j++) {
      if (a[i][j] == maxnum) {
        result[p] = a[i][0];
        p++;
      }
    }
  }
  cout << maxnum << endl;
  sort(result, result + p);
  cout << result[0];
  for (int i = 1; i < p; i++) {
    if (result[i] == result[i - 1]) {
      continue;
    } else {
      cout << " " << result[i];
    }
  }
  return 0;
}
题目详情
303 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

字符三角形

描述

给定一个字符,用它构造一个底边长5个字符,高3个字符的等腰字符三角形。

输入

输入只有一行, 包含一个字符。

输出

该字符构成的等腰三角形,底边长5个字符,高3个字符。

样例输入

*

样例输出

  *
 ***
*****
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
  char a;
  cin >> a;
  cout << "  " << a << "  " << endl;
  cout << " " << a << a << a << " " << endl;
  cout << a << a << a << a << a << endl;
}
题目详情
304 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

晶晶赴约会

晶晶的朋友贝贝约晶晶下周一起去看展览,但晶晶每周的1、3、5有课必须上课, 请帮晶晶判断她能否接受贝贝的邀请,如果能输出YES;如果不能则输出NO。注意YES 和NO都是大写字母!

输入

输入有一行,贝贝邀请晶晶去看展览的日期,用数字1到7表示从星期一到星期 日。

输出

输出有一行,如果晶晶可以接受贝贝的邀请,输出YES,否则,输出NO。

注 意YES和NO都是大写字母!

输入样例

2

输出样例

YES

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a;
  cin >> a;
  if (a == 1 || a == 3 || a == 5)
    cout << "NO";
  else
    cout << "YES";
}
题目详情
305 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

铺砖

对于一个2行N列的走道。现在用1*2,2*2的砖去铺满。问有多少种不同的方式。

时间限制:3000

内存限制:131072

输入

整个测试有多组数据,请做到文件底结束。每行给出一个数字N,0 <= n <= 250

输出

如题

样例输入

2
8
12
100
200

样例输出

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251
答案与解析
参考答案
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;
int a[1005][255] = {{0, 0}, {0, 1}, {0, 3}, {0, 5}};
int b[1005], c[1005], len[255] = {0, 1, 1, 1}, n;
int main() {
  for (int l = 4; l <= 255; l++) {
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
    int len3;
    for (int i = len[l - 2]; i >= 1; i--)
      b[i] = a[l - 2][i];
    for (int i = 1; i <= len[l - 2]; i++) {
      c[i] += b[i] * 2;
      c[i + 1] = c[i] / 10;
      c[i] %= 10;
    }
    len3 = len[l - 2] + 1;
    while (c[len3] == 0 && len3 > 1)
      len3--;
    int x = 0;
    len3 = 1;
    while (len3 <= len[l - 1] || len3 <= len[l - 2]) {
      a[l][len3] += a[l - 1][len3] + c[len3];
      a[l][len3 + 1] = a[l][len3] / 10;
      a[l][len3] %= 10;
      len3++;
    }
    while (a[l][len3] == 0 && len3 > 1)
      len3--;
    len[l] = len3;
  }
  while (scanf("%d", &n) != EOF) {
    if (n == 0) {
      cout << "1" << endl;
      continue;
    }
    for (int i = len[n]; i >= 1; i--)
      cout << a[n][i];
    cout << endl;
  }
  return 0;
}
题目详情
306 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

质数的和与积

两个质数的和是S,它们的积最大是多少?

时间限制:10000

内存限制:65536

输入

一个不大于10000的正整数S,为两个质数的和。

输出

一个整数,为两个质数的最大乘积。数据保证有解。

样例输入

50

样例输出

589
答案与解析
参考答案
#include <cstdio>
#include <cstring>
#include <iostream>
#include <math.h>
#include <string>

using namespace std;
int prime(int a) {
  int i;
  if (a == 1)
    return 0;
  for (i = 2; i <= sqrt(a); i++)
    if (a % i == 0)
      return 0;
  return 1;
}
int main() {
  int j, s, x = 0, y;
  scanf("%d", &s);
  y = s;
  for (j = 2; j <= s / 2; j++) {
    if (prime(j) == 1 && prime(s - j) == 1) {
      if (j > x && (s - j) < y) {
        x = j;
        y = s - j;
      }
    }
  }
  printf("%d", x * y);
  return 0;
}
题目详情
307 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

因子问题

任给两个正整数N、M,求一个最小的正整数a,使得a和(M-a)都是N的因子。

时间限制:10000

内存限制:65536

输入

包括两个整数N、M。N不超过1,000,000。

输出

输出一个整数a,表示结果。如果某个案例中满足条件的正整数不存在,则在对应行输出-1

样例输入

35 10

样例输出

5
答案与解析
参考答案
#include <iostream>
using namespace std;
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i < m; i++) {
    if (n % i == 0 && n % (m - i) == 0) {
      cout << i;
      return 0;
    }
  }
  cout << "-1";
  return 0;
}
题目详情
308 简答题 偏难 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 n;
struct stu {
  bool ss;
  double height;
  void ini() {
    string s;
    cin >> s;
    if (s == "male")
      ss = 1;
    else
      ss = 0;
    scanf("%lf", &height);
  }
} a[41];
bool cmp(stu a1, stu b) {
  if (a1.ss != b.ss)
    return a1.ss == 1;
  else if (a1.ss == 1)
    return a1.height < b.height;
  else
    return b.height < a1.height;
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    a[i].ini();
  sort(a + 1, a + n + 1, cmp);
  for (int i = 1; i <= n; i++)
    printf("%.2lf ", a[i].height);
  return 0;
}
题目详情
309 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

大整数加法

求两个不超过200位的非负整数的和。

时间限制:1000

内存限制:65536

输入

有两行,每行是一个不超过200位的非负整数,可能有多余的前导0。

输出

一行,即相加后的结果。结果里不能有多余的前导0,即如果结果是342,那么就不能输出为0342。

样例输入

22222222222222222222
33333333333333333333

样例输出

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

using namespace std;

char s1[220], s2[220];

void exchange() {
  int l, r;
  l = 0, r = strlen(s1) - 1;
  while (r > l) {
    if (s1[l] >= '0')
      s1[l] -= '0';
    if (s1[r] >= '0')
      s1[r] -= '0';
    swap(s1[l], s1[r]);
    l++, r--;
  }
  if (l == r)
    s1[l] -= '0';
  l = 0, r = strlen(s2) - 1;
  while (r > l) {
    if (s2[l] >= '0')
      s2[l] -= '0';
    if (s2[r] >= '0')
      s2[r] -= '0';
    swap(s2[l], s2[r]);
    l++, r--;
  }
  if (l == r)
    s2[l] -= '0';
}

int main() {
  cin >> s1;
  cin >> s2;
  exchange();
  for (int i = 0; i <= 219; i++) {
    s1[i] += s2[i];
    if (s1[i] > 9)
      s1[i + 1] += s1[i] / 10;
    s1[i] %= 10;
  }
  bool if_zero = true;
  for (int i = 220; i >= 0; i--) {
    if (s1[i] == 0)
      continue;
    for (int j = i; j >= 0; j--)
      putchar(s1[j] + '0');
    if_zero = false;
    break;
  }
  if (if_zero)
    putchar('0');
  return 0;
}
题目详情
310 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

细菌的繁殖与扩散

在边长为9的正方形培养皿中,正中心位置有m个细菌。假设细菌的寿命仅一天,但每天可繁殖10个后代,而且这10个后代,有两个分布在原来的单元格中,其余的均匀分布在其四周相邻的八个单元格中。求经过n(1≤n≤4)天后,细菌在培养皿中的分布情况。

时间限制:10000

内存限制:65536

输入

输入为两个整数,第一个整数m表示中心位置细菌的个数(2 ≤ m ≤ 30),第二个整数n表示经过的天数(1 ≤ n ≤ 4)。

输出

输出九行九列整数矩阵,每行的整数之间用空格分隔。整个矩阵代表n天后细菌在培养皿上的分布情况。

样例输入

2 1

样例输出

0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 2 2 2 0 0 0
0 0 0 2 4 2 0 0 0
0 0 0 2 2 2 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int m, n;
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int a[5][10][10];
int main() {
  cin >> m >> n;
  a[0][5][5] = m;
  for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= 9; i++)
      for (int j = 1; j <= 9; j++) {
        a[k][i][j] = 2 * a[k - 1][i][j];
        for (int l = 0; l < 8; l++) {
          int nx = i + dx[l], ny = j + dy[l];
          if (nx > 0 && nx <= 9 && ny > 0 && ny <= 9)
            a[k][i][j] += a[k - 1][nx][ny];
        }
      }
  }
  for (int i = 1; i <= 9; i++) {
    for (int j = 1; j <= 9; j++)
      cout << a[n][i][j] << ' ';
    cout << endl;
  }
}
题目详情
311 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

单词倒排

编写程序,读入一行英文(只包含字母和空格,单词间以单个空格分隔),将所有单词的顺序倒排并输出,依然以单个空格分隔。

时间限制:10000

内存限制:65536

输入

输入为一个字符串(字符串长度至多为100)。

输出

输出为按要求排序后的字符串。

样例输入

I am a student

样例输出

student a am I
答案与解析
参考答案
#include <iostream>
#include <string>
using namespace std;
string str;
string de[100];
int main() {
  getline(cin, str);
  int len = str.length();
  int ind = 0;
  for (int i = 0; i < len; i++) {
    if (str[i] >= 'a' && str[i] <= 'z' || str[i] >= 'A' && str[i] <= 'Z') {
      de[ind] += str[i];
    } else {
      ind++;
      de[ind] = " ";
      ind++;
    }
  }
  if (de[ind] == " ") {
    ind--;
  }
  for (int i = ind; i >= 0; i--) {
    cout << de[i];
  }
  return 0;
}

//解法2
//样例代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string s[105];
  int i=0;
  while(cin>>s[++i]){}
  while(i>0)cout<<s[--i]<<" ";
  return 0;
}
题目详情
312 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

输出整数

输入四个整数,把输入的第三、第四个整数输出。

时间限制:3000

内存限制:65536

输入

只有一行,共四个整数,整数之间由一个空格分隔。整数是32位有符号整数。

输出

只有一行,二个整数,即输入的第三、第四个整数,以一个空格分开。

样例输入

12 34 56 789

样例输出

56 789
答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  cout << c;
  cout << " ";
  cout << d;
}
题目详情
313 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

金币

国王将金币作为工资,发放给忠诚的骑士。第一天,骑士收到一枚金币;之后两天(第二天和第三天)里,每天收到两枚金币;之后三天(第四、五、六天)里,每天收到三枚金币;之后四天(第七、八、九、十天)里,每天收到四枚金币……这种工资发放模式会一直这样延续下去:当连续N天每天收到N枚金币后,骑士会在之后的连续N+1天里,每天收到N+1枚金币(N为任意正整数)。

你需要编写一个程序,确定从第一天开始的给定天数内,骑士一共获得了多少金币。

时间限制:10000

内存限制:65536

输入

一个整数(范围1到10000),表示天数。

输出

骑士获得的金币数。

样例输入

6

样例输出

14
答案与解析
参考答案
//解法1
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n, sum = 0, cnt = 0;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < i; j++) {
      sum += i;
      cnt++;
      if (cnt == n)
        break;
    }
    if (cnt == n)
      break;
  }
  cout << sum << endl;
  return 0;
}
//解法2
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,t=0,b=1,ans=0;
  cin>>n;
  for(int i=1;i<=n;i++){
  	ans+=b;
  	t++;
  	if(t==b){
	  	b++;
	  	t=0;
	}
  }
  cout<<ans;
  return 0;
}
题目详情
314 简答题 偏难 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;
}
题目详情
315 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

忍者道具

忍者道具有很多种,苦无,飞镖,震爆弹。L君热衷于收集忍者道具,现在他有N个道具,每个道具的重量分别是C1、C2…CN。现在他想把这N个道具装到载重量为W的工具包里,请问他最少需要多少个工具包?

时间限制:1000

内存限制:65536

输入

第一行包含两个用空格隔开的整数,N和W。 接下来N行每行一个整数,其中第i+1行的整数表示第i个道具的重量Ci。

输出

输出一个整数,最少需要多少个工具包。

样例输入

5 1996
1
2
1994
12
29

样例输出

2

提示

对于100%的数据,1=N=18,1=Ci=W=10^8。

答案与解析
参考答案
#include <iostream>
using namespace std;
const int MAXN = 18;
int used[MAXN];
int W;
int m, n, ans = (1 << 30);
int item[MAXN];
int bag[MAXN];
void dfs(int x, int sum) {
  if (sum >= ans)
    return;
  if (x == n) {
    ans = min(ans, sum);
    return;
  }
  for (int i = 0; i < sum; ++i) {
    if (bag[i] >= item[x]) {
      bag[i] -= item[x];
      dfs(x + 1, sum);
      bag[i] += item[x];
    }
  }
  bag[sum] -= item[x];
  dfs(x + 1, sum + 1);
  bag[sum] += item[x];
}
int main() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> item[i];
    bag[i] = m;
  }
  dfs(0, 1);
  cout << ans << endl;
  return 0;
}
//解法2  深搜
#include <bits/stdc++.h>  
using namespace std; 
int n,w,ans=20;
int a[20],bag[20];
void dfs(int x,int sum){//放第x个物品,已使用sum个包
	if(sum>=ans) return;//背包数量不够
	if(x>n) {ans=min(ans,sum);return;}//所有物品已放完
	for(int i=1;i<=sum;i++){//放入现有背包
		if(bag[i]>=a[x]){
			bag[i]-=a[x];
			dfs(x+1,sum);
			bag[i]+=a[x];//回溯
		}
	}
	bag[sum+1]-=a[x];//放入新背包
	dfs(x+1,sum+1);
	bag[sum+1]+=a[x];//回溯
}
int main() {
	cin>>n>>w;
	for(int i=1;i<=n;i++) {
		cin>>a[i];
		bag[i]=w;//初始化n个背包的开始可用容量
	}
	dfs(1,1);
	cout<<ans<<endl;
	return 0;
}
题目详情
316 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

求逆序对问题

给定N个数的序列a1,a2,...aN,定义一个数对(ai, aj)为“重要逆序对”的充要条件为 i < j 且 ai > 2aj。求给定序列中“重要逆序对”的个数。

时间限制:1000

内存限制:256000

输入

本题有多个测试点,每个测试点分为两行:第一行为序列中数字的个数N(1 ≤ N ≤ 200000),第二行为序列a1, a2 ... aN(0 ≤a ≤ 10000000),由空格分开。N=0表示输入结束。

输出

每个测试点一行,输出一个整数,为给序列中“重要逆序对”的个数。

样例输入

10

0 9 8 7 6 5 4 3 2 1

0

样例输出

16

提示

请注意答案范围,如果使用printf输出long long类型,请用%lld

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

int arr[200005];
int tmp[200005];
int N;

long long mergesort(int start, int end) {
  long long cnt = 0, mid = (start + end) / 2;
  if (start >= end)
    return 0;
  cnt += mergesort(start, mid);
  cnt += mergesort(mid + 1, end);
  // find important reverse pair
  int i = start, j = mid + 1;
  while (i <= mid && j <= end) {
    if (arr[i] > 2 * arr[j] && j <= end) {
      cnt += (mid - i + 1);
      j++;
    } else {
      i++;
    }
  }
  // merge sort
  i = start, j = mid + 1;
  int idx = 0;
  while (i <= mid && j <= end) {
    if (arr[i] > arr[j]) {
      tmp[idx++] = arr[j++];
    } else {
      tmp[idx++] = arr[i++];
    }
  }
  while (i <= mid)
    tmp[idx++] = arr[i++];
  while (j <= end)
    tmp[idx++] = arr[j++];
  for (int k = 0; k < idx; k++) {
    arr[start + k] = tmp[k];
  }
  return cnt;
}

int main() {
  while (cin >> N) {
    if (N == 0)
      break;
    for (int i = 1; i <= N; i++) {
      cin >> arr[i];
    }
    cout << mergesort(1, N) << endl;
  }
  return 0;
}
题目详情
317 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

数字三角形问题

(图1)

图1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。 注意:路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。

时间限制:1000

内存限制:65536

输入

输入的是一行是一个整数N (1 < N <= 100),给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。

输出

输出最大的和。

样例输入

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;
int a[110][110];
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 - 1; i >= 1; i--)
    for (int j = 1; j <= i; j++)
      a[i][j] = max(a[i + 1][j], a[i + 1][j + 1]) + a[i][j];

  cout << a[1][1] << endl;
  return 0;
}
题目详情
318 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

大盗

阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。

这条街上一共有 N 家店铺,每家店中都有一些现金。阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动,然后警察就会蜂拥而至。

作为一向谨慎作案的大盗,阿福不愿意冒着被警察追捕的风险行窃。他想知道,在不惊动警察的情况下,他今晚最多可以得到多少现金?

时间限制:1000

内存限制:65536

输入

输入的第一行是一个整数 T (T <= 50) ,表示一共有 T 组数据。 接下来的每组数据,第一行是一个整数 N (1 <= N <= 100, 000) ,表示一共有 N 家店铺。第二行是 N 个被空格分开的正整数,表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过 1000 。

输出

对于每组数据,输出一行。该行包含一个整数,表示阿福在不惊动警察的情况下可以得到的现金数量。

样例输入

2
3
1 8 2
4
10 7 6 14

样例输出

8
24

提示

对于第一组样例,阿福选择第 2 家店铺行窃,获得的现金数量为 8 。 对于第二组样例,阿福选择第 1 和 4 家店铺行窃,获得的现金数量为 10 + 14 = 24 。

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
int t;
int n;
int a[100010];
int d[100010];
int main() {
  cin >> t;
  for (int i = 1; i <= t; i++) {
    cin >> n;
    for (int j = 1; j <= n; j++)
      cin >> a[j];
    int maxe;
    d[1] = a[1];
    d[2] = maxe = max(a[1], a[2]);
    // cout << d[1] << " " << d[2] << " ";
    for (int j = 3; j <= n; j++) {
      d[j] = max(d[j - 1], a[j] + d[j - 2]);
      maxe = max(d[j], maxe);
      // cout << d[j] << " ";
    }
    // cout <<endl;
    cout << maxe << endl;
  }
  return 0;
}
题目详情
319 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

井和绳子

有A, B, C, D, E五家人共用一口井,已知井深不超过k米。A, B, C, D, E的绳长各不相同,而且厘米表示的绳长一定是整数。

从井口放下绳索正好达到水面时:

(a)需要A家的绳n1条接上B家的绳1条

(b)需要B家的绳n2条接上C家的绳1条

(c)需要C家的绳n3条接上D家的绳1条

(d)需要D家的绳n4条接上E家的绳1条

(e)需要E家的绳n5条接上A家的绳1条

问井深和各家绳长。

时间限制:1000

内存限制:65536

输入

输入只有1行。包括空格分开的6个整数。 第一个整数k(1 <= k <= 20),代表井的最大深度(单位:米)。 接下来是5个正整数n1, n2, n3, n4, n5。这五个整数的含义见上面的题目描述。

输出

输出只有1行。 如果找到了可行解,就输出6个整数,用空格分开,分别代表井的深度和A, B, C, D, E的绳长(单位都是厘米)。 如果有多组可行解,输出井的深度最小的那组解。 如果不存在可行解,就输出一行: not found

样例输入

10 2 3 4 5 6

样例输出

721 265 191 148 129 76
答案与解析
参考答案
#include <iostream>
using namespace std;
int main() {
  int n[6], l, a, b, c, d, e, len;
  cin >> l;
  l *= 100;
  for (int i = 1; i <= 5; i++)
    cin >> n[i];
  int flag = 0;
  for (len = 1; len <= l; len++) {
    for (a = 1; a <= len; a++) {
      b = len - n[1] * a;
      c = len - n[2] * b;
      d = len - n[3] * c;
      e = len - n[4] * d;

      if (a == b || a == c || a == d || a == e || b == c || b == d || b == e ||
          c == d || c == e || d == e || a <= 0 || b <= 0 || c <= 0 || d <= 0 ||
          e <= 0)
        continue;
      if (e * n[5] + a == len) {
        printf("%d %d %d %d %d %d\n", len, a, b, c, d, e);
        return 0;
      }
    }
  }
  printf("not found");
  return 0;
}
题目详情
320 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 1.1 舞台区与角色区

爬楼

已知楼梯的数量,可以每次走2级或者3级,求不同的走法数

例如:楼梯一共有7级,一共3种方法:2 2 3或者 2 3 2 或者 3 2 2。

时间限制:1000

内存限制:65536

输入

输入包含若干行,每行包含一个正整数N,代表楼梯级数,1 <= N <= 50。 最后一行为0,表示测试结束。

输出

不同的走法数,每一行输入对应一行输出

样例输入

7
0

样例输出

3
答案与解析
参考答案
#include <iostream>
using namespace std;
#define maxn 55
long long dp[maxn];
void init() {
  dp[1] = 0, dp[2] = 1, dp[3] = 1, dp[4] = 1;
  for (int i = 5; i <= maxn; i++)
    dp[i] = dp[i - 3] + dp[i - 2];
}

int main() {
  init();
  int n;
  while (cin >> n) {
    if (n == 0) {
      return 0;
    }
    cout << dp[n] << endl;
  }
  return 0;
}
题目详情