Scratch编程一级 题库
小球放盒子
有N个相同的球,M个不同的盒子,每个盒子最多放K个球
请计算将这N个球全部放入盒子中的方案数模1000007后的结果
时间限制:10000
内存限制:131072
输入
三个正整数,依次为N,M,K
输出
输出方案数模1000007后的结果
样例输入
4 2 3
样例输出
3
提示
总共有3种方案,依次为 { 3 , 1 },{ 2 , 2 },{ 1 , 3 }。 对于100%的数据, N,M ≤ 5000
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#include <vector>
#define DEBUG(x) cout << #x << " = " << x << endl
typedef long long ll;
using namespace std;
const int MAXN = 5e3 + 10;
const int MOD = 1000007;
int N, M, K;
ll ways[MAXN][MAXN];
/// 前m个盒子放入n个球的放法
int main() {
// freopen("in.txt","r",stdin);
scanf("%d %d %d", &N, &M, &K);
ways[0][0] = 1;
for (int i = 1; i <= M; i++) {
ways[i][0] = 1;
ways[0][i] = 0;
}
for (int m = 1; m <= M; m++) {
int sum = m;
for (int n = 1; n <= N; n++) {
// int l=min(n,K);
// int r=0;
// for(int i=0;i<=l;i++){
// r=(r+ways[m-1][n-i])%MOD;
// }
ways[m][n] = sum;
sum = (sum + ways[m - 1][n + 1]) % MOD;
if (n - K >= 0)
sum = (sum - ways[m - 1][n - K] + MOD) % MOD;
}
}
printf("%lld\n", ways[M][N]);
return 0;
}数对
给定2到15个不同的正整数,你的任务是计算这些数里面有多少个数对满足:数对中一个数是另一个数的两倍。 比如给定1 4 3 2 9 7 18 22,得到的答案是3,因为2是1的两倍,4是2个两倍,18是9的两倍。
时间限制:1000
内存限制:65536
输入
一行,给出2到15个两两不同且小于100的正整数。最后用0表示输入结束。
输出
一个整数,即有多少个数对满足其中一个数是另一个数的两倍。
样例输入
1 4 3 2 9 7 18 22 0
样例输出
3
#include <iostream>
using namespace std;
int main() {
int c = 0, x = 0;
int a[15];
for (int i = 0; i < 15; i++) {
cin >> a[i];
if (a[i] == 0)
break;
c++;
}
for (int i = 0; i < c; i++) {
for (int j = 0; j < c; j++) {
if ((a[i] / a[j] == 2) && (a[i] % a[j] == 0) && a[j] != 0) {
x++;
}
}
}
cout << x;
}内部元素之和
输入一个整数矩阵,计算位于矩阵内部的元素之和。所谓矩阵内部的元素,不在第一行和最后一行的元素以及第一列和最后一列的元素。
时间限制:1000
内存限制:65536
输入
第一行分别为矩阵的行数m和列数n(m < 100,n < 100),两者之间以一个空格分开。 接下来输入的m行数据中,每行包含n个整数(每个数大于等于0,小于1000),整数之间以一个空格分开。
输出
输出对应矩阵的内部元素和
样例输入
3 3 3 4 1 3 7 1 2 0 1
样例输出
7
//参考代码2
#include <cstdio>
int a[110][110];
int main() {
int m, n;
int sum = 0;
scanf("%d%d", &m, &n);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
scanf("%d", &a[i][j]);
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i != 0 && j != 0 && i != m - 1 && j != n - 1) {
sum += a[i][j];
}
}
}
printf("%d", sum);
return 0;
}//参考代码2
#include <iostream>
using namespace std;
int main()
{
int m,n,a;
cin>>m>>n;
int ans=0;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++){
cin>>a;
if(i!=1&&i!=m&&j!=1&&j!=n)
ans+=a;
}
cout<<ans;
return 0;
}计算好数
若将一个正整数化为二进制数,在此二进制数中,我们将数字1的个数多于数字0的个数的这类二进制数称为好数。
例如:
(13)10 = (1101)2,其中1的个数为3,0的个数为1,则此数是好数;
(10)10 = (1010)2,其中1的个数为2,0的个数也为2,则此数不是好数;
(24)10 = (11000)2,其中1的个数为2,0的个数为3,则此数不是好数;
对于给定的N,写程序求出1~N之中(包括1与N)中的好数个数。
时间限制:1000
内存限制:65536
输入
一个整数,题目中的N(N ≤ 1000)
输出
一个整数,表示1~N之中(包括1与N)中的好数个数
样例输入
10
样例输出
5
//参考代码1
#include <cstdio>
int main() {
int j;
scanf("%d", &j);
int t;
int s = 0, c = 0, w = 0;
for (int n = 1; n <= j; n++) {
for (int i = n; i; i /= 2) {
t = i % 2;
if (t == 1) {
s++;
} else {
c++;
}
}
if (s > c) {
w++;
}
s = 0;
c = 0;
}
printf("%d", w);
return 0;
}//参考代码2
#include <algorithm>
#include <iostream>
using namespace std;
int a[12], b[12];
int main() {
int n;
cin >> n;
int ans = 0;
for (int i = 1; i <= n; i++) {
int t = i, a = 0, b = 0;
while (t) {
if (t & 1)
a++;
else
b++;
t >>= 1;
}
if (a > b)
ans++;
}
cout << ans;
return 0;
}(a/b)*c的值
给定整数a、b、c,计算(a / b)*c的值,这里的除法为实数除法。
时间限制:1000
内存限制:65536
输入
一行,三个整数a、b、c,整数间以空格分隔。(1 ≤ a,b,c ≤ 1000)
输出
将计算结果保留6位小数输出。
样例输入
1 3 3
样例输出
1.000000
#include <bits/stdc++.h>
using namespace std;
int main() {
int x, y, z;
cin >> x >> y >> z;
printf("%lf", (x * 1.0 / y) * z);
return 0;
}苹果消消乐
有100个苹果和香蕉排成一条直线,其中有N个香蕉,你可以使用至多M次魔法道具将香蕉变成苹果,最后“最长的连续苹果数量”即为你本次苹果消消乐的得分,给定苹果和香蕉的排列,求你能获得的最大得分。
时间限制:1000
内存限制:65536
输入
第一行是一个整数T(1 <= T <= 10),代表测试数据的组数。 每个测试数据第一行是2个整数N和M(0 <= N, M <= 100)。第二行包含N个整数a1, a2, ... aN(1 <= a1 < a2 < ... < aN <= 100),表示第a1, a2, ... aN个位置上摆放的是香蕉。
输出
对于每组数据,输出通过使用魔法道具后你能获得的最大得分。
样例输入
3 5 1 34 77 82 83 84 5 2 10 30 55 56 90 5 10 10 30 55 56 90
样例输出
76 59 100
提示
这是个枚举题
#include <bits/stdc++.h>
using namespace std;
// 计算最大长度
void fun(int n, int m, int a[]) {
int ma = 0;
if (m >= n)
ma = 100; // 如果道具次数大于香蕉的个数,能把香蕉全变成苹果,不用算,直接得100
else {
int s;
for (int i = m + 1; i <= n + 1; i++) { // 3 2 10 50 90
s = a[i] - 1 - a[i - m - 1];
if (s > ma)
ma = s;
}
}
cout << ma << endl;
}
int main() {
int t, n, m, i, j; // n个香蕉,m个道具,t组数据
cin >> t;
for (i = 1; i <= t; i++) {
cin >> n >> m;
int a[102] = {0};
for (j = 1; j <= n; j++)
cin >> a[j]; // 香蕉的位置
a[0] = 0; // 在最前面和最后面添加一个香蕉
a[n + 1] = 101;
fun(n, m, a);
}
return 0;
}//解法2 模拟+尺取
#include <iostream>
#include <cstring>
using namespace std;
int a[102];
int main(){
int t,n,m,maxn;
cin>>t;
while(t--){
memset(a,0,sizeof(a)); maxn=0;
cin>>n>>m;
if(m>=n) {cout<<100<<endl;continue;}
for(int i=1;i<=n;i++) cin>>a[i];
a[n+1]=101;
for(int i=1;i+m-1<=n;i++)
maxn=max(maxn,a[i+m]-a[i-1]-1);
cout<<maxn<<endl;
}
return 0;
}石头剪刀布
石头剪刀布是常见的猜拳游戏。石头胜剪刀,剪刀胜布,布胜石头。如果两个人出拳一样,则不分胜负。
一天,小A和小B正好在玩石头剪刀布。已知他们的出拳都是有周期性规律的,比如:“石头-布-石头-剪刀-石头-布-石头-剪刀……”,就是以“石头-布-石头-剪刀”为周期不断循环的。请问,小A和小B比了N轮之后,谁赢的轮数多?
时间限制:1000
内存限制:65536
输入
输入包含三行。 第一行包含三个整数:N,NA,NB,分别表示比了N轮,小A出拳的周期长度,小B出拳的周期长度。0 < N,NA,NB < 100。 第二行包含NA个整数,表示小A出拳的规律。 第三行包含NB个整数,表示小B出拳的规律。 其中,0表示“石头”,2表示“剪刀”,5表示“布”。相邻两个整数之间用单个空格隔开。
输出
输出一行,如果小A赢的轮数多,输出A;如果小B赢的轮数多,输出B;如果两人打平,输出draw。
样例输入
10 3 4 0 2 5 0 5 0 2
样例输出
A
提示
对于测试数据,猜拳过程为: A:0 2 5 0 2 5 0 2 5 0 B:0 5 0 2 0 5 0 2 0 5 A赢了4轮,B赢了2轮,双方打平4轮,所以A赢的轮数多。
#include <stdio.h>
int N, NA, NB, i, A[200], B[200], Y = 0;
int judge(int A, int B) {
int x;
switch (A) {
case 0:
x = (B == 2 ? 1 : -1);
if (B == 0)
x = 0;
break;
case 2:
x = (B == 5 ? 1 : -1);
if (B == 2)
x = 0;
break;
case 5:
x = (B == 2 ? -1 : 1);
if (B == 5)
x = 0;
break;
}
return x;
}
void copy(int N, int A[]) {
for (i = N; i < 200; i++) {
A[i] = A[i - N];
}
}
int main() {
scanf("%d %d %d", &N, &NA, &NB);
for (i = 0; i < NA; i++) {
scanf("%d", &A[i]);
}
copy(NA, A);
for (i = 0; i < NB; i++) {
scanf("%d", &B[i]);
}
copy(NB, B);
for (i = 0; i < N; i++) {
Y += judge(A[i], B[i]);
}
if (Y > 0) {
printf("A");
} else if (Y < 0) {
printf("B");
} else
printf("draw");
return 0;
}计算鞍点
给定一个5*5的矩阵,每行只有一个最大值,每列只有一个最小值,寻找这个矩阵的鞍点。 鞍点指的是矩阵中的一个元素,它是所在行的最大值,并且是所在列的最小值。 例如:在下面的例子中(第4行第1列的元素就是鞍点,值为8 )。
11 3 5 6 9
12 4 7 8 10
10 5 6 9 11
8 6 4 7 2
15 10 11 20 25
时间限制:1000
内存限制:65536
输入
输入包含一个5行5列的矩阵
输出
如果存在鞍点,输出鞍点所在的行、列及其值,如果不存在,输出"not found"
样例输入
11 3 5 6 9 12 4 7 8 10 10 5 6 9 11 8 6 4 7 2 15 10 11 20 25
样例输出
4 1 8
#include <bits/stdc++.h>
using namespace std;
int a[6][6];
int main() {
int i, j, x, z, y, flag1;
bool q;
for (i = 1; i <= 5; i++)
for (j = 1; j <= 5; j++)
cin >> a[i][j];
for (i = 1; i <= 5; i++) {
x = 0;
flag1 = true;
for (j = 1; j <= 5; j++)
if (a[i][j] > x) {
x = a[i][j];
z = i;
y = j;
}
for (j = 1; j <= 5; j++) {
if (a[j][y] < x)
flag1 = false;
}
if (flag1 == true)
{
cout << z << " " << y << " " << x;
return 0;
}
}
cout << "not found";
return 0;
}子串计算
给出一个只包含0和1的字符串(长度在1到100之间),求其每一个子串出现的次数。
时间限制:1000
内存限制:65536
输入
一行,一个01字符串。
输出
对所有出现次数在1次以上的子串,输出该子串及出现次数,中间用单个空格隔开。按子串的字典序从小到大依次输出,每行一个。
样例输入
10101
样例输出
0 2 01 2 1 3 10 2 101 2
#include <cstring>
#include <iostream>
using namespace std;
char a[105], s[101];
void dfs(int n) {
int h = 0;
for (int i = 0; i <= strlen(a) - n; i++) {
int f = 1;
for (int j = 0; j < n; j++) {
if (a[i + j] != s[j]) {
f = 0;
break;
}
}
h += f;
}
if (h <= 1)
return;
for (int i = 0; i < n; i++) {
cout << s[i];
}
cout << ' ' << h << endl;
s[n] = '0';
dfs(n + 1);
s[n] = '1';
dfs(n + 1);
}
int main() {
cin >> a;
s[0] = '0';
dfs(1);
s[0] = '1';
dfs(1);
}疫情集中隔离
A同学12月初从国外回来,按照防疫要求,需要进行14天集中隔离,请你实现一个程序,根据回国的时间计算集中隔离结束的日期。
比如,12月1号回来,1号当天开始隔离,14号是隔离的最后一天,因此14号是集中隔离结束的日期。
时间限制:1000
内存限制:65536
输入
一个整数x,表示A同学12月x号回国。(1 ≤ x ≤ 15)
输出
一个整数y,表示A同学结束集中隔离的日期(即12月y号A结束集中隔离)。
样例输入
1
样例输出
14
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
int a, b = 1, c = 1;
cin >> a;
if (a <= 18) {
b = a + 13;
} else {
b = a - 18;
}
cout << b;
return 0;
}数字构造
火山宝打算造一个 n 位的十进制数字出来。
对于 1 到 n 中的每一个 i,火山宝可以从 xi,1, ..., xi,ki 这 ki 个 0-9 的数字中选择一个作为 ai。
在选择结束后,a1a2...an 形成了一个 n 位的十进制数——这就是火山宝造出来的数。
你需要帮火山宝计算他能造出的数中,有多少个是 3 的倍数。
时间限制:1000
内存限制:65536
输入
第一行输入一个整数 n(1 ≤ n ≤ 18),表示数字的位数。 接下来 n 行,每行第一个整数 ki (1 ≤ ki ≤ 10),表示第 i 中候选的数字数量。接着是 ki 个两两不同的 0-9 范围内的数字 xi,1, ..., xi,ki。 输入保证 0 不是第一位的可选项。
输出
你需要输出一行一个整数,表示火山宝能造出的数字中,3 的倍数的数量。
样例输入
样例输入1:
2 5 5 6 7 8 9 5 0 1 2 3 4
样例输入2:
5 9 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9
样例输出
样例输出1:
9
样例输出2:
30000
提示
样例1能造出来的 3 的倍数有 51, 54,60,63,72,81,84,90, 93。
#include <cstring>
#include <iostream>
using namespace std;
int num[20][10];
int k[20];
int mod[20][3] = {};
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> k[i];
for (int j = 0; j < k[i]; j++) {
cin >> num[i][j];
mod[i][num[i][j] % 3]++;
}
}
long result[3] = {};
for (int i = 0; i < 3; i++)
result[i] = mod[0][i];
for (int i = 1; i < n; i++) {
long temp0 = result[0], temp1 = result[1], temp2 = result[2];
result[0] = temp0 * mod[i][0] + temp1 * mod[i][2] + temp2 * mod[i][1];
result[1] = temp0 * mod[i][1] + temp1 * mod[i][0] + temp2 * mod[i][2];
result[2] = temp0 * mod[i][2] + temp1 * mod[i][1] + temp2 * mod[i][0];
}
cout << result[0] << endl;
return 0;
}生成括号
Paul是一名数学专业的同学,在课余选修了C++编程课,现在他能够自己写程序判断判断一个给定的由'('和')'组成的字符串是否是正确匹配的。可是他不满足于此,想反其道而行之,设计一个程序,能够生成所有合法的括号组合,请你帮助他解决这个问题。
时间限制:1000
内存限制:65536
输入
输入只有一行N,代表生成括号的对数(1 ≤ N ≤ 10)。
输出
输出所有可能的并且有效的括号组合,按照字典序进行排列,每个组合占一行。
样例输入
3
样例输出
((())) (()()) (())() ()(()) ()()()
#include <bitset>
#include <ctime>
#include <iostream>
using namespace std;
int N;
bool judge(bitset<20> temp) {
int numL = 0, numR = 0; // numL 表0 左括号数 numR表1 右括号数
for (int i = 2 * N - 1; i >= 0; i--) {
if (temp[i])
numR++;
else
numL++;
if (numL - numR < 0)
return false; // 在任何一个位置所得的前缀中0的个数不少于1的个数。
}
if (numL != numR)
return false; // 有相同个数的0和1,都是N个
return true;
}
int main() {
cin >> N;
int max = 1 << (2 * N - 1); // 2的2*N-1次方
// cout<<max<<endl;
for (int i = 1; i <= max; i++) {
bitset<20> temp;
// 开始枚举每种可能
for (int j = 0; j < 2 * N; j++) {
temp[j] = (i >> j) & 1; // 这里是反着取的 如000111,先取个位的1
}
// 对每种可能进行判断
if (judge(temp)) {
for (int j = 2 * N - 1; j >= 0; j--) {
if (temp[j])
cout << ")"; // 所以这要反过来输出
else
cout << "(";
}
cout << endl;
}
}
return 0;
}计算乘积
给定两个数a,b,计算它们的乘积
输入
一行两个整数a,b,以空格隔开。0<a,b<10的8次方
输出
一个整数,表示a,b的乘积。
样例输入
123456 123456
样例输出
15241383936
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
char x[50010], y[50010];
int a[50010], b[50010], c[50010];
int main() {
cin >> x >> y;
a[0] = strlen(x);
b[0] = strlen(y);
for (int i = 1; i <= a[0]; ++i)
a[i] = x[a[0] - i] - '0';
for (int i = 1; i <= b[0]; ++i)
b[i] = y[b[0] - i] - '0';
for (int i = 1; i <= a[0]; ++i)
for (int j = 1; j <= b[0]; ++j)
c[i + j - 1] += a[i] * b[j];
int len = a[0] + b[0];
for (int i = 1; i <= len - 1; ++i)
if (c[i] > 9) {
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
while (c[len] == 0 && len > 1)
len--;
for (int i = len; i >= 1; --i)
printf("%d", c[i]);
return 0;
}表达式求值
求一个可能包含加、减、乘、除、乘方运算的中缀表达式的值。
在计算机中,我们常用栈来解决这一问题。首先将中缀表达式转换到后缀表达式,然后对后缀表达式求值。
加、减、乘、除、乘方分别用+,-,*, /, ^来表示。表达式可以有圆括号()。
时间限制:1000
内存限制:65536
输入
第一行为测试数据的组数N。 接下来的N行,每行是一个中缀表达式。 每个表达式中,圆括号、运算符和运算数相互之间都用空格分隔,运算数是整数。一般运算数可正可负(负数的符号和数字之间无空格),指数一定为自然数(0和正整数)。不必考虑除0的情况。每个运算数均可由int放下。不必考虑溢出。中缀表达式的字符串长度不超过600。乘方的优先级比乘除都高,结合性是向左结合,如2 ^ 3 ^ 4表示( 2 ^ 3 ) ^ 4 = 4096。除法的商向下取整。
输出
对每一组测试数据输出一行,为表达式的值
样例输入
2 31 * ( 5 - ( -3 + 25 ) ) + 70 ^ 2 2 * 5 + 6 * ( 7 - 8 ) + 6
样例输出
4373 10
#include <bits/stdc++.h>
using namespace std;
int get_fast(string op) // 运算符的优先级
{
int ans = -1;
switch (op[0]) {
case '+':
case '-':
ans = 1;
break;
case '*':
case '/':
ans = 2;
break;
case '^':
ans = 3;
break;
}
return ans;
}
vector<string> scaner(string s) // 字符串拆解放入vector
{
vector<string> ans;
string ops = "+-*/^()";
string t = "";
for (int i = 0; i < s.size(); i++) {
if (s[i] == '-' && (i + 1 < s.size()) && s[i + 1] >= '0' && s[i + 1] <= '9')
t = "-";
else if (s[i] >= '0' && s[i] <= '9')
t += s[i];
else if (ops.find(s[i]) != string::npos)
t += s[i];
else if (s[i] == ' ') {
if (t.size() > 0)
ans.push_back(t);
t = "";
}
}
if (t.size())
ans.push_back(t);
return ans;
}
vector<string> infix_Suffix(vector<string> exp) // 中缀表达式转后缀表达式
{
vector<string> ans;
stack<string> st;
string op = "+-*/^()";
for (int i = 0; i < exp.size(); i++) {
if (exp[i] == "(")
st.push(exp[i]);
else if (exp[i] == ")") {
while (st.top() != "(") {
ans.push_back(st.top());
st.pop();
}
st.pop();
} else if (op.find(exp[i]) != string::npos) {
while (st.size() && get_fast(exp[i]) <= get_fast(st.top())) {
ans.push_back(st.top());
st.pop();
}
st.push(exp[i]);
} else
ans.push_back(exp[i]);
}
while (st.size()) {
ans.push_back(st.top());
st.pop();
}
return ans;
}
int suffix_calc(vector<string> exp) // 后缀表达式计算结果
{
stack<int> num;
string ops = "+-*/^";
for (int i = 0; i < exp.size(); i++) {
if (ops.find(exp[i]) != string::npos) {
int a = num.top();
num.pop();
int b = num.top();
num.pop();
if (exp[i] == "+")
num.push(b + a);
else if (exp[i] == "-")
num.push(b - a);
else if (exp[i] == "*")
num.push(b * a);
else if (exp[i] == "/")
num.push(b / a);
else if (exp[i] == "^")
num.push(pow(b * 1.0, a));
} else
num.push(atoi(exp[i].c_str()));
}
cout << num.top() << endl;
return num.top();
}
int main() {
string s;
getline(cin, s);
int n;
n = atoi(s.c_str());
while (n--) {
getline(cin, s);
vector<string> vs = scaner(s);
vs = infix_Suffix(vs);
suffix_calc(vs);
}
return 0;
}城堡问题
1 2 3 4 5 6 7
#############################
1 # | # | # | | #
#####---#####---#---#####---#
2 # # | # # # # #
#---#####---#####---#####---#
3 # | | # # # # #
#---#########---#####---#---#
4 # # | | | | # #
#############################
(图 1)
# = Wall
| = No wall
- = No wall
图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 <bits/stdc++.h>
using namespace std;
int maze[60][60], M, N;
int book[60][60];
int roomnum = 0, maxroom = 0, room;
void dfs(int x, int y) {
if (book[x][y])
return;
room++;
book[x][y] = 1;
if ((maze[x][y] & 1) == 0)
dfs(x, y - 1);
if ((maze[x][y] & 2) == 0)
dfs(x - 1, y);
if ((maze[x][y] & 4) == 0)
dfs(x, y + 1);
if ((maze[x][y] & 8) == 0)
dfs(x + 1, y);
}
int main() {
cin >> M >> N;
memset(book, 0, sizeof(book));
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
cin >> maze[i][j];
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++) {
if (!book[i][j]) {
room = 0;
roomnum++;
dfs(i, j);
maxroom = maxroom > room ? maxroom : room;
}
}
cout << roomnum << endl << maxroom << endl;
return 0;
}出栈序列统计
栈是常用的一种数据结构,有n个元素在栈顶端一侧等待进栈,栈顶端另一侧是出栈序列。你已经知道栈的操作有两种:push和pop,前者是将一个元素进栈,后者是将栈顶元素弹出。现在要使用这两种操作,由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n,计算并输出由操作数序列1,2,…,n,经过一系列操作可能得到的输出序列总数。
时间限制:1000
内存限制:65536
输入
就一个数n(1≤n≤15)。
输出
一个数,即可能输出序列的总数目。
样例输入
3
样例输出
5
提示
先了解栈的两种基本操作,进栈push就是将元素放入栈顶,栈顶指针上移一位,等待进栈队列也上移一位,出栈pop是将栈顶元素弹出,同时栈顶指针下移一位。 用一个过程采模拟进出栈的过程,可以通过循环加递归来实现回溯:重复这样的过程,如果可以进栈则进一个元素,如果可以出栈则出一个元素。就这样一个一个地试探下去,当出栈元素个数达到n时就计数一次(这也是递归调用结束的条件)。
#include <cstdio>
#include <iostream>
using namespace std;
int n, ans;
void dfs(int in, int out) {
if (out == 0)
ans++;
else if (in == 0) {
dfs(in + 1, out - 1); // 进栈
} else {
dfs(in + 1, out - 1); // 进栈
dfs(in - 1, out); // 出栈
}
}
int main() {
while (scanf("%d", &n) != EOF) {
ans = 0;
dfs(0, n);
printf("%d\n", ans);
}
return 0;
}多余的数
小A同学在完成一个数学题:求给定的10个整数的和。小A同学在求完之后发现和参考答案对不上,检查后发现在求和过程中多计算了一个数,其他过程没有问题。现给出小A计算用的11个数,以及正确的参考答案,请算出小A同学多计算的那一个数。
时间限制:1000
内存限制:65536
输入
第一行11个正整数,每个数小于等于1000000 第二行一个整数,表示参考答案
输出
一个整数,表示多计算的那一个数。
样例输入
2 4 6 8 1 3 5 7 9 5 11 54
样例输出
7
提示
样例中原有的10个数为2 4 6 8 1 3 5 9 5 11,和为54,多余的数为7。
#include <iostream>
using namespace std;
int main() {
int sum = 0, a, t;
for (int i = 1; i <= 11; i++) {
cin >> a;
sum = sum + a; // 11个数总和
}
cin >> t;
cout << sum - t; // 11个数总和-10个数总和=多加的数
return 0;
}最好的草
奶牛Bessie计划好好享受柔软的春季新草。新草分布在R行C列的牧场里。它想计算一下牧场中的草丛数量。
在牧场地图中,每个草丛要么是单个“#”,要么是有公共边的相邻两个“#”。给定牧场地图,计算有多少个草丛。
例如,考虑如下5行6列的牧场地图
. # . . . .
. . # . . .
. . # . . #
. . . # # .
. # . . . .
这个牧场有5个草丛:一个在第一行,一个在第二列横跨了二、三行,一个在第三行,一个在第四行横跨了四、五列,最后一个在第五行。
时间限制:10000
内存限制:65536
输入
第一行包含两个整数R和C,中间用单个空格隔开。 接下来R行,每行C个字符,描述牧场地图。字符只有“#”或“.”两种。(1 <= R, C <= 100 )
输出
输出一个整数,表示草丛数。
样例输入
5 6 .#.... ..#... ..#..# ...##. .#....
样例输出
5
#include <iostream>
using namespace std;
int R, C, cnt = 0;
string grass[100];
void dfs(int x, int y) {
int step[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 记录当前位置的四个方向
for (int i = 0; i < 4; ++i) {
int xx = x + step[i][0], yy = y + step[i][1];
if (xx < 0 || xx >= R || yy < 0 || yy >= C) // 判断边界
continue;
if (grass[xx][yy] == '#') {
grass[xx][yy] = '.'; // 标记
dfs(xx, yy);
}
}
}
int main() {
cin >> R >> C;
for (int i = 0; i < R; ++i)
cin >> grass[i];
for (int i = 0; i < R; ++i)
for (int j = 0; j < C; ++j)
if (grass[i][j] == '#') {
cnt++;
dfs(i, j);
}
cout << cnt;
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;
}计算成绩优秀的人数
现有一个班一门课程考试的分数,请统计其中成绩为优秀的人数。成绩为优秀的要求是分数大于等于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;
}