首页 › 题库 › Scratch编程考级 › 2.4 大小设置

Scratch编程一级 题库

共 39 道题 ,第 2 / 2 页 · 按题型筛选,点「查看答案」核对解析
章节 2.4 大小设置 清除
21 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 2.4 大小设置

按照个位数排序

对于给定的正整数序列,按照个位数从小到大排序,个位数相同的按照本身大小从小到大排序。

时间限制:1000

内存限制:65536

输入

第一行1个整数n,表示序列的大小。( 0 < n ≤ 1000) 第二行n个正整数,表示序列的每个数,每个数不大于100000000。

输出

输出按照题目要求排序后的序列

样例输入

6
17 23 9 13 88 10

样例输出

10 13 23 17 88 9
答案与解析
参考答案
#include <algorithm>
#include <iostream>

using namespace std;
bool cmp(int a, int b) {
  if (a % 10 != b % 10) {
    return a % 10 < b % 10;
  }
  return a < b;
}
int main() {
  int n, arr[1003];
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  sort(arr, arr + n, cmp);
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  return 0;
}

 

题目详情
22 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 2.4 大小设置

图像叠加

给出两幅相同大小的黑白图像(用0-1矩阵)表示,0表示白点,1表示黑点,求两幅图像叠加后的图像。

说明:若两幅图像在相同位置上的像素点都是白色,叠加后为白色,否则为黑色。

时间限制:1000

内存限制:65536

输入

第一行包含两个整数m和n,表示图像的行数和列数,中间用单个空格隔开。1 <= m <= 100, 1 <= n <= 100。 之后m行,每行n个整数0或1,表示第一幅黑白图像上各像素点的颜色。相邻两个数之间用单个空格隔开。 之后m行,每行n个整数0或1,表示第二幅黑白图像上各像素点的颜色。相邻两个数之间用单个空格隔开。

输出

m行,每行n个整数,表示叠加后黑白图像上各像素点的颜色。

样例输入

3 3
1 0 1
0 0 1
1 1 0
1 1 0
0 0 1
0 0 1

样例输出

1 1 1
0 0 1
1 1 1
答案与解析
参考答案
#include <iostream>
using namespace std;
int arr[100][100];
int arr1[100][100];
int ans[100][100];
int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> arr[i][j];
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> arr1[i][j];
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (arr[i][j] == 0 && arr1[i][j] == 0) {
        ans[i][j] = 0;
      } else {
        ans[i][j] = 1;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cout << ans[i][j] << " ";
    }
    cout << endl;
  }
  return 0;
}
题目详情
23 简答题 偏难 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;
}
题目详情
24 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 2.4 大小设置

替换单词

输入一个字符串,以回车结束(字符串长度<=100)。该字符串由若干个单词组成,单词之间用一个空格隔开,所有单词区分大小写。现需要将其中的某个单词替换成另一个单词,并输出替换之后的字符串。

时间限制:1000

内存限制:65536

输入

输入包括3行, 第1行是包含多个单词的字符串 s; 

第2行是待替换的单词a(长度 <= 100); 

第3行是a将被替换的单词b(长度 <= 100). 

s, a, b 最前面和最后面都没有空格.

输出

输出只有 1 行,将s中所有单词a替换成b之后的字符串。

样例输入

You want someone to help you

You

I

样例输出

I want someone to help you

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

using namespace std;
int main() {
  string src;
  string s, s1;
  while (getline(cin, src)) {
    getline(cin, s);
    getline(cin, s1);
    int flag = src.find(s);
    while (flag != string::npos) {
      if (flag + s.size() < src.size() && src[flag + s.size()] != ' ') {
        flag = src.find(s, flag + 1);
        continue;
      }
      src.replace(flag, s.size(), s1);
      flag = src.find(s, flag + 1);
    }
    cout << src << endl;
  }
  return 0;
}
题目详情
25 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 2.4 大小设置

多项式相加

我们经常遇到两多项式相加的情况,在这里,我们就需要用程序来模拟实现把两个多项式相加到一起。首先,我们会有两个多项式,每个多项式是独立的一行,每个多项式由系数、幂数这样的多个整数对来表示。

如多项式2x20- x17+ 5x9- 7x7+ 16x5+ 10x4 + 22x2- 15

对应的表达式为:2 20 -1 17 5 9 - 7 7 16 5 10 4 22 2 -15 0。  

 为了标记每行多项式的结束,在表达式后面加上了一个幂数为负数的整数对。

同时输入表达式的幂数大小顺序是随机的。

我们需要做的就是把所给的两个多项式加起来。

时间限制:1000

内存限制:65536

输入

输入包括多行。 第一行整数n,表示有多少组的多项式需要求和。(1 < n < 100) 下面为2n行整数,每一行都是一个多项式的表达式。表示n组需要相加的多项式。 每行长度小于300。

输出

