Scratch编程一级 题库
铺砖
对于一个2行N列的走道。现在用1*2,2*2的砖去铺满。问有多少种不同的方式。
时间限制:3000
内存限制:131072
输入
整个测试有多组数据,请做到文件底结束。每行给出一个数字N,0 <= n <= 250
输出
如题
样例输入
2 8 12 100 200
样例输出
3 171 2731 845100400152152934331135470251 1071292029505993517027974728227441735014801995855195223534251
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int a[1005][255] = {{0, 0}, {0, 1}, {0, 3}, {0, 5}};
int b[1005], c[1005], len[255] = {0, 1, 1, 1}, n;
int main() {
for (int l = 4; l <= 255; l++) {
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
int len3;
for (int i = len[l - 2]; i >= 1; i--)
b[i] = a[l - 2][i];
for (int i = 1; i <= len[l - 2]; i++) {
c[i] += b[i] * 2;
c[i + 1] = c[i] / 10;
c[i] %= 10;
}
len3 = len[l - 2] + 1;
while (c[len3] == 0 && len3 > 1)
len3--;
int x = 0;
len3 = 1;
while (len3 <= len[l - 1] || len3 <= len[l - 2]) {
a[l][len3] += a[l - 1][len3] + c[len3];
a[l][len3 + 1] = a[l][len3] / 10;
a[l][len3] %= 10;
len3++;
}
while (a[l][len3] == 0 && len3 > 1)
len3--;
len[l] = len3;
}
while (scanf("%d", &n) != EOF) {
if (n == 0) {
cout << "1" << endl;
continue;
}
for (int i = len[n]; i >= 1; i--)
cout << a[n][i];
cout << endl;
}
return 0;
}质数的和与积
两个质数的和是S,它们的积最大是多少?
时间限制:10000
内存限制:65536
输入
一个不大于10000的正整数S,为两个质数的和。
输出
一个整数,为两个质数的最大乘积。数据保证有解。
样例输入
50
样例输出
589
#include <cstdio>
#include <cstring>
#include <iostream>
#include <math.h>
#include <string>
using namespace std;
int prime(int a) {
int i;
if (a == 1)
return 0;
for (i = 2; i <= sqrt(a); i++)
if (a % i == 0)
return 0;
return 1;
}
int main() {
int j, s, x = 0, y;
scanf("%d", &s);
y = s;
for (j = 2; j <= s / 2; j++) {
if (prime(j) == 1 && prime(s - j) == 1) {
if (j > x && (s - j) < y) {
x = j;
y = s - j;
}
}
}
printf("%d", x * y);
return 0;
}因子问题
任给两个正整数N、M,求一个最小的正整数a,使得a和(M-a)都是N的因子。
时间限制:10000
内存限制:65536
输入
包括两个整数N、M。N不超过1,000,000。
输出
输出一个整数a,表示结果。如果某个案例中满足条件的正整数不存在,则在对应行输出-1
样例输入
35 10
样例输出
5
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i < m; i++) {
if (n % i == 0 && n % (m - i) == 0) {
cout << i;
return 0;
}
}
cout << "-1";
return 0;
}合影效果
小云和朋友们去爬香山,为美丽的景色所陶醉,想合影留念。如果他们站成一排,男生全部在左(从拍照者的角度),并按照从矮到高的顺序从左到右排,女生全部在右,并按照从高到矮的顺序从左到右排,请问他们合影的效果是什么样的(所有人的身高都不同)?
时间限制:1000
内存限制:65536
输入
第一行是人数n(2 <= n <= 40,且至少有1个男生和1个女生)。 后面紧跟n行,每行输入一个人的性别(男male或女female)和身高(浮点数,单位米),两个数据之间以空格分隔。
输出
n个浮点数,模拟站好队后,拍照者眼中从左到右每个人的身高。每个浮点数需保留到小数点后2位,相邻两个数之间用单个空格隔开。
样例输入
6 male 1.72 male 1.78 female 1.61 male 1.65 female 1.70 female 1.56
样例输出
1.65 1.72 1.78 1.70 1.61 1.56
#include <bits/stdc++.h>
using namespace std;
int n;
struct stu {
bool ss;
double height;
void ini() {
string s;
cin >> s;
if (s == "male")
ss = 1;
else
ss = 0;
scanf("%lf", &height);
}
} a[41];
bool cmp(stu a1, stu b) {
if (a1.ss != b.ss)
return a1.ss == 1;
else if (a1.ss == 1)
return a1.height < b.height;
else
return b.height < a1.height;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
a[i].ini();
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++)
printf("%.2lf ", a[i].height);
return 0;
}大整数加法
求两个不超过200位的非负整数的和。
时间限制:1000
内存限制:65536
输入
有两行,每行是一个不超过200位的非负整数,可能有多余的前导0。
输出
一行,即相加后的结果。结果里不能有多余的前导0,即如果结果是342,那么就不能输出为0342。
样例输入
22222222222222222222 33333333333333333333
样例输出
55555555555555555555
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
char s1[220], s2[220];
void exchange() {
int l, r;
l = 0, r = strlen(s1) - 1;
while (r > l) {
if (s1[l] >= '0')
s1[l] -= '0';
if (s1[r] >= '0')
s1[r] -= '0';
swap(s1[l], s1[r]);
l++, r--;
}
if (l == r)
s1[l] -= '0';
l = 0, r = strlen(s2) - 1;
while (r > l) {
if (s2[l] >= '0')
s2[l] -= '0';
if (s2[r] >= '0')
s2[r] -= '0';
swap(s2[l], s2[r]);
l++, r--;
}
if (l == r)
s2[l] -= '0';
}
int main() {
cin >> s1;
cin >> s2;
exchange();
for (int i = 0; i <= 219; i++) {
s1[i] += s2[i];
if (s1[i] > 9)
s1[i + 1] += s1[i] / 10;
s1[i] %= 10;
}
bool if_zero = true;
for (int i = 220; i >= 0; i--) {
if (s1[i] == 0)
continue;
for (int j = i; j >= 0; j--)
putchar(s1[j] + '0');
if_zero = false;
break;
}
if (if_zero)
putchar('0');
return 0;
}细菌的繁殖与扩散
在边长为9的正方形培养皿中,正中心位置有m个细菌。假设细菌的寿命仅一天,但每天可繁殖10个后代,而且这10个后代,有两个分布在原来的单元格中,其余的均匀分布在其四周相邻的八个单元格中。求经过n(1≤n≤4)天后,细菌在培养皿中的分布情况。
时间限制:10000
内存限制:65536
输入
输入为两个整数,第一个整数m表示中心位置细菌的个数(2 ≤ m ≤ 30),第二个整数n表示经过的天数(1 ≤ n ≤ 4)。
输出
输出九行九列整数矩阵,每行的整数之间用空格分隔。整个矩阵代表n天后细菌在培养皿上的分布情况。
样例输入
2 1
样例输出
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 2 4 2 0 0 0 0 0 0 2 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
#include <bits/stdc++.h>
using namespace std;
int m, n;
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int a[5][10][10];
int main() {
cin >> m >> n;
a[0][5][5] = m;
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= 9; i++)
for (int j = 1; j <= 9; j++) {
a[k][i][j] = 2 * a[k - 1][i][j];
for (int l = 0; l < 8; l++) {
int nx = i + dx[l], ny = j + dy[l];
if (nx > 0 && nx <= 9 && ny > 0 && ny <= 9)
a[k][i][j] += a[k - 1][nx][ny];
}
}
}
for (int i = 1; i <= 9; i++) {
for (int j = 1; j <= 9; j++)
cout << a[n][i][j] << ' ';
cout << endl;
}
}单词倒排
编写程序,读入一行英文(只包含字母和空格,单词间以单个空格分隔),将所有单词的顺序倒排并输出,依然以单个空格分隔。
时间限制:10000
内存限制:65536
输入
输入为一个字符串(字符串长度至多为100)。
输出
输出为按要求排序后的字符串。
样例输入
I am a student
样例输出
student a am I
#include <iostream>
#include <string>
using namespace std;
string str;
string de[100];
int main() {
getline(cin, str);
int len = str.length();
int ind = 0;
for (int i = 0; i < len; i++) {
if (str[i] >= 'a' && str[i] <= 'z' || str[i] >= 'A' && str[i] <= 'Z') {
de[ind] += str[i];
} else {
ind++;
de[ind] = " ";
ind++;
}
}
if (de[ind] == " ") {
ind--;
}
for (int i = ind; i >= 0; i--) {
cout << de[i];
}
return 0;
}//解法2
//样例代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s[105];
int i=0;
while(cin>>s[++i]){}
while(i>0)cout<<s[--i]<<" ";
return 0;
}输出整数
输入四个整数,把输入的第三、第四个整数输出。
时间限制:3000
内存限制:65536
输入
只有一行,共四个整数,整数之间由一个空格分隔。整数是32位有符号整数。
输出
只有一行,二个整数,即输入的第三、第四个整数,以一个空格分开。
样例输入
12 34 56 789
样例输出
56 789
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << c;
cout << " ";
cout << d;
}金币
国王将金币作为工资,发放给忠诚的骑士。第一天,骑士收到一枚金币;之后两天(第二天和第三天)里,每天收到两枚金币;之后三天(第四、五、六天)里,每天收到三枚金币;之后四天(第七、八、九、十天)里,每天收到四枚金币……这种工资发放模式会一直这样延续下去:当连续N天每天收到N枚金币后,骑士会在之后的连续N+1天里,每天收到N+1枚金币(N为任意正整数)。
你需要编写一个程序,确定从第一天开始的给定天数内,骑士一共获得了多少金币。
时间限制:10000
内存限制:65536
输入
一个整数(范围1到10000),表示天数。
输出
骑士获得的金币数。
样例输入
6
样例输出
14
//解法1
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, sum = 0, cnt = 0;
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
sum += i;
cnt++;
if (cnt == n)
break;
}
if (cnt == n)
break;
}
cout << sum << endl;
return 0;
}//解法2
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,t=0,b=1,ans=0;
cin>>n;
for(int i=1;i<=n;i++){
ans+=b;
t++;
if(t==b){
b++;
t=0;
}
}
cout<<ans;
return 0;
}数字变换
给定一个包含5个数字(0-9)的字符串,例如 “02943”,请将“12345”变换到它。 你可以采取3种操作进行变换
1. 交换相邻的两个数字
2. 将一个数字加1。如果加1后大于9,则变为0
3. 将一个数字加倍。如果加倍后大于9,则将其变为加倍后的结果除以10的余数。
最多只能用第2种操作3次,第3种操作2次 求最少经过多少次操作可以完成变换。
时间限制:1000
内存限制:65536
输入
有最多 100,000 组数据 每组数据就是包含5个数字的字符串
输出
对每组数据,输出将12345变换到给定字符串所需要的最少操作步数。如果无法变换成功,输出-1
样例输入
12435 99999 12374
样例输出
1 -1 3
提示
由于测试数据太多,如果对每组数据都从头进行搜索,就会超时。 建议先做预处理,即以“12345”作为初始状态做一遍彻底的广搜,找出“12345”经合法变换能够到达的所有字符串,并记录到达这些字符串各需要多少步操作。 然后对读入的每组数据,在上述预处理记录的结果中进行查询即可。
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
#define _init(x, v) memset(x, v, sizeof(x))
int rcd[100000];
bool vis[100000][5][5];
struct node {
int a[5], d, o2, o3;
};
queue<node> q;
void in() {
_init(rcd, -1);
node s = {1, 2, 3, 4, 5, 0, 3, 2};
q.push(s);
vis[12345][3][2] = 1;
rcd[12345] = 0;
}
int toNum(node &n) {
int t = 0;
for (int i = 0; i < 5; ++i) {
t *= 10;
t += n.a[i];
}
return t;
}
void bfs() {
while (!q.empty()) {
node s = q.front();
int t = toNum(s);
if (rcd[t] == -1 || rcd[t] > s.d)
rcd[t] = s.d;
// printf("n = %d, d = %d, o2 = %d, o3 = %d\n", toNum(s), s.d, s.o2, s.o3);
++s.d;
q.pop();
for (int i = 0; i < 5; ++i) {
// o1
if (i < 4 && s.a[i] != s.a[i + 1]) {
swap(s.a[i], s.a[i + 1]);
if (!vis[toNum(s)][s.o2][s.o3]) {
vis[toNum(s)][s.o2][s.o3] = 1;
q.push(s);
}
swap(s.a[i], s.a[i + 1]);
}
// o2
if (s.o2 > 0) {
--s.o2;
s.a[i] = (s.a[i] + 1) % 10;
if (!vis[toNum(s)][s.o2][s.o3]) {
vis[toNum(s)][s.o2][s.o3] = 1;
q.push(s);
}
s.a[i] = (s.a[i] + 10 - 1) % 10;
++s.o2;
}
// o3
if (s.o3 > 0) {
--s.o3;
int bak = s.a[i];
s.a[i] = (2 * s.a[i]) % 10;
if (!vis[toNum(s)][s.o2][s.o3]) {
vis[toNum(s)][s.o2][s.o3] = 1;
q.push(s);
}
s.a[i] = bak;
++s.o3;
}
}
}
}
int main() {
in();
bfs();
int n;
while (cin >> n) {
cout << rcd[n] << endl;
}
system("pause");
return 0;
}圣诞老人的礼物
圣诞节来临了,在城市A中圣诞老人准备分发糖果,现在有多箱不同的糖果,每箱糖果有自己的价值和重量,每箱糖果都可以拆分成任意散装组合带走。圣诞老人的驯鹿最多只能承受一定重量的糖果,请问圣诞老人最多能带走多大价值的糖果。
时间限制:1000
内存限制:65536
输入
第一行由两个部分组成,分别为糖果箱数正整数n(1 = n = 100),驯鹿能承受的最大重量正整数w(0<w<10000),两个数用空格隔开。其余n行每行对应一箱糖果,由两部分组成,分别为一箱糖果的价值正整数v和重量正整数w,中间用空格隔开。
输出
输出圣诞老人能带走的糖果的最大总价值,保留1位小数。输出为一行,以换行符结束。
样例输入
4 15 100 4 412 8 266 7 591 2
样例输出
1193.0
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
struct gift {
int value;
int weight;
double density;
} gf[101];
bool cmp(gift f1, gift f2) { // 按照单重价值从大到小排序
return f1.density > f2.density;
}
int main() {
int n, w;
cin >> n >> w;
for (int i = 0; i < n; i++) {
cin >> gf[i].value >> gf[i].weight;
gf[i].density = 1.0 * gf[i].value / gf[i].weight;
}
sort(gf, gf + n, cmp);
double totw = 0, totv = 0; // 注意到w为int型,可拆分为double型
// 所以新建一个double型保存背包剩余重量
for (int i = 0; i < n; i++) {
if (totw + gf[i].weight <= w) {
totw += gf[i].weight;
totv += gf[i].value;
} else {
totv += gf[i].density * (w - totw);
totw = w;
break;
}
}
printf("%.1lf", totv);
return 0;
}忍者道具
忍者道具有很多种,苦无,飞镖,震爆弹。L君热衷于收集忍者道具,现在他有N个道具,每个道具的重量分别是C1、C2…CN。现在他想把这N个道具装到载重量为W的工具包里,请问他最少需要多少个工具包?
时间限制:1000
内存限制:65536
输入
第一行包含两个用空格隔开的整数,N和W。 接下来N行每行一个整数,其中第i+1行的整数表示第i个道具的重量Ci。
输出
输出一个整数,最少需要多少个工具包。
样例输入
5 1996 1 2 1994 12 29
样例输出
2
提示
对于100%的数据,1=N=18,1=Ci=W=10^8。
#include <iostream>
using namespace std;
const int MAXN = 18;
int used[MAXN];
int W;
int m, n, ans = (1 << 30);
int item[MAXN];
int bag[MAXN];
void dfs(int x, int sum) {
if (sum >= ans)
return;
if (x == n) {
ans = min(ans, sum);
return;
}
for (int i = 0; i < sum; ++i) {
if (bag[i] >= item[x]) {
bag[i] -= item[x];
dfs(x + 1, sum);
bag[i] += item[x];
}
}
bag[sum] -= item[x];
dfs(x + 1, sum + 1);
bag[sum] += item[x];
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; ++i) {
cin >> item[i];
bag[i] = m;
}
dfs(0, 1);
cout << ans << endl;
return 0;
}//解法2 深搜
#include <bits/stdc++.h>
using namespace std;
int n,w,ans=20;
int a[20],bag[20];
void dfs(int x,int sum){//放第x个物品,已使用sum个包
if(sum>=ans) return;//背包数量不够
if(x>n) {ans=min(ans,sum);return;}//所有物品已放完
for(int i=1;i<=sum;i++){//放入现有背包
if(bag[i]>=a[x]){
bag[i]-=a[x];
dfs(x+1,sum);
bag[i]+=a[x];//回溯
}
}
bag[sum+1]-=a[x];//放入新背包
dfs(x+1,sum+1);
bag[sum+1]+=a[x];//回溯
}
int main() {
cin>>n>>w;
for(int i=1;i<=n;i++) {
cin>>a[i];
bag[i]=w;//初始化n个背包的开始可用容量
}
dfs(1,1);
cout<<ans<<endl;
return 0;
}求逆序对问题
给定N个数的序列a1,a2,...aN,定义一个数对(ai, aj)为“重要逆序对”的充要条件为 i < j 且 ai > 2aj。求给定序列中“重要逆序对”的个数。
时间限制:1000
内存限制:256000
输入
本题有多个测试点,每个测试点分为两行:第一行为序列中数字的个数N(1 ≤ N ≤ 200000),第二行为序列a1, a2 ... aN(0 ≤a ≤ 10000000),由空格分开。N=0表示输入结束。
输出
每个测试点一行,输出一个整数,为给序列中“重要逆序对”的个数。
样例输入
10
0 9 8 7 6 5 4 3 2 1
0
样例输出
16
提示
请注意答案范围,如果使用printf输出long long类型,请用%lld
#include <iostream>
using namespace std;
int arr[200005];
int tmp[200005];
int N;
long long mergesort(int start, int end) {
long long cnt = 0, mid = (start + end) / 2;
if (start >= end)
return 0;
cnt += mergesort(start, mid);
cnt += mergesort(mid + 1, end);
// find important reverse pair
int i = start, j = mid + 1;
while (i <= mid && j <= end) {
if (arr[i] > 2 * arr[j] && j <= end) {
cnt += (mid - i + 1);
j++;
} else {
i++;
}
}
// merge sort
i = start, j = mid + 1;
int idx = 0;
while (i <= mid && j <= end) {
if (arr[i] > arr[j]) {
tmp[idx++] = arr[j++];
} else {
tmp[idx++] = arr[i++];
}
}
while (i <= mid)
tmp[idx++] = arr[i++];
while (j <= end)
tmp[idx++] = arr[j++];
for (int k = 0; k < idx; k++) {
arr[start + k] = tmp[k];
}
return cnt;
}
int main() {
while (cin >> N) {
if (N == 0)
break;
for (int i = 1; i <= N; i++) {
cin >> arr[i];
}
cout << mergesort(1, N) << endl;
}
return 0;
}数字三角形问题

