10、排序
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝最近学习了一些排序算法，其中冒泡排序让他印象深刻。
在冒泡排序中，每次只能交换相邻的两个元素。
小蓝发现，如果对一个字符串中的字符排序，只允许交换相邻的两个字符， 则在所有可能的排序方案中，冒泡排序的总交换次数是最少的。
例如，对于字符串
�
�
�
lan 排序，只需要
1
1 次交换。对于字符串
�
�
�
�
qiao 排序，总共需要
4
4 次交换。
小蓝找到了很多字符串试图排序，他恰巧碰到一个字符串，需要
100
100 次交 换，可是他忘了吧这个字符串记下来，现在找不到了。
请帮助小蓝找一个只包含小写英文字母且没有字母重复出现的字符串，对 该串的字符排序，正好需要
100
100 次交换。如果可能找到多个，请告诉小蓝最短的那个。如果最短的仍然有多个，请告诉小蓝字典序最小的那个。
AC代码：
#include <stdio.h> #include <stdlib.h> int main() { int i,m,t,j; int n=0; while((n*n-n)/2<100)n++; m=(n*n-n)/2-100; char arr[n]; for(i=0;i<n;i++)arr[i]=97+n-i-1; for(i=m;i>0;i--) { if(arr[i]<arr[i-1]) { t=arr[i]; arr[i]=arr[i-1]; arr[i-1]=t; } } for(i=0;i<n;i++) { printf("%c",arr[i]); } return 0; }
11、跑步锻炼
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝每天都锻炼身体。
正常情况下，小蓝每天跑
1
1 千米。如果某天是周一或者月初（
1
1 日），为了激励自己，小蓝要跑
2
2 千米。如果同时是周一或月初，小蓝也是跑
2
2 千米。
小蓝跑步已经坚持了很长时间，从
2000
2000 年
1
1 月
1
1 日周六（含）到
2020
2020 年
10
10 月
1
1 日周四（含）。请问这段时间小蓝总共跑步多少千米？
AC代码：
#include<iostream> using namespace std; int main() { int week[7]={6,7,1,2,3,4,5}; int month[13]={0,31,0,31,30,31,30,31,31,30,31,30,31}; int sum=0,day=0; for(int year=2000;year<=2020;year++) { if( (year%4==0&&year%100!=0) ||year%400==0 ) month[2]=29; else month[2]=28; for(int i=1;i<=12;i++) { for(int j=1;j<=month[i];j++) { if(week[day%7]==1||j==1) sum++; sum++; day++; if(year==2020&&i==10&&j==1) { cout<<sum; return 0; } } } } }
12、蛇形填数
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
如下图所示，小明用从
1
1 开始的正整数“蛇形”填充无限大的矩阵。
1 2 6 7 15 …
3 5 8 14 …
4 9 13 …
10 12 …
11 …
…
copy
容易看出矩阵第二行第二列中的数是
5
5。请你计算矩阵中第
20
20 行第
20
20 列的数是多少？
AC代码：
#include<bits/stdc++.h> using namespace std; int main() { int mp[101][101],row=0,col=0,cnt=1; mp[0][0]=1; while(!mp[19][19]) { mp[row][++col]=++cnt; while(col) { mp[++row][--col]=++cnt; } mp[++row][col]=++cnt; while(row) { mp[--row][++col]=++cnt; } } cout<<mp[19][19]; return 0; }
13、递增序列
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
对于一个字母矩阵，我们称矩阵中的一个递增序列是指在矩阵中找到两个字母，它们在同一行，同一列，或者在同一
45
45 度的斜线上，这两个字母从左向右看、或者从上向下看是递增的。
例如，如下矩阵中
LANN
QIAO
copy
有
LN、LN、AN、AN、IO、AO、LQ、AI、NO、NO、AQ、IN、AN 等
13
13 个 递增序列。注意当两个字母是从左下到右上排列时，从左向右看和从上向下看 是不同的顺序。
对于下面的
30
30 行
50
50 列的矩阵，请问总共有多少个递增序列？
VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG
SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF
ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA
BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL
YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH
ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU
XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR
ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG
MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA
VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF
GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC
EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK
PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW
CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP
RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS
PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR
JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL
YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP
HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN
DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF
LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW
CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ
IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI
ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB
HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP
FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS
VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ
BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR
RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY
ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX
AC代码：
#include <iostream> using namespace std; int main() { char v[30][51]={"VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG",\ "SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF",\ "ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA",\ "BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL",\ "YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH",\ "ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU",\ "XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR",\ "ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG",\ "MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA",\ "VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF",\ "GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC",\ "EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK",\ "PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW",\ "CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP",\ "RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS",\ "PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR",\ "JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL",\ "YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP",\ "HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN",\ "DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF",\ "LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW",\ "CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ",\ "IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI",\ "ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB",\ "HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP",\ "FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS",\ "VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ",\ "BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR",\ "RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY",\ "ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX"}; int s=0; for(int i=0;i<30;i++) for(int j=0;j<50;j++) for(int x=0;x<30;x++) for(int y=0;y<50;y++) if(v[i][j]<v[x][y]&&((i==x&&y>j)||(j==y&&x>i)||abs(y-j)==abs(x-i)&&!(x<=i&&y<=j))) s++; cout<<s; }
14、货物摆放
题目描述
小蓝有一个超大的仓库，可以摆放很多货物。
现在，小蓝有
n 箱货物要摆放在仓库，每箱货物都是规则的正方体。小蓝规定了长、宽、高三个互相垂直的方向，每箱货物的边都必须严格平行于长、宽、高。
小蓝希望所有的货物最终摆成一个大的长方体。即在长、宽、高的方向上分别堆
L、W、H 的货物,满足
n=L×W×H。
给定
n，请问有多少种堆放货物的方案满足要求。
例如，当
4
n=4 时，有以下
6
6 种方案：
1×1×4、1×2×2、1×4×1、2×1×2、2×2×1、4×1×1。
请问，当
2021041820210418
n=2021041820210418 （注意有
16
16 位数字）时，总共有多少种方案？
提示：建议使用计算机编程解决问题。
答案提交
这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
AC代码：
#include<iostream> #include<cmath> #include<vector> using namespace std; int main() { long long n=2021041820210418; vector<long long>divisor; for(long long i=1;i<=sqrt(n);i++) { if(n%i==0) { divisor.push_back(i); long long k=n/i; if(k!=i) divisor.push_back(k); } } int count=0; vector<long long>::iterator a,b,c; for(a=divisor.begin();a!=divisor.end();a++) { for(b=divisor.begin();b!=divisor.end();b++) { for(c=divisor.begin();c!=divisor.end();c++) { if((*a)*(*b)*(*c)==n) count++; } } } cout<<count<<endl; return 0; }
15、九进制转十进制
问题描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
九进制正整数
(
2022
)
9
(2022)
9
转换成十进制等于多少？
AC代码：
#include <iostream> using namespace std; int main() { cout<<2+2*9+2*9*9*9; return 0; }
16、等差素数列
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
2,3,5,7,11,13,… 是素数序列。 类似：
7,37,67,97,127,157 这样完全由素数组成的等差数列，叫等差素数数列。
上边的数列公差为 30，长度为 6
2004 年，格林与华人陶哲轩合作证明了：存在任意长度的素数等差数列。 这是数论领域一项惊人的成果！
有这一理论为基础，请你借助手中的计算机，满怀信心地搜索：
长度为
10 的等差素数列，其公差最小值是多少？
AC代码：
#include<bits/stdc++.h> using namespace std; bool judge(int x) { for(int i=2;i<x;i++) { if(x%i==0) return false; } return true; } int main() { int ans=1,num,d; for(int i=2;i<50000;i++) { if(judge(i)) { for(int d=1;d<1000;d++) { for(int j=1;j<1000;j++) { num=i+d*j; if(judge(num)) ans++; else { ans=1; break; } if(ans==10) { cout<<d; return 0; } } } } } }
17、七段码
题目描述
本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。
小蓝要用七段码数码管来表示一种特殊的文字。
上图给出了七段码数码管的一个图示，数码管中一共有
7
7 段可以发光的二 极管，分别标记为
a,b,c,d,e,f,g。
小蓝要选择一部分二极管（至少要有一个）发光来表达字符。在设计字符 的表达时，要求所有发光的二极管是连成一片的。
例如：
b 发光，其他二极管不发光可以用来表达一种字符。
例如
c 发光，其他二极管不发光可以用来表达一种字符。这种方案与上 一行的方案可以用来表示不同的字符，尽管看上去比较相似。
例如：
a,b,c,d,e 发光，
f,g 不发光可以用来表达一种字符。
例如：
b,f 发光，其他二极管不发光则不能用来表达一种字符，因为发光 的二极管没有连成一片。
请问，小蓝可以用七段码数码管表达多少种不同的字符？
AC代码：
#include <iostream> using namespace std; int BackTrack(int graph[][7],int visit[],int n,int i){ int count=1; for(int x=0;x<n;x++){ if(visit[x]!=1&&graph[i][x]!=0){ visit[x]=1; count+=BackTrack(graph,visit,n,x); visit[x]=0; } } return count; } int main() { int graph[7][7]={ {1,1,0,0,0,1,0}, {1,1,1,0,0,0,1}, {0,1,1,1,0,0,1}, {0,0,1,1,1,0,0}, {0,0,0,1,1,1,1}, {1,0,0,0,1,1,1}, {0,1,1,0,1,1,1} }; int visit[7]={0}; printf("%d",BackTrack(graph,visit,7,0)/2); return 0; }
18、跳跃
题目描述
小蓝在一个
�
n 行
�
m 列的方格图中玩一个游戏。
开始时，小蓝站在方格图的左上角，即第
1
1 行第
1
1 列。
小蓝可以在方格图上走动，走动时，如果当前在第
�
r 行第
�
c 列，他不能走到行号比
�
r 小的行，也不能走到列号比
�
c 小的列。同时，他一步走的直线距离不超过
3
3。
例如，如果当前小蓝在第
3
3 行第
5
5 列，他下一步可以走到第
3
3 行第
6
6 列、第
3
3 行第
7
7 列、第
3
3 行第
8
8 列、第
4
4 行第
5
5 列、第
4
4 行第
6
6 列、第
4
4 行第
7
7 列、第
5
5 行第
5
5 列、第
5
5 行第
6
6 列、第
6
6 行第
5
5 列之一。
小蓝最终要走到第
�
n 行第
�
m 列。
在图中，有的位置有奖励，走上去即可获得，有的位置有惩罚，走上去就要接受惩罚。奖励和惩罚最终抽象成一个权值，奖励为正，惩罚为负。
小蓝希望，从第
1
1 行第
1
1 列走到第
�
n 行第
�
m 列后，总的权值和最大。请问最大是多少？
输入描述
输入的第一行包含两个整数
�
,
�
n,m，表示图的大小。
接下来
�
n 行，每行
�
m 个整数，表示方格图中每个点的权值。
其中，
1
≤
�
≤
100
，
−
1
0
4
≤
权值
≤
1
0
4
1≤n≤100，−10
4
≤权值≤10
4
。
输出描述
输出一个整数，表示最大权值和。
输入输出样例
示例 1
输入
3 5
-4 -5 -10 -3 1
7 5 -9 3 -10
10 -2 6 -10 -4
copy
输出
15
AC代码：
#include<bits/stdc++.h> using namespace std; int main() { int n,m,trans; cin>>n>>m; int grapth[n+1][m+1]; int x[9]={0,0,0,-1,-1,-1,-2,-2,-3}; int y[9]={-1,-2,-3,0,-1,-2,-1,0}; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>grapth[i][j]; trans=INT_MIN; for(int t=0;t<9;t++) { if(i+x[t]>0&&j+y[t]>0) trans=max(trans,grapth[i+x[t]][j+y[t]]); } if(trans!=INT_MIN) grapth[i][j]+=trans; } } cout<<grapth[n][m]<<endl; }
19、时间显示
题目描述
小蓝要和朋友合作开发一个时间显示的网站。
在服务器上，朋友已经获取了当前的时间，用一个整数表示，值为从
1970
1970 年
1
1 月
1
1 日
00
:
00
:
00
00:00:00 到当前时刻经过的毫秒数。
现在，小蓝要在客户端显示出这个时间。小蓝不用显示出年月日，只需要显示出时分秒即可，毫秒也不用显示，直接舍去即可。
给定一个用整数表示的时间，请将这个时间对应的时分秒输出。
输入描述
输入一行包含一个整数，表示时间。
输出描述
输出时分秒表示的当前时间，格式形如 HH:MM:SS，其中 HH 表示时，值为
0
0 到
23
23，MM 表示分，值为
0
0 到
59
59，SS 表示秒，值为
0
0 到
59
59。时、分、秒 不足两位时补前导
0
0。
输入输出样例
示例 1
输入
46800999
copy
输出
13:00:00
copy
示例 2
输入
1618708103123
copy
输出
01:08:23
copy
评测用例规模与约定
对于所有评测用例，给定的时间为不超过
1
0
18
10
18
的正整数。
AC代码：
#include<iostream> using namespace std; int main() { long long sum; cin>>sum; int hh,mm,ss; sum/=1000; hh=sum/60/60%24; mm=sum/60%60; ss=sum%60; printf("%02d:%02d:%02d",hh,mm,ss); }
