Scratch编程一级 题库
田忌赛马
你一定听过田忌赛马的故事吧?
如果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;
}迷信的病人
医院为了方便对患者进行建档和管理,引入了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;
}最小的数
依次输入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;
}开关灯
假设有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;
}字符串插入
有两个字符串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");
}书架
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;
}课程表
现在你总共有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);
}
}最长公共子上升序列
给定两个整数序列,写一个程序求它们的最长上升公共子序列。 当以下条件满足的时候,我们将长度为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;
}双精度浮点数的输入输出
输入一个双精度浮点数,保留8位小数,输出这个浮点数。
时间限制:1000
内存限制:65536
输入
只有一行,一个双精度浮点数。
输出
一行,保留8位小数的浮点数。
样例输入
3.1415926535798932
样例输出
3.14159265
#include <cstdio>
using namespace std;
int main() {
double a;
scanf("%lf", &a);
printf("%.8lf", a);
return 0;
}足球联赛积分
在足球联赛里,一个球队赢下一场比赛得到3个积分,打平一场比赛得到1个积分,输掉比赛得到0分。
现已知一个球队在整个联赛里的比赛情况,求该球队最终的积分。
时间限制:1000
内存限制:65536
输入
三个整数x,y,z,以空格分开,分别表示这个球队赢下的比赛场数,打平的比赛场数,输掉的比赛场数。(0 ≤ x,y,z ≤ 40)
输出
一个整数,表示该球队最终的积分。
样例输入
19 6 4
样例输出
63
提示
63=19*3+6*1+4*0
#include <iostream>
using namespace std;
int main() {
int x, y, z, a = 0;
cin >> x >> y >> z;
a = x * 3 + y;
cout << a;
return 0;
}