输出包括n行,每行为1组多项式相加的结果。 在每一行的输出结果中,多项式的每一项用“[x y]”形式的字符串表示,x是该项的系数、y 是该项的幂数。要求按照每一项的幂从高到低排列,即先输出幂数高的项、再输出幂数低的项。 系数为零的项不要输出。

样例输入

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

样例输出

[ 2 20 ] [ 2 19 ] [ 2 17 ] [ 15 10 ] [ 5 9 ] [ 6 5 ] [ 14 4 ] [ 35 2 ] [ -22 0 ]
[ 2 23 ] [ 2 19 ] [ 2 17 ] [ 15 10 ] [ 6 8 ] [ 8 7 ] [ -3 5 ] [ 44 4 ] [ 22 2 ] [ -18 0 ]

提示

第一组样例数据的第二行末尾的8 -8,因为幂次-8为负数,所以这一行数据结束,8 -8不要参与计算。

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

using namespace std;
typedef struct LNode {
  int num;
  int pow;
  struct LNode *next;
} LNode, *LinkList;
bool cmp(LNode a, LNode b) { return a.pow > b.pow; }
void ListInsert(LNode *pHead, int a, int b) {
  LNode *p = new LNode;
  p->num = a;
  p->pow = b;
  p->next = pHead->next;
  pHead->next = p;
}
LNode *find(LNode *pHead, int b) {
  LNode *p = pHead->next;
  while (p && p->pow != b) {
    p = p->next;
  }
  return p;
}
void sort(LNode *pHead) {
  LNode *p, *q;
  int ta, tb;
  for (p = pHead->next; p != NULL; p = p->next)
    for (q = pHead->next; q->next != NULL; q = q->next) {
      if (q->pow < q->next->pow) {
        ta = q->num;
        tb = q->pow;
        q->num = q->next->num;
        q->pow = q->next->pow;
        q->next->num = ta;
        q->next->pow = tb;
      }
    }
}
int main(void) {
  LNode *pHead = NULL, *p, *q;
  int n, t, a, b, i;
  cin >> n;
  for (i = 0; i < n; i++) {
    pHead = new LNode;
    pHead->next = NULL;
    t = 1;
    while (t <= 2) {
      while (cin >> a >> b) {
        if (b < 0)
          break;
        if ((p = find(pHead, b)) != NULL) {
          p->num += a;
        } else
          ListInsert(pHead, a, b);
      }
      t++;
    }
    sort(pHead);
    p = pHead->next;
    while (p != NULL) {
      if (p->num == 0) {
        p = p->next;
        continue;
      }
      cout << "[ " << p->num << " " << p->pow << " ]"
           << " ";
      p = p->next;
    }
    cout << endl;
    p = pHead->next;
    while (!p) {
      q = p;
      p = p->next;
      delete q;
    }
  }
  return 0;
}
题目详情
26 简答题 偏难 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;
}
题目详情
27 简答题 偏难 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;
}
题目详情
28 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 2.4 大小设置

滑动窗口

给定一个长度为n(n<=10^6)的数组。有一个大小为k的滑动窗口从数组的最左端移动到最右端。你可以看到窗口中的k个数字。窗口每次向右滑动一个数字的距离。

下面是一个例子:

数组是 [1 3 -1 -3 5 3 6 7], k = 3。

窗口位置 最小值 最大值

[1  3  -1] -3  5  3  6  7 -1 3

 1 [3  -1  -3] 5  3  6  7 -3 3

 1  3 [-1  -3  5] 3  6  7 -3 5

 1  3  -1 [-3  5  3] 6  7 -3 5

 1  3  -1  -3 [5  3  6] 7 3 6

 1  3  -1  -3  5 [3  6  7] 3 7

你的任务是得到滑动窗口在每个位置时的最大值和最小值。

时间限制:20000

内存限制:65536

输入

输入包括两行。 第一行包括n和k,分别表示数组的长度和窗口的大小。 第二行包括n个数字。

输出

输出包括两行。 第一行包括窗口从左至右移动的每个位置的最小值。 第二行包括窗口从左至右移动的每个位置的最大值。

样例输入

8 3
1 3 -1 -3 5 3 6 7

样例输出

-1 -3 -3 -3 3 3
3 3 5 5 6 7
答案与解析
参考答案
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
int a[N], q[N];
int n, k;
int main() {
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  // 最小值队列  建立单调递增队列
  int h = 0, t = -1;
  for (int i = 1; i <= n; i++) {
    if (t >= h && q[h] < i - k + 1)
      h++;
    while (t >= h && a[i] <= a[q[t]])
      t--;
    q[++t] = i;
    if (i >= k)
      printf("%d ", a[q[h]]);
  }
  printf("\n");
  // 最大值队列  建立单调递减队列
  h = 0, t = -1;
  for (int i = 1; i <= n; i++) {
    // 队列中有元素且队头元素不在窗口[i-m+1,i]内,队头出队
    if (h <= t && q[h] < i - k + 1)
      h++;
    // 队列中有元素且当前值>=队尾值,队尾出队
    while (h <= t && a[i] >= a[q[t]])
      t--;
    // 下标入队,便于队头出队
    q[++t] = i;
    // 使用队头最大值
    if (i >= k)
      printf("%d ", a[q[h]]);
  }
  return 0;
}
题目详情
29 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 2.4 大小设置

