Scratch编程一级 题库
内部元素之和
输入一个整数矩阵,计算位于矩阵内部的元素之和。所谓矩阵内部的元素,不在第一行和最后一行的元素以及第一列和最后一列的元素。
时间限制: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;
}整数排序
给定10个整数的序列,要求对其重新排序。排序要求:
1.奇数在前,偶数在后;
2.奇数按从大到小排序;
3.偶数按输入顺序逆序排序。
时间限制:1000
内存限制:65536
输入
输入一行,包含10个整数,彼此以一个空格分开,每个整数的范围是大于等于0,小于等于100。
输出
按照要求排序后输出一行,包含排序后的10个整数,数与数之间以一个空格分开。
样例输入
4 7 3 13 11 12 0 47 34 98
样例输出
47 13 11 7 3 98 34 0 12 4
//参考代码1
#include <bits/stdc++.h>
using namespace std;
int main() {
int a[11], b[11];
for (int i = 1; i <= 10; i++) {
cin >> a[i];
b[i] = a[i];
}
sort(a + 1, a + 10 + 1);
for (int i = 10; i >= 1; i--) {
if (a[i] % 2 == 1)
cout << a[i] << " ";
}
for (int i = 10; i >= 1; i--) {
if (b[i] % 2 == 0)
cout << b[i] << " ";
}
return 0;
}//参考代码2
//样例代码
#include <iostream>
#include <algorithm>
using namespace std;
int a[12],b[12];
int main()
{
int t,i,j,k;
j=k=1;
for(int i=1;i<=10;i++){
cin>>t;
if(t%2!=0) a[j++]=t;
else b[k++]=t;
}
sort(a+1,a+j);
for(i=j-1;i>=1;i--) cout<<a[i]<<" ";
for(i=k-1;i>=1;i--) cout<<b[i]<<" ";
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;
}数的输入和输出
输入一个整数和双精度浮点数,先将浮点数保留2位小数输出,然后输出整数。
时间限制:1000
内存限制:65536
输入
一行两个数,分别为整数N(不超过整型范围),双精度浮点数F,以一个空格分开。
输出
一行两个数,分别为保留2位小数输出的F,以及整数N,以一个空格分开。
样例输入
100 123.456789
样例输出
123.46 100
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
float F;
cin >> N >> F;
printf("%.2f", F);
cout << " " << N;
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;
}大写字母的判断
输入一个字符,判断是否是英文大写字母,即是否是A-Z中的一个。
时间限制:1000
内存限制:65536
输入
一个字符。
输出
如果是英文大写字母,则输出YES,否者输出NO。
样例输入
K
样例输出
YES
//解法1
#include <bits/stdc++.h>
using namespace std;
int main() {
char a;
cin >> a;
if ((int)a >= 65 && (int)a <= 91) {
cout << "YES";
} else {
cout << "NO";
}
}//解法2
#include<bits/stdc++.h>
using namespace std;
int main()
{
char c;
cin>>c;
if(c>='A' && c<='Z') cout<<"YES";
else cout<<"NO";
return 0;
}特殊求和
如果一个数能够被7整除或者十进制表示中含有数字7,那么我们称这个数为幻数,比如17,21,73是幻数,而6,59不是。
对于给定的N,求出1~N中所有幻数的和。
时间限制:1000
内存限制:65536
输入
一个整数N(1 < N < 10000)。
输出
一个整数,表示1~N中所有幻数的和。
样例输入
14
样例输出
21
#include <iostream>
using namespace std;
int reversal(int x) {
int remain = 0;
while (x) {
remain = x % 10;
if (remain == 7) {
return true;
}
x = x / 10;
}
return false;
}
int main() {
int N;
int sum = 0;
cin >> N;
for (int i = 1; i <= N; i++) {
if (i % 7 == 0 || reversal(i)) {
sum += i;
}
}
cout << sum;
return 0;
}硬币翻转
假设有N个硬币(N为不大于5000的正整数),从1到N按顺序依次编号,初始时全部处于正面向上的状态;有M个人(M为不大于N的正整数)也从1到M依次编号。
第一个人(1号)将硬币全部翻转一次,第二个人(2号)将编号为2的倍数的硬币翻转一次,第三个人(3号)将编号为3的倍数的硬币翻转一次。依照编号递增顺序,以后的人都和3号一样,将凡是自己编号倍数的硬币翻转一次。
请问:当第M个人操作之后,哪些硬币是正面向上的,按从小到大输出其编号,以空格分开。
时间限制:10000
内存限制:65536
输入
输入正整数N和M,以单个空格隔开。
输出
顺次输出正面向上的硬币的编号,其间用空格间隔。
样例输入
10 10
样例输出
2 3 5 6 7 8 10
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
int n[N] = {0};
for (int i = 1; i <= M; i++) {
for (int j = 0; j < N; j++) {
if ((j + 1) % i == 0) {
if (n[j] == 0) {
n[j] = 1;
} else {
n[j] = 0;
}
}
}
}
for (int i = 0; i < N; i++) {
if (n[i] == 0) {
cout << i + 1 << " ";
}
}
}生日相同 2.0
在一个有180人的大班级中,存在两个人生日相同的概率非常大,现给出每个学生的名字,出生月日。试找出所有生日相同的学生。
时间限制:1000
内存限制:65536
输入
第一行为整数n,表示有n个学生,n ≤ 180。此后每行包含一个字符串和两个整数,分别表示学生的名字(名字第一个字母大写,其余小写,不含空格,且长度小于20)和出生月(1 ≤ m ≤ 12)日(1 ≤ d ≤ 31)。名字、月、日之间用一个空格分隔
输出
每组生日相同的学生,输出一行,其中前两个数字表示月和日,后面跟着所有在当天出生的学生的名字,数字、名字之间都用一个空格分隔。对所有的输出,要求按日期从前到后的顺序输出。 对生日相同的名字,按名字从短到长按序输出,长度相同的按字典序输出。如没有生日相同的学生,输出”None”
样例输入
6 Avril 3 2 Candy 4 5 Tim 3 2 Sufia 4 5 Lagrange 4 5 Bill 3 2
样例输出
3 2 Tim Bill Avril 4 5 Candy Sufia Lagrange
#include <bits/stdc++.h>
using namespace std;
struct student {
char name[21];
int m;
int d;
};
int comp(const student &a, const student &b) {
if (a.m < b.m)
return 1;
if (a.m > b.m)
return 0;
if (a.d < b.d)
return 1;
if (a.d > b.d)
return 0;
if (strlen(a.name) < strlen(b.name))
return 1;
if (strlen(a.name) > strlen(b.name))
return 0;
if (strcmp(a.name, b.name) < 0)
return 1;
if (strcmp(a.name, b.name) > 0)
return 0;
return 0;
}
int main() {
int b[13][32] = {0};
int n;
bool bl = false;
student a[181];
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%s%d%d", &a[i].name, &a[i].m, &a[i].d);
}
sort(a + 1, a + n + 1, comp);
for (int i = 1; i <= n; ++i) {
b[a[i].m][a[i].d]++;
}
for (int i = 1; i <= 12; ++i) {
for (int k = 1; k <= 31; ++k) {
if (b[i][k] > 1) {
printf("%d %d ", i, k);
for (int j = 1; j <= n; ++j) {
if (a[j].m == i && a[j].d == k)
printf("%s ", a[j].name);
}
printf("\n");
bl = true;
}
}
}
if (bl == false)
printf("None");
return 0;
}机器翻译
VariantF的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。这个翻译软件的原理很简单,它只是从头到尾,依次将每个英文单词用对应的中文含义来替换。对于每个英文单词,软件会先在内存中查找这个单词的中文含义,如果内存中有,软件就会用它进行翻译;如果内存中没有,软件就会在外存中的词典内查找,查出单词的中文含义然后翻译,并将这个单词和译义放入内存,以备后续的查找和翻译。
假设内存中有M 个单元,每单元能存放一个单词和译义。每当软件将一个新单词存入内存前,如果当前内存中已存入的单词数不超过M,软件会将新单词存入一个未使用的内存单元;若内存中已存入M 个单词,软件会清空最早进入内存的那个单词,腾出单元来,存放新单词。
假设一篇英语文章的长度为N 个单词。给定这篇待译文章,翻译软件需要去外存查找多少次词典?假设在翻译开始前,内存中没有任何单词。
时间限制:1000
内存限制:262144
输入
第一行为两个正整数M 和N,代表内存容量和文章的长度。 第二行为N 个非负整数,按照文章的顺序,每个数(大小不超过1000000)代表一个英文单词。文章中两个单词是同一个单词,当且仅当它们对应的非负整数相同。 对于50%的数据,1<=N、M<=1000; 对于100%的数据,1<=N、M<=1000000。
输出
一个整数,为软件需要查词典的次数。
样例输入
3 7 1 2 1 5 4 4 1
样例输出
5
提示
整个查字典过程如下:每行表示一个单词的翻译,冒号前为本次翻译后的内存状况: 空:内存初始状态为空。 1. 1:查找单词1 并调入内存。 2. 1 2:查找单词2 并调入内存。 3. 1 2:在内存中找到单词1。 4. 1 2 5:查找单词5 并调入内存。 5. 2 5 4:查找单词4 并调入内存替代单词1。 6. 2 5 4:在内存中找到单词4。 7. 5 4 1:查找单词1 并调入内存替代单词2。 共计查了5 次词典。
#include <cstdio>
int word[2000];
bool sch(int tgt, int range) // 线性搜索,因为数据<1000,不会超时。
{
for (int i = 0; i < range; i++) {
if (word[i] == tgt) {
return true;
}
}
return false;
}
int main() {
int mem, num, tm, wor, ans = 0;
scanf("%d %d", &mem, &num);
tm = 0;
for (int i = 0; i < 2000; i++) {
word[i] = -1; // 数组初始化一定要初始化成-1!!!!
// 字母代号有可能是0,所以初始化成0会出错!!!!
}
for (int i = 0; i < num; i++) {
scanf("%d", &wor);
// 非常节省空间和时间的模拟
if (tm >= mem) {
tm = 0;
}
if (!sch(wor, mem)) {
// 自己进行轮回。。。
ans++;
word[tm] = wor;
tm++;
}
}
printf("%d", ans);
}括号画家
Candela是一名漫画家,她有一个奇特的爱好,就是在纸上画括号。这一天,刚刚起床的Candela画了一排括号序列,其中包含小括号()、中括号[]和大括号{},总长度为N。这排随意绘制的括号序列显得杂乱无章,于是Candela定义了什么样的括号序列是美观的:
(1) 空的括号序列是美观的;
(2) 若括号序列A是美观的,则括号序列(A)、[A]、{A}也是美观的;
(3) 若括号序列A、B都是美观的,则括号序列AB也是美观的;
例如 [(){}]() 是美观的括号序列,而 )({)[}]( 则不是。
现在Candela想知道她画出的括号序列是不是美观的。你能帮帮她吗?
时间限制:1000
内存限制:262144
输入
一个括号序列,长度不超过10000。
输出
如果它是美观的,输出Yes,否则输出No。
样例输入
{}[(){}]()样例输出
Yes
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;
stack<char> str;
// 判断左右两个括号是否美观
bool beauty(char s1, char s2) {
switch (s1) {
case '{':
if (s2 == '}')
return true;
else
return false;
case '[':
if (s2 == ']')
return true;
else
return false;
case '(':
if (s2 == ')')
return true;
else
return false;
}
}
int main() {
string Brackets;
char s;
int i = 0;
cin >> Brackets;
while (i < Brackets.length()) {
s = Brackets[i];
i++;
str.push(s); // 将当前字符入栈
char s2 = str.top();
if (s2 == ']' || s2 == '}' ||
s2 == ')') // 是右括号,进行判断是否与左括号美观
{
str.pop(); // 将s2出栈
if (str.empty()) { // 无左括号,肯定不美观
cout << "No" << endl;
return 0;
}
char s1 = str.top(); // s1是左括号
if (beauty(s1, s2)) { // 美观,将s1出栈
str.pop();
} else { // 不美观
cout << "No" << endl;
return 0;
}
}
}
cout << "Yes";
}中缀表达式的值
人们熟悉的四则运算表达式称为中缀表达式,例如(23+34*45/(5+6+7))。在程序设计语言中,可以利用堆栈的方法把中缀表达式转换成保值的后缀表达式(又称逆波兰表示法),并最终变为计算机可以直接执行的指令,得到表达式的值。 给定一个中缀表达式,编写程序,利用堆栈的方法,计算表达式的值。
时间限制:200
内存限制:65536
输入
第一行为测试数据的组数N 接下来的N行,每行是一个中缀表达式。表达式中只含数字、四则运算符和圆括号,操作数都是正整数,数和运算符、括号之间没有空格。中缀表达式的字符串长度不超过600。
输出
对每一组测试数据输出一行,为表达式的值
样例输入
3 3+5*8 (3+5)*8 (23+34*45/(5+6+7))
样例输出
43 64 108
提示
注意:运算过程均为整数运算(除法运算'/'即按照C++定义的int除以int的结果,测试数据不会出现除数为0的情况),输出结果也为整数(可能为负)。 中间计算结果可能为负。
#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] >= '0' && s[i] <= '9')
t += s[i];
else if (ops.find(s[i]) != string::npos) {
if (t.size() > 0)
ans.push_back(t);
t = s[i];
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;
int n;
cin >> n;
while (n--) {
cin >> s;
vector<string> vs = scaner(s);
vs = infix_Suffix(vs);
suffix_calc(vs);
}
return 0;
}最小新整数
给定一个十进制正整数n(0 < n < 1000000000),每个数位上数字均不为0。n的位数为m。 现在从m位中删除k位(0<k < m),求生成的新整数最小为多少? 例如: n = 9128456, k = 2, 则生成的新整数最小为12456
时间限制:1000
内存限制:65536
输入
第一行t, 表示有t组数据; 接下来t行,每一行表示一组测试数据,每组测试数据包含两个数字n, k。
输出
t行,每行一个数字,表示从n中删除k位后得到的最小整数。
样例输入
2 9128456 2 1444 3
样例输出
12456 1
#include <stdio.h>
#include <string.h>
int main() {
int t, k;
char a[200];
scanf("%d", &t);
while (t--) {
int i, j, l;
scanf("%s %d", a, &k);
int len = strlen(a);
for (i = 0; i < k; i++) {
for (j = 0; j < len - 1; j++) {
if (a[j] > a[j + 1]) {
for (l = j; l < len - 1; l++) {
a[l] = a[l + 1];
}
break;
}
}
len -= 1;
}
for (i = 0; i < strlen(a) - k; i++) {
if (i == 0 && a[i] == '0') {
continue;
}
printf("%d", a[i] - '0');
}
printf("\n");
}
}求逆序对数
对于一个长度为N的整数序列A,满足i < j 且 Ai > Aj.的数对(i,j)称为整数序列A的一个逆序
请求出整数序列A的所有逆序对个数
时间限制:500
内存限制:65536
输入
输入包含多组测试数据,每组测试数据有两行 第一行为整数N(1 <= N <= 20000),当输入0时结束 第二行为N个整数,表示长为N的整数序列
输出
每组数据对应一行,输出逆序对的个数
样例输入
5 1 2 3 4 5 5 5 4 3 2 1 1 1 0
样例输出
0 10 0
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
int m;
cin >> m;
while (m != 0) {
int a[20005] = {0};
for (int i = 0; i < m; i++) {
cin >> a[i];
}
int count = 0;
for (int i = 1; i < m; i++) {
for (int j = m - 1; j >= i; j--) {
if (a[j] < a[j - 1]) {
count++;
int t = a[j];
a[j] = a[j - 1];
a[j - 1] = t;
}
}
}
cout << count << endl;
cin >> m;
}
return 0;
}密室逃脱
小Y喜欢玩密室逃脱,每次游戏开始时,小Y会进入一个密室,她需要按照顺序解开各个隐藏线索才能成功逃脱密室。小Y非常聪明,解开线索对她来说并不难,但是她有一点懒,她希望在通关过程中移动次数最少。请你帮小Y计算她至少要移动多少次才能成功通关。
密室是m行n列的格子矩阵,小Y从左上角(1,1)进入密室,密室中有三种格子:
墙,以数字0标记
路,以数字1标记
隐藏线索处,以数字( > 1)标记, 代表该线索的难度
小Y需要按照难度递增的顺序解开各个线索,逃脱密室。
时间限制:1000
内存限制:65536
输入
第一行是一个整数 T,表示输入包含 T 组数据,分别是不同的游戏中小Y所处的密室。 对于每组数据,第一行包括两个整数:m(1 <= m <= 100)、n(1 <= n <= 100)。 接下来 m 行,每行有n个数字,第 i 行的第 j 个数字表示密室中第 i 行第 j 列的格子的类型。 题目保证进入密室处(1,1)不是墙壁,线索的难度都不相同。
输出
对于每组数据,你需要输出一个整数,表示小Y在这个密室中至少要移动多少次才能成功通关。 如果小Y不可能解开所有线索,输出-1.
样例输入
2 3 3 1 3 2 1 0 4 10 6 5 3 3 1 3 2 0 0 0 10 6 5
样例输出
8 -1
提示
样例解释:由于需要按难度顺序解开线索,在第一组数据中,小Y第一次移动到3时不能解密,在完成2之后需要回到3.最后小Y解开10时,她成功通关。
//示例代码 条件+广搜
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int m,n;
int maze[104][104] = {};
int dx[4] = {0,0,-1,1};
int dy[4] = {-1,1,0,0};
bool legal(int x, int y){
if(0 <= x && x< m && 0 <= y && y < n && maze[x][y] != 0)return 1;
return 0;
}
struct Node{
int x, y, k, t;
};
int main()
{
int T;
cin >> T;
while(T--){
memset(maze, 0, sizeof(maze));
int vis[104][104] = {};
memset(vis, 0xff, sizeof(vis));
int S[10050] = {};
int cnt = 0;
cin >> m >> n;
for(int i = 0; i < m; ++i){
for(int j = 0; j < n; ++j){
cin >> maze[i][j];
if (maze[i][j] > 1) {
S[cnt++] = maze[i][j];
}
}
}
queue<Node> open;
sort(S, S + cnt);
if (maze[0][0] == S[0]) {
open.push({0, 0, 1, 0});
vis[0][0] = 1;
}
else {
open.push({0, 0, 0, 0});
vis[0][0] = 0;
}
bool flag = 0;
while (!open.empty()) {
Node temp = open.front();
open.pop();
if (temp.k == cnt) {
flag = 1;
cout << temp.t << endl;
break;
}
for (int i = 0; i < 4; i++) {
int x = temp.x + dx[i], y = temp.y + dy[i], k = temp.k;
if (!legal(x,y)) continue;
if (maze[x][y] == S[k]) k++;
if (vis[x][y] >= k) continue;
vis[x][y] = k;
open.push({x, y, k, temp.t + 1});
}
}
if (!flag) cout << -1 << endl;
}
return 0;
}红与黑
有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上,只能向相邻的黑色瓷砖移动。请写一个程序,计算你总共能够到达多少块黑色的瓷砖。
时间限制:1000
内存限制:65536
输入
包括多个数据集合。每个数据集合的第一行是两个整数W和H,分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中,每行包括W个字符。每个字符表示一块瓷砖的颜色,规则如下 1)‘.’:黑色的瓷砖; 2)‘#’:白色的瓷砖; 3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。 当在一行中读入的是两个零时,表示输入结束。
输出
对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
样例输入
6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 0 0
样例输出
45
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int N = 25;
int n, m;
int x, y;
char ct[N][N];
bool num[N][N];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int dfs(int x, int y) {
int ans = 1;
num[x][y] = true;
for (int i = 0; i < 4; i++) {
int x1 = dx[i] + x;
int y1 = dy[i] + y;
if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= m)
continue;
if (ct[x1][y1] == '#')
continue;
if (num[x1][y1] == true)
continue;
ans = ans + dfs(x1, y1);
}
return ans;
}
int main() {
while (scanf("%d%d", &m, &n) != EOF) {
if (m == 0 && n == 0)
break;
for (int i = 0; i < n; i++) {
scanf("%s", ct[i]);
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j < m; j++) {
if (ct[i][j] == '@') {
x = i;
y = j;
}
}
}
cout << dfs(x, y) << endl;
memset(num, 0, sizeof num);
}
return 0;
}酒鬼
Santo刚刚与房东打赌赢得了一间在New Clondike 的大客厅。今天,他来到这个大客厅欣赏他的奖品。房东摆出了一行瓶子在酒吧上。瓶子里都装有不同体积的酒。令Santo高兴的是,瓶子中的酒都有不同的味道。房东说道:“你可以喝尽可能多的酒,但是一旦打开酒盖你就必须把它喝完,喝完一瓶后把它放回原处。还有一件最重要的事,你必须从左至右依次喝,并且不能连续超过三瓶,不然会给你带来坏运气。”现在可怜的Santo站在酒吧前努力的想着,他到底应该喝哪几瓶才能使喝的酒最多呢?请帮助他找出他应该喝的酒瓶号,因为思考让他感到不安。
时间限制:2000
内存限制:131072
输入
第一行一个整数N,有N个酒瓶。N<=700接下有N行,第I+1行的数字代表酒瓶I中酒的体积。
输出
一个数字,喝的酒的最大总体积。遵守以上规则,使得三个连续瓶子中至少一个瓶子是满的。
样例输入
6 6 10 13 9 8 1
样例输出
33
#include <bits/stdc++.h>
using namespace std;
int f[701][5];
int main() {
int n;
int a[1000];
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
f[i][0] = f[i - 1][3];
int mx = f[i][0];
for (int j = 1; j <= 2; j++) {
f[i][j] = f[i - 1][j - 1] + a[i];
mx = max(mx, f[i][j]);
}
f[i][3] = mx;
}
cout << f[n][3];
return 0;
}// 参考答案2 递推
#include <bits/stdc++.h>
using namespace std;
int n, a[10005], dp[10005][2];
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
dp[1][0] = 0; // 第一瓶没喝
dp[1][1] = a[1]; // 第一瓶喝了
for (int i = 2; i <= n; i++) {
// 第i瓶没喝=max(i-1瓶没喝,i-1瓶喝了)
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
// 第i瓶喝了=max(i-1瓶没喝,i-2瓶没喝+i-1瓶喝了)
dp[i][1] = a[i] + max(dp[i - 1][0], dp[i - 2][0] + a[i - 1]);
}
cout << max(dp[n][0], dp[n][1]);
return 0;
}重启系统
小明帮助管理一个处理数据的计算系统,有N个待处理的任务,需要按照顺序来完成这些任务,即每次所完成任务的编号都要大于前一个完成任务的编号,且单个任务不可以分解完成。计算系统运行着一个奇怪的保护程序,它限制了系统当前所能处理的数据量不能超过上次完成任务所处理的数据量。重启系统可以使它立刻恢复到最高性能(一开始系统拥有最高性能,最高性能大于任何待处理任务的数据量)。小明有一次重启系统的权限(也可以不使用),你能帮他算出最多能完成几个任务吗?
时间限制:1000
内存限制:65536
输入
第一行: N (2 <= N <= 1000) 待处理的任务数 第二行: N个整数,每个任务的数据量
输出
输出只包括一行,这一行只包含一个整数,表示最多能完成的任务数。
样例输入
10
1 5 4 3 2 10 9 8 7 6
样例输出
9
提示
回想一下最长上升子序列问题
#include <bits/stdc++.h>
using namespace std;
int dpleft[10005], dpright[10005], a[10005];
int n;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
dpright[i] = dpleft[i] = 1;
}
reverse(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (a[i] >= a[j]) {
dpleft[i] = max(dpleft[i], dpleft[j] + 1);
}
}
}
for (int i = 2; i <= n; i++) {
dpleft[i] = max(dpleft[i - 1], dpleft[i]);
}
// for(int i = 1; i <= n; i++){
// printf("%d = %d\n", i, dpleft[i]);
// }
for (int i = n - 1; i >= 1; i--) {
for (int j = n; j > i; j--) {
if (a[i] <= a[j]) {
dpright[i] = max(dpright[i], dpright[j] + 1);
}
}
}
for (int i = n - 1; i >= 1; i--) {
dpright[i] = max(dpright[i], dpright[i + 1]);
}
int ans = 0;
for (int x = 1; x <= n; x++) {
ans = max(ans, dpleft[x] + dpright[x + 1]);
}
// printf("---------\n");
// for(int i = 1; i <= n; i++){
// printf("%d = %d\n", i, dpright[i]);
// }
printf("%d\n", ans);
return 0;
}鸣人的影分身
在火影忍者的世界里,令敌人捉摸不透是非常关键的。我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。
影分身是由鸣人身体的查克拉能量制造的,使用的查克拉越多,制造出的影分身越强。
针对不同的作战情况,鸣人可以选择制造出各种强度的影分身,有的用来佯攻,有的用来发起致命一击。
那么问题来了,假设鸣人的查克拉能量为M,他影分身的个数为N,那么制造影分身时有多少种(用K表示)不同的分配方法?(影分身可以被分配到0点查克拉能量)
时间限制:1000
内存限制:65536
输入
第一行是测试数据的数目t(0 <= t <= 20)。以下每行均包含二个整数M和N,以空格分开。1 <= M,N <= 10。
输出
对输入的每组数据M和N,用一行输出相应的K。
样例输入
1 7 3
样例输出
8
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 11;
int n, m;
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &m, &n);
int f[N][N] = {0};
f[0][0] = 1;
for (int i = 0; i <= m; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = f[i][j - 1];
if (i >= j)
f[i][j] += f[i - j][j];
}
}
printf("%d\n", f[m][n]);
}
return 0;
}
宠物小精灵之收服
宠物小精灵是一部讲述小智和他的搭档皮卡丘一起冒险的故事。
一天,小智和皮卡丘来到了小精灵狩猎场,里面有很多珍贵的野生宠物小精灵。小智也想收服其中的一些小精灵。然而,野生的小精灵并不那么容易被收服。对于每一个野生小精灵而言,小智可能需要使用很多个精灵球才能收服它,而在收服过程中,野生小精灵也会对皮卡丘造成一定的伤害(从而减少皮卡丘的体力)。当皮卡丘的体力小于等于0时,小智就必须结束狩猎(因为他需要给皮卡丘疗伤),而使得皮卡丘体力小于等于0的野生小精灵也不会被小智收服。当小智的精灵球用完时,狩猎也宣告结束。
我们假设小智遇到野生小精灵时有两个选择:收服它,或者离开它。如果小智选择了收服,那么一定会扔出能够收服该小精灵的精灵球,而皮卡丘也一定会受到相应的伤害;如果选择离开它,那么小智不会损失精灵球,皮卡丘也不会损失体力。
小智的目标有两个:主要目标是收服尽可能多的野生小精灵;如果可以收服的小精灵数量一样,小智希望皮卡丘受到的伤害越小(剩余体力越大),因为他们还要继续冒险。
现在已知小智的精灵球数量和皮卡丘的初始体力,已知每一个小精灵需要的用于收服的精灵球数目和它在被收服过程中会对皮卡丘造成的伤害数目。请问,小智该如何选择收服哪些小精灵以达到他的目标呢?
时间限制:1000
内存限制:65536
输入
输入数据的第一行包含三个整数:N(0 < N < 1000),M(0 < M < 500),K(0 < K < 100),分别代表小智的精灵球数量、皮卡丘初始的体力值、野生小精灵的数量。 之后的K行,每一行代表一个野生小精灵,包括两个整数:收服该小精灵需要的精灵球的数量,以及收服过程中对皮卡丘造成的伤害。
输出
输出为一行,包含两个整数:C,R,分别表示最多收服C个小精灵,以及收服C个小精灵时皮卡丘的剩余体力值最多为R。
样例输入
样例输入1:
10 100 5 7 10 2 40 2 50 1 20 4 20
样例输入2:
10 100 5 8 110 12 10 20 10 5 200 1 110
样例输出
样例输出1:
3 30
样例输出2:
0 100
提示
对于样例输入1:小智选择:(7,10) (2,40) (1,20) 这样小智一共收服了3个小精灵,皮卡丘受到了70点伤害,剩余100-70=30点体力。所以输出3 30 对于样例输入2:小智一个小精灵都没法收服,皮卡丘也不会收到任何伤害,所以输出0 100
#include <bits/stdc++.h>
#define N 5000
using namespace std;
int f[N][N];
int n, m, k;
int a[N], b[N], c[N];
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= k; i++) {
cin >> a[i] >> b[i];
}
for (int i = 1; i <= k; i++) {
for (int j = n; j >= a[i]; j--) {
for (int l = m; l >= b[i]; l--)
f[j][l] = max(f[j][l], f[j - a[i]][l - b[i]] + 1);
}
}
int ans;
for (ans = 0; ans <= m; ans++) {
if (f[n][ans] == f[n][m])
break;
}
printf("%d %d\n", f[n][m], m - ans);
return 0;
}