Scratch编程一级 题库
我家的门牌号
我家住在一条短胡同里,这条胡同的门牌号从1开始顺序编号。
若所有的门牌号之和减去我家门牌号的两倍,恰好等于n,求我家的门牌号及总共有多少家。
数据保证有唯一解。
时间限制:1000
内存限制:65536
输入
一个正整数n。n < 100000。
输出
一行,包含两个正整数,分别是我家的门牌号及总共有多少家,中间用单个空格隔开。
样例输入
100
样例输出
10 15
#include <bits/stdc++.h>
using namespace std;
int plass(int n) { return (1 + n) * n / 2; }
int main() {
int n;
int sum, my;
cin >> n;
for (sum = 1; sum > 0; sum++) {
for (my = 1; my <= sum; my++) {
if (plass(sum) - (2 * my) == n) {
cout << my << " " << sum;
return 0;
}
}
}
}吃糖果
名名的妈妈从外地出差回来,带了一盒好吃又精美的巧克力给名名(盒内共有 N 块巧克力,20 > N >0)。妈妈告诉名名每天可以吃一块或者两块巧克力。假设名名每天都吃巧克力,问名名共有多少种不同的吃完巧克力的方案。例如:如果N=1,则名名第1天就吃掉它,共有1种方案;如果N=2,则名名可以第1天吃1块,第2天吃1块,也可以第1天吃2块,共有2种方案;如果N=3,则名名第1天可以吃1块,剩2块,也可以第1天吃2块剩1块,所以名名共有2+1=3种方案;如果N=4,则名名可以第1天吃1块,剩3块,也可以第1天吃2块,剩2块,共有3+2=5种方案。现在给定N,请你写程序求出名名吃巧克力的方案数目。
时间限制:1000
内存限制:65536
输入
输入只有1行,即整数N。
输出
输出只有1行,即名名吃巧克力的方案数。
样例输入
4
样例输出
5
#include <bits/stdc++.h>
using namespace std;
int eat(int N) {
if (N == 1)
return 1;
if (N == 2)
return 2;
return eat(N - 1) + eat(N - 2);
}
int main() {
int N;
cin >> N;
cout << eat(N);
}统计指定范围里的数
给定一个数的序列S,以及一个区间[L, R], 求序列中介于该区间的数的个数,即序列中大于等于L且小于等于R的数的个数。
时间限制:1000
内存限制:65536
输入
第一行1个整数n、,分别表示序列的长度。(0 < n ≤ 10000) 第二行n个正整数,表示序列里的每一个数,每个数小于等于10000000 第三行2个整数L、R,分别表示区间的左端点,区间的右端点。(1 ≤ L ≤ R ≤ 1000000)
输出
输出一个整数,表示序列中大于等于L且小于等于R的数的个数。
样例输入
5 11 8 1 10 16 1 10
样例输出
3
#include <bits/stdc++.h>
using namespace std;
int m[10005];
int main() {
int n, L, R, o = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> m[i];
}
cin >> L >> R;
for (int i = 0; i < n; i++) {
if (m[i] >= L && m[i] <= R) {
o++;
}
}
cout << o << endl;
return 0;
}过滤多余的空格
一个句子中也许有多个连续空格,过滤掉多余的空格,只留下一个空格。
时间限制:1000
内存限制:65536
输入
一行,一个字符串(长度不超过200),句子的头和尾都没有空格。
输出
过滤之后的句子。
样例输入
Hello world.This is c language.
样例输出
Hello world.This is c language.
#include <bits/stdc++.h>
using namespace std;
char st[200];
int main() {
while (scanf("%s", &st) == 1)
cout << st << " ";
return 0;
}出书最多
假定图书馆新进了m(10 ≤ m ≤ 999)本图书,它们都是由n(1 ≤ n ≤ 26)个作者独立或相互合作编著的。假设m本图书编号为整数(1到999),作者的姓名为字母('A'到'Z'),请根据图书作者列表找出参与编著图书最多的作者和他的图书列表。
时间限制:1000
内存限制:65536
输入
第一行为所进图书数量m,其余m行,每行是一本图书的信息,其中第一个整数为图书编号,接着一个空格之后是一个由大写英文字母组成的没有重复字符的字符串,每个字母代表一个作者。输入数据保证仅有一个作者出书最多。
输出
输出有多行: 第一行为出书最多的作者字母; 第二行为作者出书的数量; 其余各行为作者参与编著的图书编号(按输入顺序输出)。
样例输入
11 307 F 895 H 410 GPKCV 567 SPIM 822 YSHDLPM 834 BXPRD 872 LJU 791 BPJWIA 580 AGMVY 619 NAFL 233 PDJWXK
样例输出
P 6 410 567 822 834 791 233
#include <cstring>
#include <iostream>
using namespace std;
char c;
string str;
int no, len, m, a[10000][100], ch[27];
int main() {
int max = 0;
scanf("%d", &m);
for (int i = 0; i < m; i++) {
cin >> no >> str;
len = str.size();
for (int j = 0; j < len; j++) {
a[str[j] - 'A'][++ch[str[j] - 'A']] = no;
}
}
for (int i = 0; i < 26; i++) {
if (ch[i] > max) {
max = ch[i];
c = char(i + 'A');
}
}
cout << c << endl;
cout << max << endl;
for (int i = 1; i <= max; i++) {
cout << a[c - 'A'][i] << endl;
}
return 0;
}输出整数部分
输入一个双精度浮点数f, 输出其整数部分。
时间限制:1000
内存限制:65536
输入
一个双精度浮点数f(0 < f < 100000000)。
输出
一个整数,表示浮点数的整数部分。
样例输入
3.8889
样例输出
3
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
double a;
cin >> a;
int b;
b = a;
cout << b;
return 0;
}统计数
给定一个数的序列S,以及一个区间[L, R], 求序列中介于该区间的数的个数,即序列中大于等于L且小于等于R的数的个数。
时间限制:1000
内存限制:65536
输入
第一行3个整数n、L、R,分别表示序列的长度,区间的左端点,区间的右端点。(0 < n ≤ 10000, 1 ≤ L ≤ R ≤ 1000000) 第二行n个正整数,表示序列里的每一个数,每个数小于等于10000000
输出
输出一个整数,表示序列中大于等于L且小于等于R的数的个数。
样例输入
5 1 10 11 8 1 10 16
样例输出
3
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
int a, b, c, d, e, g = 0;
cin >> a >> b >> c;
for (e = 1; e <= a; e++) {
cin >> d;
if (d >= b && d <= c) {
g++;
}
}
cout << g;
return 0;
}最大质因子
质因子是指能整除给定正整数的质数。而最大质因子是指一个整数的所有质因子中最大的那个。
比如30的质因子有2,3, 5,所以最大质因子就是5。
时间限制:1000
内存限制:65536
输入
一个整数N( 2 ≤ N ≤ 10000)
输出
N的最大质因子
样例输入
30
样例输出
5
提示
质数是指在大于1的自然数中,除了1和它本身以外不再有其他因数的自然数。
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
int a;
bool b = true;
cin >> a;
for (int i = a; i >= 1; i--) {
if (a % i == 0) {
for (int j = 2; j < i; j++) {
if (i % j == 0)
b = false;
}
if (b == true) {
cout << i;
break;
} else {
b = true;
}
}
}
return 0;
}双端队列
定义一个双端队列,进队操作与普通队列一样,从队尾进入。出队操作既可以从队头,也可以从队尾。编程实现这个数据结构。
时间限制:1000
内存限制:65535
输入
第一行输入一个整数t,代表测试数据的组数。 每组数据的第一行输入一个整数n,表示操作的次数。 接着输入n行,每行对应一个操作,首先输入一个整数type。
当type=1,进队操作,接着输入一个整数x,表示进入队列的元素。
当type=2,出队操作,接着输入一个整数c,c=0代表从队头出队,c=1代表从队尾出队。
n <= 1000
输出
对于每组测试数据,输出执行完所有的操作后队列中剩余的元素,元素之间用空格隔开,按队头到队尾的顺序输出,占一行。如果队列中已经没有任何的元素,输出NULL。
样例输入
2 5 1 2 1 3 1 4 2 0 2 1 6 1 1 1 2 1 3 2 0 2 1 2 0
样例输出
3 NULL
//解法1
//用deque模拟一下即可
#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{
int n,m,type,x;
cin>>n;
for(int i=1;i<=n;i++){
cin>>m;
deque<int> q;
for(int j=1;j<=m;j++){
cin>>type>>x;
if(type==1){
q.push_back(x);
}else {
if(x==0)q.pop_front();
else q.pop_back();
}
}
if(q.empty()){
cout<<"NULL";continue;
}
while(!q.empty()){
cout<<q.front()<<" ";
q.pop_front();
}
cout<<endl;
}
return 0;
}//解法2
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
int n, t, type, c;
int a[1005] = {0};
int Top = 0, Back = 0;
int main() {
cin >> t;
while (t--) {
Top = 0;
Back = 0;
cin >> n;
while (n--) {
cin >> type >> c;
if (type == 1) {
a[Back++] = c;
} else {
if (c == 0) {
Top++;
} else {
Back--;
}
}
}
if (Top == Back) {
cout << "NULL" << endl;
} else {
for (int i = Top; i < Back; ++i) {
cout << a[i] << " ";
}
cout << endl;
}
}
return 0;
}区间合并
给定 n 个闭区间 [ai; bi],其中i=1,2,...,n。任意两个相邻或相交的闭区间可以合并为一个闭区间。例如,[1;2] 和 [2;3] 可以合并为 [1;3],[1;3] 和 [2;4] 可以合并为 [1;4],但是[1;2] 和 [3;4] 不可以合并。
我们的任务是判断这些区间是否可以最终合并为一个闭区间,如果可以,将这个闭区间输出,否则输出no。
时间限制:1000
内存限制:65536
输入
第一行为一个整数n,3 ≤ n ≤ 50000。表示输入区间的数量。 之后n行,在第i行上(1 ≤ i ≤ n),为两个整数 ai 和 bi ,整数之间用一个空格分隔,表示区间 [ai; bi](其中 1 ≤ ai ≤ bi ≤ 10000)。
输出
输出一行,如果这些区间最终可以合并为一个闭区间,输出这个闭区间的左右边界,用单个空格隔开;否则输出 no。
样例输入
5 5 6 1 5 10 10 6 9 8 10
样例输出
1 10
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
using namespace std;
int t, n, min1, max1;
struct node {
int x, y;
} a[101000];
int N;
int cmp(const node &w, const node &e) {
if (w.x > e.x)
return 0;
return 1;
}
bool f(int i) {
min1 = a[1].x;
if (i == t)
return 1;
if (a[i + 1].x >= a[i].x && a[i + 1].x <= max1) {
max1 = max(max1, a[i + 1].y);
f(i + 1);
} else
return 0;
}
int main() {
int i = 1;
cin >> n;
t = n;
while (n--) {
cin >> a[i].x >> a[i].y;
i++;
}
sort(a + 1, a + t + 1, cmp);
max1 = a[1].y;
if (f(1))
printf("%d %d\n", min1, max1);
else
printf("no\n");
return 0;
}奇怪的括号
某天小A和同学在课堂上讨论到:“栈这种数据结构真是太优美了,既简单用途又广泛。”小B仰慕小A许久,于是他拿出了自己在网上抄写的一道题问小A,如何判断括号是否匹配呢
时间限制:1000
内存限制:65536
输入
多组数据,每组数据占一行,且都是由(、)、[、]、*、/这六种字符组成。
输出
每组数据输出一行,如果括号能匹配成功,输出True,否则输出False。括号匹配规则是: ( 和 ) 匹配 [ 和 ] 匹配 /* 和 */ 匹配 如果含有冗余字符也算匹配失败,例如 /***/ 是匹配失败的因为中间多了一个*。
样例输入
()/*[()]*/ */**/
样例输出
True False
#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
while (cin >> s) {
stack<char> st;
for (int i = 0; i < s.size(); i++) {
if (st.empty()) {
st.push(s[i]);
} else {
if (s[i] == ')' && st.top() == '(')
st.pop();
else if (s[i] == ']' && st.top() == '[')
st.pop();
else if (s[i] == '/' && st.top() == '*' && st.size() >= 3) {
st.pop();
char a = st.top();
st.pop();
char b = st.top();
st.pop();
if (!(a == '*' && b == '/')) {
st.push(b);
st.push(a);
st.push('*');
}
} else
st.push(s[i]);
}
}
if (st.empty())
cout << "True" << endl;
else
cout << "False" << endl;
}
return 0;
}合法出栈序列
给定一个由不同小写字母构成的长度不超过8的字符串x,现在要将该字符串的字符依次压入栈中,然后再全部弹出。
要求左边的字符一定比右边的字符先入栈,出栈顺序无要求。
再给定若干字符串,对每个字符串,判断其是否是可能的x中的字符的出栈序列。
时间限制:1000
内存限制:65536
输入
第一行是原始字符串x 后面有若干行,每行一个字符串
输出
对除第一行以外的每个字符串,判断其是否是可能的出栈序列。如果是,输出"YES",否则,输出"NO"
样例输入
abc abc bca cab
样例输出
YES YES NO
#include <bits/stdc++.h>
using namespace std;
string a, b;
int main() {
cin >> a;
while (cin >> b) {
stack<char> st;
int j = 0;
for (int i = 0; i < a.size(); i++) {
if (!st.empty())
if (st.top() == b[j]) {
st.pop();
j++;
}
st.push(a[i]);
}
while (!st.empty() && st.top() == b[j] && j < b.size()) {
st.pop();
j++;
}
if (st.empty())
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}交易市场
市场里面一共有n种物品,有m种交易途径,每个交易途径可以由(x,y,z)表示,意思是可以用第x种物品换成第y种物品,并且得到z元的收益(z均大于0)。最开始你只有第一种物品,请问最多可以赚取多少收益。
时间限制:1000
内存限制:65536
输入
第一行两个正整数n和m(n ≤ 1000,m ≤ 4000) 接下来m行,每行三个正整数x, y, z,意思是可以用第x种物品换成第y种物品,并且得到z元的收益。(1 ≤ x,y ≤ n, 1 ≤ z ≤ 100)
输出
一个整数表示最大收益,如果可以赚取无穷多的收益则输出1000000000
样例输入
3 3 1 2 2 2 3 3 1 3 4
样例输出
5
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#define INF 1000000000
using namespace std;
struct exchangeTo {
int target;
int p;
exchangeTo(int a, int b) : target(a), p(b) {}
};
struct path {
int pre;
int val;
} dp[1005];
map<int, vector<exchangeTo>> tables;
bool inPath(int n, int k) {
while (k != -1) {
if (n == k)
return true;
k = dp[k].pre;
}
return false;
}
int main() {
memset(dp, -1, sizeof(dp));
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y, z;
cin >> x >> y >> z;
tables[x].push_back(exchangeTo(y, z));
}
dp[1].val = 0, dp[1].pre = 0;
bool done = false;
int result = 0;
queue<int> myqueues;
myqueues.push(1);
while (!myqueues.empty()) {
int top = myqueues.front();
myqueues.pop();
if (!tables[top].empty()) {
vector<exchangeTo>::iterator ii;
for (ii = tables[top].begin(); ii != tables[top].end(); ii++) {
if (inPath(ii->target, top)) {
result = INF;
done = true;
break;
}
if (dp[top].val + ii->p > dp[ii->target].val) {
dp[ii->target].val = dp[top].val + ii->p;
dp[ii->target].pre = top;
myqueues.push(ii->target); // 注意这里的更新
}
result = max(result, dp[ii->target].val);
}
if (done)
break;
}
}
cout << result << endl;
return 0;
}最佳路径
如下所示的由正整数数字构成的三角形:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。
注意:路径上的每一步只能从一个数走到下一层上和它最近的下边(正下方)的数或者右边(右下方)的数。
时间限制:1000
内存限制:65536
输入
第一行为三角形高度100>=h>=1,同时也是最底层边的数字的数目。 从第二行开始,每行为三角形相应行的数字,中间用空格分隔。
输出
最佳路径的长度数值。
样例输入
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5
样例输出
30
#include <bits/stdc++.h>
using namespace std;
int n, a[1001][1001] = {};
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
cin >> a[i][j];
}
}
for (int i = n; i >= 1; i--) {
for (int j = i; j >= 1; j--) {
a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
}
}
cout << a[1][1];
return 0;
}奶牛散步
从一个无限大的矩阵的中心点出发,一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法?
输入
一个数字,代表N,N<=1000
输出
输出有多少方案数模12345
样例输入
2
样例输出
7
// 上一步向上走,下一步可以向左、右、上
// 上一步向左走,下一步可以向左、上
// 上一步向右走,下一步可以向右、上
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long lr = 2, up = 1;
int i = 0;
long long tmplr = 0, tmpup = 0;
if (n == 1) {
cout << 3;
} else {
for (i = 2; i <= n; i++) {
tmplr = lr;
tmpup = up;
lr = (tmpup * 2 + tmplr) % 12345;
up = (tmpup + tmplr) % 12345;
}
cout << (up + lr) % 12345;
}
return 0;
}吃奶酪
Jerry准备偷吃Tom的奶酪。所有的奶酪排成了一条直线,每块奶酪都有不同的美味程度。然而,如果有相邻两块奶酪都被Jerry偷吃,Tom就会发现这一点并迅速抓住Jerry。Jerry当然希望在不被Tom发现的条件下吃到的奶酪美味度总和最大。当然,他也可以选择一块奶酪都不吃。请你帮助他规划一下偷吃的方案,告诉他最多能偷吃到多少的美味度吧。
时间限制:1000
内存限制:65536
输入
第一行一个整数T (T<=100),表示测试数据组数。 接下来,每组测试数据包含两行。其中,第一行一个整数n (1 <= n <= 100,000) ,表示奶酪的数量;第二行n个整数,表示这一排直线上奶酪的美味程度,请注意,美味度保证能够被int类型存储,且可能是负数。
输出
对于每组测试数据,输出一个整数,表示Jerry可以吃到的最大美味度总和。请注意,美味度总和可能超过int存储范围
样例输入
2 4 1 2 3 1 5 2 7 9 3 1
样例输出
4 12
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
long long d[100005];
int a[100005];
int main() {
int t;
cin >> t;
while (t--) {
int n;
memset(d, 0, sizeof(d));
memset(a, 0, sizeof(a));
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
d[1] = max(0, a[1]);
d[2] = max(int(d[1]), a[2]);
for (int i = 3; i <= n; i++) {
d[i] = max(d[i - 1], a[i] + d[i - 2]);
}
cout << d[n] << endl;
}
return 0;
}余数相同问题
已知三个正整数 a,b,c。
现有一个大于1的整数x,将其作为除数分别除a,b,c,得到的余数相同。
请问满足上述条件的x的最小值是多少?
数据保证x有解。
输入
一行,三个不大于1000000的正整数a,b,c,两个整数之间用一个空格隔开。
输出
一个整数,即满足条件的x的最小值。
样例输入
300 262 205
样例输出
19
#include <iostream>
using namespace std;
int min(int a, int b, int c) {
int min = a;
if (b < min)
min = b;
if (c < min)
min = c;
return min;
}
int ys(int a, int b, int c) {
int i;
for (i = 2; i <= min(a, b, c); i++) {
int y1 = a % i, y2 = b % i, y3 = c % i;
if (y1 == y2 && y1 == y3 && y2 == y3)
break;
}
return i;
}
int main() {
int a, b, c;
cin >> a >> b >> c;
cout << ys(a, b, c) << endl;
}课程冲突
小 A 修了 n 门课程, 第 i 门课程是从第 ai 天一直上到第 bi 天。
定义两门课程的冲突程度为 : 有几天是这两门课程都要上的。
例如 a1=1,b1=3,a2=2,b2=4 时, 这两门课的冲突程度为 2。
现在你需要求的是这 n 门课中冲突程度最大的两门课的冲突程度。
时间限制:1000
内存限制:65536
输入
第一行一个正整数 n 表示课程数量。 接下来 n 行,每行两个正整数 ai,bi。 2 ≤ n≤ 1000, 1 ≤ ai ≤ bi ≤ 1000。
输出
输出一个整数表示最大的冲突程度
样例输入
3 1 3 2 4 5 5
样例输出
2
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct project {
int start;
int end;
project(int a, int b) : start(a), end(b) {}
bool operator<(const project A) const {
if (start == A.start)
return end < A.end;
else
return start < A.start;
}
};
int main() {
int n;
cin >> n;
vector<project> alls;
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
alls.push_back(project(a, b));
}
sort(alls.begin(), alls.end());
int result = 0;
for (int i = 0; i < n; i++) {
if (alls[i].end - alls[i].start < result) // 剪枝
continue;
for (int j = i + 1; j < n; j++) {
if (alls[j].start > alls[i].end)
break;
int t = min(alls[i].end, alls[j].end) - alls[j].start + 1;
result = max(t, result);
}
}
cout << result << endl;
return 0;
}菲波那契数列
菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。 给出一个正整数a,要求菲波那契数列中第a个数对10000取模的结果是多少。
时间限制:1000
内存限制:65536
输入
第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数a(1 <= a <= 1000000)。
输出
n行,每行输出对应一个输入。输出应是一个正整数,为菲波那契数列中第a个数对10000取模得到的结果。
样例输入
4 5 2 19 1
样例输出
5 1 181 1
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int num;
int a, b, c;
while (n--) {
scanf("%d", &num);
a = 1;
b = 1;
c = 2;
if (num == 1 || num == 2) {
printf("1\n");
} else if (num == 3) {
printf("2\n");
} else {
num -= 3;
while (num--) {
a = b;
b = c;
c = (a + b) % 1000;
}
printf("%d\n", c);
}
}
return 0;
}字符统计
给定一个由a-z这26个字符组成的字符串,统计其中哪个字符出现的次数最多。
输入
输入包含一行,一个字符串,长度不超过1000。
输出
输出一行,包括出现次数最多的字符和该字符出现的次数,中间以一个空格分开。如果有多个字符出现的次数相同且最多,那么输出ascii码最小的那一个字符。
样例输入
abbccc
样例输出
c 3
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
char str[1100];
int main() {
int a[30] = {0};
int len, max = -1;
int i, j;
cin >> str;
len = strlen(str);
for (i = 0; i < len; i++)
a[str[i] - 'a']++;
for (i = 0; i < 26; i++)
if (a[i] > max) {
j = i;
max = a[i];
}
cout << char('a' + j) << " " << max << endl;
return 0;
}