棋盘问题

在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放k个棋子的所有可行的摆放方案C。

时间限制:1000

内存限制:65536

输入

输入含有多组测试数据。 每组数据的第一行是两个正整数,n k,用一个空格隔开,表示了将在一个n*n的矩阵内描述棋盘,以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状:每行有n个字符,其中 # 表示棋盘区域, . 表示空白区域(数据保证不出现多余的空白行或者空白列)。

输出

对于每一组数据,给出一行输出,输出摆放的方案数目C (数据保证C<2^31)。

样例输入

2 1
#.
.#
4 4
...#
..#.
.#..
#...
-1 -1

样例输出

2
1
答案与解析
参考答案
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;
int vis[20];
char G[20][20];
int ans, n, k;
int dfs(int x, int total) {
  if (total == k) {
    ans++;
    return 0;
  }
  for (int i = x; i < n; i++)
    for (int j = 0; j < n; j++)
      if (!vis[j] && G[i][j] == '#') {
        vis[j] = 1;
        dfs(i + 1, total + 1);
        vis[j] = 0;
      }
  return 0;
}
int main() {
  while (cin >> n >> k) {
    if (n == -1 && k == -1)
      break;
    memset(vis, 0, sizeof(vis));
    memset(G, 0, sizeof(G));
    for (int i = 0; i < n; i++)
      cin >> G[i];
    ans = 0;
    dfs(0, 0);
    cout << ans << endl;
  }
  return 0;
}
题目详情
30 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 2.4 大小设置

序列排序

对于给定的正整数序列,按照每个数的各位数和从大到小排序,各位数和相同的按照本身大小排序,大的在前,小的在后。

时间限制:1000

内存限制:65536

输入

第一行1个整数n,表示序列的大小。( 0 < n ≤ 1000) 第二行n个正整数,表示序列的每个数,每个数不大于100000000。

输出

输出按照题目要求排序后的序列

样例输入

6
17 26 9 13 88 10

样例输出

88 9 26 17 13 10
答案与解析
参考答案
#include <iostream>
using namespace std;
int sum(int n) {
  int s = 0;
  while (n > 0) {
    s += n % 10;
    n /= 10;
  }
  return s;
}
int main() {
  int i, j, t, n, a[1000], b[1000];
  cin >> n;
  for (i = 0; i < n; i++) {
    cin >> a[i];
    b[i] = sum(a[i]);
  }
  for (i = 0; i < n - 1; i++) {
    for (j = 0; j < n - i - 1; j++) {
      if ((b[j] < b[j + 1]) || ((b[j] == b[j + 1]) && (a[j] < a[j + 1]))) {
        t = b[j];
        b[j] = b[j + 1];
        b[j + 1] = t;
        t = a[j];
        a[j] = a[j + 1];
        a[j + 1] = t;
      }
    }
  }
  for (i = 0; i < n; i++)
    cout << a[i] << " ";
  return 0;
}
题目详情
31 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 2.4 大小设置

priority queue练习题

我们定义一个正整数a比正整数b优先的含义是:

*a的质因数数目(不包括自身)比b的质因数数目多;

*当两者质因数数目相等时,数值较大者优先级高。

现在给定一个容器,初始元素数目为0,之后每次往里面添加10个元素,每次添加之后,要求输出优先级最高与最低的元素,并把该两元素从容器中删除。

时间限制:2500

内存限制:131072

输入

第一行: num (添加元素次数,num <= 30)

下面10*num行,每行一个正整数n(n < 10000000).

输出

每次输入10个整数后,输出容器中优先级最高与最低的元素,两者用空格间隔。

样例输入

1
10 7 66 4 5 30 91 100 8 9

样例输出

66 5
答案与解析
参考答案
#include <cmath>
#include <iostream>
#include <set>

using namespace std;
// 判断一个数是否为质数
bool isPrime(int iVal) {
  for (int i = 2; i <= sqrt((float)iVal); i++) {
    if (iVal % i == 0)
      return false;
  }
  return true;
}
// 得到一个数的质因数数目
int getFactor(int a) {
  int sum = 0;
  int k = 0;
  for (int i = 2; i <= sqrt((float)a); i++) {
    if (a % i == 0) // 即a/i = k,无余数
    {
      k = a / i;
      if (i != k && isPrime(k))
        sum += 1;
      if (isPrime(i)) {
        sum += 1;
      }
    }
  }
  return sum;
}
// 函数对象,判断大小
class Compare_Class_Up {
public:
  bool operator()(const int &a, const int &b) {
    int sumA = 0, sumB = 0;
    sumA = getFactor(a);
    sumB = getFactor(b);
    if (sumA == sumB) {
      if (a < b) {
        return true;
      } else
        return false;
    } else if (sumA > sumB) {
      return false;
    } else
      return true;
  }
};
int main() {
  set<int, Compare_Class_Up> queue;
  int n = 0;
  cin >> n;
  while (n--) {
    int num;
    for (int i = 0; i < 10; i++) {
      cin >> num;
      queue.insert(num);
    }
    int min = *(queue.begin());
    int max = *(queue.rbegin());
    queue.erase(max);
    queue.erase(min);
    cout << max << ' ' << min << endl;
  }
  return 0;
}
题目详情
32 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 2.4 大小设置

