Scratch编程一级 题库
旅行相册
1.准备工作
(1)删除小猫角色;
(2)选择角色Wizard-toad;
(3)删除默认白色背景,选择背景依次为:Forest,Boardwalk,Water And Rocks,Arctic;
(4)为背景选择声音Chill。
2.功能实现
(1)点击绿旗开始,角色Wizard-toad初始位置如图所示,初始造型为wizard-toad-a;
(2)程序开始1秒后,角色Wizard-toad向上跳起100步,换成wizard-toad-b造型,在空中停留1秒后,落到地面,换成wizard-toad-a造型,注意角色Wizard-toad始终朝向右;
(3)点击绿旗后,初始背景为Forest,背景播放着声音Chill,同时每隔1秒切换一次背景,最后停在第四个背景Arctic。

参考程序:


评分标准:
(1)删除小猫角色和默认白色背景;(1分)
(2)按照要求添加背景和角色;(2分)
(3)角色初始造型、位置及背景设置正确;(2分)
(4)角色能够跳起,并且能切换造型;(2分)
(5)角色跳起和落下的过程中,始终朝向右边;(2分)
(6)背景能够播放音乐;(2分)
(7)能够切换四次背景;(2分)
(8)播放声音的同时切换背景。(2分)
报时的公鸡
故事背景:公鸡在黎明时分会打鸣迎接太阳升起,古人也将鸡鸣声当做晨起的“闹钟”。
1.准备工作
(1) 背景:根据下图绘制两张背景;

(2) 删除默认角色,添加角色Rooster。

2.功能实现
(1) 点击小绿旗,角色Rooster初始化位置、大小,位于舞台左侧,面向右侧,造型为“rooster-a”,背景为“背景1”;

(2) 点击角色Rooster,Rooster从舞台左侧走到右侧,再从右侧走到中间;(注意走的过程中脚不能朝上,并且朝哪个方向走Rooster就面朝哪里)
(3) 走完后,切换成造型“rooster-b”,播放声音“rooster”,声音播完后,切换背景为“背景2”。

角色Rooster代码:

评分标准:
(1)能够添加角色Rooster,正确绘制出两张背景,两张背景能分别表示黑夜和白天;(5分)
(2)能够正确设置角色Rooster的初始位置、大小、方向;(2分)
(3)能够使用“当角色被点击”、“将旋转方式设为左右翻转”、“面向...方向”,实现角色Rooster被点击时,先向右走到舞台右侧,再向左走到舞台中间;(3分)
(4)能够使用“换成...造型”实现角色Rooster的造型初始化和造型切换,使用“换成...背景”实现背景初始化和背景切换;(3分)
(5)能够使用“播放声音...等待播完”,在角色Rooster切换造型后播放“rooster”。(2分)
药房管理
随着信息技术的蓬勃发展,医疗信息化已经成为医院建设中必不可少的一部分。计算机可以很好地辅助医院管理医生信息、病人信息、药品信息等海量数据,使工作人员能够从这些机械的工作中解放出来,将更多精力投入真正的医疗过程中,从而极大地提高了医院整体的工作效率。
对药品的管理是其中的一项重要内容。现在药房的管理员希望使用计算机来帮助他管理。假设对于任意一种药品,每天开始工作时的库存总量已 知,并且一天之内不会通过进货的方式增加。每天会有很多病人前来取药,每个病人希望取走不同数量的药品。如果病人需要的数量超过了当时的库存量,药房会拒 绝该病人的请求。管理员希望知道每天会有多少病人没有取上药。
时间限制:1000
内存限制:65536
输入
共3行 第一行是每天开始时的药品总量m 第二行是这一天取药的人数n(0 < n <= 100) 第三行共有n个数,分别记录了每个病人希望取走的药品数量(按照时间先后的顺序),两数之间以空格分隔
输出
只有1行,为这一天没有取上药品的人数。
样例输入
30 6 10 5 20 6 7 8
样例输出
2
#include <iostream>
using namespace std;
int main() {
int i = 0, m, n, x, s = 0;
cin >> m >> n;
while (n--) {
cin >> x;
s = s + x;
if (s > m) {
i++;
s = s - x;
}
}
cout << i;
return 0;
}奇数求和
计算非负整数 m 到 n(包括m 和 n )之间的所有奇数的和,其中,m 不大于 n,且n 不大于300。例如 m=3, n=12,
其和则为:3+5+7+9+11=35。
时间限制:1000
内存限制:65536
输入
两个数 m 和 n,两个数以一个空格分开,其中 0 <= m <= n <= 300 。
输出
输出一行,包含一个整数,表示m 到 n(包括m 和 n )之间的所有奇数的和
样例输入
7 15
样例输出
55
#include <iostream>
using namespace std;
int main() {
int m, n, sum = 0;
cin >> m >> n;
for (int i = m; i <= n; i++) {
if (i % 2 == 1) {
sum = sum + i;
}
}
cout << sum;
return 0;
}苹果和虫子2
你买了一箱n个苹果,很不幸的是买完时箱子里混进了一条虫子。虫子每x小时能吃掉一个苹果,假设虫子在吃完一个苹果之前不会吃另一个,那么经过y小时你还有多少个完整的苹果?
时间限制:1000
内存限制:65536
输入
输入仅一行,包括n,x和y(均为整数)。
输出
输出也仅一行,剩下的苹果个数
样例输入
10 4 9
样例输出
7
提示
注意:是要求完整的苹果数。
#include <iostream>
using namespace std;
int main() {
int n, x, y, t;
cin >> n >> x >> y;
if (y % x != 0) {
t = n - (int)(y / x) - 1;
} else {
t = n - (int)(y / x);
}
if (t > 0) {
cout << t << endl;
} else {
cout << 0 << endl;
}
return 0;
}与圆相关的计算
给出圆的半径,求圆的直径、周长和面积。
时间限制:1000
内存限制:65536
输入
输入包含一个实数r(0 < r <= 10,000),表示圆的半径。
输出
输出一行,包含三个数,分别表示圆的直径、周长、面积,数与数之间以一个空格分开,每个数保留小数点后4位。
样例输入
3.0
样例输出
6.0000 18.8495 28.2743
提示
如果圆的半径是r,那么圆的直径、周长、面积分别是2*r、2 * pi * r、pi * r * r,其中约定pi=3.14159。 可以
使用printf("%.4lf", ...)实现保留小数点后4位。
#include <bits/stdc++.h>
using namespace std;
int main() {
double r, c, a, pi, t;
cin >> r;
pi = 1.0 * 3.14159;
c = 1.0 * 2 * r;
a = 1.0 * pi * r * r;
t = 1.0 * 2 * (pi * r);
cout << setiosflags(ios::fixed) << setprecision(4);
cout << c << " " << t << " " << a << " " << endl;
return 0;
}字符菱形
给定一个字符,用它构造一个对角线长5个字符,倾斜放置的菱形。
时间限制:1000
内存限制:65536
输入
输入只有一行, 包含一个字符。
输出
该字符构成的菱形。
样例输入
*
样例输出
*
***
*****
***
*
#include <iostream>
using namespace std;
int main() {
char a;
cin >> a;
cout << " " << a << endl;
cout << " " << a << a << a << endl;
cout << a << a << a << a << a << endl;
cout << " " << a << a << a << endl;
cout << " " << a << endl;
}漫漫回国路
2020年5月,国际航班机票难求。一位在美国华盛顿的中国留学生,因为一些原因必须在本周内回到北京。现在已知各个机场之间的航班情况,求问他回不回得来(不考虑转机次数和机票价格)。
时间限制:1000
内存限制:65536
输入
第一行为case个数n(n < 10)。 每一个case,第一行为机场个数N,N ≤ 10。 之后的N行,每一行包含N个整数。第i(1 ≤ i ≤ N)行的第j(1 ≤ j ≤ N)个整数代表从第i个机场出发到第j个机场的能买到的航班的最低票价t(0 < t < 10000)。如果不幸没有航班,那么用-1表示。第i行第i个整数为0。 起点华盛顿杜勒斯国际机场的编号为1,终点北京首都国际机场的编号为N。
输出
每一个case一行。 能够回国,输出字符串:YES。如果无法回国,输出字符串:NO
样例输入
2 3 0 100 -1 -1 0 200 -1 -1 0 4 0 1 5 -1 3 0 1 -1 2 4 0 -1 4 1 1 0
样例输出
YES NO
// 广搜
#include <bits/stdc++.h>
using namespace std;
int a[12][12], n;
bool v[12][12];
bool bfs(int p) {
queue<int> q;
q.push(p);
v[p][p] = true;
while (!q.empty()) {
int h = q.front();
q.pop();
for (int i = 1; i <= n; i++) {
if (!v[h][i] && a[h][i] > 0) {
if (i == n)
return true;
else {
q.push(i);
v[h][i] = true;
}
}
}
}
return false;
}
int main() {
int k;
cin >> k;
while (k--) {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
if (bfs(1))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}// 参考代码2
// 深度优先搜索
#include <stdbool.h>
#include <stdio.h>
#define MAX_N 10
#define INF 10000
int airports[MAX_N][MAX_N]; // 存储机场之间的航班票价
bool visited[MAX_N]; // 记录机场是否被访问过
int n; // 机场个数
bool found; // 是否找到回国路径
void dfs(int start, int end) {
if (start == end) {
found = true; // 找到回国路径
return;
}
visited[start] = true;
for (int i = 1; i <= n; i++) {
if (!visited[i] && airports[start][i] != -1) {
dfs(i, end);
}
}
}
bool canReturn() {
found = false;
for (int i = 1; i <= n; i++) {
visited[i] = false;
}
dfs(1, n);
return found;
}
int main() {
int cases;
scanf("%d", &cases);
while (cases--) {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
scanf("%d", &airports[i][j]);
}
}
if (canReturn()) {
printf("YES\n");
} else {
printf("NO\n");
}
}
return 0;
}装箱问题
一个工厂制造的产品形状都是长方体,它们的高度都是h,长和宽都相等,一共有六个型号,他们的长宽分别为1*1, 2*2, 3*3, 4*4, 5*5, 6*6。这些产品通常使用一个 6*6*h 的长方体包裹包装然后邮寄给客户。因为邮费很贵,所以工厂要想方设法的减小每个订单运送时的包裹数量。他们很需要有一个好的程序帮他们解决这个问题从而节省费用。现在这个程序由你来设计。
时间限制:1000
内存限制:65536
输入
输入文件包括几行,每一行代表一个订单。每个订单里的一行包括六个整数,中间用空格隔开,分别为1*1至6*6这六种产品的数量。输入文件将以6个0组成的一行结尾。
输出
除了输入的最后一行6个0以外,输入文件里每一行对应着输出文件的一行,每一行输出一个整数代表对应的订单所需的最小包裹数。
样例输入
0 0 4 0 0 1 7 5 1 0 0 0 0 0 0 0 0 0
样例输出
2 1
#include <cstdio>
#include <cstring>
using namespace std;
int a[7];
int main() {
int x, xx, i, ans;
while (1) {
for (i = 1; i <= 6; i++) {
scanf("%d", &a[i]);
}
if (a[1] == 0 && a[2] == 0 && a[3] == 0 && a[4] == 0 && a[5] == 0 &&
a[6] == 0)
break;
ans = 0;
ans = a[6];
ans = ans + a[5];
xx = a[5] * 11;
if (xx <= a[1])
a[1] = a[1] - xx;
else
a[1] = 0;
ans = ans + a[4];
x = a[4] * 5;
if (x <= a[2]) {
a[2] = a[2] - x;
} else {
xx = 4 * (x - a[2]);
if (xx <= a[1])
a[1] = a[1] - xx;
else
a[1] = 0;
a[2] = 0;
}
ans = ans + a[3] / 4;
a[3] = a[3] % 4;
if (a[3] > 0) {
if (a[3] == 3) {
ans++;
if (a[2] >= 1) {
a[2]--;
xx = 5;
if (xx <= a[1])
a[1] = a[1] - xx;
else
a[1] = 0;
} else {
xx = 9;
if (xx <= a[1])
a[1] = a[1] - xx;
else
a[1] = 0;
}
} else if (a[3] == 2) {
ans++;
if (a[2] >= 3) {
a[2] -= 3;
xx = 6;
if (xx <= a[1])
a[1] = a[1] - xx;
else
a[1] = 0;
} else {
xx = 6 + (3 - a[2]) * 4;
a[2] = 0;
if (xx <= a[1])
a[1] = a[1] - xx;
else
a[1] = 0;
}
} else if (a[3] == 1) {
ans++;
if (a[2] >= 5) {
a[2] -= 5;
xx = 7;
if (xx <= a[1])
a[1] = a[1] - xx;
else
a[1] = 0;
} else {
xx = 7 + (5 - a[2]) * 4;
a[2] = 0;
if (xx <= a[1])
a[1] = a[1] - xx;
else
a[1] = 0;
}
}
}
ans = ans + a[2] / 9;
a[2] = a[2] % 9;
if (a[2] > 0) {
ans++;
xx = 36 - a[2] * 4;
a[2] = 0;
if (xx <= a[1])
a[1] = a[1] - xx;
else
a[1] = 0;
}
ans = ans + a[1] / 36;
a[1] = a[1] % 36;
if (a[1] > 0) {
ans++;
a[1] = 0;
}
printf("%d\n", ans);
}
return 0;
}鸣人和佐助
描述
佐助被大蛇丸诱骗走了,鸣人在多少时间内能追上他呢?
已知一张地图(以二维矩阵的形式表示)以及佐助和鸣人的位置。地图上的每个位置都可以走到,只不过有些位置上有大蛇丸的手下,需要先打败大蛇丸的手下才能到这些位置。鸣人有一定数量的查克拉,每一个单位的查克拉可以打败一个大蛇丸的手下。假设鸣人可以往上下左右四个方向移动,每移动一个距离需要花费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;
}分成互质组
给定n个正整数,将它们分组,使得每组中任意两个数互质。至少要分成多少个组?
时间限制:1000
内存限制:65536
输入
第一行是一个正整数n。1 <= n <= 10。 第二行是n个不大于10000的正整数。
输出
一个正整数,即最少需要的组数。
样例输入
6 14 20 33 117 143 175
样例输出
3
#include <algorithm>
#include <bits/stdc++.h>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int n, a[12], ans, huzhi[12][12];
int group[12][12], group_size[12];
int hz(int x, int y) {
if (y == 0)
return x;
return hz(y, x % y);
}
void ss(int x, int group_cnt) {
if (x > n) {
ans = min(group_cnt, ans);
return;
}
for (int i = 1; i <= group_cnt; i++) {
int pd = 0;
for (int j = 1; j <= group_size[i]; j++) {
if (huzhi[x][group[i][j]] == 0) {
pd = 1;
break;
}
}
if (pd == 1)
continue;
group_size[i]++;
group[i][group_size[i]] = x;
ss(x + 1, group_cnt);
group[i][group_size[i]] = 0;
group_size[i]--;
}
group_size[group_cnt + 1] = 1;
group[group_cnt + 1][1] = x;
ss(x + 1, group_cnt + 1);
group[group_cnt + 1][1] = 0;
group_size[group_cnt + 1] = 0;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
if (hz(a[i], a[j]) == 1) {
huzhi[i][j] = 1;
}
}
ans = 10;
ss(1, 0);
printf("%d", ans);
return 0;
}开餐馆
北大信息学院的同学小明毕业之后打算创业开餐馆.现在共有n 个地点可供选择。小明打算从中选择合适的位置开设一些餐馆。这 n 个地点排列在同一条直线上。我们用一个整数序列m1, m2, … mn 来表示他们的相对位置。由于地段关系,开餐馆的利润会有所不同。我们用pi 表示在mi 处开餐馆的利润。为了避免自己的餐馆的内部竞争,餐馆之间的距离必须大于k。请你帮助小明选择一个总利润最大的方案。
时间限制:1000
内存限制:65536
输入
标准的输入包含若干组测试数据。输入第一行是整数T (1 <= T <= 1000) ,表明有T组测试数据。紧接着有T组连续的测试。每组测试数据有3行, 第1行:地点总数 n (n < 100), 距离限制 k (k > 0 && k < 1000). 第2行:n 个地点的位置m1 , m2, … mn ( 1000000 > mi > 0 且为整数,升序排列) 第3行:n 个地点的餐馆利润p1 , p2, … pn ( 1000 > pi > 0 且为整数)
输出
对于每组测试数据可能的最大利润
样例输入
2 3 11 1 2 15 10 2 30 3 16 1 2 15 10 2 30
样例输出
40 30
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int f[1010], a[1010], v[1010];
int main() {
int t, o, i, j, k, n, m, maxn;
cin >> t;
for (o = 1; o <= t; o++) {
cin >> n >> k;
for (i = 1; i <= n; i++)
cin >> a[i];
for (i = 1; i <= n; i++)
cin >> v[i];
memset(f, 0, sizeof(f));
f[1] = v[1];
for (i = 2; i <= n; i++) {
maxn = 0;
for (j = 1; j < i; j++)
if (f[j] > maxn && a[i] - a[j] > k)
maxn = f[j];
f[i] = v[i] + maxn;
}
maxn = 0;
for (i = 1; i <= n; i++)
maxn = max(maxn, f[i]);
cout << maxn << endl;
}
return 0;
}//C语言实现的代码:
#include <stdio.h>
#include <stdbool.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int maxProfit(int m[], int p[], int n, int k) {
int dp[100];
dp[0] = p[0];
for (int i = 1; i < n; i++) {
dp[i] = p[i];
for (int j = i - 1; j >= 0; j--) {
if (m[i] - m[j] > k) {
dp[i] = max(dp[i], dp[j] + p[i]);
}
}
}
int maxProfit = 0;
for (int i = 0; i < n; i++) {
maxProfit = max(maxProfit, dp[i]);
}
return maxProfit;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n, k;
scanf("%d %d", &n, &k);
int m[100];
int p[100];
for (int i = 0; i < n; i++) {
scanf("%d", &m[i]);
}
for (int i = 0; i < n; i++) {
scanf("%d", &p[i]);
}
int result = maxProfit(m, p, n, k);
printf("%d\n", result);
}
return 0;
}邮票收集
小A是个邮票收集爱好家,他有n种面值的邮票,每种邮票都有无数张。一天小B想要寄信,需要一共面值和为k的邮票组合。小A想要知道拼出面值为k的邮票最少需要多少张。
时间限制:1000
内存限制:131072
输入
输入是多组数据。(不超过10组) 每组数据的第一行正整数n,k,表示邮票的种类数目和目标要拼出的钱。(0 < n ≤ 100, 0 < k ≤ 1000 ) 接下来的一行有n个正整数ai(0 < ai ≤ 1000)。 若n=k=0表示输入结束。
输出
每组数据输出一行一个数,分别表示拼出k需要的最少的邮票数量。 如果不存在能够拼出k的方案,输出-1。
样例输入
4 10 1 2 3 4 5 16 1 2 3 4 5 2 7 4 5 0 0
样例输出
3 4 -1
提示
第一组数据: 10 = 4+4+2 第二组数据:16 = 5+5+5+1 第三组数据: 不存在。
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int a[1010], f[1010];
int main() {
int n, k, i, j;
cin >> n >> k;
while (n != 0 && k != 0) {
for (i = 1; i <= n; i++)
cin >> a[i];
for (i = 1; i <= k; i++)
f[i] = 1000000000;
f[0] = 0;
for (i = 1; i <= n; i++)
for (j = a[i]; j <= k; j++)
f[j] = min(f[j], f[j - a[i]] + 1);
if (f[k] != 1000000000)
cout << f[k] << endl;
else
cout << -1 << endl;
cin >> n >> k;
}
return 0;
}带通配符的字符串匹配
通配符是一类键盘字符,当我们不知道真正字符或者不想键入完整名字时,常常使用通配符代替一个或多个真正字符。通配符有问号(?)和星号(*)等,其中,“?”可以代替一个字符,而“*”可以代替零个或多个字符。
你的任务是,给出一个带有通配符的字符串和一个不带通配符的字符串,判断他们是否能够匹配。
例如,1?456 可以匹配 12456、13456、1a456,但是却不能够匹配23456、1aa456;
2*77?8可以匹配 24457798、237708、27798。
时间限制:1000
内存限制:65536
输入
输入有两行,每行为一个不超过20个字符的字符串,第一行带通配符,第二行不带通配符
输出
如果两者可以匹配,就输出“matched”,否则输出“not matched”
样例输入
1*456? 11111114567
样例输出
matched
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
int f[3005][3005] = {0}, q[3005] = {0}, prt[3005][3005] = {0};
string st1, st2;
int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
void Get(int x, int y) {
if (x == 0 && y == 0)
return;
int lx = x - 1, ly = prt[x][y];
if (st1[x] == '*' && y != ly) {
q[++q[0]] = y - ly;
}
Get(lx, ly);
}
int main() {
cin >> st1 >> st2;
int i, j, k, bj, div, ans = 0, len1 = st1.length(), len2 = st2.length();
st1 = ' ' + st1;
st2 = ' ' + st2;
f[0][0] = 1;
for (i = 1; i <= len1; i++)
for (j = 0; j <= len2; j++) {
if (st1[i] == '?' || st1[i] == st2[j]) {
f[i][j] = f[i - 1][j - 1];
if (f[i][j])
prt[i][j] = j - 1;
} else if (st1[i] == '*') {
for (k = j, bj = 0; k >= 0; k--)
if (f[i - 1][k]) {
bj = 1;
break;
}
if (bj) {
f[i][j] = 1;
prt[i][j] = k;
}
}
}
if (f[len1][len2]) {
cout << "matched\n";
} else
cout << "not matched";
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 <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
struct node {
int data, lenth;
int next;
} a[1010];
int main() {
int t, n, i, j, p, maxn, o;
cin >> t;
for (o = 1; o <= t; o++) {
cin >> n;
for (i = 1; i <= n; i++)
cin >> a[i].data;
a[n].lenth = 1;
a[n].next = 0;
for (i = n - 1; i >= 1; i--) {
maxn = p = 0;
for (j = i + 1; j <= n; j++)
if ((a[j].lenth > maxn) && (a[i].data < a[j].data)) {
p = j;
maxn = a[j].lenth;
}
a[i].lenth = maxn + 1;
a[i].next = p;
}
maxn = j = 0;
for (i = 1; i <= n; i++)
if (a[i].lenth > maxn) {
maxn = a[i].lenth;
j = i;
}
cout << maxn << endl;
}
return 0;
}完美立方
形如 a3= b3 + c3 + d3的等式被称为完美立方等式。例如 123= 63 + 83 + 103 。
编写一个程序,对任给的正整数 N (N≤100),寻找所有的四元组 (a, b, c, d),使得 a3= b3 + c3 + d3 ,其中 a,b,c,d均大于 11, 小于等于 N,且 b≤c≤d 。
时间限制:1000
内存限制:65536
输入
一个正整数 N(N≤100)。
输出
每行输出一个完美立方。输出格式为:
Cube = a, Triple = (b,c,d)
其中 a,b,c,d 所在位置分别用实际求出四元组值代入。
请按照 a 的值,从小到大依次输出。
当两个完美立方等式中 a 的值相同,则 b 值小的优先输出、仍相同则 c 值小的优先输出。
样例输入
24
样例输出
Cube = 6, Triple = (3,4,5) Cube = 12, Triple = (6,8,10) Cube = 18, Triple = (2,12,16) Cube = 18, Triple = (9,12,15) Cube = 19, Triple = (3,10,18) Cube = 20, Triple = (7,14,17) Cube = 24, Triple = (12,16,20)
#include <cstdio>
using namespace std;
int main() {
int N;
scanf("%d", &N);
for (int a = 2; a <= N; ++a)
for (int b = 2; b < a; ++b)
for (int c = b; c < a; ++c)
for (int d = c; d < a; ++d)
if (a * a * a == b * b * b + c * c * c + d * d * d)
printf("Cube = %d, Triple = (%d,%d,%d)\n", a, b, c, d);
return 0;
}不定方程求解
给定正整数a,b,c。求不定方程 ax+by=c 关于未知数x和y的所有非负整数解组数。
时间限制:1000
内存限制:65536
输入
一行,包含三个正整数a,b,c,两个整数之间用单个空格隔开。每个数均不大于1000。
输出
一个整数,即不定方程的非负整数解组数。
样例输入
2 3 18
样例输出
4
#include <iostream>
using namespace std;
int main() {
int a, b, c, x, y, s = 0;
cin >> a >> b >> c;
for (x = 0; x <= c / a; x++) {
y = (c - a * x) / b;
if (a * x + b * y == c)
s++;
}
cout << s;
return 0;
}分解因数
给出一个正整数 a ,要求分解成若干个正整数的乘积,即 a = a1· a2 ·a3·...·an,并且 1<a1≤a2≤a3≤...≤ an,问这样的分解的种数有多少。
注意到 a = a 也是一种分解。
时间限制:1000
内存限制:65536
输入
第 1 行是测试数据的组数 n(1≤n≤1000) ,后面跟着 n 行输入。每组测试数据占 1 行,包括一个正整数 a (1<a<32768)
输出
n 行,每行输出对应一个输入。输出应是一个正整数,指明满足要求的分解的种数。
样例输入
2 2 20
样例输出
1 4
#include <stdio.h>
int count = 0;
int func(int a, int b) {
if (a == 1)
return 1;
if (b == 1)
return 0;
if (a % b == 0)
return func(a / b, b) + func(a, b - 1);
return func(a, b - 1);
}
int main() {
int N, a;
scanf("%d", &N);
while (N--) {
scanf("%d", &a);
printf("%d\n", func(a, a));
}
return 0;
}上台阶
楼梯有 n(1≤n≤30) 阶台阶,上楼时可以一步上 1 阶,也可以一步上 2 阶,也可以一步上 3 阶,编程计算共有多少种不同的走法。
时间限制:1000
内存限制:65536
输入
输入的每一行包括一组测试数据,即为台阶数 n(1≤n≤30) 。最后一行为0,表示测试结束。
输出
每一行输出对应一行输入的结果,即为走法的数目。
样例输入
1 2 3 4 0
样例输出
1 2 4 7
#include <iostream>
using namespace std;
const int N = 73;
long long c[N + 1] = {0};
long long countN(int n) {
c[0] = c[1] = 1, c[2] = 2;
for (int i = 3; i <= N; i++) {
c[i] = c[i - 1] + c[i - 2] + c[i - 3];
}
return c[n];
}
int main() {
int n;
countN(N);
while (cin >> n && n > 0 && n <= N) {
cout << c[n] << endl;
}
return 0;
}田忌赛马
在田忌赛马的故事中,孙膑用自己的下等马对战对手的上等马,自己上等马对阵对手的中等马,自己的中等马对阵对手的下等马,从而赢得了胜利。现在即将进行的是N匹马的赛马比赛。双方队伍的马各分为N等。已知只有当我方马的等级比对方马等级高 X 等以上(包含 X )时,我方才可以取得这场比赛的胜利。如果在N场比赛中我方的胜场数大于对方,则我方取得最终的胜利。现在已知对方这 N 场比赛的出战方案,请计算所有令我方最终获胜的出战方案。
时间限制:1000
内存限制:65536
输入
第一行两个整数, N 和 X 。0≤X<N≤9 。 第二行 N 个正整数,A1, A2,..., AN 。Ai表示第 i 场比赛对方马的等级,1≤i≤N。等级越高越强。
输出
按字典序输出所有我方最终获胜的方案,每个方案一行。每行是 N 个正整数,两两之间以一个空格分隔,第 i 个数表示我方第 i 场比赛马的等级。
样例输入1
3 1 3 2 1
样例输入2
3 0 3 1 2
样例输出1
1 3 2
样例输出2
1 2 3 1 3 2 2 1 3 3 1 2 3 2 1
#include <bits/stdc++.h>
using namespace std;
int A[12];
int N, X, xy;
int x[12];
#include <algorithm>
#include <iostream>
using namespace std;
void prt(int arr[], int end) {
int i;
int sum = 0;
for (i = 0; i <= end; i++)
if (arr[i] >= A[i] + X)
sum++;
if (sum >= xy) {
for (i = 0; i <= end; ++i) {
printf("%d ", arr[i]);
}
printf("\n");
}
}
void perm(int arr[], int len) {
if (len < 2)
return;
int i, j, temp;
do {
// 输出当前序列
prt(arr, len - 1);
i = j = len - 1;
// 向前查找第一个变小的元素
while (i > 0 && arr[i] < arr[i - 1])
--i;
temp = i;
if (i == 0)
break;
// 先后查找第一个比arr[i-1]大的元素
while (temp + 1 < len && arr[temp + 1] > arr[i - 1])
++temp;
swap(arr[i - 1], arr[temp]); // 交换两个值
reverse(arr + i, arr + len); // 逆序
} while (true);
}
int main() {
int i, j, k;
scanf("%d%d", &N, &X);
for (i = 0; i < N; i++)
scanf("%d", &A[i]);
if (N % 2 == 0)
xy = N / 2 + 1;
else
xy = (N + 1) / 2;
for (i = 1; i <= N; i++)
x[i] = i;
perm(x + 1, N);
return 0;
}