Scratch编程一级 题库
合影效果
小云和朋友们去爬香山,为美丽的景色所陶醉,想合影留念。如果他们站成一排,男生全部在左(从拍照者的角度),并按照从矮到高的顺序从左到右排,女生全部在右,并按照从高到矮的顺序从左到右排,请问他们合影的效果是什么样的(所有人的身高都不同)?
时间限制: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 main() {
int n;
cin >> n;
vector<float> Men;
vector<float> Women;
string gender;
float height;
for (int i = 1; i <= n; i++) {
cin >> gender >> height;
if (gender == "male") {
Men.push_back(height);
} else if (gender == "female") {
Women.push_back(height);
}
}
sort(Men.begin(), Men.end(), less<float>()); // sort ascending
sort(Women.begin(), Women.end(), greater<float>()); // sort descending
cout << setiosflags(ios::fixed);
copy(Men.begin(), Men.end(),
ostream_iterator<float>(cout << setprecision(2), " "));
copy(Women.begin(), Women.end(),
ostream_iterator<float>(cout << setprecision(2), " "));
cout << endl;
return 0;
}城堡问题
1 2 3 4 5 6 7
#############################
1 # | # | # | | #
#####---#####---#---#####---#
2 # # | # # # # #
#---#####---#####---#####---#
3 # | | # # # # #
#---#########---#####---#---#
4 # # | | | | # #
#############################
(图 1)
# = Wall
| = No wall
- = No wall
1
2
3
4
5
6
7
8
9
10
11
12
13
14
图1是一个城堡的地形图。请你编写一个程序,计算城堡一共有多少房间,最大的房间有多大。城堡被分割成m×n(m≤50,n≤50)个方块,每个方块可以有0~4面墙。
时间限制:1000
内存限制:65536
输入
程序从标准输入设备读入数据。第1、2行每行1个整数,分别是南北向、东西向的方块数。在接下来的输入行里,每个方块用一个数字(0≤p≤50)描述。用一个数字表示方块周围的墙,1表示西墙,2表示北墙,4表示东墙,8表示南墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次,方块(1,1)的南墙同时也是方块(2,1)的北墙。输入的数据保证城堡至少有两个房间。
输出
输出2行,每行一个数,表示城堡的房间数、城堡中最大房间所包括的方块数。结果显示在标准输出设备上。
样例输入
4 7 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13
样例输出
5 9
#include <iostream>
using namespace std;
int Room[60][60];
int RoomSign[60][60];
int RoomArea;
int RoomNum;
int MaxRoomArea;
void DFS(int i, int j) {
if (RoomSign[i][j])
return;
RoomSign[i][j] = 1;
RoomArea++;
if ((Room[i][j] & 1) == 0)
DFS(i, j - 1);
if ((Room[i][j] & 2) == 0)
DFS(i - 1, j);
if ((Room[i][j] & 4) == 0)
DFS(i, j + 1);
if ((Room[i][j] & 8) == 0)
DFS(i + 1, j);
return;
}
int main() {
int m, n;
cin >> m >> n;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> Room[i][j];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!RoomSign[i][j]) {
RoomArea = 0;
RoomNum++;
DFS(i, j);
MaxRoomArea = max(MaxRoomArea, RoomArea);
}
}
}
cout << RoomNum << endl;
cout << MaxRoomArea << 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;
}玩具摆放
在一个4*4的方框内摆放了若干个相同的玩具。
某人想通过移动玩具,将这些玩具重新摆放成为他心中理想的状态。要求每次移动时,只能将某一个玩具向上下左右四个方向之一移动一步。不能将玩具移出方框,并且移动的目标位置不能已经放置有玩具。
请你用最少的移动次数将初始的玩具状态移动到他心中的目标状态。
时间限制:10000
内存限制:524288
输入
前4行表示玩具的初始状态,每行4个数字1或0,1表示方格中放置了玩具,0表示没有放置玩具。 接着是一个空行。接下来4行表示玩具的目标状态,每行4个数字1或0,意义同上。
输出
一个整数,所需要的最少移动次数。保证初始状态可以达到目标状态。
样例输入
1111 0000 1110 0010 1010 0101 1010 0101
样例输出
4
提示
可以考虑将玩具局面表示为一个16 bit的整数,设置一个标志数组用来判重,用这个整数做下标找其对应标志位
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
// #include<cmath>
using namespace std;
const int INF = 9999999;
#define LL long long
inline int read() {
int x = 0, f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar())
if (c == '-')
f = -1;
for (; isdigit(c); c = getchar())
x = x * 10 + c - '0';
return x * f;
}
int N, E;
bool vis[65539];
char c;
int l = 1, r = 1;
struct data {
int st, k;
} Que[700001];
void BFS() {
Que[l].st = 0, Que[l].k = N;
int step, Now;
if (Que[l].k == E) {
printf("%d", Que[l].st);
return;
}
while (l <= r) {
Now = Que[l].k, step = Que[l].st;
for (int i = 1; i <= 4; i++) {
for (int j = 1; j <= 4; j++) {
if (((Now >> ((4 - i) * 4 + 4 - j)) & 1)) {
for (int p = 0; p < 4; p++) {
if (p == 0 && i != 1 &&
!((Now >> ((4 - (i - 1)) * 4 + 4 - j)) & 1) &&
!vis[Now - (1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 + 8 - j))]) {
Que[++r].k = Now - (1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 + 8 - j));
if (Que[r].k == E) {
printf("%d", step + 1);
return;
}
Que[r].st = step + 1;
vis[Que[r].k] = 1;
}
if (p == 1 && i != 4 &&
!((Now >> ((4 - (i + 1)) * 4 + 4 - j)) & 1) &&
!vis[Now - (1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 - j))]) {
Que[++r].k =
Now - (1 << ((4 - i) * 4 + 4 - j)) + (1 << ((4 - i) * 4 - j));
if (Que[r].k == E) {
printf("%d", step + 1);
return;
}
Que[r].st = step + 1;
vis[Que[r].k] = 1;
}
if (p == 2 && j != 1 &&
!((Now >> ((4 - i) * 4 + 4 - (j - 1))) & 1) &&
!vis[(1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 + 4 - (j - 1)))]) {
Que[++r].k = Now - (1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 + 4 - (j - 1)));
if (Que[r].k == E) {
printf("%d", step + 1);
return;
}
Que[r].st = step + 1;
vis[Que[r].k] = 1;
}
if (p == 3 && j != 4 &&
!((Now >> ((4 - i) * 4 + 4 - (j + 1))) & 1) &&
!vis[Now - (1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 + 4 - (j + 1)))]) {
Que[++r].k = Now - (1 << ((4 - i) * 4 + 4 - j)) +
(1 << ((4 - i) * 4 + 4 - (j + 1)));
if (Que[r].k == E) {
printf("%d", step + 1);
return;
}
Que[r].st = step + 1;
vis[Que[r].k] = 1;
}
}
}
}
}
l++;
}
}
int main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int tmp = 16;
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++) {
cin >> c;
N = N + (1 << (tmp - 1)) * (c - '0');
tmp--;
}
vis[N] = true;
tmp = 16;
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++) {
cin >> c;
E = E + (1 << (tmp - 1)) * (c - '0');
tmp--;
}
BFS();
return 0;
}哥斯拉大战金刚
众所周知,哥斯拉和金刚是时代仇敌,大战一触即发。金刚为了打败哥斯拉,要先前往地心空洞获得战斧。金刚现在所在之处可以被视为一个n*m的网格图,S表示金刚目前的位置,T表示地心空洞的入口,X表示障碍物,.表示平地。在前往地心空洞之前,金刚必须先获得一系列打开地心空洞的钥匙(在地图上通过数字1,2,…,k表示),并且获得i类钥匙的前提是金刚已经获得了1,2,…,i-1类钥匙,金刚在拿到地图上所有种类的钥匙之后即可前往地心空洞的入口。另外,同一种类的钥匙可能有多把,金刚只需获得其中任意一把即可。金刚每一步可以朝上下左右四个方向中的一个移动一格,值得注意的是,哥斯拉为了阻挠金刚的计划,还在地图上设置了q个陷阱(在网格图中用G表示),金刚第一次进入某个陷阱需要花费额外的一步来破坏陷阱(这之后该陷阱即可被视为平地)。为了更好的掌握全局,请你帮金刚计算到达地心空洞入口所需要花费的最少步数。输入数据保证有解。
时间限制:6000
内存限制:262144
输入
第一行输入两个整数n,m,表示网格图的大小。 接下来n行,每行输入m个字符,表示地图 1 ≤ n,m ≤ 100 1 ≤ k ≤ 9 1 ≤ q ≤ 7
输出
输出一行包含一个整数,表示金刚到达地心空洞入口所需要花费的最少步数。
样例输入
5 5 XX13X X.GXX S...T XXGXX ....2
样例输出
24
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct point {
int x, y;
short keys;
short fighted;
int steps;
short layout;
point(int inx, int iny, short k, short f, int s, short l)
: x(inx), y(iny), keys(k), fighted(f), steps(s), layout(l) {}
};
char flags[105][105][10][130];
int n, m;
int k, q;
char maze[105][105];
vector<pair<int, int>> traps;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int findTraps(int x, int y) {
for (int i = 0; i < q; i++) {
if (traps[i].first == x && traps[i].second == y)
return i;
}
}
int main() {
cin >> n >> m;
int startx, starty;
q = 0;
k = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> maze[i][j];
if (maze[i][j] == 'S') {
startx = i;
starty = j;
}
if (maze[i][j] == 'G') {
q++;
traps.push_back(make_pair(i, j));
}
if (maze[i][j] > '0' && maze[i][j] <= '9')
k = max(k, maze[i][j] - '0');
}
}
queue<point> myqueues;
short oriLayout = (1 << q) - 1;
myqueues.push(point(startx, starty, 0, 0, 0, oriLayout));
memset(flags, 0, sizeof(flags));
flags[startx][starty][0][oriLayout] = 1;
while (!myqueues.empty()) {
point top = myqueues.front();
myqueues.pop();
if (maze[top.x][top.y] == 'T' && top.keys == k) {
cout << top.steps << endl;
break;
}
if (maze[top.x][top.y] == 'G' && top.fighted == 0) {
int index = findTraps(top.x, top.y);
short layout = top.layout & (~(1 << index));
myqueues.push(point(top.x, top.y, top.keys, 1, top.steps + 1, layout));
flags[top.x][top.y][top.keys][layout] = 1;
continue;
}
for (int i = 0; i < 4; i++) {
int tx = top.x + dx[i];
int ty = top.y + dy[i];
if (tx < 0 || tx >= n || ty < 0 || ty >= m)
continue;
if (maze[tx][ty] == 'X')
continue;
else if (maze[tx][ty] == 'G') {
if (flags[tx][ty][top.keys][top.layout])
continue;
int index = findTraps(tx, ty);
if ((top.layout >> index) & 1) // 还没打
myqueues.push(point(tx, ty, top.keys, 0, top.steps + 1, top.layout));
else
myqueues.push(point(tx, ty, top.keys, 1, top.steps + 1, top.layout));
flags[tx][ty][top.keys][top.layout] = 1;
} else if (maze[tx][ty] == '.' || maze[tx][ty] == 'S' ||
maze[tx][ty] == 'T') {
if (flags[tx][ty][top.keys][top.layout])
continue;
myqueues.push(point(tx, ty, top.keys, 0, top.steps + 1, top.layout));
flags[tx][ty][top.keys][top.layout] = 1;
} else {
int key = maze[tx][ty] - '0';
if (key == top.keys + 1) {
if (flags[tx][ty][key][top.layout])
continue;
myqueues.push(point(tx, ty, key, 0, top.steps + 1, top.layout));
flags[tx][ty][key][top.layout] = 1;
} else {
if (flags[tx][ty][top.keys][top.layout])
continue;
myqueues.push(point(tx, ty, top.keys, 0, top.steps + 1, top.layout));
flags[tx][ty][top.keys][top.layout] = 1;
}
}
}
}
return 0;
}解题思路
思路:广搜题,属于较为复杂的一种,既要收集钥匙也要破坏陷阱。
状态包括:x,y坐标,keys表示现在收集的钥匙种数,fighted表示是否已经消灭陷阱,steps记录此时的步数,layout是陷阱的分布(用short变量表示)。
去重:xy坐标+钥匙+陷阱分布
地图上的标识有
‘.’:平地;‘X’:障碍,不能通过;‘T’:终点;‘S’:起点;‘G’:陷阱;1~9的数字:钥匙
起点和没有拿完钥匙的终点,不能拿的钥匙,破坏完的陷阱都当做平地处理
最长上升子序列
一个数的序列bi,当b1 < b2 < … < bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN),我们可以得到一些上升的子序列(ai1, ai2, …, aiK),这里1 <= i1 < i2 < … < iK <= N。比如,对于序列(1, 7, 3, 5, 9, 4, 8),有它的一些上升子序列,如(1, 7), (3, 4, 8)等等。这些子序列中最长的长度是4,比如子序列(1, 3, 5, 8). 你的任务,就是对于给定的序列,求出最长上升子序列的长度。
时间限制:11000
内存限制:65536
输入
输入的第一行是序列的长度N (1 <= N <= 1000)。第二行给出序列中的N个整数,这些整数的取值范围都在0到10000。
输出
最长上升子序列的长度。
样例输入
7 1 7 3 5 9 4 8
样例输出
4
#include <bits/stdc++.h>
#define fio \
ios::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
using namespace std;
const int maxn = 1010;
int a[maxn];
int maxLen[maxn];
int main() {
fio int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
maxLen[i] = 1;
}
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (a[i] > a[j]) {
maxLen[i] = max(maxLen[i], maxLen[j] + 1);
}
}
}
cout << *max_element(maxLen + 1, maxLen + n + 1) << endl;
}神奇的口袋
有一个神奇的口袋,总的容积是40,用这个口袋可以变出一些物品,这些物品的总体积必须是40。John现在有n个想要得到的物品,每个物品的体积分别是a1,a2……an。John可以从这些物品中选择一些,如果选出的物体的总体积是40,那么利用这个神奇的口袋,John就可以得到这些物品。现在的问题是,John有多少种不同的选择物品的方式。
时间限制:10000
内存限制:65536
输入
输入的第一行是正整数n (1 <= n <= 20),表示不同的物品的数目。接下来的n行,每行有一个1到40之间的正整数,分别给出a1,a2……an的值。
输出
输出不同的选择物品的方式的数目。
样例输入
3 20 20 20
样例输出
3
#include <bits/stdc++.h>
using namespace std;
int goods[30];
// 从前k种物品中选择一些,凑成体积w的做法数目
int ways(int w, int k) {
if (w == 0)
return 1; // 没有需要凑的体积了,刚好凑满
if (k <= 0)
return 0; // 还差体积或者体积过了,但是没有物品可以选了。
if (w >= goods[k]) {
return ways(w, k - 1) +
ways(w - goods[k], k - 1); // 体积:选择第k种物品 + 不选第k种物品
} else {
return ways(w, k - 1);
}
}
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &goods[i]);
}
printf("%d", ways(40, n));
return 0;
}滑雪
Michael喜欢滑雪百这并不奇怪, 因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度减小。在上面的例子中,一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上,这是最长的一条。
时间限制:1000
内存限制:65536
输入
输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行,每行有C个整数,代表高度h,0<=h<=10000。
输出
输出最长区域的长度。
样例输入
5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
样例输出
25
#include <cmath>
#include <cstdio>
#include <iostream>
using namespace std;
int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
// 控制方向的常用方法
int n, m, a[205][205], s[205][205], ans;
int dfs(int x, int y) {
if (s[x][y])
return s[x][y];
s[x][y] = 1; // 自身算一个距离
for (int i = 0; i < 4; i++) {
int tx = dx[i] + x, ty = dy[i] + y;
if (tx > 0 && tx <= n && ty >= 1 && ty <= m && a[x][y] > a[tx][ty]) {
dfs(tx, ty);
s[x][y] = max(s[x][y], s[tx][ty] + 1);
// 记忆化
}
}
return s[x][y];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &a[i][j]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
ans = max(ans, dfs(i, j)); // 将每个点当成起点做dfs
printf("%d", ans);
return 0;
}解题思路
采用递推的动态规划方式求解
先用结构体保存每个点对应的原本坐标位置和高度;
将所有点按高度从小到大排序;
用一个二维数组保存输入的原本数据,
再用一个二维数组保存对应位置的最大滑行距离;
从第二个点开始求解(因为第一个点高度最低,显然滑行距离为1)
依次和它在原本坐标里的上下左右四个方向进行判断,
如果它比某一方向上的高度高,则它的滑行距离就应该是相比较的最大滑行距离+1和它保存的最大滑行距离中的最大值。
最后求完总共的点,进行遍历,得到最终最大值。
删除数字
娇娇一年级了,刚刚学会了识数和比大小。有一天,她在黑板上写上了一串数字: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。
课程冲突
小 A 修了 n 门课程, 第 i 门课程是从第 ai 天一直上到第 bi 天。
定义两门课程的冲突程度为 : 有几天是这两门课程都要上的。
例如 a1=1,b1=3,a2=2,b2=4 时, 这两门课的冲突程度为 2。
现在你需要求的是这 n 门课中冲突程度最大的两门课的冲突程度。
时间限制:1000
内存限制:65536
输入
第一行一个正整数 n 表示课程数量。接下来 n 行,每行两个正整数 ai,bi。 2 ≤ n≤ 1000, 1 ≤ai ≤bi ≤ 1000。
输出
输出一个整数表示最大的冲突程度。
样例输入
3 1 3 2 4 5 5
样例输出
2
#include <bits/stdc++.h>
using namespace std;
// #define PPYDEBUG
struct lesson {
int no; // 课程编号
int a; // 课程开始a天
int b; // 课程结束b天
};
int max_chongtu(lesson x, lesson y) {
int r = min(x.b, y.b) - max(x.a, y.a) + 1;
if (r < 0) {
r = 0;
}
#ifdef PPYDEBUG
printf("%d = x[%d,%d] - y[%d,%d]\n", r, x.a, x.b, y.a, y.b);
#endif
return r;
}
int main() {
#ifdef LOCAL
freopen("202209_3_1.in", "r", stdin);
#endif
int n;
scanf("%d", &n);
lesson le[1010];
for (int i = 0; i < n; i++) {
le[i].no = i + 1;
scanf("%d%d", &le[i].a, &le[i].b);
}
int r = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
r = max(r, max_chongtu(le[i], le[j]));
}
}
printf("%d", r);
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 <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;
}最长下坡
小明天天沿着未名湖环湖路跑,有时候也觉得蛮累。
累的时候跑下坡就很开心。小明想知道最长的一段下坡有多长。
环湖路是个圆形,周长n米。每隔一米测一下路面高度,两个测高点之间的高度是单调变化或不变的。
问最长的一段下坡有多少米长。小明只能顺时针跑。下坡必须高度单调减少。
时间限制:1000
内存限制:65536
输入
第一行是整数n,表示环湖路一共n米长(2<=n<=100)。 第二行是n个整数,每个整数范围[0,10000],按顺时针顺序给出了n个测高点的高度。
输出
最长下坡路段的长度。
样例输入
样例输入1:
5 2 1 5 6 3
样例输入2:
5 2 1 5 4 3
样例输入3:
4 1 1 1 1
样例输出
样例输出1:
3
样例输出2:
4
样例输出3:
0
提示
这是个简单枚举题,枚举起点即可
#include <stdio.h>
int main() {
int n, i, max = 0, t = 0, s;
int a[100];
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d", &a[i]);
s = a[0];
for (i = 1; i < n; i++) {
if (a[i] < s)
t++;
else {
if (t > max)
max = t;
t = 0;
}
s = a[i];
}
for (i = 0; i < n; i++) {
if (a[i] < s)
t++;
else {
if (t > max)
max = t;
break;
}
s = a[i];
}
printf("%d", max);
return 0;
}吃糖果
现有n(20 > n > 0)个糖果,每天可以吃1个,也可以每天吃2个,也可以每天吃3个,请计算共有多少种不同的吃法。
时间限制:1000
内存限制:65536
输入
输入的每一行包括一组测试数据,即为糖果数n。最后一行为0,表示测试结束。
输出
每一行输出对应一行输入的结果,即为吃法的数目。
样例输入
1 2 3 4 0
样例输出
1 2 4 7
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef LOCAL
freopen("202209_3_4.in", "r", stdin);
#endif
int dp[30];
dp[0] = 1;
dp[1] = 2;
dp[2] = 4; // 111,12,21,3
for (int i = 3; i < 20; i++) {
dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
}
int n;
do {
scanf("%d", &n);
// printf("%d\n", n);
if (n == 0) {
break;
}
printf("%d\n", dp[n - 1]);
} while (true);
return 0;
}放苹果
把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。
时间限制:1000
内存限制:65536
输入
第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。1<=M,N<=10。
输出
对输入的每组数据M和N,用一行输出相应的K。
样例输入
1 7 3
样例输出
8
#include <bits/stdc++.h>
using namespace std;
int dp(int m, int n) {
if (m == 0 or n == 1) {
// 如果,碟子只有1个,无论苹果有多少个都只有一种放法
return 1;
}
if (n > m) {
// 如果,碟子的个数大于苹果的个数
return dp(m, m);
} else {
return dp(m, n - 1) + dp(m - n, n);
}
}
int main() {
#ifdef LOCAL
freopen("202209_3_5.in", "r", stdin);
#endif
int t;
scanf("%d", &t);
int n, m;
for (int i = 0; i < t; i++) {
scanf("%d%d", &m, &n);
printf("%d", dp(m, n));
}
return 0;
}统计误差范围内的数
统计一个整数序列中与指定数字m误差范围小于等于X的数的个数。
时间限制:5000
内存限制:65536
输入
输入包含三行:
第一行为N,表示整数序列的长度(N <= 100);
第二行为N个整数,整数之间以一个空格分开;
第三行包含2个整数,为指定的整数m,误差范围X。
输出
输出为N个数中与指定数字m误差范围小于等于X的数的个数。
样例输入
5 1 2 3 4 5 3 1
样例输出
3
提示
样例中2,3,4都满足条件,故答案为3
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef LOCAL
freopen("1.in", "r", stdin);
#endif
int N;
scanf("%d", &N);
int *a = new int[N + 1];
for (int i = 0; i < N; i++) {
scanf("%d", &a[i]);
}
int m, X;
scanf("%d%d", &m, &X);
int count = 0;
for (int i = 0; i < N; i++) {
if (abs(a[i] - m) <= X) {
count = count + 1;
}
}
printf("%d", count);
return 0;
}全在其中
你设计了一个新的加密技术,可以用一种聪明的方式在一个字符串的字符间插入随机的字符串从而对信息进行编码。由于专利问题,我们将不会详细讨论如何在原有信息中产生和插入字符串。不过,为了验证你的方法,有必要写一个程序来验证原来的信息是否全在最后的字符串之中。
给定两个字符串s和t,你需要判断s是否是t的“子列”。也就是说,如果你去掉t中的某些字符,剩下字符将连接而成为s。
时间限制:1000
内存限制:65536
输入
输入包括多个测试样例。每一个都是由空格分隔的由字母数字ASCII字符组成的两个特定的字符串s和t。s和t的长度不超过100000
输出
对于每个测试样例,如果s是t的“子列”,则输出”Yes”,否则输出”No”
样例输入
sequence subsequence person compression VERDI vivaVittorioEmanueleReDiItalia caseDoesMatter CaseDoesMatter
样例输出
Yes No Yes No
#include <bits/stdc++.h>
using namespace std;
bool isok(string a, string b) {
int b_start = 0;
int count = 0;
for (int i = 0; i < a.length(); i++) {
for (int j = b_start; j < b.length(); j++) {
b_start = j + 1;
if (b[j] == a[i]) {
count++;
break;
}
}
}
if (count == a.length()) {
return true;
}
return false;
}
int main() {
#ifdef LOCAL
freopen("202209_2_2.in", "r", stdin);
#endif
string a;
string b;
while (cin >> a) {
cin >> b;
bool r = isok(a, b);
if (r == true) {
printf("Yes\n");
} else {
printf("No\n");
}
}
return 0;
}Lab杯
“Lab杯”乒乓球赛就要在PKU的实验室之间举行了。人工智能实验室的学生都是乒乓球的狂热分子,都强烈希望代表实验室去比赛。但是由于名额限制,他们之中只能由一个人被选作代表。
为了让选择的过程公平,他们决定打一次单循环赛,每一对学生之间都打一场五局三胜的比赛。赢得最多比赛的人就将代表实验室去比赛。现在Ava手里有一份表,表里面记录了每一场比赛的比分。她应该让谁去比赛?
时间限制:5000
内存限制:131072
输入
输入包含一组测试数据。第一行包含n(2 ≤ n ≤ 100),实验室里学生的数目。接下来给出一个n × n矩阵A。矩阵的每一个元素都是0、1、2、3中的一个。第i行第j列的元素aij是第i个学生在和第j个学生的比赛中赢的局数。aij和aji(i ≠ j)正好有一个是3,另外一个小于3。矩阵的所有对角线元素都是0。
输出
输出赢了最多比赛的学生的编号。如果有平分,选择编号最小的。
样例输入
4 0 0 3 2 3 0 3 1 2 2 0 2 3 3 3 0
样例输出
4
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef LOCAL
freopen("202209_2_3.in", "r", stdin);
#endif
int n;
scanf("%d", &n);
int a[110][110];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &a[i][j]);
}
}
int max_score = 0;
int no = 1;
for (int i = 0; i < n; i++) {
int t = 0;
for (int j = 0; j < n; j++) {
t = t + a[i][j];
}
if (t > max_score) {
max_score = t;
no = i + 1;
}
}
printf("%d", no);
return 0;
}有趣的跳跃
一个长度为n(n>0)的序列中存在“有趣的跳跃”当且仅当相邻元素的差的绝对值经过排序后正好是从1到(n-1)。例如,1 4 2 3存在“有趣的跳跃”,因为差的绝对值分别为3,2,1。当然,任何只包含单个元素的序列一定存在“有趣的跳跃”。你需要写一个程序判定给定序列是否存在“有趣的跳跃”。
时间限制:1000
内存限制:65536
输入
一行,第一个数是n(0 < n < 3000),为序列长度,接下来有n个整数,依次为序列中各元素,各元素的绝对值均不超过1,000,000,000
输出
一行,若该序列存在“有趣的跳跃”,输出"Jolly",否则输出"Not jolly"
样例输入
4 1 4 2 3
样例输出
Jolly
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef LOCAL
freopen("202209_2_4.in", "r", stdin);
#endif
int n;
scanf("%d", &n);
int *a = new int[n + 1]; // 元素列表
int *b = new int[n + 2]; // 元素差绝对值列表
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
for (int i = 0; i < n - 1; i++) {
b[i] = abs(a[i] - a[i + 1]);
}
// 元素差绝对值列表从小到大排序
sort(b, b + n - 1);
for (int i = 0; i < n - 1; i++) {
if (b[i] != i + 1) {
printf("Not jolly");
return 0;
}
}
printf("Jolly");
return 0;
}反反复复
Mo和Larry发明了一种信息加密方法。他们首先决定好列数,然后将信息(只包含字母)从上往下依次填入各列,并在末尾补充一些随机字母使其成为一个完整的字母矩阵。例如,若信息是“There's no place like home on a snowy night”并且有5列,Mo会写成:
t o i o y
h p k n n
e l e a i
r a h s g
e c o n h
s e m o t
n l e w x
注意Mo只会填入字母,且全部是小写形式。在这个例子中,Mo用字母“x”填充了信息使之成为一个完整的矩阵,当然他使用任何字母都是可以的。
Mo根据这个矩阵重写信息:首先从左到右写下第一行,然后从右到左写下第二行,再从左到右写下第三行……以此左右交替地从上到下写下各行字母,形成新的字符串。这样,例子中的信息就被加密为:toioynnkpheleaigshareconhtomesnlewx。
你的工作是帮助Larry从加密后的信息中还原出原始信息(包括填充的字母)。
时间限制:1000
内存限制:65536
输入
第一行包含一个整数(范围2到20),表示使用的列数。 第二行是一个长度不超过200的字符串。
输出
一行,即原始信息。
样例输入
5
toioynnkpheleaigshareconhtomesnlewx
样例输出
theresnoplacelikehomeonasnowynightx
#include <stdio.h>
#include <string.h>
char sz[300], a[30][30], b[30][30];
int main() {
int n, i, j, mm, m, k = 0;
scanf("%d", &n);
scanf("%s", sz);
mm = strlen(sz);
m = mm / n;
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++) {
a[i][j] = sz[k++];
}
}
for (i = 0; i < m; i++) {
if (i % 2 == 0) {
for (j = 0; j < n; j++) {
b[i][j] = a[i][j];
}
}
if (i % 2 != 0) {
for (j = 0; j < n; j++) {
b[i][j] = a[i][n - j - 1];
}
}
}
for (j = 0; j < n; j++) {
for (i = 0; i < m; i++) {
printf("%c", b[i][j]);
}
}
}指定顺序输出
依次输入3个整数a、b、c,将他们以c、a、b的顺序输出。
时间限制:1000
内存限制:65536
输入
一行3个整数a、b、c,以空格分隔。 0 < a,b,c < 108
输出
一行3个整数c、a、b,整数之间以一个空格分隔。
样例输入
1 2 3
样例输出
3 1 2
#include <iostream>
using namespace std;
int main() {
int a, b, c;
cin >> a >> b >> c;
cout << c << " " << a << " " << b;
}