斗地主大师

斗地主大师今天有P个欢乐豆,他夜观天象,算出了一个幸运数字Q,如果他能有恰好Q个欢乐豆,就可以轻松完成程设大作业了。

斗地主大师显然是斗地主大师,可以在斗地主的时候轻松操控游戏的输赢。

1.他可以轻松赢一把,让自己的欢乐豆变成原来的Y倍

2.他也可以故意输一把,损失X个欢乐豆(注意欢乐豆显然不能变成负数,所以如果手里没有X个豆就不能用这个能力)

而斗地主大师还有一种怪癖,扑克除去大小王只有52张,所以他一天之内最多只会打52把斗地主。

斗地主大师希望你能告诉他,为了把P个欢乐豆变成Q个,他至少要打多少把斗地主?

时间限制:1000

内存限制:65536

输入

第一行4个正整数 P,Q,X,Y 0< P,X,Q <= 2^31, 1< Y <= 225

输出

输出一个数表示斗地主大师至少要用多少次能力 如果打了52次斗地主也不能把P个欢乐豆变成Q个,请输出一行 “Failed”

样例输入

输入样例1:

2 2333 666 8

输入样例2:

1264574 285855522 26746122 3

样例输出

输出样例1:

Failed

输出样例2:

33

提示

可以考虑深搜 要用long long

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
long long p, q, x, y;
int sign = 55;
void dfs(long long p, int step) {
  if (p == q) {
    sign = min(sign, step);
    return;
  }
  if (step == 52)
    return;
  if (p * y <= q + (q / x) * x)
    dfs(p * y, step + 1);
  if (p - x >= 0)
    dfs(p - x, step + 1);
}
int main() {
  cin >> p >> q >> x >> y;
  dfs(p, 0);
  if (sign == 55)
    cout << "Failed";
  else
    cout << sign;
  return 0;
}
题目详情
33 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 2.4 大小设置

删除数字

娇娇一年级了,刚刚学会了识数和比大小。有一天,她在黑板上写上了一串数字:2,1,2,5,4。接着她擦掉了第一个2,发现剩下1,2,4都在自己的位置上,即:1在第1位,2在第2位,4在第4位。

娇娇希望擦掉某些数后,剩下的数列中在自己位置上的数尽量多。她发现这个问题很有趣,想知道最多能有几个数在自己的位置上,请你帮帮她!

时间限制:1000

内存限制:65536

输入

第一行,一个整数 TestNum( ≤ 10),表示测试数据的组数。 接下来每组数据有两行,第一行:一个整数n( ≤ 1000),第二行:n个正整数(≤ 1000)。

输出

对于每组测试数据,输出一个数表示答案。

样例输入

3
5
2 1 2 5 4
7
2 2 3 2 4 5 3
10
1 1 2 2 3 3 4 4 5 5

样例输出

3
4
5

提示

第一组测试数据:擦掉第一个数,1 2 4 有 3 个数在自己的位置上。

第二组测试数据:擦掉第4个、第7个数,2 3 4 5 有 4 个数在自己的位置上。

第三组测试数据:每种相同的数擦掉一个,1 2 3 4 5 有 5 个数在自己的位置上。

答案与解析
参考答案

#include <bits/stdc++.h>

using namespace std;

int d[1010][1010]; //全局变量,默认为0,避免数组过大崩溃 

//d[i][j]表示1到i中删除j个数满足条件的最大个数 

int main()

{

int i,j,n,a[1010]; 

int f=0; //初始化标记为0

cin>>n;

for(i=1;i<=n;i++){

cin>>a[i];

}

for(i=1;i<=n;i++){

        d[i][0]=d[i-1][0]; //未删除 

        if(a[i]==i){ //统计初始时满足条件个数 

        d[i][0]++;

        }

    }

for(i=1;i<=n;i++){

for(j=0;j<=i;j++){

  if(a[i]==i-j){ //删除数之后的位置满足条件 

                d[i][j]=max(d[i-1][j-1],d[i-1][j]+1);

            }

            else{ //前i个数删除j个,考虑第i个数删和不删的情况 

d[i][j]=max(d[i-1][j-1],d[i-1][j]);

}

}

}

for(int i=0;i<=n;i++){

    f=max(f,d[n][i]); //找出最大值 

    }

cout<<f;

return 0;

}

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

