Scratch编程一级 题库
迷信的病人
医院为了方便对患者进行建档和管理,引入了9位整数ID号来标识每个病人。最近医院入住了一个迷信的病人,他认为ID号的好坏直接决定了自己的命运。他对ID号x有如下要求:
(1)x的前三位数构成的整数是素数
(2)x的后三位数构成的整数是平方数(所谓平方数,是指它是某一个正整数的平方,e.g. 1,4,9,16...)
(3)x中不包含"13"
为了避免不必要的医患矛盾,医院须尽量满足他的需求。现给定正整数区间[m,n],请你判断存在几个满足病人需求的ID号。
时间限制:1000
内存限制:65536
输入
两个正整数m,n,以空格隔开。(999999999>=n>=m>=111111111)
输出
一个整数(满足要求的ID的个数)。
样例输入
157689476 157689687
样例输出
5
提示
存在5个满足要求的ID:157689484,157689529,157689576,157689625,157689676
#include <bits/stdc++.h>
using namespace std;
bool su(int x) {
for (int i = 2; i < x; i++) {
if (x % i == 0)
return false;
}
return true;
}
bool pf(int x) {
int n = sqrt(x);
if (n * n == x)
return true;
return false;
}
int main() {
int m, n, ans = 0;
cin >> m >> n;
for (int i = m; i <= n; i++) {
int q, h;
q = i / 1000000;
h = i % 1000;
int flag = 0, k = i;
while (k) {
if (k % 10 == 3 && k / 10 % 10 == 1)
flag = 1;
k /= 10;
}
if (flag == 0 && su(q) && pf(h))
ans++;
}
cout << ans;
return 0;
}算24
给出4个小于10个正整数,你可以使用加减乘除4种运算以及括号把这4个数连接起来得到一个表达式。现在的问题是,是否存在一种方式使得得到的表达式的结果等于24。 这里加减乘除以及括号的运算结果和运算的优先级跟我们平常的定义一致(这里的除法定义是实数除法)。 比如,对于5,5,5,1,我们知道5 * (5 – 1 / 5) = 24,因此可以得到24。又比如,对于1,1,4,2,我们怎么都不能得到24。
时间限制:6000
内存限制:65536
输入
输入数据包括多行,每行给出一组测试数据,包括4个小于10个正整数。最后一组测试数据中包括4个0,表示输入的结束,这组数据不用处理。
输出
对于每一组测试数据,输出一行,如果可以得到24,输出“YES”;否则,输出“NO”。
样例输入
5 5 5 1 1 1 4 2 0 0 0 0
样例输出
YES NO
#include <bits/stdc++.h>
#include <cmath>
#include <iostream>
#define EPS 1e-6
using namespace std;
bool iszero(double c) {
if (fabs(c) <= EPS)
return 1;
else
return 0;
}
bool suan24(double *a, int k) {
if (k == 1 && iszero(a[0] - 24))
return 1;
double b[5];
for (int i = 0; i < k - 1; i++)
for (int j = i + 1; j < k; j++) {
int z = 0;
for (int xx = 0; xx < k; xx++)
if (xx != i && xx != j)
b[z++] = a[xx];
b[z] = a[i] + a[j];
if (suan24(b, k - 1))
return 1;
b[z] = a[i] - a[j];
if (suan24(b, k - 1))
return 1;
b[z] = a[j] - a[i];
if (suan24(b, k - 1))
return 1;
b[z] = a[i] * a[j];
if (suan24(b, k - 1))
return 1;
if (a[j] != 0) {
b[z] = a[i] / a[j];
if (suan24(b, k - 1))
return 1;
}
if (!iszero(a[i])) {
b[z] = a[j] / a[i];
if (suan24(b, k - 1))
return 1;
}
}
return 0;
}
int main() {
while (1) {
double a[6];
int sum = 0;
for (int i = 0; i < 4; ++i) {
cin >> a[i];
sum += a[i];
}
if (sum == 0)
break;
bool flag = suan24(a, 4);
if (flag == 1)
cout << "YES" << endl;
else
cout << "NO" << endl;
// cout<<flag<<endl;
}
return 0;
}//解法2 深搜
#include <bits/stdc++.h>
using namespace std;
double a[5];
bool fig(double a[],int n){
double b[5];
int i,j,k,m;
if(fabs(a[0]-24)<1e-6 && n==1) return 1;
if(n==1) return 0;
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++){
m=0;
for(k=0;k<n;k++)
if(k!=i&&k!=j) b[++m]=a[k];
b[0]=a[i]+a[j];if(fig(b,n-1)) return 1;
b[0]=a[i]-a[j];if(fig(b,n-1)) return 1;
b[0]=a[j]-a[i];if(fig(b,n-1)) return 1;
b[0]=a[i]*a[j];if(fig(b,n-1)) return 1;
b[0]=a[i]/a[j];if(fig(b,n-1)) return 1;
b[0]=a[j]/a[i];if(fig(b,n-1)) return 1;
}
return 0;
}
int main() {
while(1){
for(int i=0;i<4;i++) cin>>a[i];
if(a[0]==0&&a[1]==0&&a[2]==0&&a[3]==0) break;
if(fig(a,4)) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}倒序输出
依次输入4个整数a、b、c、d,将他们倒序输出,即依次输出d、c、b、a这4个数。
时间限制:1000
内存限制:65536
输入
一行4个整数a、b、c、d,以空格分隔。 0 < a,b,c,d < 108
输出
一行4个整数d、c、b、a,整数之间以一个空格分隔。
样例输入
1 2 3 4
样例输出
4 3 2 1
#include <bits/stdc++.h>
using namespace std;
int a, b, c, d;
int main() {
cin >> a >> b >> c >> d;
cout << d << ' ' << c << ' ' << b << ' ' << a;
return 0;
}平方差计算
给定的两个整数a, b, 他们的平方差结果为a2-b2 ,可以化简为 (a + b)(a-b)。例如5和4的平方差为52-42=(5+4)(5-4)=9。现给定两个整数,求他们的平方差。
时间限制:1000
内存限制:65536
输入
一行两个整数a、b,以空格分隔。 0 < b < a < 104
输出
输出a和b的平方差
样例输入
5 4
样例输出
9
#include <bits/stdc++.h>
using namespace std;
int a, b;
long long sum;
int main() {
cin >> a >> b;
sum = (a + b) * (a - b);
cout << sum;
return 0;
}最小的数
依次输入3个整数a、b、c,将a、b、c中的最小值输出。
时间限制:1000
内存限制:65536
输入
一行3个整数a、b、c,以空格分隔。 0 < a,b,c < 108
输出
1个整数,即3个整数的最小值。
样例输入
2 3 2
样例输出
2
#include <bits/stdc++.h>
using namespace std;
long long a, b, c, ss;
int main() {
cin >> a >> b >> c;
ss = min(a, b);
ss = min(ss, c);
cout << ss;
return 0;
}计算成绩优秀的人数
现有一个班一门课程考试的分数,请统计其中成绩为优秀的人数。成绩为优秀的要求是分数大于等于85。
时间限制:1000
内存限制:65536
输入
第一行1个整数n,表示分数的个数。(0 < n ≤ 100, ) 第二行n个正整数,表示每一个分数,每个分数小于等于100。
输出
输出一个整数,表示成绩为优秀的人数。
样例输入
10 85 70 99 90 78 55 100 62 88 84
样例输出
5
#include <bits/stdc++.h>
using namespace std;
const int N = 100 + 10;
int ss[N];
int n, m = 0;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> ss[i];
if (ss[i] >= 85)
m++;
}
cout << m;
return 0;
}开关灯
假设有N盏灯(N为不大于5000的正整数),从1到N按顺序依次编号,初始时全部处于开启状态;有M个人(M为不大于N的正整数)也从1到M依次编号。
第一个人(1号)将灯全部关闭,第二个人(2号)将编号为2的倍数的灯打开,第三个人(3号)将编号为3的倍数的灯做相反处理(即,将打开的灯关闭,将关闭的灯打开)。依照编号递增顺序,以后的人都和3号一样,将凡是自己编号倍数的灯做相反处理。
请问:当第M个人操作之后,哪几盏灯是关闭的,按从小到大输出其编号,其间用逗号间隔。
时间限制:1000
内存限制:65536
输入
输入正整数N和M,以单个空格隔开。
输出
顺次输出关闭的灯的编号,其间用逗号间隔。
样例输入
10 10
样例输出
1,4,9
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[5010];
int i, j;
int flag = 1;
int main() {
cin >> n >> m;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
if (j % i == 0)
a[j] = !a[j];
for (i = 1; i <= n; i++) {
if (a[i]) {
if (flag)
flag = 0;
else
cout << ",";
cout << i;
}
}
cout << endl;
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;
}字符串插入
有两个字符串str和substr,str的字符个数不超过10,substr的字符个数为3。(字符个数不包括字符串结尾处的'\0'。)将substr插入到str中ASCII码最大的那个字符后面,若有多个最大则只考虑第一个。
时间限制:1000
内存限制:65536
输入
输入包括若干行,每一行为一组测试数据,格式为 str substr
输出
对于每一组测试数据,输出插入之后的字符串。
样例输入
abcab eee 12343 555
样例输出
abceeeab 12345553
#include <cstring>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
typedef char ElemType;
const int M = 14;
typedef struct {
ElemType data[M];
int length;
} SqList;
void lnitList(SqList &L) { L.length = 0; }
void f(SqList &s1, SqList s2) {
ElemType maxc = s1.data[0];
int index = 0;
int j = 0;
for (int i = 0; i < s1.length; i++) {
if (maxc < s1.data[i]) {
index = i;
maxc = s1.data[i];
}
}
s1.data[s1.length] = 0;
s1.data[s1.length + 3] = '\0';
for (int i = s1.length; i > index; i--) {
s1.data[i + 3] = s1.data[i];
}
for (int i = index + 1; i <= index + 3; i++) {
s1.data[i] = s2.data[j++];
}
s1.length += 3;
}
int main() {
SqList s1, s2;
while (cin >> s1.data >> s2.data) {
lnitList(s1);
lnitList(s2);
s1.length = strlen(s1.data);
s2.length = strlen(s2.data);
f(s1, s2);
cout << s1.data << endl;
}
return 0;
}栈基本操作
依次读入序列元素1,2,...,n进栈,每进一个元素,机器可要求下一个元素进栈或弹栈,如此进行。给定一个输入序列,判断栈空时弹出的元素构成的序列是否可能等于给定的序列,如果是则输出栈的操作过程,否则输出“NO”。
时间限制:1000
内存限制:65535
输入
输入分两行 第一行为n的值(即序列元素个数) 第二行为给定的输入序列(序列元素均为整型)
输出
如果输入序列能够由题目规定的操作得到,则输出对栈的操作过程 否则直接输出“NO”
样例输入
7 4 5 3 6 2 7 1
样例输出
PUSH 1 PUSH 2 PUSH 3 PUSH 4 POP 4 PUSH 5 POP 5 POP 3 PUSH 6 POP 6 POP 2 PUSH 7 POP 7 POP 1
提示
给定序列中有可能有不在1...n之间的数字
#include <bits/stdc++.h>
using namespace std;
const int MAXL = 100010;
vector<int> v;
int n;
int visited[MAXL];
bool isLegal() {
stack<int> sk;
int idx = 1;
int k = 0;
while (idx <= n) {
sk.push(idx++);
while (!sk.empty() && sk.top() == v[k]) {
sk.pop();
k++;
}
}
return sk.empty() && k == n;
}
int main() {
// 数据的输入和非法输入判断
cin >> n;
for (int i = 0; i < n; i++) {
int tmp;
cin >> tmp;
if (visited[tmp] || tmp <= 0 || tmp > n) {
cout << "NO" << endl;
system("pause");
return 0;
}
v.push_back(tmp);
visited[tmp] = 1;
}
// 判断是否合法
if (!isLegal()) {
cout << "NO" << endl;
system("pause");
return 0;
}
// 模拟栈
stack<int> sk;
int i = 0; // i是出栈的指针
int j = 1; // j是入栈的指针
while (i < n) { // 最后一个操作是出栈
if (!sk.empty() && sk.top() == v[i]) {
cout << "POP " << v[i] << endl;
sk.pop();
i++;
} else {
cout << "PUSH " << j << endl;
sk.push(j);
j++;
}
}
system("pause");
}滑动窗口
给定一个长度为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;
}书架
John最近买了一个书架用来存放奶牛养殖书籍,但书架很快被存满了,只剩最顶层有空余。
John共有N头奶牛(1 ≤ N ≤ 20,000),每头奶牛有自己的高度Hi(1 ≤ Hi ≤ 10,000),N头奶牛的总高度为S。书架高度为B(1 ≤ B ≤ S < 2,000,000,007).
为了到达书架顶层,奶牛可以踩着其他奶牛的背,像叠罗汉一样,直到他们的总高度不低于书架高度。当然若奶牛越多则危险性越大。为了帮助John到达书架顶层,找出使用奶牛数目最少的解决方案吧。
时间限制:10000
内存限制:65536
输入
第1行:空格隔开的整数N和B 第2~N+1行:第i+1行为整数Hi
输出
能达到书架高度所使用奶牛的最少数目
样例输入
6 40 6 18 11 13 19 11
样例输出
3
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define INF 999999999
#define N 20001
using namespace std;
int a[N];
void qsort(int x, int y) {
int i = x, j = y, mid = a[(x + y) / 2];
while (i <= j) {
while (a[i] > mid)
i++;
while (a[j] < mid)
j--;
if (i <= j) {
swap(a[i], a[j]);
i++;
j--;
}
}
if (x < j)
qsort(x, j);
if (i < y)
qsort(i, y);
}
int main() {
int n, b;
int sum = 0;
int i;
cin >> n >> b;
for (i = 1; i <= n; i++)
cin >> a[i];
qsort(1, n);
for (i = 1; i <= n; i++) {
sum += a[i];
if (sum >= b)
break;
}
cout << i << endl;
;
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;
}课程表
现在你总共有n门课需要选,记为0到n-1。在选修某些课程之前需要一些先修课程。例如,想要学习课程0,你需要先完成课程1,我们用一个匹配来表示他们:[0, 1]。给定课程总量以及它们的先决条件,判断是否可能完成所有课程的学习?
时间限制:1000
内存限制:65536
输入
多组数据。每组数据第一行是n和m,n表示有n门课程,m表示有m组依赖关系,接下来的m行是依赖关系的具体信息a b,表示第a门课程依赖第b门课程。 0<=n <=1000,0 <= m <= 4000 两组数据之间可能有空行
输出
对每组数据,能完成输出 True,不能完成输出 False
样例输入
2 1 1 0 2 2 1 0 0 1
样例输出
True False
提示
示例2解释: 总共有2门课程。学习课程1之前,你需要先完成课程0;并且学习课程0之前,你还应先完成课程1。这是不可能的。
// 拓扑排序:Kahn算法+邻接表+栈
#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[1005][1005]; // 邻接点
int rd[1005], cd[1005]; // 入度 出度
int main() {
int r, c, num, i, j, k;
stack<int> st;
while (cin >> n >> m) {
memset(a, 0, sizeof(a));
memset(rd, 0, sizeof(rd));
memset(cd, 0, sizeof(cd));
while (!st.empty())
st.pop();
for (i = 1; i <= m; i++) {
cin >> r >> c;
rd[c]++;
cd[r]++;
a[r][cd[r]] = c;
}
for (i = 0; i <= n - 1; i++)
if (rd[i] == 0) {
st.push(i);
}
num = 0;
while (!st.empty()) {
i = st.top();
st.pop();
num++;
for (j = 1; j <= cd[i]; j++) {
k = a[i][j];
rd[k]--;
if (rd[k] == 0)
st.push(k);
}
}
if (num == n)
cout << "True" << endl;
else
cout << "False" << endl;
}
return 0;
}拯救公主
多灾多难的公主又被大魔王抓走啦!国王派遣了第一勇士阿福去拯救她。
身为超级厉害的术士,同时也是阿福的好伙伴,你决定祝他一臂之力。你为阿福提供了一张大魔王根据地的地图,上面标记了阿福和公主所在的位置,以及一些不能够踏入的禁区。你还贴心地为阿福制造了一些传送门,通过一个传送门可以瞬间转移到任意一个传送门,当然阿福也可以选择不通过传送门瞬移。传送门的位置也被标记在了地图上。此外,你还查探到公主所在的地方被设下了结界,需要集齐K种宝石才能打开。当然,你在地图上也标记出了不同宝石所在的位置。
你希望阿福能够带着公主早日凯旋。于是在阿福出发之前,你还需要为阿福计算出他最快救出公主的时间。
地图用一个R×C的字符矩阵来表示。字符S表示阿福所在的位置,字符E表示公主所在的位置,字符#表示不能踏入的禁区,字符$表示传送门,字符.表示该位置安全,数字字符0至4表示了宝石的类型。阿福每次可以从当前的位置走到他上下左右四个方向上的任意一个位置,但不能走出地图边界。阿福每走一步需要花费1个单位时间,从一个传送门到达另一个传送门不需要花费时间。当阿福走到宝石所在的位置时,就视为得到了该宝石,不需要花费额外时间。
时间限制:1000
内存限制:65536
输入
第一行是一个正整数T(1 <= T <= 10),表示一共有T组数据。 每一组数据的第一行包含了三个用空格分开的正整数R、C(2 <= R, C <= 200)和K,表示地图是一个R×C的矩阵,而阿福需要集齐K种宝石才能够打开拘禁公主的结界。 接下来的R行描述了地图的具体内容,每一行包含了C个字符。字符含义如题目描述中所述。保证有且仅有一个S和E。$的数量不超过10个。宝石的类型在数字0至4范围内,即不会超过5种宝石。
输出
对于每一组数据,输出阿福救出公主所花费的最少单位时间。若阿福无法救出公主,则输出“oop!”(只输出引号里面的内容,不输出引号)。每组数据的输出结果占一行。
样例输入
1 7 8 2 ........ ..S..#0. .##..1.. .0#..... ...1#... ...##E.. ...1....
样例输出
11
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define N 210
using namespace std;
int dir[2][4] = {{1, 0, 0, -1}, {0, 1, -1, 0}};
int dp[N][N][1 << 5 - 1], trans[20][2], n, m, k, tot, num, T, x, y, ans;
char map[N][N];
struct node {
int x, y, step, key;
node(int xx, int yy, int ss, int kk) : x(xx), y(yy), step(ss), key(kk){};
};
bool check(int key) {
int cnt = 0;
for (int i = 0; i <= 5; i++)
if ((key >> i) & 1)
cnt++; // 位运算 统计这条路上可获不同种类的宝石数量
if (cnt >= k)
return 1;
return 0;
}
int bfs(int x, int y) {
queue<node> que; // 根据结构体 定义队列que
dp[x][y][0] = 1;
node now(x, y, 0, 0); // 相当于 定义了now这个结构体变量
que.push(now); // 进队
while (!que.empty()) // 当队列不为空时 .empty()-->若队列为空返回1;
{
now = que.front(); // 把队头的值赋给now这个结构体上
que.pop(); // 弹出队首
for (int i = 0; i < 4; i++) // 上下左右四个执行方案
{
int xx = now.x + dir[0][i]; // 具体变动
int yy = now.y + dir[1][i];
int step = now.step; // 步数
int key = now.key; //
if (xx < 0 || xx >= n || yy < 0 || yy >= m)
continue; // 判断边界
if (dp[xx][yy][key])
continue; // 若在队中 不走
if (map[xx][yy] == '#')
continue; // 禁区 不走
if (map[xx][yy] == 'E' && check(key)) // 既到达营救点 且 宝石够数
{
return step + 1; // 返回步数 //结束遍历
}
if (isdigit(map[xx][yy])) //
{
dp[xx][yy][key] = 1; // 标记 相当于vis
key = key | (1 << (map[xx][yy] - '0')); // 记录宝石
que.push(node(xx, yy, step + 1, key)); // 进队
}
if (map[xx][yy] == '.') // 普通地带
{
dp[xx][yy][key] = 1; // 标记
que.push(node(xx, yy, step + 1, key));
}
if (map[xx][yy] == '$') // 传送门
{
dp[xx][yy][key] = 1; // 标记
que.push(node(xx, yy, step + 1, key)); // 进队
for (int j = 1; j <= tot; j++) // 遍历 方案
{
xx = trans[j][0], yy = trans[j][1];
if (!dp[xx][yy][key]) {
dp[xx][yy][key] = 1; // 标记
que.push(node(xx, yy, step + 1, key)); // 进队
}
}
}
}
}
return -1; // 若遍历完还没返回 就说明没有可行方案
}
main() {
cin >> T; // 组数
while (T--) {
memset(dp, 0, sizeof(dp));
tot = 0;
num = 0; // 初始化
scanf("%d%d%d", &n, &m, &k);
// cin>>n>>m>>k;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
cin >> map[i][j];
// scanf("%c",&map[i][j]);还是没搞明白为什么不能用scanf和getchar
// map[i][j]=getchar();
if (map[i][j] == 'S')
x = i, y = j, map[i][j] = '.'; // 标记起点
if (map[i][j] == '$')
trans[++tot][0] = i, trans[tot][1] = j; // 记录传送门
if (isdigit(map[i][j]))
num++; // 判断是否是宝石(数字)
}
if (k > num) {
printf("oop!\n");
continue;
} // 没有足够的宝石
ans = bfs(x, y);
if (ans == -1)
printf("oop!\n");
else
printf("%d\n", ans);
}
}移动路线
桌子上有一个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]);
}最长公共子上升序列
给定两个整数序列,写一个程序求它们的最长上升公共子序列。 当以下条件满足的时候,我们将长度为N的序列S1 , S2 , . . . , SN 称为长度为M的序列A1 , A2 , . . . , AM 的上升子序列: 存在 1 <= i1 < i2 < . . . < iN <= M ,使得对所有 1 <= j <=N,均有Sj = Aij,且对于所有的1 <= j < N,均有Sj < Sj+1。
时间限制:10000
内存限制:65536
输入
每个序列用两行表示,第一行是长度M(1 <= M <= 500),第二行是该序列的M个整数Ai (-231 <= Ai < 231 )
输出
在第一行,输出两个序列的最长上升公共子序列的长度L。在第二行,输出该子序列。如果有不止一个符合条件的子序列,则输出任何一个即可。
样例输入
5 1 4 2 5 -12 4 -12 1 2 4
样例输出
2 1 4
#include <bits/stdc++.h>
using namespace std;
#define N 505
int dp
[N]
[N]; // dp[i][j]:x前i个元素与y前j个元素构成的以x[i]为结尾的最长公共上升子序列的长度
int x[N], y[N];
vector<int> seq
[N]; // seq[i]:当j为某确定值时,x前i个元素与y前j个元素构成的以x[i]为结尾的最长公共上升子序列
int main() {
int xn, yn;
cin >> xn;
for (int i = 1; i <= xn; ++i)
cin >> x[i];
cin >> yn;
for (int i = 1; i <= yn; ++i)
cin >> y[i];
for (int j = 1; j <= yn; ++j)
for (int i = 1; i <= xn; ++i) {
if (x[i] == y[j]) {
dp[i][j] = 1;
seq[i] = vector<int>();
for (int k = 1; k < i; ++k) {
if (x[k] < x[i] && dp[k][j - 1] + 1 > dp[i][j]) {
dp[i][j] = dp[k][j - 1] + 1;
seq[i] = seq[k];
}
}
seq[i].push_back(x[i]);
} else
dp[i][j] = dp[i][j - 1];
}
int mxi = 1;
for (int i = 1; i <= xn; i++) {
if (dp[i][yn] > dp[mxi][yn])
mxi = i;
}
cout << dp[mxi][yn] << endl;
for (int i = 0; i < seq[mxi].size(); ++i)
cout << seq[mxi][i] << ' ';
return 0;
}技能树
设二叉树中每个节点的子节点数为0或2,求有N个节点高度为M的不同的二叉树有多少个
(输出 mod 9901 后的结果)。
时间限制:10000
内存限制:131072
输入
两个空格分开的整数, N和K。
输出
第 1 行: 一个整数,表示可能的技能树的个数除以9901的余数。
样例输入
5 3
样例输出
2
提示
有5个节点,高为3的两个不同的技能树。约定:n在[3,300]间,m在(1,100)间
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
#define N 310
#define M 110
#define mod 9901
int f[M][N], sum[N][M];
int main() {
int n, m;
scanf("%d%d", &n, &m);
f[1][1] = sum[1][1] = 1;
for (int j = 2; j <= n; j++)
f[1][j] = sum[1][j] = 0;
for (int i = 2; i <= m; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = 0;
for (int k = 1; k < j; k++)
f[i][j] = (f[i][j] + (2 * f[i - 1][k] * sum[i - 1][j - k - 1] -
f[i - 1][k] * f[i - 1][j - k - 1]) %
mod) %
mod;
sum[i][j] = (sum[i - 1][j] + f[i][j]) % mod;
}
}
printf("%d\n", f[m][n]);
return 0;
}温度统计
现有一段时间的温度数据,请统计指定温度出现的次数。
时间限制:1000
内存限制:65536
输入
第一行一个整数n,表示温度数据的个数。(0 < n ≤ 200) 第二行n个整数,以空格分隔,每个整数表示一个温度,温度的范围大于等于0,小于等于40。 第三行一个整数,表示需要查询的温度t。(0 ≤ t ≤ 40)
输出
输出一个整数,表示温度t出现的次数。
样例输入
10 18 19 21 17 20 18 21 21 22 21 21
样例输出
4
#include <bits/stdc++.h>
using namespace std;
int a[202];
int main() {
int n, t, ans;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
cin >> t;
ans = 0;
for (int i = 1; i <= n; i++)
if (a[i] == t)
ans++;
cout << ans << endl;
return 0;
}