(图1)
图1给出了一个数字三角形。从三角形的顶部到底部有很多条不同的路径。对于每条路径,把路径上面的数加起来可以得到一个和,你的任务就是找到最大的和。 注意:路径上的每一步只能从一个数走到下一层上和它最近的左边的那个数或者右边的那个数。
时间限制:1000
内存限制:65536
输入
输入的是一行是一个整数N (1 < N <= 100),给出三角形的行数。下面的N行给出数字三角形。数字三角形上的数的范围都在0和100之间。
输出
输出最大的和。
样例输入
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;
int a[110][110];
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 - 1; i >= 1; i--)
for (int j = 1; j <= i; j++)
a[i][j] = max(a[i + 1][j], a[i + 1][j + 1]) + a[i][j];
cout << a[1][1] << endl;
return 0;
}大盗
阿福是一名经验丰富的大盗。趁着月黑风高,阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 N 家店铺,每家店中都有一些现金。阿福事先调查得知,只有当他同时洗劫了两家相邻的店铺时,街上的报警系统才会启动,然后警察就会蜂拥而至。
作为一向谨慎作案的大盗,阿福不愿意冒着被警察追捕的风险行窃。他想知道,在不惊动警察的情况下,他今晚最多可以得到多少现金?
时间限制:1000
内存限制:65536
输入
输入的第一行是一个整数 T (T <= 50) ,表示一共有 T 组数据。 接下来的每组数据,第一行是一个整数 N (1 <= N <= 100, 000) ,表示一共有 N 家店铺。第二行是 N 个被空格分开的正整数,表示每一家店铺中的现金数量。每家店铺中的现金数量均不超过 1000 。
输出
对于每组数据,输出一行。该行包含一个整数,表示阿福在不惊动警察的情况下可以得到的现金数量。
样例输入
2 3 1 8 2 4 10 7 6 14
样例输出
8 24
提示
对于第一组样例,阿福选择第 2 家店铺行窃,获得的现金数量为 8 。 对于第二组样例,阿福选择第 1 和 4 家店铺行窃,获得的现金数量为 10 + 14 = 24 。
#include <bits/stdc++.h>
using namespace std;
int t;
int n;
int a[100010];
int d[100010];
int main() {
cin >> t;
for (int i = 1; i <= t; i++) {
cin >> n;
for (int j = 1; j <= n; j++)
cin >> a[j];
int maxe;
d[1] = a[1];
d[2] = maxe = max(a[1], a[2]);
// cout << d[1] << " " << d[2] << " ";
for (int j = 3; j <= n; j++) {
d[j] = max(d[j - 1], a[j] + d[j - 2]);
maxe = max(d[j], maxe);
// cout << d[j] << " ";
}
// cout <<endl;
cout << maxe << endl;
}
return 0;
}井和绳子
有A, B, C, D, E五家人共用一口井,已知井深不超过k米。A, B, C, D, E的绳长各不相同,而且厘米表示的绳长一定是整数。
从井口放下绳索正好达到水面时:
(a)需要A家的绳n1条接上B家的绳1条
(b)需要B家的绳n2条接上C家的绳1条
(c)需要C家的绳n3条接上D家的绳1条
(d)需要D家的绳n4条接上E家的绳1条
(e)需要E家的绳n5条接上A家的绳1条
问井深和各家绳长。
时间限制:1000
内存限制:65536
输入
输入只有1行。包括空格分开的6个整数。 第一个整数k(1 <= k <= 20),代表井的最大深度(单位:米)。 接下来是5个正整数n1, n2, n3, n4, n5。这五个整数的含义见上面的题目描述。
输出
输出只有1行。 如果找到了可行解,就输出6个整数,用空格分开,分别代表井的深度和A, B, C, D, E的绳长(单位都是厘米)。 如果有多组可行解,输出井的深度最小的那组解。 如果不存在可行解,就输出一行: not found
样例输入
10 2 3 4 5 6
样例输出
721 265 191 148 129 76
#include <iostream>
using namespace std;
int main() {
int n[6], l, a, b, c, d, e, len;
cin >> l;
l *= 100;
for (int i = 1; i <= 5; i++)
cin >> n[i];
int flag = 0;
for (len = 1; len <= l; len++) {
for (a = 1; a <= len; a++) {
b = len - n[1] * a;
c = len - n[2] * b;
d = len - n[3] * c;
e = len - n[4] * d;
if (a == b || a == c || a == d || a == e || b == c || b == d || b == e ||
c == d || c == e || d == e || a <= 0 || b <= 0 || c <= 0 || d <= 0 ||
e <= 0)
continue;
if (e * n[5] + a == len) {
printf("%d %d %d %d %d %d\n", len, a, b, c, d, e);
return 0;
}
}
}
printf("not found");
return 0;
}爬楼
已知楼梯的数量,可以每次走2级或者3级,求不同的走法数
例如:楼梯一共有7级,一共3种方法:2 2 3或者 2 3 2 或者 3 2 2。
时间限制:1000
内存限制:65536
输入
输入包含若干行,每行包含一个正整数N,代表楼梯级数,1 <= N <= 50。 最后一行为0,表示测试结束。
输出
不同的走法数,每一行输入对应一行输出
样例输入
7 0
样例输出
3
#include <iostream>
using namespace std;
#define maxn 55
long long dp[maxn];
void init() {
dp[1] = 0, dp[2] = 1, dp[3] = 1, dp[4] = 1;
for (int i = 5; i <= maxn; i++)
dp[i] = dp[i - 3] + dp[i - 2];
}
int main() {
init();
int n;
while (cin >> n) {
if (n == 0) {
return 0;
}
cout << dp[n] << endl;
}
return 0;
}表达式求值
输入一个布尔表达式,请你输出它的真假值。
比如:( V | V ) & F & ( F | V )
V表示true,F表示false,&表示与,|表示或,!表示非。
上式的结果是F
时间限制:1000
内存限制:65536
输入
输入包含多行,每行一个布尔表达式,表达式中可以有空格,总长度不超过1000
输出
对每行输入,如果表达式为真,输出"V",否则出来"F"
样例输入
( V | V ) & F & ( F| V) !V | V & V & !F & (F | V ) & (!F | F | !V & V) (F&F|V|!V&!F&!(F|F&V))
样例输出
F V V
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
char s[1005];
stack<bool> B;
stack<char> C;
int main() {
while (cin.getline(s, 1000, '\n')) {
int len = strlen(s);
while (!B.empty())
B.pop();
while (!C.empty())
C.pop();
for (int i = 0; i < len; ++i) {
if (s[i] == ' ')
continue;
if (s[i] == 'V') {
bool tmp = true;
while (!C.empty() && C.top() == '!') {
C.pop();
tmp = !tmp;
}
B.push(tmp);
} else if (s[i] == 'F') {
bool tmp = false;
while (!C.empty() && C.top() == '!') {
C.pop();
tmp = !tmp;
}
B.push(tmp);
} else if (s[i] == '(' || s[i] == '!') {
C.push(s[i]);
} else if (s[i] == ')') {
while (C.top() != '(') {
char op = C.top();
C.pop();
bool tmp1 = B.top();
B.pop();
bool tmp2 = B.top();
B.pop();
if (op == '&')
B.push(tmp2 && tmp1);
else if (op == '|')
B.push(tmp2 || tmp1);
}
C.pop();
while (!C.empty() && C.top() == '!') {
bool tmp = B.top();
B.pop();
B.push(!tmp);
C.pop();
}
} else if (s[i] == '&') {
while (!C.empty() && C.top() == '&') {
C.pop();
bool tmp1 = B.top();
B.pop();
bool tmp2 = B.top();
B.pop();
B.push(tmp1 && tmp2);
}
C.push(s[i]);
} else if (s[i] == '|') {
while (!C.empty() && (C.top() == '|' || C.top() == '&')) {
bool tmp1 = B.top();
B.pop();
bool tmp2 = B.top();
B.pop();
char op = C.top();
C.pop();
if (op == '&')
B.push(tmp1 && tmp2);
else if (op == '|')
B.push(tmp1 || tmp2);
}
C.push(s[i]);
}
}
while (!C.empty()) {
bool tmp1 = B.top();
B.pop();
bool tmp2 = B.top();
B.pop();
char op = C.top();
C.pop();
if (op == '&')
B.push(tmp1 && tmp2);
else if (op == '|')
B.push(tmp1 || tmp2);
}
if (B.top())
cout << "V" << endl;
else
cout << "F" << endl;
}
return 0;
}数列
用以下方式构造数列: 数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。
给出一个正整数a,要求数列中第a个数对1000取模的结果是多少。
时间限制:1000
内存限制:65536
输入
第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数a(1 <= a <= 1000000)。
输出
n行,每行输出对应一个输入。输出应是一个正整数,为数列中第a个数对1000取模得到的结果。
样例输入
4 5 2 19 1
样例输出
5 1 181 1
#include <iostream>
using namespace std;
int main() {
int n = 0;
cin >> n;
int a[n];
for (int i = 0; i < n; i++) {
int a, f0 = 1, f1 = 1, f2;
cin >> a;
if (a == 1 || a == 2) {
cout << 1 << endl;
} else {
for (int j = 3; j <= a; j++) {
f2 = (f0 + f1) % 1000;
f0 = f1;
f1 = f2;
}
f0 = 1;
f1 = 1;
cout << f2 << endl;
}
}
}数字放大
给定一个整数序列以及放大倍数x,将序列中每个整数放大x倍后输出。
时间限制:1000
内存限制:65536
输入
包含三行: 第一行为N,表示整数序列的长度(N ≤ 100); 第二行为N个整数(不超过整型范围),整数之间以一个空格分开; 第三行包含一个整数(不超过整型范围),为指定的整数x。
输出
N个整数,为原序列放大之后的序列,整数之间以一个空格分开。
样例输入
3 1 5 7 2
样例输出
2 10 14
提示
注意答案的数据范围
//参考代码1
#include <iostream>
using namespace std;
int main() {
int n, a[101], x;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
cin >> x;
for (int i = 1; i <= n; i++) {
a[i] = a[i] * x;
cout << a[i] << " ";
}
return 0;
}