解题思路

d[i][j]表示1到i中删除j个数满足条件的最大个数,

d[i][j]的前一种情况可能是d[i-1][j-1]和d[i-1][j],若第i个数删除,则为d[i][j]=d[i-1][j-1],

若第i个数不删,则d[i][j]=d[i-1][j],

考虑当a[i]==i-j时,若第i个数不删,则符合位置条件的数增加一个,所以比较d[i-1][j-1]和d[i-1][j]+1。

题目详情
34 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 2.4 大小设置

42点

42是:

· 组合数学上的第5个卡特兰数

· 字符'*'的ASCII码

· 钼的原子序数

· 6与9的乘积结果的13进制表示

· 生命、宇宙以及任何事情的终极答案

· 以及……表达式(1+5)/2*(6-4)*7的值

因此,小机器人Marvin发明了这个叫42点的小游戏。在这个游戏中,玩家会获得n个数。玩家需要使用'+'、'-'、'*'、'/'、'('、')'以及这n个数构成一个合法的中缀表达式,并使得该表达式的值为42。n个数之间的顺序可以改变。表达式运算过程中只能出现整数。

由于过于抑郁,Marvin无力完成这个游戏,于是来找你帮忙。你的任务是对于给定的n个数,判断他们是否能根据上述游戏规则算出42。

时间限制:1000

内存限制:65536

输入

第一行为一个数n,1<=n<=6。 第二行为n个数,每个数均为[1,13]范围内的整数

输出

输出一行,若可以算出42则输出“YES”,否则输出“NO”(注意大小写)

样例输入

6
1 5 2 6 4 7

样例输出

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

using namespace std;
vector<int> ele;
int n;
bool dfs(int m) {
  if (m == 1) {
    if (ele[0] == 42)
      return true;
    return false;
  }
  for (int i = 0; i < m - 1; ++i)
    for (int j = i + 1; j < m; ++j) {
      int t1 = ele[i], t2 = ele[j];
      ele[i] = t1 + t2;
      ele[j] = ele[m - 1];
      if (dfs(m - 1))
        return true;
      ele[i] = t1 - t2;
      if (dfs(m - 1))
        return true;
      ele[i] = t2 - t1;
      if (dfs(m - 1))
        return true;
      ele[i] = t1 * t2;
      if (dfs(m - 1))
        return true;
      if (t2 != 0 && abs(t1) % abs(t2) == 0) {
        ele[i] = t1 / t2;
        if (dfs(m - 1))
          return true;
      } else if (t1 != 0 && abs(t2) % abs(t1) == 0) {
        ele[i] = t2 / t1;
        if (dfs(m - 1))
          return true;
      }
      ele[i] = t1, ele[j] = t2;
    }
  return false;
}
int main() {
  cin >> n;
  int t;
  for (int i = 0; i < n; ++i) {
    cin >> t;
    ele.push_back(t);
  }
  //  sort(ele.begin(), ele.end());
  if (dfs(n))
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
}
题目详情
35 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 2.4 大小设置

多项式相加

我们经常遇到两多项式相加的情况, 在这里, 我们就需要用程序来模拟实现把两个多项式相加到一起。 首先, 我们会有两个多项式,每个多项式是独立的一行, 每个多项式由系数、 幂数这样的多个整数对来表示。

如多项式 2x20- x17+ 5x9- 7x7+ 16x5+ 10x4 + 22x2- 15

对应的表达式为: 2 20 -1 17 5 9 - 7 7 16 5 10 4 22 2 -15 0。

为了标记每行多项式的结束, 在表达式后面加上了一个幂数为负数的整数对。

同时输入表达式的幂数大小顺序是随机的。我们需要做的就是把所给的两个多项式加起来。

时间限制: 1000

内存限制: 65536

输入

输入包括多行。 第一行整数 n,表示有多少组的多项式需要求和。 (1 <n < 100) 下面为 2n 行整数, 每一行都是一个多项式的表达式。 表示 n组需要相加的多项式。 每行长度小于 300。

输出

输出包括 n 行, 每行为 1 组多项式相加的结果。 在每一行的输出结果中, 多项式的每一项用“[x y]” 形式的字符串表示, x 是该项的系数、 y 是该项的幂数。 要求按照每一项的幂从高到低排列, 即先输出幂数高的项、 再输出幂数低的项。 系数为零的项不要输出。

样例输入

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

样例输出

[ 2 20 ] [ 2 19 ] [ 2 17 ] [ 15 10 ] [ 5 9 ] [ 6 5 ] [ 14 4 ] [ 35 2 ] [ -22 0 ]
[ 2 23 ] [ 2 19 ] [ 2 17 ] [ 15 10 ] [ 6 8 ] [ 8 7 ] [ -3 5 ] [ 44 4 ] [ 22 2 ] [ -18 0 ]

提示

第一组样例数据的第二行末尾的 8 -8, 因为幂次-8 为负数, 所以这一行数据结束, 8 -8 不要参与计算。

