Scratch编程一级 题库
小章鱼的演出

1.准备工作
(1)选择背景 Underwater lzUnderwater 2;
(2)选择角色Octopus;
(3)选择背景声音Bossa Novao。
2.功能实现
(1)点击开始,角色Octopus初始化位置在舞台左侧中部,初始造型为0ctopus-b,初始 背景为 Underwater1;
(2)角色Octopus从舞台左侧移动到右侧,不断改变造型;
(3)章鱼到达舞台最右边后,切换为Underwater2.章鱼移到舞台中心位置;
(4)背景播放Bossa Nova声音。
章鱼代码:

音乐代码:

或者

评分标准:
(1)能够选择题目要求的背景、角色和声音;
(2)初始化角色坐标、造型;(2分)
(3)角色从舞台左端移动到右端;(3分)
(4)移动过程中角色不断切换;(2分)
(5)角色到达舞台右端切换背景;(3分)
(6)程序开始后播放声音。(2分)
放学
放学时间到了, 校车行驶到学校门口, 按下喇叭提醒同学们上车, 送同学们回家。
1.准备工作
(1)添加背景:School ;
(2) 删除默认的小猫角色,添加角色:City Bus 、Kai;
(3)为角色City Bus 添加声音;Car Horn;
2.功能实现
(1)点击绿旗,City Bus 出现在舞台左下角,Kai 出现在学校门口;

(2)City Bus 向前移动一段距离,连续播放两次声音 Car Horn;

(3)听到声音后,Kai 调整方向,走到车门的位置后消失;


(4)City Bus 继续向前行驶直到舞台右侧。

City Bus 的程序:

Kai 的程序:

评分标准:
(1)背景和角色添加正确。(3 分);
(2)点击绿旗后,两个角色的位置正确(2 分);
(3)City Bus 有向前移动的效果(2 分),连续播放了两次 Car Horn(3 分);
(4)Kai 在声音播放后移动到了 City Bus 车门的位置(2 分),到达车门位置后消失(1 分);
(5)City Bus 移动到了舞台右侧(2 分)。
小狗进圈
小狗非常听话,收到命令能在舞台上向右移动,如下图所示,它只能移动到相邻的圈里,不能跑到圆圈外。

1.准备工作
(1)背景:根据上图绘制背景;
(2)删除小猫角色,添加角色:Dog2;
(3)给Dog2添加声音:Dog2。
2.功能实现
(1)舞台颜色为蓝色,绘制3个椭圆,椭圆的大小要能容下小狗,内部填充白色,椭圆的间距尽量相等。
(2)点击绿色旗,程序开始时,Dog2位于最左侧椭圆内,面向右侧,造型为“dog2-a”;
(3)按下空格键,Dog2发出“Dog2”叫声、切换下一个造型,向右跳到下一个椭圆。
注意:点击绿旗后,只测试两次按下空格键即可,第一次按下能跳到第二个椭圆,第二次按下能跳到第三个椭圆。
参考程序:

评分标准:
(1)背景绘制正确、角色、声音选择正确;(6分,背景绘制正确3分,角色、声音选择正确各1.5分)
(2)Dog2初始位置、方向、造型正确;(3分)
(3)按下空格键,Dog2发出叫声,切换造型,朝右边移动到下一个圈内。(6分,按下空格键1分,播放声音1分,造型切换1分、正好移动到下个圈中不跑出圈外3分,每个圈各1分)
小镇一日游
花花小学组织了小镇一日游的活动,乘坐scratch Tours号车浏览小镇风光,浏览的顺序为Colorful City、School、Urban以及Night City With Street。

1.准备工作
(1)选择背景Colorful City、School、Urban以及Night City With Street;
(2)去掉小猫角色;
(3)选择City Bus汽车角色,添加Car Horn声音。
2. 功能实现
(1)初始的背景为Colorful City,汽车的初始位置在屏幕右下角,面向右面;
(2)点击绿旗,汽车角色向左移动50步后从City Bus-a造型切换到City Bus-b造
2.型,之后播放Car Horn声音,等待两秒后进入School背景;
(3)进入School背景后汽车向左移动50步,播放Car Horn声,等待两秒后进
3.入Urban背景;
(4)进入Urban背景后汽车向左移动50步,播放Car Horn声音,等待两秒后进
4.入背景Night City With Street;
(5)进入背景Night City With Street后汽车向左移动50步,播放Car Horn声音。
参考程序:

评分标准:
(1)添加汽车角色和四个背景;(3分)
(2)给汽车角色切换造型;(2分)
(3)汽车角色进行移动并等待2秒;(4分)
(4)汽车角色播放声音;(2分)
(5)切换背景操作;(4分)
舞蹈演出
1.准备工作
(1)删除小猫角色;
(2)添加角色Ballerina,为角色添加声音Bossa Nova;
(3)添加背景Theater和Concert。
2.功能实现
(1)点击绿旗,角色Ballerina初始造型为ballerina-a,初始背景为Theater,初始位置在舞台左侧;

(2)1秒后,Ballerina每隔0.2秒,移动40步,向右移动到舞台中间;

(3)背景切换为Concert,播放声音Bossa Nova;

(4)播放声音的同时,角色Ballerina每隔1秒切换一次造型,切换4次造型,最后切换为ballerina-a。


评分标准:
(1)能正确添加背景角色;(3分)
(2)角色初始造型、位置及背景设置正确;(3分)
(3)角色Ballerina能够移动到舞台中间;(4分)
(4)完成背景切换(1分),播放音乐Bossa Nova(2分)和至少完成一次造型切换(2分)。
猫捉老鼠
1.准备工作
(1)选择背景Witch House;
(2)删除默认的小猫角色,选择角色Cat 2和Mouse1,Cat 2大小设为80,Mouse1大小设为60。
2.功能实现
(1)Cat 2位于舞台左下角,面朝右上(方向55);Mouse1位于舞台右上角,面朝左;
(2)程序开始,Cat 2边叫边朝向舞台右上角扑去,500步的路程每跑100步就要歇息0.5秒;
(3)程序开始,Mouse1由舞台右上角跑向舞台左上角,静止不动;
(4)Cat 2扑到舞台右上角落空后,又转向舞台左上角,最终将Mouse1抓住。

Cat 2:

Mouse1:

