Scratch编程一级 题库
小白鼠再排队2
N只小白鼠(1 < N < 100),每只鼠头上戴着一顶有颜色的帽子。现在称出每只白鼠的重量,要求按照白鼠重量从小到大的顺序输出它们头上帽子的颜色。帽子的颜色用 “red”,“blue”等字符串来表示。不同的小白鼠可以戴相同颜色的帽子。白鼠的重量用整数表示。
时间限制:1000
内存限制:65536
输入
输入第一行为一个整数N,表示小白鼠的数目。 下面有N行,每行是一只白鼠的信息。第一个为正整数,表示白鼠的重量,不超过整型范围;第二个为字符串,表示白鼠的帽子颜色,字符串长度不超过10个字符。 注意:白鼠的重量各不相同。
输出
按照白鼠的重量从小到大的顺序输出白鼠的帽子颜色。
样例输入
3 30 red 50 blue 40 green
样例输出
red green blue
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
struct sb {
int z;
char s[15];
} a[105];
bool cmp(sb a, sb b) { return a.z < b.z; }
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].z >> a[i].s;
}
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < strlen(a[i].s); j++) {
cout << a[i].s[j];
}
cout << endl;
}
return 0;
}队列和栈
队列和栈是两种重要的数据结构,它们具有push k和pop操作。push k是将数字k加入到队列或栈中,pop则是从队列和栈取一个数出来。队列和栈的区别在于取数的位置是不同的。
队列是先进先出的:把队列看成横向的一个通道,则push k是将k放到队列的最右边,而pop则是从队列的最左边取出一个数。
栈是后进先出的:把栈也看成横向的一个通道,则push k是将k放到栈的最右边,而pop也是从栈的最右边取出一个数。
假设队列和栈当前从左至右都含有1和2两个数,则执行push 5和pop操作示例图如下:
push 5 pop
队列 1 2 -------> 1 2 5 ------> 2 5
push 5 pop
栈 1 2 -------> 1 2 5 ------> 1 2
现在,假设队列和栈都是空的。给定一系列push k和pop操作之后,输出队列和栈中存的数字。若队列或栈已经空了,仍然接收到pop操作,则输出error。
时间限制:1000
内存限制:65536
输入
第一行为m,表示有m组测试输入,m<100。 每组第一行为n,表示下列有n行push k或pop操作。(n<150) 接下来n行,每行是push k或者pop,其中k是一个整数。 (输入保证同时在队列或栈中的数不会超过100个)
输出
对每组测试数据输出两行,正常情况下,第一行是队列中从左到右存的数字,第二行是栈中从左到右存的数字。若操作过程中队列或栈已空仍然收到pop,则输出error。输出应该共2*m行。
样例输入
2 4 push 1 push 3 pop push 5 1 pop
样例输出
3 5 1 5 error error
#include <stdio.h>
#include <string.h>
#define N 150
int stack[N], ps;
int queue[N], qh, qt;
char cmd[5];
int main(void) {
int m, n, sflag, qflag, a, i;
scanf("%d", &m);
while (m--) {
scanf("%d", &n);
sflag = qflag = 0;
ps = 0, qh = 0;
qt = 0;
while (n--) {
scanf("%s", cmd);
if (cmd[1] == 'u') {
scanf("%d", &a);
stack[ps++] = a;
queue[qt++] = a;
} else if (cmd[1] == 'o') {
if (ps == 0)
sflag = 1;
if (qt - qh == 0)
qflag = 1;
ps--;
qh++;
}
}
if (qflag)
printf("error\n");
else {
for (i = qh; i < qt; i++)
printf("%d ", queue[i]);
printf("\n");
}
if (sflag)
printf("error\n");
else {
for (i = 0; i < ps; i++)
printf("%d ", stack[i]);
printf("\n");
}
}
return 0;
}出栈序列统计
栈是常用的一种数据结构,有n个元素在栈顶端一侧等待进栈,栈顶端另一侧是出栈序列。你已经知道栈的操作有两种:push和pop,前者是将一个元素进栈,后者是将栈顶元素弹出。现在要使用这两种操作,由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n,计算并输出由操作数序列1,2,…,n,经过一系列操作可能得到的输出序列总数。
时间限制:1000
内存限制:65536
输入
就一个数n(1≤n≤15)。
输出
一个数,即可能输出序列的总数目。
样例输入
3
样例输出
5
提示
先了解栈的两种基本操作,进栈push就是将元素放入栈顶,栈顶指针上移一位,等待进栈队列也上移一位,出栈pop是将栈顶元素弹出,同时栈顶指针下移一位。 用一个过程采模拟进出栈的过程,可以通过循环加递归来实现回溯:重复这样的过程,如果可以进栈则进一个元素,如果可以出栈则出一个元素。就这样一个一个地试探下去,当出栈元素个数达到n时就计数一次(这也是递归调用结束的条件)。
#include <cstdio>
#include <iostream>
using namespace std;
int n, ans;
void dfs(int in, int out) {
if (out == 0)
ans++;
else if (in == 0) {
dfs(in + 1, out - 1); // 进栈
} else {
dfs(in + 1, out - 1); // 进栈
dfs(in - 1, out); // 出栈
}
}
int main() {
while (scanf("%d", &n) != EOF) {
ans = 0;
dfs(0, n);
printf("%d\n", ans);
}
return 0;
}词典
你旅游到了一个国外的城市。那里的人们说的外国语言你不能理解。不过幸运的是,你有一本词典可以帮助你。
时间限制:3000
内存限制:65536
输入
首先输入一个词典,词典中包含不超过100000个词条,每个词条占据一行。每一个词条包括一个英文单词和一个外语单词,两个单词之间用一个空格隔开。而且在词典中不会有某个外语单词出现超过两次。词典之后是一个空行,然后给出一个由外语单词组成的文档,文档不超过100000行,而且每行只包括一个外语单词。输入中出现单词只包括小写字母,而且长度不会超过10。
输出
在输出中,你需要把输入文档翻译成英文,每行输出一个英文单词。如果某个外语单词不在词典中,就把这个单词翻译成“eh”。
样例输入
dog ogday cat atcay pig igpay froot ootfray loops oopslay atcay ittenkay oopslay
样例输出
cat eh loops
提示
输入比较大,推荐使用C语言的I / O函数。
#include <algorithm>
#include <stdio.h>
#include <string.h>
#define MAXSTR 11
#define MAXWORD 100010
using namespace std;
typedef struct {
char foreign[MAXSTR];
char english[MAXSTR];
} m_word;
m_word m_dic[MAXWORD];
int compare(const void *elem1, const void *elem2) {
return strcmp(((m_word *)elem1)->foreign, ((m_word *)elem2)->foreign);
}
int main() {
int count = 0;
char chs[30];
while (fgets(chs, 29, stdin), chs[0] != '\n') {
sscanf(chs, "%s%s", m_dic[count].english, m_dic[count].foreign);
count++;
}
qsort(m_dic, count, sizeof(m_word), compare);
m_word tmp;
m_word *ans;
while (scanf("%s", tmp.foreign) != EOF) {
ans = (m_word *)bsearch(&tmp, m_dic, count, sizeof(m_word), compare);
if (ans != NULL)
printf("%s\n", ans->english);
else
printf("eh\n");
}
return 0;
}逃离迷宫
你在一个地下迷宫中找到了宝藏,但是也触发了迷宫机关,导致迷宫将在T分钟后坍塌,为此你需要在T分钟内逃离迷宫,你想知道你能不能逃离迷宫。迷宫是一个边长为m的正方形,其中"S"表示你所在的位置,"E"表示迷宫出口,"."是可以随意走动的区域,"#"是不可穿行的墙壁,每次你可以耗费1分钟在区域间移动(上下左右四个方向)。
时间限制:1000
内存限制:65536
输入
输入包含多组数组,第一行是一个整数K(1 <= K <= 10),表示有K组数据。接下来每组数组包含整数m(2<=m<=10)和整数T,m表示正方形迷宫的边长,T表示坍塌时间。其后是一个m*m的字符矩阵,包含字符"S", "E", "."和"#"。
输出
每组数据输出一行,输出“YES"或者"NO",表示是否可以在坍塌之前逃离(也就是说移动次数是否可以不超过T)。
样例输入
2 4 7 S... ###. .#E. ..#. 3 4 S.. ..# .#E
样例输出
YES NO
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAX_M 12
struct node {
int x, y;
int tcnt;
};
int m, t;
char mat[MAX_M][MAX_M];
int bfs(int x0, int y0, int x1, int y1) {
if (x0 == x1 && y0 == y1) {
return 0;
}
struct node nd = {x0, y0, 0};
int x, y;
struct node q[MAX_M * MAX_M];
int front = 0, rear = 0;
q[rear++] = nd;
while (front < rear) {
nd = q[front++];
x = nd.x;
y = nd.y;
if (x < m - 1) {
if (mat[x + 1][y] == 'E') {
return nd.tcnt + 1;
} else if (mat[x + 1][y] == '.') {
struct node newNode = {x + 1, y, nd.tcnt + 1};
q[rear++] = newNode;
mat[x + 1][y] = '*';
}
}
if (x > 0) {
if (mat[x - 1][y] == 'E') {
return nd.tcnt + 1;
} else if (mat[x - 1][y] == '.') {
struct node newNode = {x - 1, y, nd.tcnt + 1};
q[rear++] = newNode;
mat[x - 1][y] = '*';
}
}
if (y < m - 1) {
if (mat[x][y + 1] == 'E') {
return nd.tcnt + 1;
} else if (mat[x][y + 1] == '.') {
struct node newNode = {x, y + 1, nd.tcnt + 1};
q[rear++] = newNode;
mat[x][y + 1] = '*';
}
}
if (y > 0) {
if (mat[x][y - 1] == 'E') {
return nd.tcnt + 1;
} else if (mat[x][y - 1] == '.') {
struct node newNode = {x, y - 1, nd.tcnt + 1};
q[rear++] = newNode;
mat[x][y - 1] = '*';
}
}
}
return -1;
}
int main() {
int k, i, j, x0, y0, x1, y1, ans;
scanf("%d", &k);
while (k--) {
scanf("%d %d", &m, &t);
for (i = 0; i < m; i++) {
for (j = 0; j < m; j++) {
scanf(" %c", &mat[i][j]);
if (mat[i][j] == 'S') {
x0 = i;
y0 = j;
} else if (mat[i][j] == 'E') {
x1 = i;
y1 = j;
}
}
}
ans = bfs(x0, y0, x1, y1);
if (ans <= t && ans >= 0) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}夺宝探险
你无意中发现了装满了宝藏的迷宫,你想要获得尽可能多的宝藏,但是迷宫里的机关阻碍了你的计划。迷宫的地面是M行N列的矩形网格,每格是一块带有机关且放置了1个宝藏的地砖,宝藏一共有K种,用1-K表示其种类,迷宫的入口只有一个,为迷宫的第一行第一列。地砖的机关如下:
1. 每次你只能踏到你与你所在地砖相邻的地砖上(即前后左右4块);
2. 当你踏上某块地砖后,其上的宝藏(假设种类为k)自动归属你,同时所有放置了种类为k的宝藏的地砖碎裂,你无法踏上,你当前所在的地砖在你离开后也会立刻碎裂;
3. 当你无路可走的时候,你会被传送回迷宫出口,无法再进入迷宫。
你想知道你最多能获得多少宝藏。
时间限制:1000
内存限制:65536
输入
输入的第一行是三个用空格隔开的整数,分别是M、N和K(1 <= M,N <= 20, 1 <= K <= 100) 之后是M行,每行包含N个范围为1-K的整数,用空格隔开,表示放置的宝藏种类
输出
只有一行,为一个整数,表示最多能获得的宝藏个数。
样例输入
3 4 5 1 2 3 3 2 1 4 3 1 5 1 2
样例输出
4
#include <iostream>
using namespace std;
int m, n, k;
int a[22][22];
bool jewel[101];
int have = 0; // 获得的宝石数
int ans = 0;
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 (!jewel[a[nx][ny]]) {
jewel[a[nx][ny]] = true;
have++;
dfs(nx, ny);
have--;
jewel[a[nx][ny]] = false;
}
}
ans = max(ans, have);
}
int main() {
cin >> m >> n >> k;
int i, j;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
cin >> a[i][j];
jewel[a[1][1]] = true;
jewel[0] = true;
have = 1;
dfs(1, 1);
cout << ans;
return 0;
}晶矿的个数
在某个区域发现了一些晶矿,已经探明这些晶矿总共有分为两类,为红晶矿和黑晶矿。现在要统计该区域内红晶矿和黑晶矿的个数。假设可以用二维地图m[][]来描述该区域,若m[i][j]为#表示该地点是非晶矿地点,若m[i][j]为r表示该地点是红晶矿地点,若m[i][j]为b表示该地点是黑晶矿地点。一个晶矿是由相同类型的并且上下左右相通的晶矿点组成。现在给你该区域的地图,求红晶矿和黑晶矿的个数。
时间限制:1000
内存限制:65536
输入
第一行为k,表示有k组测试输入。 每组第一行为n,表示该区域由n*n个地点组成,3 <= n<= 30 接下来n行,每行n个字符,表示该地点的类型。
输出
对每组测试数据输出一行,每行两个数字分别是红晶矿和黑晶矿的个数,一个空格隔开。
样例输入
2 6 r##bb# ###b## #r##b# #r##b# #r#### ###### 4 #### #rrb #rr# ##bb
样例输出
2 2 1 2
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
char b[N][N + 1];
int n;
void dfs(int r, int c, char type) {
if (r < 0 || r >= n || c < 0 || c >= n)
return;
if (b[r][c] != type)
return;
b[r][c] = '#';
dfs(r - 1, c, type);
dfs(r + 1, c, type);
dfs(r, c - 1, type);
dfs(r, c + 1, type);
}
int main() {
int k;
scanf("%d", &k);
while (k--) {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%s", b[i]);
int rcnt = 0, bcnt = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (b[i][j] == 'r') {
rcnt++;
dfs(i, j, 'r');
} else if (b[i][j] == 'b') {
bcnt++;
dfs(i, j, 'b');
}
printf("%d %d\n", rcnt, bcnt);
}
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;
}小白鼠再排队
N只小白鼠(1 < N < 100),每只鼠头上戴着一顶有颜色的帽子。现在称出每只白鼠的重量,要求按照白鼠重量从小到大的顺序输出它们头上帽子的颜色。帽子的颜色用 “red”,“blue”等字符串来表示。不同的小白鼠可以戴相同颜色的帽子。白鼠的重量用整数表示。
时间限制:1000
内存限制:65536
输入
输入第一行为一个整数N,表示小白鼠的数目。 下面有N行,每行是一只白鼠的信息。第一个为正整数,表示白鼠的重量,不超过整型范围;第二个为字符串,表示白鼠的帽子颜色,字符串长度不超过10个字符。 注意:白鼠的重量各不相同。
输出
按照白鼠的重量从小到大的顺序输出白鼠的帽子颜色。
样例输入
3 30 red 50 blue 40 green
样例输出
red green blue
#include <iostream>
using namespace std;
int main() {
int a[100]; // 体重
string b[100]; // 帽子颜色
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i] >> b[i];
for (int i = n - 1; i > 0; i--) // 冒泡排序
for (int j = 0; j < i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
swap(b[j], b[j + 1]);
}
}
for (int i = 0; i < n; i++)
cout << b[i] << endl;
return 0;
}多余的数
小A同学在完成一个数学题:求给定的10个整数的和。小A同学在求完之后发现和参考答案对不上,检查后发现在求和过程中多计算了一个数,其他过程没有问题。现给出小A计算用的11个数,以及正确的参考答案,请算出小A同学多计算的那一个数。
时间限制:1000
内存限制:65536
输入
第一行11个正整数,每个数小于等于1000000 第二行一个整数,表示参考答案
输出
一个整数,表示多计算的那一个数。
样例输入
2 4 6 8 1 3 5 7 9 5 11 54
样例输出
7
提示
样例中原有的10个数为2 4 6 8 1 3 5 9 5 11,和为54,多余的数为7。
#include <iostream>
using namespace std;
int main() {
int sum = 0, a, t;
for (int i = 1; i <= 11; i++) {
cin >> a;
sum = sum + a; // 11个数总和
}
cin >> t;
cout << sum - t; // 11个数总和-10个数总和=多加的数
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;
}最好的草
奶牛Bessie计划好好享受柔软的春季新草。新草分布在R行C列的牧场里。它想计算一下牧场中的草丛数量。
在牧场地图中,每个草丛要么是单个“#”,要么是有公共边的相邻两个“#”。给定牧场地图,计算有多少个草丛。
例如,考虑如下5行6列的牧场地图
. # . . . .
. . # . . .
. . # . . #
. . . # # .
. # . . . .
这个牧场有5个草丛:一个在第一行,一个在第二列横跨了二、三行,一个在第三行,一个在第四行横跨了四、五列,最后一个在第五行。
时间限制:10000
内存限制:65536
输入
第一行包含两个整数R和C,中间用单个空格隔开。 接下来R行,每行C个字符,描述牧场地图。字符只有“#”或“.”两种。(1 <= R, C <= 100 )
输出
输出一个整数,表示草丛数。
样例输入
5 6 .#.... ..#... ..#..# ...##. .#....
样例输出
5
#include <iostream>
using namespace std;
int R, C, cnt = 0;
string grass[100];
void dfs(int x, int y) {
int step[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 记录当前位置的四个方向
for (int i = 0; i < 4; ++i) {
int xx = x + step[i][0], yy = y + step[i][1];
if (xx < 0 || xx >= R || yy < 0 || yy >= C) // 判断边界
continue;
if (grass[xx][yy] == '#') {
grass[xx][yy] = '.'; // 标记
dfs(xx, yy);
}
}
}
int main() {
cin >> R >> C;
for (int i = 0; i < R; ++i)
cin >> grass[i];
for (int i = 0; i < R; ++i)
for (int j = 0; j < C; ++j)
if (grass[i][j] == '#') {
cnt++;
dfs(i, j);
}
cout << cnt;
return 0;
}字符串中最长的连续出现的字符
求一个字符串中最长的连续出现的字符,输出该字符及其出现次数。字符串中无空白字符(空格、回车和tab),如果这样的字符不止一个,则输出出现最早的字符。
时间限制:1000
内存限制:65536
输入
一行,一个不包含空白字符的字符串,字符串长度小于200。
输出
一行,输出最长的连续出现的字符及其最长的连续出现次数,中间以一个空格分开。
样例输入
aaaaadbbbbbcccccccdddddddddd
样例输出
d 10
#include <iostream>
using namespace std;
int main() {
string s;
int n = 1, maxn = 1;
char maxc;
cin >> s;
int len = s.size(); // 字符串长度
maxc = s[0];
for (int i = 1; i < len; i++) {
if (s[i] == s[i - 1]) { // 与前一个字符相同,将n累加
n++;
if (n > maxn) { // 当前字符连续出现次数超过存储的最大值
maxn = n;
maxc = s[i];
}
} else
n = 1;
}
cout << maxc << " " << maxn;
return 0;
}公共子序列
我们称序列Z = < z1, z2, ..., zk >是序列X = < x1, x2, ..., xm >的子序列当且仅当存在 严格上升 的序列< i1, i2, ..., ik >,使得对j = 1, 2, ... ,k, 有xij = zj。比如Z = < a, b, f, c > 是X = < a, b, c, f, b, c >的子序列。 现在给出两个序列X和Y,你的任务是找到X和Y的最大公共子序列,也就是说要找到一个最长的序列Z,使得Z既是X的子序列也是Y的子序列。
时间限制:3000
内存限制:65536
输入
输入包括多组测试数据。每组数据包括一行,给出两个长度不超过200的字符串,表示两个序列。两个字符串之间由若干个空格隔开。
输出
对每组输入数据,输出一行,给出两个序列的最大公共子序列的长度。
样例输入
abcfbc abfcab programming contest abcd mnp
样例输出
4 2 0
#include <bits/stdc++.h>
#include <string>
using namespace std;
int f[1000][1000];
int main() {
string a, b;
while (cin >> a >> b) {
int n = a.size();
int m = b.size();
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= m; k++) {
if (a[i - 1] == b[k - 1]) {
f[i][k] = max(f[i][k], f[i - 1][k - 1] + 1);
} else {
f[i][k] = max(f[i][k - 1], f[i - 1][k]);
}
}
}
cout << f[n][m] << endl;
}
return 0;
}硬币问题
有N(不大于100)种硬币,编号为1至N,已知每种硬币的重量(不超过100的正整数)和面额(不超过100的正整数),每种硬币数量不限。选取总重量不超过C(不大于1000的正整数)的硬币,最多能获得多少总面额?
时间限制:1000
内存限制:65536
输入
第一行输入N 第二行输入C 第三行输入各硬币重量,用空格隔开 第四行输入各硬币价值,用空格隔开
输出
最大总面额
样例输入
3 5 1 2 5 1 3 6
样例输出
7
#include <bits/stdc++.h>
using namespace std;
int t[105], v[105];
int dp[1005];
int main() {
int n, c;
cin >> n >> c;
for (int i = 1; i <= n; i++)
cin >> t[i];
for (int i = 1; i <= n; i++)
cin >> v[i];
for (int i = 1; i <= n; i++) {
for (int j = t[i]; j <= c; j++) {
dp[j] = max(dp[j], dp[j - t[i]] + v[i]);
}
}
cout << dp[c];
return 0;
}田忌赛马
你一定听过田忌赛马的故事吧?
如果3匹马变成1000匹,齐王仍然让他的马按从优到劣的顺序出赛,田忌可以按任意顺序选择他的赛马出赛。赢一局,田忌可以得到200两银子,输一局,田忌就要输掉200两银子,平局的话不输不赢。
请问田忌最多能赢多少银子?
时间限制:5000
内存限制:65536
输入
输入包含多组测试数据. 每组测试数据的第一行是一个整数n(1<=n<=1000),表示田忌和齐王都拥有n匹马。接下来一行是n个整数,表示田忌的马的速度,下一行也是n个整数,表示齐王的马的速度。 输入的最后以一个0表示结束。
输出
对每组数据,输出一个整数,表示田忌至多可以赢多少银子,如果田忌赢不了,就输出一个负数,表示田忌最少要输多少银子。
样例输入
3 92 83 71 95 87 74 2 20 20 20 20 2 20 19 22 18 0
样例输出
200 0 0
#include <bits/stdc++.h>
using namespace std;
int h1, h2, t1, t2, n, i, ans = 0;
int t[100001], k[100001];
int cmp(int a, int b) { return a > b; }
int main() {
while (cin >> n && n) {
for (i = 1; i <= n; i++)
cin >> t[i];
for (i = 1; i <= n; i++)
cin >> k[i];
sort(t + 1, t + n + 1, cmp);
sort(k + 1, k + n + 1, cmp);
h1 = h2 = 1;
t1 = t2 = n;
while (h1 <= t1) {
if (t[h1] > k[h2])
ans += 200, h1++, h2++;
else {
if (t[h1] < k[h2])
ans -= 200, t1--, h2++;
else {
if (t[t1] > k[t2])
ans += 200, t1--, t2--;
else {
if (t[t1] < k[h2])
ans -= 200;
t1--, h2++;
}
}
}
}
cout << ans << endl;
ans = 0;
}
}上机
又到周末了,同学们陆陆续续开开心心的来到机房上机。jbr也不例外,但是他到的有点晚,发现有些机位上已经有同学正在做题,有些机位还空着。细心的jbr发现,一位同学来到机房,坐在机位i上,如果他的左右两边都空着,他将获得能力值a[i];如果当他坐下时,左边或者右边已经有一个人在上机了,他将获得能力值b[i];如果当他坐下时,他的左边右边都有人在上机,他将获得能力值c[i]。
同时他发现,已经在上机的同学不会受到刚要坐下的同学的影响,即他们的能力值只会在坐下时产生,以后不会发生变化;第一个机位左边没有机位,最后一个机位右边没有机位,无论何时坐在这两个机位上将无法获得c值。
这时jbr发现有一排机器还空着,一共有N个机位,编号1到N。这时有N位同学们陆陆续续来到机房,一个一个按照顺序坐在这排机位上。聪明的jbr想知道怎么安排座位的顺序,可以使这N位同学获得能力值的和最大呢?
时间限制:1000
内存限制:65536
输入
第一行一个整数N(1<= N <= 10000)
第二行N个数,表示a[i]
第三行N个数,表示b[i]
第四行N个数,表示c[i]
(1<= a[i],b[i],c[i] <=10000)
输出
一个整数,表示获得最大的能力值和
样例输入
4 1 2 2 4 4 3 3 1 2 1 1 2
样例输出
14
提示
第一位同学坐在第四个机位上,获得能力值4; 第二位同学坐在第三个机位上,获得能力值3; 第三位同学坐在第二个机位上,获得能力值3; 第四位同学坐在第一个机位上,获得能力值4; 总和为14。
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
int a[10005];
int b[10005];
int c[10005];
int d
[10005]
[4]; // 考虑前i的座位已经坐好的前i个座位最大值,0-第i个人坐下的时候两边没人,1-左边有人,2-右边有人,3-都有人
int main() {
int n;
cin >> n;
int i;
for (i = 1; i <= n; i++)
cin >> a[i];
for (i = 1; i <= n; i++)
cin >> b[i];
for (i = 1; i <= n; i++)
cin >> c[i];
d[1][0] = a[1];
d[1][2] = b[1];
for (i = 2; i <= n; i++) {
d[i][0] =
max(d[i - 1][3], d[i - 1][2]) +
a[i]; // 第i个位置坐下的时候两边没人,要求它先于第i-1个人被坐,也就是说第i-1个人坐下的时候一定是右边有人
d[i][1] = max(d[i - 1][0], d[i - 1][1]) + b[i];
d[i][2] = max(d[i - 1][3], d[i - 1][2]) + b[i];
d[i][3] = max(d[i - 1][0], d[i - 1][1]) + c[i];
}
cout << max(d[n][0], d[n][1]);
return 0;
}// 参考答案2
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 10000 + 1;
int a[N], b[N], c[N], dp[N][4];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &b[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &c[i]);
dp[1][0] = a[1];
dp[1][1] = -INF;
dp[1][2] = b[1];
dp[1][3] = -INF;
for (int i = 2; i <= n; i++) {
dp[i][0] = a[i] + max(dp[i - 1][2], dp[i - 1][3]);
dp[i][1] = b[i] + max(dp[i - 1][0], dp[i - 1][1]);
dp[i][2] = b[i] + max(dp[i - 1][2], dp[i - 1][3]);
dp[i][3] = c[i] + max(dp[i - 1][0], dp[i - 1][1]);
}
printf("%d\n", max(dp[n][0], dp[n][1]));
return 0;
}制作蛋糕
小A擅长制作香蕉蛋糕和巧克力蛋糕。制作一个香蕉蛋糕需要2个单位的香蕉,250个单位的面粉,75个单位的糖,100个单位的黄油。制作一个巧克力蛋糕需要75个单位的可可粉,200个单位的面粉,150个单位的糖,150个单位的黄油。一个香蕉蛋糕可以卖出400元,而一个巧克力蛋糕可以卖出450元。为了避免蛋糕变质,每种蛋糕至多只能制作100个。
现已知每种原料的数量,求小A至多可以卖出多少元的蛋糕。
时间限制:1000
内存限制:65536
输入
依次输入面粉、香蕉、糖、黄油、可可粉的数量,每种原料数量均为不超过100000的整数。
输出
输出一个整数,表示最多卖出的钱数。
样例输入
4000 6 2000 500 500
样例输出
1700
#include <bits/stdc++.h>
using namespace std;
int main() {
int mf, xj, t, hy, kkf, xjcake = 0, kkcake = 0, msum = 0, sum = 0;
cin >> mf >> xj >> t >> hy >> kkf;
for (int i = 0; i <= xj / 2; i++)
for (int j = 0; j <= kkf / 75; j++) {
if ((i * 250 + j * 200) <= mf && (i * 75 + j * 150) <= t &&
(i * 100 + j * 150) <= hy && i <= 100 && j <= 100) {
sum = i * 400 + j * 450;
if (sum > msum)
msum = sum;
}
}
cout << msum;
return 0;
}找和最接近但不超过K的两个元素
在一个长度为n(1 < n < 1000)的整数(0至1000之间)序列中,选出两个元素使得它们的和最接近但不超过K(0 <= K < 2000)。保证一定存在不超过K的两元素和。<n<1000)的整数(0至1000之间)序列中,选出两个元素使得它们的和最接近但不超过k(0<=k<2000)。保证一定存在不超过k的两元素和。<n<1000)的整数(0至1000之间)序列中,选出两个元素使得它们的和最接近但不超过k(0<=k<2000)。保证一定存在不超过k的两元素和。
<n<1000)的整数(0至1000之间)序列中,选出两个元素使得它们的和最接近但不超过k(0<=k<2000)。保证一定存在不超过k的两元素和。
时间限制:1000
内存限制:65536
输入
第一行输入一个整数n 第二行输入一个整数K 第三行输入序列,用空格分开
输出
最接近但不超过K的和
样例输入
4 7 1 2 2 8
样例输出
4
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
int a[10005];
int main() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a, a + n);
int l = 0, r = n - 1;
int ans = a[0] + a[1];
while (l < r) {
int sum = a[l] + a[r];
if (sum <= k) {
if (k - sum < k - ans)
ans = sum;
}
if (sum == k) {
cout << k << endl;
return 0;
} else if (sum < k)
l++;
else
r--;
}
cout << ans << endl;
}数根
树根可以通过把一个数的各个位上的数字加起来得到。如果得到的数是一位数,那么这个数就是数根。如果结果是两位数或者包括更多位的数字,那么再把这些数字加起来。如此进行下去,直到得到是一位数为止。比如,对于24来说,把2和4相加得到6,由于6是一位数,因此6是24的数根。再比如39,把3和9加起来得到12,由于12不是一位数,因此还得把1和2加起来,最后得到3,这是一个一位数,因此3是39的数根。
输入
一个正整数(小于10^1000)
输出
一个数字,即输入数字的数根
样例输入
24
样例输出
6
#include <bits/stdc++.h>
using namespace std;
int sg(int n) {
int sum = 0;
while (n) {
sum += n % 10;
n /= 10;
}
if (sum >= 10)
return sg(sum);
return sum;
}
int main() {
string s;
int len, ans = 0;
cin >> s;
len = s.size();
for (int i = 0; i < len; i++) {
ans = ans + s[i] - '0';
}
cout << sg(ans);
return 0;
}