Scratch编程一级 题库
分形盒
分形,通常被定义为一个粗糙或零碎的几何形状,可以分成数个部分,且每一部分都(至少近似地)是整体缩小后的形状,即具有自相似的性质。它跟分数维、自组织、非线性系统和混沌等具有非常重要的联系。
分形盒就是这样一种分形,它的定义如下:
维度是1的分形盒:
X
维度是2的分形盒:
X X
X
X X
如果已知维度是(n-1)的分形盒,那么维度是n的分形盒的递归定义如下所示:
Box(n-1) Box(n-1)
Box(n-1)
Box(n-1) Box(n-1)
你的任务是画一个维度为n的分形盒。
时间限制:1000
内存限制:65536
输入
输入包含多组测试数据。每一行包含一个正整数n表示分形盒的维度,n不大于7;最后一行是一个-1,表示输入结束。
输出
对于每组测试数据,输出要求维度的分形盒,注意X为大写字母。每组测试数据之后包含一行,改行只包含一个破折号。
样例输入
1 2 3 4 -1
样例输出
X - X X X X X - X X X X X X X X X X X X X X X X X X X X X X X X X - X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X -
using namespace std;
const int maxn=3010;
int n;
int ch[maxn][maxn];
void init()//标记所有显示符号位
{
ch[1][1]=1;
for(int k=2;k<=8;k++){//维度
int p=pow(3,k-2);//偏移量
for(int i=1;i<=p;i++){//行
for(int j=1;j<=p;j++){//列
ch[i+2*p][j]=ch[i][j+2*p]=ch[i+p][j+p]=ch[i+2*p][j+2*p]=ch[i][j];
//把n-1级图形作为n级图形的左上角,这个图形的每个坐标分别加上四个偏移量得到其余四个分量
}
}
}
}
void output()
{
int N=pow(3,n-1);
for(int i=1;i<=N;i++){
for(int j=1;j<=N;j++){
if(ch[i][j]) cout<<"X";
else cout<<" ";
}
cout<<endl;
}
cout<<"-"<<endl;
}
int main()
{
init();
while(cin>>n&&n!=-1){
output();
}
return 0;
}
//样例代码2 递归的应用
#include<bits/stdc++.h>
using namespace std;
char a[2200][2200];
void draw(int x, int y, int n){ //左上角为x,y,画一个层数为n的分型盒
if(n==0){
a[x][y] = 'X';
return;
}
draw(x,y,n-1); //左上
draw(x,y+2*pow(3,n-1),n-1);//右上
draw(x+2*pow(3,n-1), y, n-1); //左下
draw(x+2*pow(3,n-1), y+2*pow(3,n-1), n-1); //右下
draw(x+pow(3,n-1), y+pow(3,n-1), n-1);//中
}
int main(){
int n;
while(1){
memset(a,0,sizeof(0));
cin>>n;
if(n==-1) break;
draw(1,1,n-1);
for(int i = 1; i <= pow(3,n-1); i++){
for(int j = 1; j <= pow(3,n-1); j++){
if(a[i][j]==0) cout<<" ";
else cout<<"X";
}
cout<<endl;
}
cout<<"-"<<endl;
}
return 0;
}疫情集中隔离
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;
}单词的长度
输入一行单词序列,相邻单词之间由1个或多个空格间隔,请对应地计算各个单词的长度。
注意,如果有标点符号(如连字符,逗号),标点符号算作与之相连的词的一部分。没有被空格间开的符号串,都算作单词。
时间限制:1000
内存限制:65536
输入
一行单词序列,最少1个单词,最多300个单词,单词之间用至少1个空格间隔。单词序列总长度不超过1000。
输出
依次输出对应单词的长度,之间以逗号间隔。
样例输入
She was born in 1990-01-02 and from Beijing city.
样例输出
3,3,4,2,10,3,4,7,5
#include <bits/stdc++.h>
using namespace std;
string s, ch;
int main() {
cin >> s;
cout << s.size();
while (cin >> ch) {
cout << "," << ch.size();
}
return 0;
}扫雷游戏地雷数计算
扫雷游戏是一款十分经典的单机小游戏。它的精髓在于,通过已翻开格子所提示的周围格地雷数,来判断未翻开格子里是否是地雷。
现在给出n行m列的雷区中的地雷分布,要求计算出每个非地雷格的周围格地雷数。
注:每个格子周围格有八个:上、下、左、右、左上、右上、左下、右下。
时间限制:1000
内存限制:65536
输入
第一行包含两个整数n和m,分别表示雷区的行数和列数。1 <= n <= 100, 1 <= m <= 100。 接下来n行,每行m个字符,‘*’表示相应格子中是地雷,‘?’表示相应格子中无地雷。字符之间无任何分隔符。
输出
n行,每行m个字符,描述整个雷区。若相应格中是地雷,则用‘*’表示,否则用相应的周围格地雷数表示。字符之间无任何分隔符。
样例输入
3 3 *?? ??? ?*?
样例输出
*10 221 1*1
#include <bits/stdc++.h>
using namespace std;
char a[102][102];
int dx[8] = {1, -1, 0, 0, 1, 1, -1, -1};
int dy[8] = {0, 0, 1, -1, 1, -1, 1, -1};
int main() {
int n, m, sum;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == '*') {
cout << a[i][j];
continue;
} else {
sum = 0;
for (int k = 0; k < 8; k++) {
if (a[i + dx[k]][j + dy[k]] == '*')
sum++;
}
cout << sum;
}
}
cout << endl;
}
return 0;
}古代密码
古罗马帝国有一个拥有各种部门的强大政府组织。其中一个部门就是保密服务部门。为了保险起见,在省与省之间传递的重要文件中的大写字母是加密的。当时最流行的加密方法是替换和重新排列。
替换方法是将所有出现的字符替换成其它的字符。有些字符会替换成它自己。例如:替换规则可以是将'A' 到 'Y'替换成它的下一个字符,将'Z'替换成 'A',如果原词是 "VICTORIOUS" 则它变成 "WJDUPSJPVT"。
排列方法改变原来单词中字母的顺序。例如:将顺序例如将顺序 < 2 1 5 4 3 7 6 10 9 8 > 应用到 "VICTORIOUS" 上,则得到"IVOTCIRSUO"。
人们很快意识到单独应用替换方法或排列方法加密,都是很不保险的。但是如果结合这两种方法,在当时就可以得到非常可靠的加密方法。所以,很多重要信息先使用替换方法加密,再将加密的结果用排列的方法加密。用两种方法结合就可以将"VICTORIOUS" 加密成"JWPUDJSTVP"。
考古学家最近在一个石台上发现了一些信息。初看起来它们毫无意义,所以有人设想它们可能是用替换和排列的方法被加密了。人们试着解读了石台上的密码,现在他们想检查解读的是否正确。他们需要一个计算机程序来验证,你的任务就是写这个验证程序。
时间限制:1000
内存限制:65536
输入
输入有两行。第一行是石台上的文字。文字中没有空格,并且只有大写英文字母。第二行是被解读出来的加密前的文字。第二行也是由大写英文字母构成的。 两行字符数目的长度都不超过100。
输出
如果第二行经过某种加密方法后可以产生第一行的信息,输出 "YES",否则输出"NO"。
样例输入
JWPUDJSTVP VICTORIOUS
样例输出
YES
#include <stdio.h>
#include <string.h>
// 记录字母出现次数
int ans[26];
int test[26];
// 记录字符串
char strA[105];
char strT[105];
int main() {
while (1) {
// 注意初始化
memset(ans, 0, sizeof(ans));
memset(test, 0, sizeof(test));
if (scanf("%s", strA) == EOF) {
return 0;
}
int lenA = strlen(strA);
// 求出现次数
for (int k = 0; k < lenA; k++) {
ans[strA[k] - 'A']++;
}
scanf("%s", strT);
int lenT = strlen(strT);
for (int m = 0; m < lenT; m++) {
test[strT[m] - 'A']++;
}
int flag = 0;
int i;
for (i = 0; i < 26; i++) {
flag = 0;
// 等于0时代表没有出现,跳过
if (test[i] == 0) {
continue;
}
for (int j = 0; j < 26; j++) {
if (test[i] == ans[j]) {
// 匹配了就把ans置零
ans[j] = 0;
flag = 1;
break;
}
}
if (flag == 0) {
printf("NO\n");
break;
} else {
continue;
}
}
// 等于26代表所有字母都能有匹配
if (i == 26) {
printf("YES\n");
}
}
return 0;
}足球联赛积分2
一场足球比赛中,两支参赛队A,B,如果A队的进球数大于B队,则A赢,A积3分B积0分,如果A队的进球数等于B队,则两队打平,各积1分,如果A队的进球数小于B队,则A输,A积0分B积3分。
现有一个球队一个赛季的比赛情况,请计算该球队的积分。
时间限制:1000
内存限制:65536
输入
第一行一个整数n(0 < n ≤ 40) 接下来n行,每行两个非负整数,表示一场该球队的进球数以及对手球队的进球数。
输出
一个整数,表示该球队的赛季积分。
样例输入
5 3 1 0 0 1 2 3 2 3 3
样例输出
8
提示
该球队5场比赛的结果分别为赢,平,输,赢,平,总计2赢2平1输,积分为8分。
#include <iostream>
using namespace std;
int main() {
int n, a, b, c = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a >> b;
if (a > b)
c = c + 3;
else if (a = b)
c = c + 1;
}
cout << c;
return 0;
}控制公司
有些公司是其他公司的部分拥有者,因为他们获得了其他公司发行的股票的一部分。例如,福特公司拥有马自达公司12%的股票。据说,如果至少满足了以下条件之一,公司A就可以控制公司B了:
l 公司A = 公司B。
l 公司A拥有大于50%的公司B的股票。
l 公司A控制K(K >= 1)个公司,记为C1, …, CK,每个公司Ci拥有xi%的公司B的股票,并且x1+ … + xK > 50%。(ps:A可以控制自己,即Ci可以为A)
你将被给予一系列的三对数(i,j,p),表明公司i拥有公司j的p%的股票。计算所有的数对(h,s),表明公司h控制公司s。
写一个程序读入三对数(i,j,p),并且找出所有的数对(h,s),使得公司h控制公司s。
时间限制:1000
内存限制:65536
输入
第一行: N,表明接下来三对数的数量。 第二行到第N+1行:每行三个整数作为一个三对数(i,j,p),如上文所述。 I,J≤100,N,P≤100
输出
输出零个或更多个的控制其他公司的公司。每行包括两个整数表明序号为第一个整数的公司控制了序号为第二个整数的公司。将输出的每行以第一个数字升序排列(并且第二个数字也升序排列来避免并列)。请不要输出控制自己的公司。
样例输入
3 1 2 80 2 3 80 3 1 20
样例输出
1 2 1 3 2 3
#include <bits/stdc++.h>
using namespace std;
unsigned long long int n, gf[1000][1000], mp[1000][1000];
void jf(int x, int y) // x公司加上i公司股票
{
for (int i = 1; i <= 100; i++) {
if (gf[x][i] + gf[y][i] > 100)
gf[x][i] = 100; // 判断
else
gf[x][i] += gf[y][i];
}
return;
}
void find(int x) // 递归
{
for (int i = 1; i <= 100; i++) {
if (gf[x][i] >= 50 && mp[x][i] == 0 && x != i) {
mp[x][i] = 1; // 标记 x公司可以控制i公司
jf(x, i);
find(x); // 加上以后再找一遍
return;
}
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
int a, b, c;
cin >> a >> b >> c;
gf[a][b] = c;
}
int t = 1;
while (t <= 100) // 枚举每一个公司
{
find(t);
t++;
}
for (int i = 1; i <= 100; i++) {
for (int j = 1; j <= 100; j++) {
if (mp[i][j] == 1)
cout << i << " " << j << endl;
}
}
}发型糟糕的一天
农夫John 的N(1 ≤ N ≤ 80,000)只奶牛中,有一些也许正在经历发型糟糕的一天。每只奶牛对自己乱糟糟的发型都有自知之明,农夫John想知道所有奶牛能看到其他奶牛头顶的数量之和。
任意奶牛i身高记为 hi (1 ≤ hi ≤ 1,000,000,000),所有奶牛面向东方(本题示意图的右面)依次站成一条线。因此,奶牛i能够看到在它前面的(奶牛i+1,i+2…)所有身高比它低的奶牛,直到被一头比它高的奶牛挡住
考虑如下的例子:
=
= =
= - = Cows facing right ->
= = =
= - = = =
= = = = = =
1 2 3 4 5 6 奶牛#1 可以看见奶牛#2, 3, 4的头顶
奶牛#2 无法看到任何奶牛的头顶
奶牛#3可以看见奶牛#4的头顶
奶牛#4无法看到任何奶牛的头顶
奶牛#5可以看见奶牛#6的头顶
奶牛#6无法看到任何奶牛的头顶!
用ci表示奶牛i能够看到头顶的奶牛个数;请计算c1 至cN的和。对于上面这个例子,其和为:3 + 0 + 1 + 0 + 1 + 0 = 5。
时间限制:2000
内存限制:65536
输入
第1行:奶牛数N第2行至N+1行:第i+1行包含一个整数,表示奶牛i的高度
输出
第1行:c1 至cN的累加和
样例输入
6 10 3 7 4 12 2
样例输出
5
#include <iostream>
#include <stack>
using namespace std;
int main() {
long long n, h, sum = 0;
cin >> n;
stack<int> s;
cin >> h;
s.push(h);
n -= 1;
while (n--) {
cin >> h;
while (!s.empty() && h >= s.top()) {
s.pop();
}
sum += s.size();
s.push(h);
}
cout << sum << endl;
return 0;
}城堡问题
1 2 3 4 5 6 7
#############################
1 # | # | # | | #
#####---#####---#---#####---#
2 # # | # # # # #
#---#####---#####---#####---#
3 # | | # # # # #
#---#########---#####---#---#
4 # # | | | | # #
#############################
(图 1)
# = Wall
| = No wall
- = No wall
1
2
3
4
5
6
7
8
9
10
11
12
13
14
图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 <iostream>
using namespace std;
int Room[60][60];
int RoomSign[60][60];
int RoomArea;
int RoomNum;
int MaxRoomArea;
void DFS(int i, int j) {
if (RoomSign[i][j])
return;
RoomSign[i][j] = 1;
RoomArea++;
if ((Room[i][j] & 1) == 0)
DFS(i, j - 1);
if ((Room[i][j] & 2) == 0)
DFS(i - 1, j);
if ((Room[i][j] & 4) == 0)
DFS(i, j + 1);
if ((Room[i][j] & 8) == 0)
DFS(i + 1, j);
return;
}
int main() {
int m, n;
cin >> m >> n;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
cin >> Room[i][j];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!RoomSign[i][j]) {
RoomArea = 0;
RoomNum++;
DFS(i, j);
MaxRoomArea = max(MaxRoomArea, RoomArea);
}
}
}
cout << RoomNum << endl;
cout << MaxRoomArea << endl;
return 0;
}吃糖果
现有n(20 > n > 0)个糖果,每天可以吃1个,也可以每天吃2个,也可以每天吃3个,请计算共有多少种不同的吃法。
时间限制:1000
内存限制:65536
输入
输入的每一行包括一组测试数据,即为糖果数n。最后一行为0,表示测试结束。
输出
每一行输出对应一行输入的结果,即为吃法的数目。
样例输入
1 2 3 4 0
样例输出
1 2 4 7
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef LOCAL
freopen("202209_3_4.in", "r", stdin);
#endif
int dp[30];
dp[0] = 1;
dp[1] = 2;
dp[2] = 4; // 111,12,21,3
for (int i = 3; i < 20; i++) {
dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
}
int n;
do {
scanf("%d", &n);
// printf("%d\n", n);
if (n == 0) {
break;
}
printf("%d\n", dp[n - 1]);
} while (true);
return 0;
}