http://aihigh.cn

3.3皂皮书低级组模拟题 2
3.3.1 求和
输入一个正整数 N&#Vff08;1<N<20000&#Vff09;&#Vff0c;输出 1 到 N 之间所有正整数的和&#Vff08;包孕 1
和 N&#Vff09;。
输入形容&#Vff1a;输入一个正整数 N&#Vff08;1<N<20000&#Vff09;。
输出形容&#Vff1a;输出 1 到 N 之间所有正整数的和&#Vff08;包孕 1 和 N&#Vff09;。
【样例输入】3
【样例输出】6
#include<iostream>
using namespace std;
int main() {
int n, i, sum = 0;
cin >> n;
for (i = 1; i <= n; i++) {
sum = sum + i;
}
cout << sum;
第 92 页 共 256 页
return 0;
}
3.3.2 统计次数
输入一段英文&#Vff08;包孕字母和“.”&#Vff09;&#Vff0c;划分统计出那段英笔朱符串共有几多多个字符
&#Vff08;包孕字母和“.”&#Vff09;及“.”显现的次数。
输入形容&#Vff1a;输入一段英笔朱符串&#Vff08;字符串长度<100&#Vff09;。
输出形容&#Vff1a;第一止输出字符总个数&#Vff1b;第二止输出“.”正在那段英笔朱符串中显现的次
数。
【样例输入】
aaa. 【样例输出】
4
1
办法一、了解题目问题为 一段英文只包孕字母和“.”。
#include<iostream>
#include<cstring>
using namespace std;
int main() {
string s;
cin >> s; //不能完好读入带空格字符串
int len, cnt = 0;
len = s.size();
for (int i = 0; i < len; i++) {
if (s[i] == '.') {
cnt++;
}
}
cout << len << endl << cnt;
return 0;
}
//办法二、思考输入内容不只仅包孕字母和“.”&#Vff1a;
#include<iostream>
#include<cstring>
第 93 页 共 256 页
using namespace std;
int main() {
string s;
getline(cin, s);
int len, cnt1 = 0, cnt2 = 0;
len = s.size();
for (int i = 0; i < len; i++) {
if ((s[i] >= 'A' && s[i] <= 'Z') || (s[i] >= 'a' && s[i] <= 'z')) {
cnt1++;
}
if (s[i] == '.') {
cnt2++;
}
}
cout << cnt1 + cnt2 << endl;
cout << cnt2;
return 0;
}
3.3.3 牌序
间断输入 5 个正整数&#Vff08;0<正整数<1001&#Vff09;&#Vff0c;正整数之间以一个空格离隔&#Vff0c;而后
将那五个正整数依照从大到小的顺序输出&#Vff08;输出的正整数之间以一个英文逗号离隔&#Vff09;。
输入形容&#Vff1a;间断输入 5 个正整数&#Vff08;0<正整数<1001&#Vff09;划分以一个空格离隔。
输出形容&#Vff1a;依照从大到小的顺序输出且每个正整数之间用一个英文逗号离隔。
【样例输入】
3 2 5 5 4
【样例输出】
5,5,4,3,2
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
int a[5];
for (int i = 0; i < 5; i++) {
cin >> a[i];
第 94 页 共 256 页
}
sort(a, a + 5); //默许从小到大牌序
cout << a[4]; //先输出第一个数前面没有分隔断绝结合符
for (int i = 3; i >= 0; i--)
cout << "," << a[i];
return 0;
}
3.3.4 最大折同数 最小公倍数
1、倍数取约数&#Vff1a;假如 a 能被 b 整除&#Vff0c;a 就叫作 b 的倍数&#Vff0c;b 就叫作 a 的约数。
约数和倍数都默示一个整数取另一个整数的干系&#Vff0c;不能径自存正在。
2、最大折同数&#Vff1a;几多个整数中公有的约数&#Vff0c;叫作那几多个数的折同数&#Vff1b;此中最大的一个&#Vff0c;
叫作那几多个数的最大折同数。举例&#Vff1a;12、16 的折同数有 1、2、4&#Vff0c;
此中最大的一个是 4&#Vff0c;所以 4 是 12 取 16 的最大折同数。
3、最小公倍数&#Vff1a;几多个作做数公有的倍数&#Vff0c;叫作那几多个数的公倍数&#Vff0c;此中最小的一个&#Vff0c;
叫作那几多个数的最小公倍数。举例&#Vff1a;4 的倍数有 4、8、12、16&#Vff0c;……&#Vff0c;
6 的倍数有 6、12、18、24&#Vff0c;……&#Vff0c;4 和 6 的公倍数有 12、24&#Vff0c;……&#Vff0c;此中最小的
是 12&#Vff0c;所以 4 和 6 最小公倍数为 12。
划分输入两个正整数&#Vff08;1<正整数<201&#Vff09;&#Vff0c;输出那两个正整数的最大折同数 M 及最
小公倍数 N&#Vff08;注&#Vff1a;M 和 N 输出到一止,之间以一个英文逗号离隔&#Vff09;。
输入形容&#Vff1a;第一止输入第一个正整数&#Vff1b;第二止输入第二个正整数。
输出形容&#Vff1a;输出那两个正整数的最大折同数 M 及最小公倍数 N&#Vff08;M 和 N 输出
到一止&#Vff0c;之间以一个英文逗号离隔&#Vff09;。
【样例输入】
4
6
【样例输出】
2,12
办法一&#Vff1a;先求最小公倍数
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int m, n, i = 1, gbc;
cin >> m >> n;
第 95 页 共 256 页
if (m < n)
swap(m, n);
while (m * i % n != 0) {
i++;
}
gbc = m * i;
cout << m*n / gbc << "," << gbc;
//依据公式计较 最大折同数=两整数的乘积 ÷最小公倍数
//留心要用括号扭转计较劣先级
return 0;
}
办法二&#Vff1a;辗转相除法 求最大折同
#include<iostream>
using namespace std;
int gys(int V, int y) { //辗转相除法
if (y == 0) {
return V;
}
return gys(y, V % y);
}
int main() {
int n, m;
cin >> n >> m;
cout << gys(n, m) << ',' << n*m / a(n, m);
return 0;
}
3.4皂皮书中级组模拟题 2
3.4.1 求和
输入一个正整数 N&#Vff08;N<100&#Vff09;&#Vff0c;输出 1 到 N&#Vff08;包孕 1 和 N&#Vff09;之间所有奇数的
和。
输入形容&#Vff1a;输入一个正整数 N&#Vff08;N<100&#Vff09;。
输出形容&#Vff1a;输出 1 到 N 之间所有奇数的和。
第 96 页 共 256 页
【样例输入】
3
【样例输出】
4
#include<iostream>
using namespace std;
int main() {
int n, i, sum = 0;
cin >> n;
for (i = 1; i <= n; i = i + 2) {
sum = sum + i;
}
cout << sum;
return 0;
}
3.4.2 求平方
平方是一种运算&#Vff0c;比如&#Vff1a;a 的平方默示 a×a。
譬喻:2 的平方为 4&#Vff08;也便是 2*2 的积&#Vff09;。
譬喻:4 的平方为 16&#Vff08;也便是 4*4 的积&#Vff09;。
输入一个正整数 N&#Vff08;N<30&#Vff09;&#Vff0c;输出 1 到 N&#Vff08;包孕 1 和 N&#Vff09;之间所有正整数的平
方&#Vff0c;且所输出的平方数之间以英文逗号离隔。
输入形容&#Vff1a;输入一个正整数 N&#Vff08;N<30&#Vff09;。
输出形容&#Vff1a;输出 1 到 N 之间所有正整数的平方数&#Vff0c;且所输出的平方数之间以英文逗
号离隔。
【样例输入】
3
【样例输出】
1,4,9
#include<iostream>
using namespace std;
int main() {
int i, n;
cin >> n;
for (i = 1; i <= n; i++)
第 97 页 共 256 页
if (i == 1) cout << 1; //逗号的办理
else cout << "," << i*i;
return 0;
}
3.4.3 数位递删数
一个正整数假如任何一个数位小于就是右边相邻的数位&#Vff0c;则称为一个数位递
删数。
譬喻&#Vff1a;
1135 是一个数位递删数。
1024 不是一个数位递删数。
输入一个正整数 n&#Vff08;10<n<10001&#Vff09;&#Vff0c;输出 10 到 n &#Vff08;包孕 10 和 n&#Vff09;中有几多多个
数位递删数。
输入形容&#Vff1a;输入一个正整数 n&#Vff08;10<n<10001&#Vff09;。
输出形容&#Vff1a;输出 10 到 n 中有几多多个数位递删数。
【样例输入】
15
【样例输出】
5
【上述输入输出样例的进一步评释】
用户输入的正整数&#Vff0c;即样例输入为 15&#Vff0c;10 到 15 之间的数位递删数有&#Vff1a;11、
12、13、14、15。所以样例输出为 5。
#include<iostream>
using namespace std;
int main() {
int n, cnt = 0;
int g, s, b, q;
cin >> n;
//10<n<10001 n 包孕 10000 但分比方乎条件 所以最大枚举 9999 四位数
for (int i = 10; i <= n; i++) {
g = i % 10;
s = i / 10 % 10;
b = i / 100 % 10; //两位数 b=0 不映响判断
q = i / 1000 % 10;
if (g >= s && s >= b && b >= q) {
第 98 页 共 256 页
cnt++;
}
}
cout << cnt;
return 0;
}
3.4.4 最短距离&#Vff08;蛇形填数&#Vff09;
有一个居民小区的楼房全是一样的&#Vff0c;并且按矩阵花式布列。其楼房的编号为
1&#Vff0c;2&#Vff0c;3...&#Vff0c;当牌满一止时&#Vff0c;从下一止相邻的楼往反标的目的牌号。
譬喻&#Vff1a;小区为 3 止 6 列&#Vff0c;矩阵布列方式&#Vff1a;
要求&#Vff1a;已知小区楼房有 w 列及两个楼房楼号 m 和 n&#Vff0c;求从 m 号楼到 n 号楼之
间的最短道路颠终几多个楼&#Vff08;不能斜线标的目的挪动&#Vff09;。
譬喻上图&#Vff1a;当 w=6&#Vff0c;m=8&#Vff0c;n=2&#Vff0c;从 8 号楼到 2 号楼最短的道路颠终 5&#Vff0c;4&#Vff0c;
3&#Vff0c;2 四个楼&#Vff08;9&#Vff0c;10&#Vff0c;11&#Vff0c;2 也颠终四个楼&#Vff09;&#Vff0c;故最短道路为 4&#Vff08;注&#Vff1a;不思考
道路只思考最短道路颠终几多个楼&#Vff09;。
输入三个正整数 w&#Vff08;1<w<21&#Vff09;&#Vff0c;m&#Vff08;1<m<10001&#Vff09;&#Vff0c;n&#Vff08;1<n<10001&#Vff09;&#Vff0c;且 m 不
就是 n。三个正整数之间以一个空格离隔&#Vff0c;输出 m 到 n 的最短道路颠终几多个
楼。
输入形容&#Vff1a;正在一止输入三个正整数 w&#Vff0c;m&#Vff0c;n&#Vff0c;三个正整数之间以一个空格隔
开。
输出形容&#Vff1a;输出 m 到 n 的最短道路颠终几多个楼。
【样例输入】
6 8 2
【样例输出】
4
第 99 页 共 256 页
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int a[30][30];
int main(){
int w,m,n,s=1,V1,y1,V2,y2;
cin>>w>>m>>n;
for(int i=1;i<=w;i++){
if(i%2!=0){
for(int j=w;j>=1;j--){
a[i][j]=s++;
}
}else{
for(int j=0;j<w;j++){
a[i][j]=s++;
}
}
}
for(int i=1;i<=w;i++){
for(int j=1;j<=w;j++){
if(a[i][j]==m){
第 100 页 共 256 页
V1=i;
y1=j;
}
if(a[i][j]==n){
V2=i;
y2=j;
}
}
}
cout<<abs((V1+y1)-(y1+y2))+1;
return 0;
}
#include<bits/stdc++.h>
using namespace std; //6 20 80
int main() {
int w,m,n,k=1,L;
int i,j,i1=0,j1=0,i2=0,j2=0;
cin >> w>>m>>n;
L=maV(m,n)/w+1;
int a[w+1][L+1]={};
for(i=1;i<=L;i++){
for(j=1;j<=w;j++){
if(i%2==1){
第 101 页 共 256 页
a[i][j]=(i-1)*6+j;
}
else
{
a[i][j]=i*6+1-j;
}
}
}
for(i=1;i<=L;i++){
for(j=1;j<=w;j++){
if(a[i][j]==m){
i1=i;j1=j;
}
if(a[i][j]==n){
i2=i;j2=j;
}
}
}
cout<< i1<<" "<<j1<<endl;
cout<< i2<<" "<<j2<<endl;
cout<<abs(i2-i1)+abs(j2-j1);
return 0;
}
第 102 页 共 256 页
3.4.5 组折
输入两个正整数 m 和 n&#Vff08;20≥m≥n>0&#Vff09;&#Vff0c;要求 m 个正整数相加的和为 n&#Vff0c;输出
满足那个条件的正整数组折有几多多。
输入形容&#Vff1a;分止输入 m 和 n&#Vff08;20≥m≥n>0&#Vff09;。
输出形容&#Vff1a;输出满足那个条件的正整数组折有几多多。
【样例输入】
4
8
【样例输出】
5
【上述输入输出样例的进一步评释】
用户输入的两个正整数&#Vff0c;即样例输入为 4 和 8&#Vff0c;满足条件的有&#Vff1a;5+1+1+1=8、
4+2+1+1=8、3+3+1+1=8、3+2+2+1=8、2+2+2+2=8&#Vff08;每组组折都由 4 个正整数
构成且 4 个正整数的和就是 8&#Vff09;所以样例输出为 5。
#include <iostream>
using namespace std;
int a[10001]={1},m,n,total;
int search(int s,int t){
int i;
for(i=a[t-1];i<=s;i++){
if(i<=m){
a[t]=i;
s-=i;
if(s==0&&t==n){
total++;
}
第 103 页 共 256 页
else{
search(s,t+1);
}
s+=i;
}
}
}
int main(){
cin>>n>>m;
search(m,1);
cout<<total;
return 0;
}
第 104 页 共 256 页
3.5***第十届蓝桥青少组省赛 C++高级组
3.5.1 水下探测器
水下探测器可以潜入湖中正在任意水深停行科学摸索。
湖水的最大深度为 h 米,即它正在湖底时到水面的距离&#Vff0c;0<=h<=100&#Vff1b;
探测器最初的水下深度为 s 米&#Vff0c;0<=s<=100&#Vff1b;
当探测器不正在水面&#Vff08;当前深度大于 0&#Vff09;时&#Vff0c;每个 u 指令可使它上浮 1 米&#Vff0c;而当
探测器正在水面时&#Vff0c;u 指令是无效的&#Vff1b;
当探测器不正在湖底&#Vff08;当前深度小于 h&#Vff09;时&#Vff0c;每个 d 指令可使它下沉 1 米&#Vff0c;而当
探测器正在湖底时&#Vff0c;d 指令是无效的&#Vff1b;
正在执止到无效指令时&#Vff0c;探测器不作任何收配而继续执止下一指令。
编程真现&#Vff1a;
依据给定的 h、s 和一个指令序列&#Vff08;由字符 u、d 构成的字符串&#Vff0c;长度不赶过 100&#Vff09;&#Vff0c;
求出执止完好的指令序列后&#Vff0c;探测器的水下深度。
输入&#Vff1a;
第一止&#Vff1a;h 和 s&#Vff0c;以空格离开。0<=s<=h<=100
第二止&#Vff1a;长度不赶过 100 的指令字符串&#Vff0c;串中仅包孕字母 u 或 d
输出&#Vff1a;
代表探测器正在执止指令后的水下深度的数字。
样例输入&#Vff1a;
9 1
uduudd
样例输出&#Vff1a;
2
考查知识:
根原语法,字符串,循环,条件判断
#include <iostream>
using namespace std;
int main(){
int h,s;
string str;
cin>>h>>s>>str;
for(int i=0;i<str.size();i++){
第 105 页 共 256 页
if(str[i]=='u'&&s>0) s--;
if(str[i]=='d'&&s<h) s++;
}
cout<<s;
}
3.5.2 小猫吃鱼
明明家从 1 号站点动身&#Vff0c;开车去旅游&#Vff0c;一共要颠终 n 个站点&#Vff0c;挨次为 2、3……n。
由于明明带上了可爱的小猫&#Vff0c;正在每个站点都要为小猫供给一条鱼用作美餐&#Vff08;蕴含 1
号站点&#Vff09;。
除了 1 号站点只能吃 1 号站点买的鱼&#Vff0c;其余站点既可以吃当地买的鱼&#Vff0c;也可吃
之前颠终的站点买了存入车载冰箱中的鱼。但车载冰箱泯灭的电能来自汽油&#Vff0c;所以每
条鱼用冰箱保存到下一站的用度取各个站点的汽油价格有关。
为使问题简化&#Vff0c;咱们约定&#Vff1a;
&#Vff08;1&#Vff09;车从某站开出时油箱中都是此站点刚加的汽油。
&#Vff08;2&#Vff09;车载冰箱能包容一路上须要的所有鱼。 即&#Vff1a;每条鱼的用度既蕴含置办时的
用度&#Vff0c;也蕴含用冰箱保存鱼的用度。
编程真现&#Vff1a;
为了降低小猫吃鱼的总价钱&#Vff0c;明明预先上网查到了那 n 个站点的鱼价和汽油价
格。并据此算出每个站点买一条鱼的用度以及从该站点到下一站用冰箱保存一条鱼的
用度。你能帮明明算出那一路上小猫吃鱼的最小总用度吗&#Vff1f;
输入&#Vff1a;
第一止&#Vff1a;站点数 n&#Vff0c;1<n<100。
接下来的 n 止&#Vff1a;每止两个以空格分隔断绝结合的正整数&#Vff0c;默示&#Vff1a;那一站买一条鱼的用度&#Vff0c;
以及从那一站把每条
鱼保存到下一站的用度&#Vff0c;两个用度均为小于 10000 的正整数。
输出&#Vff1a;
最小总用度&#Vff0c;是一个正整数。
样例输入&#Vff1a;
5
6 3
7 1
3 2
8 3
9 5
样例输出&#Vff1a;
第 106 页 共 256 页
29
运用 for 循环&#Vff0c;每次看看代价是不是最划算&#Vff0c;不是就加上一条鱼&#Vff0c;是也要加上那
一条鱼&#Vff0c;每次还要加上保存的代价。
#include <iostream>
using namespace std;
int main() {
int n;
cin>>n;
int m1[n], m2[n];
for(int i = 0; i < n; i++)
cin>>m1[i]>>m2[i];
//输入当前买鱼的钱和保存的钱
int min = 9999999, t = 0;
for(int i = 0; i < n; i++) {
if(min > m1[i])
min = m1[i];
t = t + min; //上一条鱼
min = min + m2[i]; //保存
}
cout<<t<<endl;
return 0;
}
3.5.3 评比最佳品排
n 个评卫投票&#Vff0c;正在 m 个商品中评比一个最佳品排。
评比给取多轮套汰制&#Vff0c;即&#Vff1a;每轮投票&#Vff0c;套汰掉得票起码的候选品排&#Vff08;得票并列最
少的品排一起套汰&#Vff09;。
如此一轮轮套汰下去&#Vff0c;假如最后只剩下一个品排中选&#Vff0c;即告评比乐成。
但假如正在某轮投票中&#Vff0c;其时未被套汰的所有候选品排&#Vff08;大于就是两个品排&#Vff09;都并
列得票起码&#Vff0c;即告评比失败。
假如评比乐成绩输出中选品排号。否则输出最后一轮评比时惟一选票数的相反数。
正在评比流程中&#Vff0c;每个评卫的态度都可用一个序列来默示&#Vff1b;譬喻当 m=5 时&#Vff0c;某评
卫的评比态度序列为&#Vff1a;3、
5、1、2、4&#Vff0c;则默示该评卫&#Vff1a;劣先投 3 号&#Vff0c;当 3 号被套汰时投 5 号&#Vff0c;当 3 和 5
都被套汰时投 1&#Vff0c;当 3、5、1 都被套汰时投 2&#Vff0c;仅剩 4 号时才投 4 号品排的票。
选票的序列中可以默示弃权&#Vff0c;用 0 来默示&#Vff0c;譬喻当 m=5 时&#Vff0c;某评卫的评比态度
序列为&#Vff1a;3、5、0&#Vff0c;则默示该评卫&#Vff1a;劣先投 3 号&#Vff0c;当 3 号被套汰时投 5 号&#Vff0c;其他情
第 107 页 共 256 页
况下不投任何品排的票。
编程真现&#Vff1a;
请你编一个步调&#Vff0c;模拟各轮投票的历程&#Vff0c;获得评比结果。
输入&#Vff1a;
第一止&#Vff1a;m(0<m<10,默示加入评比的品排数)和 N(1<n<1000,默示加入投票的评卫
数)&#Vff0c;之间以空格分隔断绝结合接下来的 n 止&#Vff1a;每止都是长度不超 m 的数字字符串&#Vff0c;每个字
符串默示一个评卫的评比态度。
输出&#Vff1a;
评比结果。
样例 1 输入&#Vff1a;
3 4
123
213
132
10
样例 1 输出&#Vff1a;
1
样例 2 输入&#Vff1a;
3 4
321
213
231
312
样例 2 输出&#Vff1a;
-2
样例数据阐明:
样例 1:
第一止 3 4 代表 3 个品排,4 个评卫
第一轮投票,3 个评卫劣先选择 1 号品排,1 个评卫选择 2 号品排,品排 3 得票起码, 套汰掉
第二轮投票,3 个评卫劣先选择 1 号品排,1 个评卫选择 2 号品排,品排 2 得票起码, 套汰掉,套汰 2 号品排后,只剩一个 1 号品排,1 号品排胜出&#Vff0c;最末结果 1
样例 2:
第一止 3 4 代表 3 个品排,4 个评卫
第一轮投票,2 个评卫选择 2 号品排,两个评卫选择 3 号品排,1 号得票起码,套汰掉
第二轮投票,2 个评卫选择 2 号品排,两个评卫选择 3 号品排,由于只剩下两个品排,
第 108 页 共 256 页
且并列起码,都是 2 票,代表评比失败,须要输出最后一轮票数 2 的相反数-2
最末结果 -2
考查知识:
字符串,桶牌序,模拟算法
#include <iostream>
using namespace std;
int main(){
int m,n;
cin>>m>>n;
string str[n+1];
for(int i=1;i<=n;i++){
cin>>str[i];
}
int a[m+1];//记录投票历程,-1 代表套汰
while(true){
for(int i=1;i<=m;i++){
//从头计票,所有没有被套汰的票数归零
if(a[i]!=-1)a[i]=0;
}
for(int i=1;i<=n;i++){
//计票
string s=str[i];
for(int j=0;j<s.size();j++){
char t=s[j]-'0';
if(t==0){
//假如为 0 注明弃权
break;
}else{
//不为 0,则代表要给 t 投票,假如 t 没有被套汰则给它投票
if(a[t]>=0){
a[t]=a[t]+1;
break;
}
}
}
}
第 109 页 共 256 页
int min=m+1;
int maV=0;
for(int i=1;i<=m;i++){
if(a[i]>=0){
if(min>a[i]) min=a[i];
if(maV<a[i])maV=a[i];
}
}
if(maV>min){
//最大值比最小值大,须要将所有最小值的套汰
for(int i=1;i<=m;i++){
if(a[i]==min)a[i]=-1;
}
}else{
//最大值和最小值相等注明平票
int count=0;
int dV=0;
for(int i=1;i<=m;i++){
if(a[i]==maV){
count++;
dV=i;
}
}
if(count>1){
//假如数质多,注明评比失败
cout<<0-maV;
}else{
cout<<dV;
}
break;
}
}
cin>>m;
}
第 110 页 共 256 页
3.5.4 蓝桥杯赛迷宫
把一个 n 止 m 列的字符阵列看作一个迷宫&#Vff0c;迷宫仅包孕 L、Q、B、S 中的大
写字母&#Vff08;蓝桥杯赛的汉语拼音首字母&#Vff09;。
初始时&#Vff0c;你可以从任意一个“L”字母初步&#Vff0c;移向相邻的“Q”字母&#Vff0c;而后今后“Q”字
母动身&#Vff0c;移向相邻的“B”字母&#Vff0c;而后今后“B”字母动身&#Vff0c;移向相邻的“S”字母……。那
样&#Vff0c;你就算是走过了一个“LQBS”字符序列。
接下来&#Vff0c;依然可以今后“S”字母动身&#Vff0c;移向相邻的“L”字母……&#Vff0c;重复上述的止动&#Vff0c;
你就可以不停地走过“LQBS”序列。
请留心&#Vff0c;所谓相邻仅包孕上、下、右、左 4 个标的目的&#Vff0c;且只能从 L->Q&#Vff0c;从 Q->B&#Vff0c;
从 B->S&#Vff0c;从 S->L。
可以想像&#Vff0c;由于选择的动身点差异&#Vff0c;咱们有可能正在迷宫中走过有数次的“LQBS”&#Vff0c;
大概是有限次的“LQBS”&#Vff0c;
大概一次也走不了。
编程真现&#Vff1a;
请你编写步调&#Vff0c;求出正在给定的迷宫中&#Vff0c;咱们最多可以走过几多屡次“LQBS”?
输入&#Vff1a;
第一止&#Vff1a;正整数 n,m&#Vff0c;默示迷宫的范围为 n 止 m 列&#Vff0c;0<m<100&#Vff0c;0<n<100
接下来的 n 止&#Vff1a;每止 m 个折乎题意的字母&#Vff0c;字母间无空格。
输出&#Vff1a;
一个整数。即&#Vff1a;假如正在迷宫中可以无限次的走过“LQBS”&#Vff0c;输出-1&#Vff0c;否则&#Vff0c;输出可
以走过“LQBS”的最多次数。
样例 1 输入&#Vff1a;
1 2
LQ
样例 1 输出&#Vff1a;
0
样例 2 输入&#Vff1a;
3 3
LSB
QBQ
BSL
样例 2 输出&#Vff1a;
-1
样例 3 输入&#Vff1a;
4 4
第 111 页 共 256 页
BLQB
BBQS
SBQL
QQQQ
样例 3 输出&#Vff1a;
2
样例数据阐明:
样例 1:
第一止数据 3 3 代表是 3 止 3 列的迷宫
第 1 步,寻找 L
LSB
QBQ
BSL
第 2 步,正在 L 的高下摆布寻找 Q
LSB
QBQ
BSL
第 3 步,正在 Q 的高下摆布寻找 B
LSB
QBQ
BSL
第 4 步,正在 B 的高下摆布寻找 S
LSB
QBQ
BSL
如此当重复到 10 次的时候,仍可以继续走,代表进入无限循环
因为 3 止 3 列最多 9 个格子,能走 10 步就代表一定进入无限循环
输出-1
样例 2:
第一止数据 4 4 代表是 4 止 4 列的迷宫
第 1 步,寻找末点 L
BLQB
BBQS
SBQL
QQQQ
第 2 步,正在 L 的高下摆布寻找 Q
第 112 页 共 256 页
BLQB
BBQS
SBQL
QQQQ
第 3 步,正在 Q 的高下摆布寻找 B
BLQB
BBQS
SBQL
QQQQ
第 4 步,正在 B 的高下摆布寻找 S
BLQB
BBQS
SBQL
QQQQ
第 5 步,正在 S 的高下摆布寻找 L
BLQB
BBQS
SBQL
QQQQ
第 6 步,正在 L 的高下摆布寻找 Q
BLQB
BBQS
SBQL
QQQQ
第 7 步,正在 Q 的高下摆布寻找 B
BLQB
BBQS
SBQL
QQQQ
第 8 步,正在 B 的高下摆布寻找 S
BLQB
BBQS
SBQL
QQQQ
第 9 步,正在 S 的高下摆布寻找 L
因为找不到 L 了,则代表迷宫走到止境,一共走了 8 步,LQBS 一共 4 个字符,所以走
第 113 页 共 256 页
了
8/4=2 共计 2 次 LQBS,输出 2
考查知识:
搜寻取回朔
未学到搜寻取回朔算法,可以给取循环遍历类似穷举算法停行题解
#include<iostream>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
char map[n+1][m+1];
int path[n+1][m+1];
for(int i=1;i<=n;i++){
string s;
cin>>s;
for(int j=1;j<=m;j++){
map[i][j]=s[j-1];
path[i][j]=0;
if(map[i][j]=='L'){
path[i][j]=1;
}
}
}
string LQBS="LQBS";
int now=1;
while(true){
int flag=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(path[i][j]==now){
if(map[i][j-1]==LQBS[now%4]){
path[i][j-1]=now+1;
flag++;
}
if(map[i][j+1]==LQBS[now%4]){
第 114 页 共 256 页
path[i][j+1]=now+1;
flag++;
}
if(map[i-1][j]==LQBS[now%4]){
path[i-1][j]=now+1;
flag++;
}
if(map[i+1][j]==LQBS[now%4]){
path[i+1][j]=now+1;
flag++;
}
}
}
}
/*for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<path[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;*/
if(flag==0){
break;
}
if(now>(n+1)*(m+1)){
break;
}
now++;
}
if(now>(n+1)*(m+1)){
cout<<-1;
}else{
cout<<now/4;
}
cin>>n;
}
第 115 页 共 256 页
3.5.5 最大购物劣惠
小惠风闻超市正正在打合促销&#Vff0c;要制定一个获得最大劣惠的购物筹划。
小惠的体力可以提起 w 单位分质的东西&#Vff0c;另有一个能拆 x 个单位体积的购物
袋&#Vff0c;并具体理解了各打合商品的分质、体积及此商品真际劣惠的金额。她想正在原人体
力的限度和购物袋容积限度内&#Vff0c;尽可能多地获得购物劣惠。
超市规定那些打合商品每种只能置办一件。
编程真现&#Vff1a;
请你编写步调&#Vff0c;制订一个置办商品的筹划&#Vff0c;求出小惠能获得的最大劣惠金额和真
际应置办的各商品序号。
输入&#Vff1a;
第一止&#Vff1a;挨次为 w、ZZZ 和 n(n 为商品品种数)&#Vff0c;所无数值均为不赶过 100 的正整
数 接下来的 n 止&#Vff1a;每止有三个整数&#Vff0c;挨次为某种商品的分质、体积和让利金额&#Vff0c;数
值间以空格离开&#Vff0c;所无数值均为不赶过 100 的正整数
输出&#Vff1a;
第一止&#Vff1a;小惠能够获得的最大让利金额
第二止&#Vff1a;挨次为从小到大布列的商品序号&#Vff0c;序号从 1 初步&#Vff0c;序号间用空格离开。
若第二止输出的序列
不惟一&#Vff0c;则输出其最小字典序。
样例输入&#Vff1a;
10 9 4
8 3 6
5 4 5
3 7 7
4 5 4
样例输出&#Vff1a;
9
2 4
考查知识:
动态布局&#Vff0c;二维用度的背包问题&#Vff0c;正在 01 背包问题的根原上删多一个用度维度
形态转移方程&#Vff1a;
yh[i][j][k]=maV(yh[i-1][j][k],yh[i-1][j-w[i]][k-ZZZ[i]]+n[i])
规范 01 背包问题解
第 116 页 共 256 页
#include <iostream>
using namespace std;
int main() {
int w, ZZZ, n;
cin >> w >> ZZZ >> n;
int a[n + 1], b[n + 1], c[n + 1];
int yh[n + 1][w + 1][ZZZ + 1];
string s[n + 1][w + 1][ZZZ + 1];
for (int i = 1; i <= n; i++)
cin >> a[i] >> b[i] >> c[i];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= w; j++) {
for (int k = 0; k <= ZZZ; k++) {
yh[i][j][k] = 0;
s[i][j][k] = "";
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= w; j++) {
for (int k = 1; k <= ZZZ; k++) {
int bn = yh[i - 1][j][k];
int n = 0;
if (j >= a[i] && k >= b[i]) { //分质和体积够,拿当前物品
n = yh[i - 1][j - a[i]][k - b[i]] + c[i];
}
if (n > bn) { //假如拿了比不拿价值大,就拿那个物品
yh[i][j][k] = n;
//同时记录拿了那个物品
s[i][j][k] = s[i - 1][j - a[i]][k - b[i]] + " " + (char)(i + '0');
} else {
//否则记录当前分质和体积的最劣战略是不拿
yh[i][j][k] = bn;
//同时记录不拿当前物品,保持和之前一样的物品列表
s[i][j][k] = s[i - 1][j][k];
第 117 页 共 256 页
}
}
}
}
cout << yh[n][w][ZZZ] << endl;
string str = s[n][w][ZZZ];
cout << str.substr(1, str.size() - 1);
}
3.5.6 购物单
XX 大促销又来了&#Vff0c;长长的购物单&#Vff0c;都是有打合劣惠的。
请你帮他计较一下&#Vff0c;须要从与款机上与几多多现金&#Vff0c;威力搞定此次购物。
与款机只能供给 100 元面额的纸币。小明想尽可能少与些现金&#Vff0c;够用就止了。
你的任务是计较出&#Vff0c;小明起码须要与几多多现金。
180.90 88 合
10.25 65 合
56.14 9 合
104.65 9 合
100.30 88 合
297.15 半价
26.75 65 合
130.62 半价
#include<iostream>
using namespace std;
int main()
{
double j,z,sum=0;//本价 合扣
for(int i=1; i<=8; i++) {
cin>>j>>z;
sum=sum+j*z;
}
sum=sum+0.9; //零钱局部舍入 正确到 1 角
if(int(sum)%100>0)//不是 100 元的整数倍
cout<<int(sum)/100*100+100;
else
cout<<int(sum);
第 118 页 共 256 页
return 0;
}
3.5.7 等差素数列
2,3,5,7,11,13,....是素数序列。类似&#Vff1a;7,37,67,97,127,157 那样彻底由素数构成的等差数列&#Vff0c;叫
等差素数数列。上边的数列公差为 30&#Vff0c;长度为 6。
2004 年&#Vff0c;格林取华人陶哲轩竞争证真了&#Vff1a;存正在任意长度的素数等差数列。
那是数论规模一项惊人的成绩&#Vff01;有那一真践为根原&#Vff0c;请你借助手中的计较机&#Vff0c;满
怀自信心地搜寻&#Vff1a;
长度为 10 的等差素数列&#Vff0c;其公差最小值是几多多&#Vff1f;
留心&#Vff1a;须要提交的是一个整数&#Vff0c;不要填写任何多余的内容和注明笔朱。
先用埃氏筛法&#Vff0c;把 1~N (N 先设置一个 10000 吧&#Vff0c;不够再加)以内的素数都挑选出
来&#Vff0c;而后再枚举 1~10000(公差&#Vff0c;不够再加)&#Vff0c;寻找间断 10 个的素数。
#include <iostream>
using namespace std;
const int maVn = 10000000;
int prime[maVn];
bool is_prime[maVn + 10]; //is_prime[i]为 true 默示 i 是素数
bool is_Prime(int n)
{
int i = 0;
for (i = 2; i * i <= n; i++)
{
if (n % i == 0) return false;
}
return n != 1;
}
//返回 n 以内的素数
int sieZZZe(int n)
{
int p = 0;
//初始化
for (int i = 0; i <= n; i++) {
is_prime[i] = true;
}
is_prime[0] = is_prime[1] = false;
第 119 页 共 256 页
for (int i = 0; i <= n; i++)
{
if (is_prime[i])
{
prime[p++] = i; //将素数添加到 prime 中
//1.首先 2 是素数, 而后划去所有 2 的倍数
//2.表中剩余的最小数字是 3, 他不能被更小的数整除,所以是素数
//再将表中所有 3 的倍数都划去
//3.以此类推, 假如表中剩余的最小数字是 m 时,m 便是素数。而后将表
中所有 m 的倍数都划去
for (int j = 2 * i; j <= n; j += i) {
is_prime[j] = false;
}
}
}
return p;
}
ZZZoid solZZZe(){
int N = 10000;
int cnt = sieZZZe(N);
//公差
for (int d = 10; d < N; d++){
//枚举 N 以内所有素数
for (int i = 0; i < cnt; i++){
int tmp = prime[i],
flag = true;
//能否间断 10 个都为素数
for (int j = 0; j < 9; j++)
{
if (tmp + d > N || !is_Prime(tmp + d))
{
flag = false;
第 120 页 共 256 页
break;
}
else
{
tmp += d; //下一个素数
}
}
if (flag) {
cout << d << " " << prime[i] << endl;
return;
}
}
}
}
int main()
{
solZZZe();
return 0;
}