Scratch编程一级 题库
字符统计
给定一个由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;
}图像处理
给定n行m列的图像各像素点的灰度值,要求用如下方法对其进行模糊化处理:
1. 四周最外侧的像素点灰度值不变;
2. 中间各像素点新灰度值为该像素点及其上下左右相邻四个像素点原灰度值的平均(舍入到最接近的整数)。
时间限制:1000
内存限制:65536
输入
第一行包含两个整数n和m,表示图像包含像素点的行数和列数。1 <= n <= 100,1 <= m <= 100。 接下来n行,每行m个整数,表示图像的每个像素点灰度。相邻两个整数之间用单个空格隔开,每个元素均在0~255之间。
输出
n行,每行m个整数,为模糊处理后的图像。相邻两个整数之间用单个空格隔开。
样例输入
4 5 100 0 100 0 50 50 100 200 0 0 50 50 100 100 200 100 100 50 50 100
样例输出
100 0 100 0 50 50 80 100 60 0 50 80 100 90 200 100 100 50 50 100
#include <cmath>
#include <iostream>
using namespace std;
const int N = 100 + 10;
int a[N][N], b[N][N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
b[i][j] = a[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i == n || i == 1 || j == m || j == 1)
continue;
else {
double sum =
a[i][j] + a[i - 1][j] + a[i + 1][j] + a[i][j - 1] + a[i][j + 1];
sum /= 5;
b[i][j] = int(round(sum));
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j == 1)
cout << b[i][j];
else
cout << ' ' << b[i][j];
}
cout << endl;
}
}偶数降序输出
给定一个长度为N (不大于500) 的正整数序列,请将其中的所有偶数取出,并按降序输出。
输入描述:
共两行;第一行为N;第二行为N个正数,其间用空格间隔
输出描述:
降序输出的偶数序列,数与数之间用空格间隔
数据保证至少有一个偶数
样例输入:
10
1 3 2 6 5 4 9 8 7 10
样例输出:
10 8 6 4 2
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int a[N];
bool cmp(int num1, int num2) { return num1 >= num2; }
main() {
int n, t;
int j = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
if (a[i] % 2 == 0) {
t = a[i];
a[j++] = t;
}
}
sort(a, a + j, cmp);
for (int i = 0; i < j; i++) {
cout << a[i] << " ";
}
cout << endl;
}满足条件的数的累加2
现有n个整数,将其中个位数为k的数进行累加求和
输入
第一行一个整数n。第二行n个非负整数,以空格分割,每个数不大于100000。第三行一个整数k。
输出
输出满足题目要求的累加和
样例输入
10 2 5 7 17 11 18 4 27 1 7 7
样例输出
58
#include <iostream>
using namespace std;
int main() {
int n, sum = 0;
cin >> n;
int a[n];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int k;
cin >> k;
for (int i = 0; i < n; i++) {
if (a[i] % 10 == k) { // 个位数
sum += a[i];
}
}
cout << sum;
return 0;
}//解法2
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k,ans=0;
cin>>n>>k;
for(int i=1,x;i<=n;i++){
cin>>x;
if(x%10==k) ans+=x;
}
cout<<ans;
return 0;
}数字判断
输入一个字符,如果输入的字符是数字,输出yes,否则输出no
输入
一个字符
输出
如果输入的字符是数字,输出yes,否则输出no
样例1输入
5
样例1输出
yes
样例2输入
A
样例2输出
no
#include <iostream>
using namespace std;
int main() {
char ch;
cin >> ch;
if (ch >= '0' && ch <= '9') {
cout << "yes";
} else {
cout << "no";
}
return 0;
}满足条件的数的累加
现有n个整数,将其中个位数为k的数进行累加求和。
输入
第一行2个整数n、k,以空格隔开。(0<n<1000,0<=k<=9) 第二行n个非负整数,以空格隔开,每个数不大于100000。
输出
输出满足题目要求的累加和。
样例输入
10 7 2 5 7 17 11 18 4 27 1 7
样例输出
58
//解法1
#include <iostream>
using namespace std;
int main() {
int n, k, a, sum = 0;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a;
if (a % 10 == 7)
sum += a;
}
cout << sum;
return 0;
}//解法2
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k,ans=0;
cin>>n>>k;
for(int i=1,x;i<=n;i++){
cin>>x;
if(x%10==k) ans+=x;
}
cout<<ans;
return 0;
}交换输出
输入两个整数a,b,将它们交换输出
输入
一行两个整数a、b,以空格分割。0<a<108 0<b<1016
输出
一行两个整数b、a,以空格分割。
样例输入
123 12345654321
样例输出
12345654321 123
#include <iostream>
using namespace std;
int main() {
long long a, b;
cin >> a >> b;
cout << b << " " << a;
}比n小的最大质数
对于给定的n,求比n小的质数中最大的一个
质数是指大于1的自然数,除了1和它自身外,不能被其他自然数整除的数。
输入
一个整数n(2<n<1000)
输出
一个整数,即题目要求的解。
样例输入
100
样例输出
97
#include <iostream>
using namespace std;
bool isPrime(int x) {
for (int i = 2; i < x; i++) {
if (x % i == 0)
return false;
}
return true;
}
int main() {
int n;
cin >> n;
while (n > 0) {
if (isPrime(n)) {
cout << n;
break;
}
n--;
}
return 0;
}逆波兰表达式
逆波兰表达式是一种把运算符前置的算术表达式,例如普通的表达式2 + 3的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系,也不必用括号改变运算次序,例如(2 + 3) * 4的逆波兰表示法为* + 2 3 4。本题求解逆波兰表达式的值,其中运算符包括+ - * /四个。
时间限制:1000
内存限制:65536
输入
输入为一行,其中运算符和运算数之间都用空格分隔,运算数是浮点数。
输出
输出为一行,表达式的值。 可直接用printf("%f\n", v)输出表达式的值v。
样例输入
* + 11.0 12.0 + 24.0 35.0
样例输出
1357.000000
#include <cmath>
#include <cstdlib>
#include <iostream>
using namespace std;
const int N = 40;
char a[N];
double expr(void) {
scanf("%s", a);
if (a[0] == '+')
return expr() + expr();
else if (a[0] == '-')
return expr() - expr();
else if (a[0] == '*')
return expr() * expr();
else if (a[0] == '/')
return expr() / expr();
else
return atof(a);
}
int main() {
printf("%lf\n", expr());
return 0;
}扑克牌排序
假设这里有36张扑克牌,分别为A1~A9,B1~B9,C1~C9,D1~D9,其中A代表方片,B代表草花,C代表红桃,D代表黑桃,那么,设定如下的排序规则:
1.对于两张卡牌,X1Y1与X2Y2,X1与X2表示A~D,Y1与Y2表示1~9,如果X1与X2不同,那么依照D>C>B>A的方式进行排序
2.假如有X1与X2相同时,那么就比较Y1与Y2的大小。
例如,对于如下的四张牌,有如下的升序排序结果:
D3,C4,A4,C1
升序排序的结果为A4,C1,C4,D3
有人提出了如下的排序策略:
先建立9个队列,用于存放点数的大小,将卡牌依点数存放入各自的队列之中,然后再按队列1到队列9依次出队。
例如,对于上面的结果,依次进队后,结果如下:
队列1:C1;队列3:D3,队列4:C4,A4
将其依次出队后,结果为C1,D3,C4,A4
然后,再建立4个队列,用于存放花色。将卡牌依花色A~D存放入队列1~4中,然后再按队列1到队列4依次出队。
例如,对于上面刚刚出队的序列C1,D3,C4,A4,将其依次进队,结果如下:
队列1:A4;队列3:C1,C4;队列4:D3
将其依次出队后,结果为A4,C1,C4,D3,排序结束。
请根据上面的算法,编写一个用队列对扑克牌排序的程序,要求依照上面的排序规则,根据先花色后点数的方法进行排序。
时间限制:1000
内存限制:65536
输入
输入分为两行,第一行为一个整数n,表示一共有n张牌(1<=n<=100) 第二行用XY的形式表示每一张牌,其中X为A~D,Y为1~9
输出
输出三个部分 第一个部分为第一次进队出队的结果,用Queue1:...表示,共9行,结果用空格分隔,下同 第二部分为第二次进队出队的结果,用QueueA:...表示,共4行 第三部分为一行,即将卡牌排序后的结果(升序排序)
样例输入
8 D8 A6 C3 B8 C5 A1 B5 D3
样例输出
Queue1:A1 Queue2: Queue3:C3 D3 Queue4: Queue5:C5 B5 Queue6:A6 Queue7: Queue8:D8 B8 Queue9: QueueA:A1 A6 QueueB:B5 B8 QueueC:C3 C5 QueueD:D3 D8 A1 A6 B5 B8 C3 C5 D3 D8
提示
第二次入队出队时,可以复用第一次时9个队列中的4个。所以其实只需要开辟9个队列即可。
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
int n = 0;
cin >> n;
queue<string> q1[10], q2[4]; // 分别按照大小和花色存放扑克
string *strs = new string[n];
string newstr[10000];
for (int i = 0; i < n; i++) {
cin >> strs[i];
q1[strs[i][1] - '1'].push(strs[i]); // 按照大小入队q1
}
for (int i = 0; i < n; i++) // 输出q1队列,从小到大
{
cout << "Queue" << i + 1 << ":";
while (!q1[i].empty()) {
cout << q1[i].front() << " ";
q2[q1[i].front()[0] - 'A'].push(q1[i].front()); // 按照花色入队q2
q1[i].pop();
}
cout << endl;
}
int c = 0;
for (int i = 0; i < 4; i++) // 输出q2队列,按照花色
{
char t;
t = (char)i + 'A';
cout << "Queue" << t << ":"; // i+'A'做类型转换
while (!q2[i].empty()) {
cout << q2[i].front() << " ";
newstr[c++] = q2[i].front(); // 将队列q2中的string保存到newstr中
q2[i].pop();
}
cout << endl;
}
for (int i = 0; i < c; i++) // 输出升序排序后的卡牌
cout << newstr[i] << " ";
cout << endl;
return 0;
}有多少种二叉树
输入n(1<n<13),求n个结点的二叉树有多少种形态
时间限制:1000
内存限制:65536
输入
整数n
输出
答案
样例输入
3
样例输出
5
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n, h1 = 1, y = 0;
cin >> n;
for (long long i = 1; i < n + 1; i++) {
y = (4 * i - 2) * h1 / (i + 1);
h1 = y;
}
cout << y;
return 0;
}快速堆猪
小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在那里的猪最轻的是多少斤。
时间限制:1000
内存限制:65536
输入
有三种输入 1)push n n是整数(0<=0 <=20000),表示叠上一头重量是n斤的新猪 2)pop 表示将猪堆顶的猪赶走。如果猪堆没猪,就啥也不干 3)min 表示问现在猪堆里最轻的猪多重。如果猪堆没猪,就啥也不干 输入总数不超过100000条
输出
对每个min输入,输出答案。如果猪堆没猪,就啥也不干
样例输入
pop min push 5 push 2 push 3 min push 4 min
样例输出
2 2
#include <iostream>
using namespace std;
typedef long long LL;
int h[2005];
int size_;
void up(int u) {
while (u / 2 && h[u / 2] > h[u]) {
swap(h[u / 2], h[u]);
u /= 2;
}
}
void down(int u) {
int t = u;
if (u * 2 <= size_ && h[u * 2] < h[u])
t = u * 2;
if (u * 2 + 1 <= size_ && h[u * 2 + 1] < h[u])
t = u * 2 + 1;
if (u != t) {
swap(h[u], h[t]);
down(t);
}
}
int main() {
char t[10];
string s;
int n;
while (scanf("%s", t) != EOF) {
s = string(t);
if (s == "pop") {
if (size_ == 0)
continue;
h[1] = h[size_];
size_--;
down(1);
} else if (s == "min") {
if (size_ == 0)
continue;
cout << h[1] << endl;
} else if (s == "push") {
cin >> n;
size_++;
h[size_] = n;
up(size_);
}
}
return 0;
}小白鼠再排队2
N只小白鼠(1 < N < 100),每只鼠头上戴着一顶有颜色的帽子。现在称出每只白鼠的重量,要求按照白鼠重量从小到大的顺序输出它们头上帽子的颜色。帽子的颜色用 “red”,“blue”等字符串来表示。不同的小白鼠可以戴相同颜色的帽子。白鼠的重量用整数表示。
时间限制:1000
内存限制:65536
输入
输入第一行为一个整数N,表示小白鼠的数目。 下面有N行,每行是一只白鼠的信息。第一个为正整数,表示白鼠的重量,不超过整型范围;第二个为字符串,表示白鼠的帽子颜色,字符串长度不超过10个字符。 注意:白鼠的重量各不相同。
输出
按照白鼠的重量从小到大的顺序输出白鼠的帽子颜色。
样例输入
3 30 red 50 blue 40 green
样例输出
red green blue
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <vector>
using namespace std;
struct sb {
int z;
char s[15];
} a[105];
bool cmp(sb a, sb b) { return a.z < b.z; }
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i].z >> a[i].s;
}
sort(a + 1, a + 1 + n, cmp);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < strlen(a[i].s); j++) {
cout << a[i].s[j];
}
cout << endl;
}
return 0;
}词典
你旅游到了一个国外的城市。那里的人们说的外国语言你不能理解。不过幸运的是,你有一本词典可以帮助你。
时间限制:3000
内存限制:65536
输入
首先输入一个词典,词典中包含不超过100000个词条,每个词条占据一行。每一个词条包括一个英文单词和一个外语单词,两个单词之间用一个空格隔开。而且在词典中不会有某个外语单词出现超过两次。词典之后是一个空行,然后给出一个由外语单词组成的文档,文档不超过100000行,而且每行只包括一个外语单词。输入中出现单词只包括小写字母,而且长度不会超过10。
输出
在输出中,你需要把输入文档翻译成英文,每行输出一个英文单词。如果某个外语单词不在词典中,就把这个单词翻译成“eh”。
样例输入
dog ogday cat atcay pig igpay froot ootfray loops oopslay atcay ittenkay oopslay
样例输出
cat eh loops
提示
输入比较大,推荐使用C语言的I / O函数。
#include <algorithm>
#include <stdio.h>
#include <string.h>
#define MAXSTR 11
#define MAXWORD 100010
using namespace std;
typedef struct {
char foreign[MAXSTR];
char english[MAXSTR];
} m_word;
m_word m_dic[MAXWORD];
int compare(const void *elem1, const void *elem2) {
return strcmp(((m_word *)elem1)->foreign, ((m_word *)elem2)->foreign);
}
int main() {
int count = 0;
char chs[30];
while (fgets(chs, 29, stdin), chs[0] != '\n') {
sscanf(chs, "%s%s", m_dic[count].english, m_dic[count].foreign);
count++;
}
qsort(m_dic, count, sizeof(m_word), compare);
m_word tmp;
m_word *ans;
while (scanf("%s", tmp.foreign) != EOF) {
ans = (m_word *)bsearch(&tmp, m_dic, count, sizeof(m_word), compare);
if (ans != NULL)
printf("%s\n", ans->english);
else
printf("eh\n");
}
return 0;
}夺宝探险
你无意中发现了装满了宝藏的迷宫,你想要获得尽可能多的宝藏,但是迷宫里的机关阻碍了你的计划。迷宫的地面是M行N列的矩形网格,每格是一块带有机关且放置了1个宝藏的地砖,宝藏一共有K种,用1-K表示其种类,迷宫的入口只有一个,为迷宫的第一行第一列。地砖的机关如下:
1. 每次你只能踏到你与你所在地砖相邻的地砖上(即前后左右4块);
2. 当你踏上某块地砖后,其上的宝藏(假设种类为k)自动归属你,同时所有放置了种类为k的宝藏的地砖碎裂,你无法踏上,你当前所在的地砖在你离开后也会立刻碎裂;
3. 当你无路可走的时候,你会被传送回迷宫出口,无法再进入迷宫。
你想知道你最多能获得多少宝藏。
时间限制:1000
内存限制:65536
输入
输入的第一行是三个用空格隔开的整数,分别是M、N和K(1 <= M,N <= 20, 1 <= K <= 100) 之后是M行,每行包含N个范围为1-K的整数,用空格隔开,表示放置的宝藏种类
输出
只有一行,为一个整数,表示最多能获得的宝藏个数。
样例输入
3 4 5 1 2 3 3 2 1 4 3 1 5 1 2
样例输出
4
#include <iostream>
using namespace std;
int m, n, k;
int a[22][22];
bool jewel[101];
int have = 0; // 获得的宝石数
int ans = 0;
int dirx[4] = {0, 0, 1, -1};
int diry[4] = {1, -1, 0, 0};
void dfs(int x, int y) {
for (int i = 0; i < 4; i++) {
int nx = x + dirx[i];
int ny = y + diry[i];
if (!jewel[a[nx][ny]]) {
jewel[a[nx][ny]] = true;
have++;
dfs(nx, ny);
have--;
jewel[a[nx][ny]] = false;
}
}
ans = max(ans, have);
}
int main() {
cin >> m >> n >> k;
int i, j;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
cin >> a[i][j];
jewel[a[1][1]] = true;
jewel[0] = true;
have = 1;
dfs(1, 1);
cout << ans;
return 0;
}晶矿的个数
在某个区域发现了一些晶矿,已经探明这些晶矿总共有分为两类,为红晶矿和黑晶矿。现在要统计该区域内红晶矿和黑晶矿的个数。假设可以用二维地图m[][]来描述该区域,若m[i][j]为#表示该地点是非晶矿地点,若m[i][j]为r表示该地点是红晶矿地点,若m[i][j]为b表示该地点是黑晶矿地点。一个晶矿是由相同类型的并且上下左右相通的晶矿点组成。现在给你该区域的地图,求红晶矿和黑晶矿的个数。
时间限制:1000
内存限制:65536
输入
第一行为k,表示有k组测试输入。 每组第一行为n,表示该区域由n*n个地点组成,3 <= n<= 30 接下来n行,每行n个字符,表示该地点的类型。
输出
对每组测试数据输出一行,每行两个数字分别是红晶矿和黑晶矿的个数,一个空格隔开。
样例输入
2 6 r##bb# ###b## #r##b# #r##b# #r#### ###### 4 #### #rrb #rr# ##bb
样例输出
2 2 1 2
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
char b[N][N + 1];
int n;
void dfs(int r, int c, char type) {
if (r < 0 || r >= n || c < 0 || c >= n)
return;
if (b[r][c] != type)
return;
b[r][c] = '#';
dfs(r - 1, c, type);
dfs(r + 1, c, type);
dfs(r, c - 1, type);
dfs(r, c + 1, type);
}
int main() {
int k;
scanf("%d", &k);
while (k--) {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%s", b[i]);
int rcnt = 0, bcnt = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (b[i][j] == 'r') {
rcnt++;
dfs(i, j, 'r');
} else if (b[i][j] == 'b') {
bcnt++;
dfs(i, j, 'b');
}
printf("%d %d\n", rcnt, bcnt);
}
return 0;
}小白鼠再排队
N只小白鼠(1 < N < 100),每只鼠头上戴着一顶有颜色的帽子。现在称出每只白鼠的重量,要求按照白鼠重量从小到大的顺序输出它们头上帽子的颜色。帽子的颜色用 “red”,“blue”等字符串来表示。不同的小白鼠可以戴相同颜色的帽子。白鼠的重量用整数表示。
时间限制:1000
内存限制:65536
输入
输入第一行为一个整数N,表示小白鼠的数目。 下面有N行,每行是一只白鼠的信息。第一个为正整数,表示白鼠的重量,不超过整型范围;第二个为字符串,表示白鼠的帽子颜色,字符串长度不超过10个字符。 注意:白鼠的重量各不相同。
输出
按照白鼠的重量从小到大的顺序输出白鼠的帽子颜色。
样例输入
3 30 red 50 blue 40 green
样例输出
red green blue
#include <iostream>
using namespace std;
int main() {
int a[100]; // 体重
string b[100]; // 帽子颜色
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> a[i] >> b[i];
for (int i = n - 1; i > 0; i--) // 冒泡排序
for (int j = 0; j < i; j++) {
if (a[j] > a[j + 1]) {
swap(a[j], a[j + 1]);
swap(b[j], b[j + 1]);
}
}
for (int i = 0; i < n; i++)
cout << b[i] << endl;
return 0;
}字符串中最长的连续出现的字符
求一个字符串中最长的连续出现的字符,输出该字符及其出现次数。字符串中无空白字符(空格、回车和tab),如果这样的字符不止一个,则输出出现最早的字符。
时间限制:1000
内存限制:65536
输入
一行,一个不包含空白字符的字符串,字符串长度小于200。
输出
一行,输出最长的连续出现的字符及其最长的连续出现次数,中间以一个空格分开。
样例输入
aaaaadbbbbbcccccccdddddddddd
样例输出
d 10
#include <iostream>
using namespace std;
int main() {
string s;
int n = 1, maxn = 1;
char maxc;
cin >> s;
int len = s.size(); // 字符串长度
maxc = s[0];
for (int i = 1; i < len; i++) {
if (s[i] == s[i - 1]) { // 与前一个字符相同,将n累加
n++;
if (n > maxn) { // 当前字符连续出现次数超过存储的最大值
maxn = n;
maxc = s[i];
}
} else
n = 1;
}
cout << maxc << " " << maxn;
return 0;
}公共子序列
我们称序列Z = < z1, z2, ..., zk >是序列X = < x1, x2, ..., xm >的子序列当且仅当存在 严格上升 的序列< i1, i2, ..., ik >,使得对j = 1, 2, ... ,k, 有xij = zj。比如Z = < a, b, f, c > 是X = < a, b, c, f, b, c >的子序列。 现在给出两个序列X和Y,你的任务是找到X和Y的最大公共子序列,也就是说要找到一个最长的序列Z,使得Z既是X的子序列也是Y的子序列。
时间限制:3000
内存限制:65536
输入
输入包括多组测试数据。每组数据包括一行,给出两个长度不超过200的字符串,表示两个序列。两个字符串之间由若干个空格隔开。
输出
对每组输入数据,输出一行,给出两个序列的最大公共子序列的长度。
样例输入
abcfbc abfcab programming contest abcd mnp
样例输出
4 2 0
#include <bits/stdc++.h>
#include <string>
using namespace std;
int f[1000][1000];
int main() {
string a, b;
while (cin >> a >> b) {
int n = a.size();
int m = b.size();
memset(f, 0, sizeof(f));
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= m; k++) {
if (a[i - 1] == b[k - 1]) {
f[i][k] = max(f[i][k], f[i - 1][k - 1] + 1);
} else {
f[i][k] = max(f[i][k - 1], f[i - 1][k]);
}
}
}
cout << f[n][m] << endl;
}
return 0;
}硬币问题
有N(不大于100)种硬币,编号为1至N,已知每种硬币的重量(不超过100的正整数)和面额(不超过100的正整数),每种硬币数量不限。选取总重量不超过C(不大于1000的正整数)的硬币,最多能获得多少总面额?
时间限制:1000
内存限制:65536
输入
第一行输入N 第二行输入C 第三行输入各硬币重量,用空格隔开 第四行输入各硬币价值,用空格隔开
输出
最大总面额
样例输入
3 5 1 2 5 1 3 6
样例输出
7
#include <bits/stdc++.h>
using namespace std;
int t[105], v[105];
int dp[1005];
int main() {
int n, c;
cin >> n >> c;
for (int i = 1; i <= n; i++)
cin >> t[i];
for (int i = 1; i <= n; i++)
cin >> v[i];
for (int i = 1; i <= n; i++) {
for (int j = t[i]; j <= c; j++) {
dp[j] = max(dp[j], dp[j - t[i]] + v[i]);
}
}
cout << dp[c];
return 0;
}