答案与解析
参考答案
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main() {
  int n;
  cin >> n;
  for (int i = 0; i != n; ++i) {
    map<int, int> ploy;
    int index, value, over = 0;
    while (cin >> value >> index) {
      if (index < 0)
        over++;
      else {
        pair<map<int, int>::iterator, bool> ret =
            ploy.insert(make_pair(index, value));
        if (!ret.second)
          ret.first->second += value;
      }
      if (over == 2)
        break;
    }
    for (map<int, int>::reverse_iterator riter = ploy.rbegin();
         riter != ploy.rend(); ++riter) {
      if (riter->second != 0)
        cout << "[ " << riter->second << ' ' << riter->first << " ] ";
    }
    cout << endl;
  }
  return 0;
}

  

题目详情
36 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 2.4 大小设置

扩号匹配问题

在某个字符串(长度不超过 100)中有左括号、 右括号和大小写字母;规定(与常见的算数式子一样) 任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。 写一个程序, 找到无法匹配的左括号和右括号, 输出原来字符串, 并在下一行标出不能匹配的括号。 不能匹配的左括号用"$"标注,不能匹配的右括号用"?"标注.

时间限制: 3000

内存限制: 65536

输入

输入包括多组数据, 每组数据一行, 包含一个字符串, 只包含左右括号和大小写字母, 字符串长度不超过 100

输出

对每组输出数据, 输出两行, 第一行包含原始输入字符, 第二行由"$","?"和空格组成, "$"和"?"表示与之对应的左括号和右括号不能匹配。

样例输入