评分标准:
(1)能够选择题目要求的背景和角色;(2分)
(2)能初始化角色和坐标;(1分)
(3)角色Cat 2播放声音(不是播放等待播完)(2分),方向调为55(1分);每移动100步就等待0.5秒(5分),Mouse1由右上角移动至左上角;(2分)
(4)角色Cat 2调整方向为-90,移动至舞台左上角。(2分)
鸣人和佐助
描述
佐助被大蛇丸诱骗走了,鸣人在多少时间内能追上他呢?
已知一张地图(以二维矩阵的形式表示)以及佐助和鸣人的位置。地图上的每个位置都可以走到,只不过有些位置上有大蛇丸的手下,需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉,每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动,每移动一个距离需要花费1个单位时间,打败大蛇丸的手下不需要时间。如果鸣人查克拉消耗完了,则只可以走到没有大蛇丸手下的位置,不可以再移动到有大蛇丸手下的位置。佐助在此期间不移动,大蛇丸的手下也不移动。请问,鸣人要追上佐助最少需要花费多少时间?
输入
输入的第一行包含三个整数:M,N,T。代表M行N列的地图和鸣人初始的查克拉数量T。0 < M,N < 200,0 ≤ T < 10
后面是M行N列的地图,其中@代表鸣人,+代表佐助。*代表通路,#代表大蛇丸的手下。
输出
输出包含一个整数R,代表鸣人追上佐助最少需要花费的时间。如果鸣人无法追上佐助,则输出-1。
样例输入1
4 4 1 #@## **## ###+ ****
样例输入2
4 4 2 #@## **## ###+ ****
样例输出1
6
样例输出2
4
#include <bits/stdc++.h>
using namespace std;
int n, m, t, s2[10][256][256], fx[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
char s1[256][256];
struct AAA {
int i;
int j;
int bs;
int st;
};
int bfs() {
int i, j, k, ti, tj, ret = -1;
queue<AAA> dl;
AAA tmp, tmp1;
for (i = 0; i < m; i++) {
for (j = 0; j < n; j++)
if (s1[i][j] == '@') {
tmp.i = i;
tmp.j = j;
tmp.bs = 0;
tmp.st = t;
break;
}
if (j < n)
break;
}
dl.push(tmp);
for (i = 0; i < 10; i++)
for (j = 0; j < m; j++)
for (k = 0; k < n; k++)
s2[i][j][k] = 0;
s2[0][tmp.i][tmp.j] = 1;
while (!dl.empty()) {
tmp = dl.front();
dl.pop();
if (s1[tmp.i][tmp.j] == '+') {
ret = tmp.bs;
break;
}
for (i = 0; i < 4; i++) {
ti = tmp.i + fx[i][0];
tj = tmp.j + fx[i][1];
if ((ti < 0) || (ti >= m) || (tj < 0) || (tj >= n))
continue;
if (s2[t - tmp.st][ti][tj] == 1)
continue;
if ((s1[ti][tj] == '#') && (tmp.st == 0))
continue;
s2[t - tmp.st][ti][tj] = 1;
tmp1.i = ti;
tmp1.j = tj;
tmp1.bs = tmp.bs + 1;
tmp1.st = tmp.st;
if (s1[ti][tj] == '#')
tmp1.st--;
dl.push(tmp1);
}
}
return ret;
}
int main() {
int i, j, k;
char tmp[16];
gets(tmp);
sscanf(tmp, "%d%d%d", &m, &n, &t);
for (i = 0; i < m; i++)
gets(s1[i]);
printf("%d", bfs());
return 0;
}//参考代码2
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,sx,sy,st,minstep=inf;
int step[201][201][11],dx[]={0,1,-1,0},dy[]={1,0,0,-1};
char mp[201][201];
bool vis[201][201];
void dfs(int x,int y,int t,int stp)
{
if(x<1 || x>n || y<1 || y>m || vis[x][y]) return ;
if(t<0) return ;
if(stp>=minstep) return ;
if(stp>=step[x][y][t]) return ;
step[x][y][t]=stp;
if(mp[x][y]=='#') t--;
else if(mp[x][y]=='+') {
if(stp<minstep) minstep=stp;
return ;
}
vis[x][y]=1;
for(int i=0;i<4;++i){
int nx=x+dx[i];
int ny=y+dy[i];
dfs(nx,ny,t,stp+1);
}
vis[x][y]=0;
}
int main()
{
scanf("%d%d%d",&n,&m,&st);
getchar();
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
scanf("%c",&mp[i][j]);
if(mp[i][j]=='@') {
sx=i;
sy=j;
}
}
getchar();
}
memset(step,0x3f,sizeof(step));
dfs(sx,sy,st,0);
if(minstep==inf) printf("-1");
else printf("%d",minstep);
return 0;
}//参考代码3
#include<cstdio>
#include<queue>
using namespace std;
struct POINT
{
int x,y,tot,T;
} point;
queue<POINT> que;
int main()
{
bool walked[205][205][15]={};
int r,c,T,F[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
scanf("%d%d%d",&r,&c,&T);
char maze[205][205]={};
for(int i=0;i<r;i++)
{
scanf("%s",maze[i]);
for(int j=0;j<c;j++)
if(maze[i][j]=='@')
{
point.x=i;point.y=j;
point.tot=0;point.T=T;
}
}
que.push(point);
while(!que.empty())
{
for(int i=0;i<4;i++)
{
point.x=que.front().x+F[i][0];
point.y=que.front().y+F[i][1];
point.tot=que.front().tot+1;
point.T=que.front().T;
if(point.x<0 || point.x>=r || point.y<0 || point.y>=c || walked[point.x][point.y][point.T]) continue;
if(maze[point.x][point.y]=='#')
if(point.T) point.T--;
else continue;
if(maze[point.x][point.y]=='+') {printf("%d\n",point.tot);return 0;}
walked[point.x][point.y][point.T]=true;
que.push(point);
}
que.pop();
}
printf("-1\n");
return 0;
}密室逃脱
小Y喜欢玩密室逃脱,每次游戏开始时,小Y会进入一个密室,她需要按照顺序解开各个隐藏线索才能成功逃脱密室。小Y非常聪明,解开线索对她来说并不难,但是她有一点懒,她希望在通关过程中移动次数最少。请你帮小Y计算她至少要移动多少次才能成功通关。
密室是m行n列的格子矩阵,小Y从左上角(1,1)进入密室,密室中有三种格子:
墙,以数字0标记
路,以数字1标记
隐藏线索处,以数字( > 1)标记, 代表该线索的难度
小Y需要按照难度递增的顺序解开各个线索,逃脱密室。
时间限制:1000
内存限制:65536
输入
第一行是一个整数 T,表示输入包含 T 组数据,分别是不同的游戏中小Y所处的密室。 对于每组数据,第一行包括两个整数:m(1 <= m <= 100)、n(1 <= n <= 100)。 接下来 m 行,每行有n个数字,第 i 行的第 j 个数字表示密室中第 i 行第 j 列的格子的类型。 题目保证进入密室处(1,1)不是墙壁,线索的难度都不相同。
输出
对于每组数据,你需要输出一个整数,表示小Y在这个密室中至少要移动多少次才能成功通关。 如果小Y不可能解开所有线索,输出-1.
样例输入
2 3 3 1 3 2 1 0 4 10 6 5 3 3 1 3 2 0 0 0 10 6 5
样例输出
8 -1
提示
样例解释:由于需要按难度顺序解开线索,在第一组数据中,小Y第一次移动到3时不能解密,在完成2之后需要回到3.最后小Y解开10时,她成功通关。
//示例代码 条件+广搜
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int m,n;
int maze[104][104] = {};
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
bool legal(int x, int y){
if(0 <= x && x< m && 0 <= y && y < n && maze[x][y] != 0)return 1;
return 0;
}
struct Node{
int x, y, k, t;
};
int main()
{
int T;
cin >> T;
while(T--){
memset(maze, 0, sizeof(maze));
int vis[104][104] = {};
memset(vis, 0xff, sizeof(vis));
int S[10050] = {};
int cnt = 0;
cin >> m >> n;
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
cin >> maze[i][j];
if (maze[i][j] > 1) {
S[cnt++] = maze[i][j];
}
}
}
queue<Node> open;
sort(S, S + cnt);
if (maze[0][0] == S[0]) {
open.push({0, 0, 1, 0});
vis[0][0] = 1;
}
else {
open.push({0, 0, 0, 0});
vis[0][0] = 0;
}
bool flag = 0;
while (!open.empty()) {
Node temp = open.front();
open.pop();
if (temp.k == cnt) {
flag = 1;
cout << temp.t << endl;
break;
}
for (int i = 0; i < 4; i++) {
int x = temp.x + dx[i], y = temp.y + dy[i], k = temp.k;
if (!legal(x,y)) continue;
if (maze[x][y] == S[k]) k++;
if (vis[x][y] >= k) continue;
vis[x][y] = k;
open.push({x, y, k, temp.t + 1});
}
}
if (!flag) cout << -1 << endl;
}
return 0;
}红与黑
有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上,只能向相邻的黑色瓷砖移动。请写一个程序,计算你总共能够到达多少块黑色的瓷砖。
时间限制:1000
内存限制:65536
输入
包括多个数据集合。每个数据集合的第一行是两个整数W和H,分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中,每行包括W个字符。每个字符表示一块瓷砖的颜色,规则如下 1)‘.’:黑色的瓷砖; 2)‘#’:白色的瓷砖; 3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。 当在一行中读入的是两个零时,表示输入结束。
输出
对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
样例输入
6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 0 0
样例输出
45
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 25;
int n, m;
int x, y;
char ct[N][N];
bool num[N][N];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int dfs(int x, int y) {
int ans = 1;
num[x][y] = true;
for (int i = 0; i < 4; i++) {
int x1 = dx[i] + x;
int y1 = dy[i] + y;
if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= m)
continue;
if (ct[x1][y1] == '#')
continue;
if (num[x1][y1] == true)
continue;
ans = ans + dfs(x1, y1);
}
return ans;
}
int main() {
while (scanf("%d%d", &m, &n) != EOF) {
if (m == 0 && n == 0)
break;
for (int i = 0; i < n; i++) {
scanf("%s", ct[i]);
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j < m; j++) {
if (ct[i][j] == '@') {
x = i;
y = j;
}
}
}
cout << dfs(x, y) << endl;
memset(num, 0, sizeof num);
}
return 0;
}踩方格
有一个方格矩阵,矩阵边界在无穷远处。我们做如下假设:
a. 每走一步时,只能从当前方格移动一格,走到某个相邻的方格上;
b. 走过的格子立即塌陷无法再走第二次;
c. 只能向北、东、西三个方向走;
请问:如果允许在方格矩阵上走n步,共有多少种不同的方案。2种走法只要有一步不一样,即被认为是不同的方案。
时间限制:1000
内存限制:65536
输入
允许在方格上行走的步数n(n <= 20)
输出
计算出的方案数量
样例输入
2
样例输出
7
#include <iostream>
using namespace std;
int main() {
int n, i, t;
int a = 1, b = 1, c = 1;
cin >> n;
for (i = 2; i <= n; i++) {
t = a + b + c;
b = a + b;
c = a + c;
a = t;
}
cout << a + b + c;
return 0;
}抓牛
农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=100000)。农夫有两种移动方式:
1、从X移动到X-1或X+1,每次移动花费一分钟
2、从X移动到2*X,每次移动花费一分钟
假设牛没有意识到农夫的行动,站在原地不动。农夫最少要花多少时间才能抓住牛?
时间限制:2000
内存限制:65536
输入
两个整数,N和K
输出
一个整数,农夫抓到牛所要花费的最小分钟数
样例输入
5 17
样例输出
4
#include <bits/stdc++.h>
using namespace std;
int b[200100];
int a[10];
queue<int> q;
int n, k;
void bfs(int x) {
q.push(x);
b[x] = 1;
while (!q.empty()) {
int s = q.front();
a[1] = s - 1;
a[2] = s + 1;
a[3] = 2 * s;
for (int i = 1; i < 4; i++) {
if (b[a[i]] == 0 && a[i] >= 0 && a[i] < 100100) {
b[a[i]] = b[s] + 1;
q.push(a[i]);
if (a[i] == k) {
cout << b[k] - 1 << endl;
}
}
}
q.pop();
}
}
int main() {
cin >> n >> k;
bfs(n);
return 0;
}泳池
学校是 N x N 的坐标方格 grid 中,每一个方格的值 grid(i,j)表示在位置 (i,j) 的高度。现在开始下雨了。当时间为 t 时,此时雨水导致方格中任意位置的水位为 t 。你可以从一个方格游向四周相邻的任意一个方格,但是前提是此时水位必须同时淹没这两个方格。假定小C的游动是不耗时的。
现在小C从坐标方格的左上(0,0)出发。最少耗时多久他才能到达坐标方格的右下平台 (N-1, N-1)?
时间限制:1000
内存限制:65536
输入
第一行有一个整数N,以下是一个N*N的方阵,代表各处的高度。
输入范围:
2 ≤ N ≤ 300
0 ≤ Height ≤ 10000000
输出
输出一个整数,代表最少等待时间T
样例输入
样例输入1:
2 0 2 1 3
样例输入2:
5 0 1 2 3 4 24 23 22 21 5 12 13 14 15 16 11 17 18 19 20 10 9 8 7 6
样例输出
样例输出1:
3
样例输出2:
16
提示
样例1:时间为3时,才可以游向平台(1,1),此时水位为3。 样例2:时间为16时,水位为16,此时才能保证(0,0)和(4,4)是联通的(请自行找出一条通路)。
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
int maze[305][305];
bool reach[305][305];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int N;
struct point {
int x, y;
point(int a, int b) : x(a), y(b) {}
};
bool canreach(int t) {
if (maze[0][0] > t)
return false;
memset(reach, 0, sizeof(reach));
reach[0][0] = 1;
queue<point> myqueues;
myqueues.push(point(0, 0));
while (!myqueues.empty()) {
point top = myqueues.front();
myqueues.pop();
if (top.x == N - 1 && top.y == N - 1)
return true;
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 >= N)
continue;
if (reach[tx][ty])
continue;
if (maze[tx][ty] > t)
continue;
reach[tx][ty] = 1;
myqueues.push(point(tx, ty));
}
}
return false;
}
int main() {
memset(maze, 0, sizeof(maze));
cin >> N;
int L = 10000000, R = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> maze[i][j];
L = min(maze[i][j], L);
R = max(maze[i][j], R);
}
}
int result = 10000000;
while (L <= R) {
int mid = (L + R) / 2;
if (canreach(mid)) {
R = mid - 1;
result = min(result, mid);
} else
L = mid + 1;
}
cout << result << endl;
return 0;
}问题求解
给定一个正整数N,求最小的M满足比N大且M与N的二进制表示中有相同数目的1。
举个例子,假如给定N为78,二进制表示为1001110,包含4个1,那么最小的比N大的并且二进制表示中只包含4个1的数是83,其二进制是1010011,因此83就是答案。
时间限制:1000
内存限制:65536
输入
输入若干行,每行一个数N(1 ≤ N ≤ 1000000),如果这行为0表示输入结束。
输出
对于每个N,输出对应的M。
样例输入
1 2 3 4 78 0
样例输出
2 4 5 8 83
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define INF 999999999
#define N 1001
using namespace std;
int main() {
int n;
while (scanf("%d", &n) != EOF && n) {
int cnt = 0;
int temp = n;
while (temp > 0) {
if (temp % 2)
cnt++;
temp /= 2;
}
int sum = 0;
while (1) {
temp = ++n;
while (temp > 0) {
if (temp % 2)
sum++;
temp /= 2;
}
if (cnt == sum) {
cout << n << endl;
break;
}
sum = 0;
}
}
return 0;
}//解法2 样例代码 枚举
using namespace std;
int n; // 定义变量 n
int tj(int x) {
int ans = 0; // 定义变量 ans
while (x) { // 当 x 不为0循环执行
if (x &)
ans++; // 如果 x 的最低位为1,则将 ans 加1
x >>= 1; // 将 x 右移1位,即将 x 的二进制表示向右移动一位
}
return ans; // 返回 ans
}
int main() {
while (1) { // 无限循环
cin >> n; // 从标准输入读取一个整数 n
if (!n)break; 如果 n 为0,则结束循环
int t = tj(n); // 调用函数 tj 计算 n 的二进制中的1的个数,并将结果赋值给 t
for (int i = n + 1;; i++) { // 从 n+1 开始递增遍历整数 i
if (t == tj(i)) {
cout << i << endl; // 输出第一个满足条件的整数 i,即其二进制表示中的1的个数与 t 相等
break; // 结束循环
}
}
}
return 0; // 返回 0,表示程序正常结束
}重建二叉树
给定一棵二叉树的前序遍历和中序遍历的结果,求其后序遍历。
时间限制:1000
内存限制:65536
输入
输入可能有多组,以EOF结束。 每组输入包含两个字符串,分别为树的前序遍历和中序遍历。每个字符串中只包含大写字母且互不重复。
输出
对于每组输入,用一行来输出它后序遍历结果。
样例输入
DBACEGF ABCDEFG BCAD CBAD
样例输出
ACBFGED CDAB
#include <stdio.h>
#include <string.h>
void bulid(int n, char s1[],
char s2[]) // n是树的节点数,s1是记录先序遍历,s2中序遍历
{
if (n <= 0)
return; // 没有节点了,找到边界return
int p = strchr(s2, s1[0]) - s2;
// strchr(s2,s1[0])是s2的地址+s1[0]第一次出现的位置i。s2是s2的地址
// 所以p是 s1[0]第一次出现在s2中的位置
bulid(p, s1 + 1, s2);
// 数的节点数为s1[0]在s2中之前的所有节点。s1+1是把s1数组整体向前移动一位(s1[0]是以前的s1[1],s1[1]改为以前s1[2]...
// 以前s1[0]是根,现在不需要,所以删除。要它左子树的根节点
// s2不变(假设中序遍历中根节点的位置是a,那么后序遍历中0~a个点是树的左子树节点)
bulid(n - p - 1, s1 + p + 1, s2 + p + 1);
// 数的节点数为s1[0]在s2中之后的所有节点(因为数组从0开始,所以-1)
// 以前s1[0]是根,现在不需要,左子树也不需要,所以都删除。要它右子树的根节点
// s2+p+1(假设中序遍历中根节点的位置是a,a~n-2(数组从0开始)个点是树的右子树节点
// )
printf("%c", s1[0]); // 输出
}
int main() {
char s1[10007], s2[10007]; // s1是树的前序遍历,s2是树的中序遍历
while (scanf("%s %s", s1, s2) != EOF) // 多组数据
{
bulid(strlen(s1), s1, s2);
printf("\n"); // 记得输出\n
}
return 0;
}
/*
先序遍历第一个节点一定是根节点。
中序遍历根节点左侧就是树的左子树,右侧就是树的右子树。
后序遍历最后一个节点一定是根节点,而假设中序序列里根节点位置是m,那么后序序列里0至m-1个节点是树的左子树节点,m至倒数第二个点是树的右子树节点。
*/逃离迷宫
你在一个地下迷宫中找到了宝藏,但是也触发了迷宫机关,导致迷宫将在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;
}电话号码
给你一些电话号码,请判断它们是否是一致的,即是否有某个电话是另一个电话的前缀。比如:
Emergency 911
Alice 97 625 999
Bob 91 12 54 26
在这个例子中,我们不可能拨通Bob的电话,因为Emergency的电话是它的前缀,当拨打Bob的电话时会先接通Emergency,所以这些电话号码不是一致的。
时间限制:1000
内存限制:65536
输入
第一行是一个整数t,1 ≤ t ≤ 40,表示测试数据的数目。 每个测试样例的第一行是一个整数n,1 ≤ n ≤ 10000,其后n行每行是一个不超过10位的电话号码。
输出
对于每个测试数据,如果是一致的输出“YES”,如果不是输出“NO”。
样例输入
2 3 911 97625999 91125426 5 113 12340 123440 12345 98346
样例输出
NO YES
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
int t;
int n;
int FLAG; // FLAG=1代表互不构成后缀,FLAG=0代表摸一个单词构成后缀
struct Node {
struct Node *next[10]; // 定义一个指针数组next,里面的元素都是Node类型的指针
int is_Cover; // 定义这个节点的访问次数
int is_End; // 定义这个节点是否是一个电话号的最后一个字符
};
void Init(Node *a) // 初始化节点i
{
memset(a->next, 0, sizeof(a->next)); // next[0]~next[9]都是指针NULL
a->is_Cover = 0;
a->is_End = 0;
}
// 内存友好型函数:释放内存
void DELETE(Node *root) {
for (int i = 0; i < 10; i++) {
if (root->next[i]) {
DELETE(root->next[i]);
} // 递归法释放内存
}
free(root); // 递归到底层,root->next[0~9]都是NULL,直接释放root即可
}
void insert(Node *root, char *temp) {
Node *p = root;
int id; // 0~9
while (*temp) // 字符串指针未到底
{
id = *temp - '0';
if (p->next[id] == NULL) {
p->next[id] = (Node *)malloc(sizeof(Node)); // 先申请内存空间
Init(p->next[id]); // 再对这个节点进行初始化
}
p = p->next[id]; // 指针往下移动
if (p->is_End) {
FLAG = 0;
} // 这个点是其他电话号的最后一个数字,包含着其他单词的前缀
p->is_Cover++;
temp++; // 字符指针向下移动
}
if (p->is_Cover > 1) {
FLAG = 0;
} // 执行到这里说明temp字符串是其他长字符串的前缀,temp字符串较短
p->is_End = 1; // 设置字符串末尾标志
}
int main() {
char ss[15];
cin >> t;
while (t--) {
Node *root = (Node *)malloc(sizeof(Node));
Init(root);
FLAG = 1; // 没有特殊情况不构成后缀
cin >> n;
while (n--) {
scanf("%s", ss);
if (FLAG) {
insert(root, ss);
} // 前面都没有前缀的发生,可以继续插入
}
if (FLAG == 0) {
cout << "NO" << endl;
} else {
cout << "YES" << endl;
}
DELETE(root); // 释放内存
}
return 0;
}移动路线
桌子上有一个m行n列的方格矩阵,将每个方格用坐标表示,行坐标从下到上依次递增,列坐标从左至右依次递增,左下角方格的坐标为(1,1),则右上角方格的坐标为(m,n)。
小明是个调皮的孩子,一天他捉来一只蚂蚁,不小心把蚂蚁的右脚弄伤了,于是蚂蚁只能向上或向右移动。小明把这只蚂蚁放在左下角的方格中,蚂蚁从左下角的方格中移动到右上角的方格中,每步移动一个方格。蚂蚁始终在方格矩阵内移动,请计算出不同的移动路线的数目。
对于1行1列的方格矩阵,蚂蚁原地移动,移动路线数为1;对于1行2列(或2行1列)的方格矩阵,蚂蚁只需一次向右(或向上)移动,移动路线数也为1……对于一个2行3列的方格矩阵,如下图所示:
-------------------
|(2,1)|(2,2)|(2,3)|
-------------------
|(1,1)|(1,2)|(1,3)|
-------------------
蚂蚁共有3种移动路线:
路线1:(1,1) → (1,2) → (1,3) → (2,3)
路线2:(1,1) → (1,2) → (2,2) → (2,3)
路线3:(1,1) → (2,1) → (2,2) → (2,3)
时间限制:1000
内存限制:65536
输入
输入只有一行,包括两个整数m和n(0<m+n<=20),代表方格矩阵的行数和列数,m、n之间用空格隔开
输出
输出只有一行,为不同的移动路线的数目。
样例输入
2 3
样例输出
3
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 40;
const int dx[2] = {0, 1};
const int dy[2] = {1, 0};
int n, m, ans = 0;
bool flag = false;
struct node {
int x;
int y;
} st[N * N], tu[N * N][N * N];
int a[N * N];
bool ran_out(int x, int y) { return x < 1 || x > n || y < 1 || y > m; }
void fuzhi(int step) {
ans++;
a[ans] = step;
flag = true;
for (int i = 0; i <= step; i++) {
tu[ans][i].x = st[i].x;
tu[ans][i].y = st[i].y;
}
}
void dfs(int x, int y, int step) {
st[step].x = x;
st[step].y = y;
if (x == n && y == m) {
fuzhi(step);
return;
}
for (int i = 0; i < 2; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (!ran_out(xx, yy)) {
dfs(xx, yy, step + 1);
}
}
}
int main() {
std::ios::sync_with_stdio(false);
cin >> n >> m;
dfs(1, 1, 0);
printf("%d\n", ans);
for (int i = 1; i <= ans; i++)
return 0;
}移动办公
假设你经营着一家公司,公司在北京和南京各有一个办公地点。公司只有你一个人,所以你只能每月选择在一个城市办公。在第i个月,如果你在北京办公,你能获得Pi的营业额,如果你在南京办公,你能获得Ni的营业额。但是,如果你某个月在一个城市办公,下个月在另一个城市办公,你需要支付M的交通费。那么,该怎样规划你的行程(可在任何一个城市开始),才能使得总收入(总营业额减去总交通费)最大?
时间限制:1000
内存限制:65536
输入
输入的第一行有两个整数T(1 <= T <= 100)和M(1 <= M <= 100),T代表总共的月数,M代表交通费。接下来的T行每行包括两个在1到100之间(包括1和100)的的整数,分别表示某个月在北京和在南京办公获得的营业额。
输出
输出只包括一行,这一行只包含一个整数,表示可以获得的最大总收入。
样例输入
4 3 10 9 2 8 9 5 8 2
样例输出
31
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
int main() {
int n; // ÔÂÊý
int m; // ½»Í¨·Ñ
int a, b;
cin >> n >> m;
int d[n][2];
for (int i = 0; i < n; i++) {
cin >> d[i][0] >> d[i][1];
}
for (int i = n - 2; i >= 0; i--) {
d[i][1] = d[i][1] + max(d[i + 1][0] - m, d[i + 1][1]);
d[i][0] = d[i][0] + max(d[i + 1][0], d[i + 1][1] - m);
}
cout << max(d[0][0], d[0][1]);
}青蛙的约会
两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。
时间限制:1000
内存限制:65536
输入
输入只包括一行5个整数x,y,m,n,L,其中x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 2100000000。
输出
输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行"Impossible"
样例输入
1 2 3 4 5
样例输出
4
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
ll gcd = exgcd(b, a % b, y, x);
y -= (a / b) * x;
return gcd;
}
ll inv(ll a, ll b, ll c) {
ll x, y;
ll gcd = exgcd(a, b, x, y);
if (c % gcd != 0)
return -1;
x *= c / gcd; // 得到当前情况下的一个x
b /= gcd; // 根据通解x = x0 + (b * t) / gcd 所以b = b / gcd
b = abs(
b); // 为了得到正数解,所以要abs,而且要在上一步/gcd之后,因为gcd可能是负的
ll ans = x % b;
if (ans < 0)
ans += b;
return ans;
}
int main() {
ll x, y, n, m, L;
cin >> x >> y >> m >> n >> L;
ll res = inv(m - n, L, y - x);
if (res == -1)
cout << "Impossible";
else
cout << res;
return 0;
}迷宫
一天Extense在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由n * n的格点组成,每个格点只有2种状态,.和#,前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上,Extense想要从点A走到点B,问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#),则看成无法办到。
时间限制:3000
内存限制:65536
输入
第1行是测试数据的组数k,后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 <= n <= 100),表示迷宫的规模是n * n的。接下来是一个n * n的矩阵,矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb,描述A处在第ha行, 第la列,B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。
输出
k行,每行输出对应一个输入。能办到则输出“YES”,否则输出“NO”。
样例输入
2 3 .## ..# #.. 0 0 2 2 5 ..... ###.# ..#.. ###.. ...#. 0 0 4 0
样例输出
YES NO
#include <queue>
#include <stdio.h>
#include <string.h>
int m;
char c[100][100];
int xa, ya, xb, yb;
bool vis[100][100];
int dir[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
struct node {
int x;
int y;
int step;
} q[10000];
void bfs(int xa, int ya, int xb, int yb) {
int head = 1, tail = 1;
memset(vis, 0, sizeof(vis));
q[tail].x = xa;
q[tail].y = ya;
q[tail].step = 0;
tail++;
vis[xa][ya] = 1;
int flag = 1;
while (head < tail) {
int x = q[head].x;
int y = q[head].y;
int step = q[head].step;
if (x == xb && y == yb) {
flag = 0;
printf("YES\n");
break;
}
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < m && c[nx][ny] == '.' &&
vis[nx][ny] == 0) {
vis[nx][ny] = 1;
q[tail].x = nx;
q[tail].y = ny;
q[tail].step = step + 1;
tail++;
}
}
head++;
}
if (flag == 1) {
printf("NO\n");
}
}
int main() {
int n;
scanf("%d", &n);
while (n--) {
scanf("%d", &m);
for (int i = 0; i < m; i++) {
scanf("%s", c[i]);
}
scanf("%d%d%d%d", &xa, &ya, &xb, &yb);
bfs(xa, ya, xb, yb);
}
return 0;
}