Scratch编程一级 题库
按照个位数排序
对于给定的正整数序列,按照个位数从小到大排序,个位数相同的按照本身大小从小到大排序。
时间限制: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;
}
图像叠加
给出两幅相同大小的黑白图像(用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;
}字符判断
对于给定的字符,如果该字符是大小写字母或者数字,输出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;
}替换单词
输入一个字符串,以回车结束(字符串长度<=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;
}多项式相加
我们经常遇到两多项式相加的情况,在这里,我们就需要用程序来模拟实现把两个多项式相加到一起。首先,我们会有两个多项式,每个多项式是独立的一行,每个多项式由系数、幂数这样的多个整数对来表示。
如多项式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;
}冠军之路
当训练师眼神对上的那一刻,就会开始对战。
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;
}打字员
有一个打字员,他打字的时候有个习惯,从来不用 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;
}滑动窗口
给定一个长度为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;
}棋盘问题
在一个给定形状的棋盘(形状可能是不规则的)上面摆放棋子,棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列,请编程求解对于给定形状和大小的棋盘,摆放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;
}序列排序
对于给定的正整数序列,按照每个数的各位数和从大到小排序,各位数和相同的按照本身大小排序,大的在前,小的在后。
时间限制: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;
}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;
}斗地主大师
斗地主大师今天有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;
}删除数字
娇娇一年级了,刚刚学会了识数和比大小。有一天,她在黑板上写上了一串数字: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;
}
解题思路
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。
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;
}多项式相加
我们经常遇到两多项式相加的情况, 在这里, 我们就需要用程序来模拟实现把两个多项式相加到一起。 首先, 我们会有两个多项式,每个多项式是独立的一行, 每个多项式由系数、 幂数这样的多个整数对来表示。
如多项式 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;
}
扩号匹配问题
在某个字符串(长度不超过 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;
}利用队列进行数字排序
对于 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;
}寻找边缘
给定一张 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;
}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;
}