((ABCD(x)
)(rttyy())sss)(

样例输出

((ABCD(x)
$$       
)(rttyy())sss)(
?            ?$
答案与解析
参考答案
// 就近原则匹配:栈
// 遍历字符串
// 遇到左括号,将其下标入栈
// 右括号则先判断栈内元素情况
// 1.空,则将其下表记录到数组中
// 2.非空,则栈顶元素弹出(匹配到了)
// 将字符串便遍历后,将栈内元素记录入另一个数组
// 用两数组内的对应下标分别改成对应字符
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
string s;
char ans[N]; // 第二排的输出数组
stack<int> st;
int a[N], cnt = 1; // 未匹配的右括号的下标存储
int b[N], cnn = 1; // 未匹配的左括号的下标存储
int main() {
  while (getline(cin, s)) { // 输入不结束
    memset(ans, 0, sizeof(ans));
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    cnt = 1;
    cnn = 1; // 数据初始化
    for (int i = 0; i < s.size(); i++) {
      if (s[i] == '(') {
        st.push(i); // 左括号统一入栈
      }
      if (s[i] == ')') {
        if (!st.empty()) {
          st.pop(); // 若栈非空,则可以匹配
        } else {
          a[cnt++] = i; // 否则无法匹配,记录
        }
      }
    }
    if (!st.empty())
      while (!st.empty()) {
        b[cnn++] = st.top();
        st.pop();
      } // 栈内数据(下标)的出栈
    for (int i = 1; i < cnn; i++) {
      ans[b[i]] = '$'; // 在ans内标记
    }
    for (int i = 1; i < cnt; i++) {
      ans[a[i]] = '?'; // 在ans内标记
    }
    cout << s << endl;
    for (int i = 0; i < s.size(); i++) {
      if (ans[i] == 0)
        cout << " ";
      if (ans[i] == '$')
        cout << "$";
      if (ans[i] == '?')
        cout << "?"; // 格式转化
    }
    cout << endl;
  }
  return 0;
}
//解法2:递归
#include <bits/stdc++.h>
using namespace std;
#define N 105
char s[N], sign[N];
int si, len;
void find()//找下一个右括号 如果找到,si指向右括号 如果没找到,做标记 
{
    int lp = si;//当前左括号的下标 
    si++;
    while(si < len)
    {
        if(s[si] == ')')
            return;
        else if(s[si] == '(')
            find();
        si++;
    }
    sign[lp] = '$';//没有找到右括号,左括号的位置标记为$ 
}
int main()
{
 while(cin >> s)
 {
     len = strlen(s);
  for(int i = 0; i < len; ++i)//初始化sign字符串为空格 
            sign[i] = ' ';
        sign[len] = '\0';
        si = 0;
        while(si < len)
        {
            if(s[si] == ')')//右括号的位置标记为? 
                sign[si] = '?';
            else if(s[si] == '(')
                find();
            si++;
        }
        cout << s << endl << sign << endl;
 }
 return 0;
}
题目详情
37 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 2.4 大小设置

利用队列进行数字排序

对于 N 个数字, 有人提出了如下的排序策略:

例如, 对于数字 53、 47、 85、 38、 64、 23

先建立 10 个队列(0 到 9) , 用于存放数字的大小, 将这 N 个数字依个位存放入各自的队列之中, 然后再按队列 0 到队列 9 依次出队。

例如, 对于上面的数字, 依次进队后, 结果如下:

队列 3: 53、 23 队列 4: 64 队列 5: 85 队列 7: 47 队列 8: 38

将其依次出队后, 结果为 53,23,64,85,47,38

然后, 再将方才出队后的队对, 依照十位放入各自的队列之中, 然后再按队列 0 到队列 9 依次出队

例如, 对于上面刚刚出队的序列 53,23,64,85,47,38, 将其依次进队,结果如下:

队列 2: 23 队列 3: 38 队列 4: 47 队列 5: 53 队列 6: 64 队列 8: 85

将其依次出队后, 结果为 23,38,47,53,64,85.因为这组数字最大只是两位数, 所以排序结束。

如果还有更大的数字, 那么, 接下来就是其百位、 千位……(如果位数不够, 就补 0.比如最大的数字是四位数, 那么数字 23 就当成 0023处理)

请根据上述算法, 对这些数字进行排序

时间限制: 1000

内存限制: 65535

输入

分为两行, 第一行为一个数字 N(1 <= N <= 1000), 表示数字的个数第二行为 N 个数字(都是非负数) , 以空格相隔, 最大的数字不超过9999

输出

输出两个部分 第一个部分为第一次进队出队的结果, 先显示一行:Step1. 之后用Queue0:...表示, 共 10 行, 结果用空格分隔, 下同 之后为第二次进队出队的结果(如果需要第二次进队出队的话) , 先显示一行: Step2. 之后仍然用 Queue0:...表示, 共 10 行 之后如果需要的话, 则分别显示第三次、 第四次的进队出队结果 第二部分为一行,即将数字排序后的结果(升序排序)

样例输入

20
41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36

样例输出

Step1.
Queue0:0
Queue1:41 81 61 91
Queue2:62 42
Queue3:
Queue4:34 24 64
Queue5:5 45 95
Queue6:36
Queue7:67 27 27
Queue8:78 58
Queue9:69
Step2.
Queue0:0 5
Queue1:
Queue2:24 27 27
Queue3:34 36
Queue4:41 42 45
Queue5:58
Queue6:61 62 64 67 69
Queue7:78
Queue8:81
Queue9:91 95
0 5 24 27 27 34 36 41 42 45 58 61 62 64 67 69 78 81 91 95
答案与解析
参考答案
#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define ElemType int
#define MaxSize 2000
typedef struct ss {
  ElemType data[MaxSize];
  int front, rear;
} SqQueue;
void InitQueue(SqQueue *&q) {
  q = (SqQueue *)malloc(sizeof(SqQueue));
  q->front = q->rear = -1;
}
void DestoryQueue(SqQueue *&q) { free(q); }
bool QueueEmpty(SqQueue *q) { return (q->front == q->rear); }
bool enQueue(SqQueue *&q, ElemType e) {
  if (q->rear == MaxSize - 1)
    return false;
  q->rear++;
  q->data[q->rear] = e;
  return true;
}
bool deQueue(SqQueue *&q, ElemType &e) {
  if (q->rear == q->front)
    return false;
  q->front++;
  e = q->data[q->front];
  return true;
}
int Num(int h) // 返回h的位数
{
  int i = 0;
  if (h == 0)
    return 1;
  while (h > 0) {
    i++;
    h /= 10;
  }
  return i;
}
int data(int g, int num) // 返回num的第g位数字
{
  int result, i = 1;
  int k = Num(num); // 获取位数
  if (num == 0 || g > k)
    return 0;
  else if (num <= 9 && g == 1)
    return num;

  while (num >= 10 && i < g) {
    num /= 10;
    i++;
  }
  result = num % 10;
  return result;
}
int main() {
  int n, i = 0, j, a[100], max = 0, k = 0, e, t = 0;
  scanf("%d\n", &n);
  SqQueue *q[10];
  for (i = 0; i < 10; i++) {
    InitQueue(q[i]);
  }

  for (i = 0; i < n; i++) {
    if (i != n - 1)
      scanf("%d ", &a[i]);
    else
      scanf("%d", &a[i]);
  }                       // a[i]='\0';
  for (i = 0; i < n; i++) // 找出最大值
  {
    k = Num(a[i]);
    if (k > max)
      max = k;
  }
  //  printf("%d\n",max);
  for (i = 1; i <= max; i++) //
  {
    printf("Step%d.\n", i);

    for (j = 0; j < 10; j++) { // 建立0-9的队对应的数字并输出
      for (k = 0; k < n; k++) {
        if (data(i, a[k]) == j)
          enQueue(q[j], a[k]);
      }
    }
    t = 0;
    for (j = 0; j < 10; j++) {
      printf("Queue%d:", j);
      while (!QueueEmpty(q[j])) {
        deQueue(q[j], e);
        a[t++] = e;
        printf("%d ", e);
      }
      printf("\n");
    }
    // printf("\n");
  }
  for (i = 0; i < n; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
  system("pause");
  return 0;
}
题目详情
38 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 2.4 大小设置

寻找边缘

给定一张 R*C 的地图, 由 "X" 和 "O" 组成。

现在需要重新处理这张地图, 找到地图边缘的那些 "O"。 你需要将这些地图边缘上的 "O" 保留下来, 然后将其他的 "O" 全部替换为 "X"。

地图边缘的 "O" 指的是那些处于第一行/列或最后一行/列上的 "O",以及从这些 "O" 的相邻位置(上下左右) 延伸出去的 "O"。

时间限制: 1000

内存限制: 65536

输入

第一行是一个正整数 T, 表示一共有 T 组数据。 对于每组数据, 其第一行是两个正整数 R 和 C, 表示地图的大小, 用一个空格分开。 接下来的 R 行, 每行包含了 C 个字符, 分别是 "X" 或 "O"。 其中,0 < T <= 10, 0 < R, C <= 500。

输出

对于每组数据, 输出 R 行, 每行包含了 C 个字符, 分别是 "X" 或"O"。 每组数据之间需要额外输出一个空行。

样例输入

2
2 3
OXX
XXO
5 5
XXXOX
XXXOX
XOOXX
XXOXX
XOXXX

样例输出

OXX
XXO

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

using namespace std;
int r, c;
char a[505][505];
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 (a[nx][ny] == 'O') {
      a[nx][ny] = '?';
      dfs(nx, ny);
    }
  }
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    memset(a, 0, sizeof(a));
    cin >> r >> c;
    int i, j;
    for (i = 1; i <= r; i++)
      for (j = 1; j <= c; j++)
        cin >> a[i][j];
    for (i = 1; i <= r; i++) {
      if (a[i][1] == 'O') {
        a[i][1] = '?';
        dfs(i, 1);
      }
      if (a[i][c] == 'O') {
        a[i][c] = '?';
        dfs(i, c);
      }
    }
    for (i = 1; i <= c; i++) {
      if (a[1][i] == 'O') {
        a[1][i] = '?';
        dfs(1, i);
      }
      if (a[r][i] == 'O') {
        a[r][i] = '?';
        dfs(r, i);
      }
    }
    for (i = 1; i <= r; i++) {
      for (j = 1; j <= c; j++) {
        if (a[i][j] == '?')
          cout << 'O';
        else
          cout << 'X';
      }
      cout << endl;
    }
    cout << endl;
  }
  return 0;
}
题目详情
39 简答题 偏难 Scratch编程考级 ·Scratch编程一级 · 2.4 大小设置

42 点

42 是:

· 组合数学上的第 5 个卡特兰数

· 字符'*'的 ASCII 码

· 钼的原子序数

· 6 与 9 的乘积结果的 13 进制表示

· 生命、 宇宙以及任何事情的终极答案

· 以及……表达式(1+5)/2*(6-4)*7 的值

因此, 小机器人 Marvin 发明了这个叫 42 点的小游戏。在这个游戏中,玩家会获得 n 个数。 玩家需要使用'+'、 '-'、 '*'、 '/'、 '('、 ')'以及这 n 个数构成一个合法的中缀表达式, 并使得该表达式的值为 42。 n 个数之间的顺序可以改变。 表达式运算过程中只能出现整数。

由于过于抑郁, Marvin 无力完成这个游戏, 于是来找你帮忙。 你的任务是对于给定的 n 个数, 判断他们是否能根据上述游戏规则算出 42。

时间限制: 1000

内存限制: 65536

输入

第一行为一个数 n, 1<=n<=6。 第二行为 n 个数, 每个数均为[1,13]范围内的整数。

输出

输出一行, 若可以算出 42 则输出“YES”, 否则输出“NO”(注意大小写)。

样例输入

6
1 5 2 6 4 7

样例输出

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

bool dfs(int a[], int n) {
  if (n == 1) {
    return a[0] == 42;
  }
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      int b[10];
      int m = 0;
      for (int k = 0; k < n; ++k) {
        if (k == i || k == j)
          continue;
        b[m++] = a[k];
      }
      ++m;
      b[m - 1] = a[i] + a[j];
      if (dfs(b, m))
        return 1;
      b[m - 1] = a[i] - a[j];
      if (dfs(b, m))
        return 1;
      b[m - 1] = a[j] - a[i];
      if (dfs(b, m))
        return 1;
      b[m - 1] = a[i] * a[j];
      if (dfs(b, m))
        return 1;
      if (a[j] != 0)
        b[m - 1] = a[i] / a[j];
      if (dfs(b, m))
        return 1;
      if (a[i] != 0)
        b[m - 1] = a[j] / a[i];
      if (dfs(b, m))
        return 1;
    }
  }
  return 0;
}

int main() {
  int n;
  int a[10];
  cin >> n;
  for (int i = 0; i < n; ++i)
    cin >> a[i];
  if (dfs(a, n))
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  system("pause");
  return 0;
}
题目详情