报了个蓝桥杯，还有一个多月的时间吧，准备刷刷题，自己水平也比较菜，算法并不拿手。。
入门训练
Fibonacci数列
问题描述
Fibonacci数列的递推公式为：Fn=Fn-1+Fn-2，其中F1=F2=1。
当n比较大时，Fn也非常大，现在我们想知道，Fn除以10007的余数是多少。
输入格式
输入包含一个整数n。
输出格式
输出一行，包含一个整数，表示Fn除以10007的余数。
样例
样例输入
10
样例输出
55
样例输入
22
样例输出
7704
数据规模与约定
1 <= n <= 1,000,000。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include<stdio.h>
#include<stdlib.h>
int f(int n){
int i;
int a=0,b=1,c=1;
if(n==1||n==2)return 1;
else {
for(i=2;i<n;i++){
a=b+c;
c=b;
b=a;
a=a%10007;
b=b%10007;
c=c%10007;
}
return a;
}
}
int main(){
int n;
scanf("%d",&n);
int r;
r=f(n);
printf("%d",r);
return 0;
}
|
基础练习
数列排序
问题描述
给定一个长度为n的数列，将这个数列按从小到大的顺序排列。1<=n<=200
输入格式
第一行为一个整数n。
第二行包含n个整数，为待排序的数，每个整数的绝对值小于10000。
输出格式
输出一行，按从小到大的顺序输出排序后的数列。
样例输入
5
8 3 6 4 9
样例输出
3 4 6 8 9
快排跑一下，用C++调用库函数更简单，这里不展示了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include<stdio.h>
#include<stdlib.h>
int array[201]={0};
void sort(int *a,int left,int right){
if(left >= right){
return ;
}
int i=left;
int j=right;
int key=a[left];
while(i<j){
while(i<j&&key<=a[j]){
j--;
}
a[i]=a[j];
while(i<j&&key>=a[i]){
i++;
}
a[j]=a[i];
}
a[i]=key;
sort(a,left,i-1);
sort(a,i+1,right);
}
int main(){
int n;
scanf("%d",&n);
int i=0;
for(i=0;i<n;i++){
scanf("%d",&array[i]);
}
sort(array,0,n-1);
for(i=0;i<n;i++){
printf("%d ",array[i]);
}
return 0;
}
|
十六进制转八进制
问题描述
给定n个十六进制正整数，输出它们对应的八进制数。
输入格式
输入的第一行为一个正整数n （1<=n<=10）。
接下来n行，每行一个由0 9、大写字母A F组成的字符串，表示要转换的十六进制正整数，每个十六进制数长度不超过100000。
输出格式
输出n行，每行为输入对应的八进制正整数。
【注意】
输入的十六进制数不会有前导0，比如012A。
输出的八进制数也不能有前导0。
样例输入
2
39
123ABC
样例输出
71
4435274
【提示】
先将十六进制数转换成某进制数，再由某进制数转换成八进制。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| #include<stdio.h>
#include<stdlib.h>
int main(){
char o[100001];
char b[400004];
char h[133334];
int n;
scanf("%d",&n);
int i=0,j=0;
for(i=0;i<n;i++){
while(scanf("%c",&o[i])!='\n'){
j++;
}
int t1=0;
int t2=0;//记录转换后的二进制数的长度
int tem=0;
int flag;
for(t1=0;t1<j;t1++){//把每一位16进制数转换为四位2进制数
tem=o[t1]-'0';
flag=4;
while(flag--){
b[t2]=tem%2;
tem%=2;
t2++;
}
}
for(t1=t2,j=0;t1;t1=t1-3,j++){//把二进制数从最低位开始每三位为一组转换为一组八进制数
h[j]=b[t1]+b[t1-1]*2+b[t1-2]*4;
}
for(t1=j;t1;t1--)printf("%d",h[t1]);
}
return 0;
}
|
十六进制转十进制
问题描述
从键盘输入一个不超过8位的正的十六进制数字符串，将它转换为正的十进制数后输出。
注：十六进制数中的10~15分别用大写的英文字母A、B、C、D、E、F表示。
样例输入
FFFF
样例输出
65535
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int main()
{
char t;
int a[10]={0},i=0;
double s=0;
while((t=getchar())!=EOF){
if(t>='A'&&t<='F'){
a[i++]=t-'A'+10;
}else {
a[i++]=t-'0';
}
}
int temp=i;
int j;
for(j=i;j;j--)
s+=pow(16,temp-j)*a[j-1];
printf("%.0f\n",s);
return 0;
}
|
十进制转十六进制
问题描述
十六进制数是在程序设计时经常要使用到的一种整数的表示方式。它有0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F共16个符号，分别表示十进制数的0至15。十六进制的计数方法是满16进1，所以十进制数16在十六进制中是10，而十进制的17在十六进制中是11，以此类推，十进制的30在十六进制中是1E。
给出一个非负整数，将它表示成十六进制的形式。
输入格式
输入包含一个非负整数a，表示要转换的数。0<=a<=2147483647
输出格式
输出这个整数的16进制表示
样例输入
30
样例输出
1E
思路：辗转相除法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| #include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int main()
{
long int i;
scanf("%ld",&i);
int a[20];
int j=0;
if(i>0){
for(j=0;i>0;j++){
a[j]=i%16;
i=i/16;
}
int k;
for(k=j-1;k>=0;k--){
if(a[k]>=10){
printf("%c",('A'+(a[k]-10)));
}else {
printf("%d",a[k]);
}
}
}else {
printf("0\n");
}
return 0;
}
|
01字串
问题描述
对于长度为5位的一个01串，每一位都可能是0或1，一共有32种可能。它们的前几个是：
00000
00001
00010
00011
00100
请按从小到大的顺序输出这32种01串。
输入格式
本试题没有输入。
输出格式
输出32行，按从小到大的顺序每行一个长度为5的01串。
样例输出
00000
00001
00010
00011
<以下部分省略>
思路：主要就是一个二进制的转化问题，对于本题，数据量也不多，当然也可以直接打印结果，我的做法可能太复杂了些。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| #include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
void f(int n)
{
if(n)
f(n/2);
else
return;
printf("%d",n%2);
}
int main()
{
int i;
printf("00000\n");
for(i=1;i<32;i++){
if(i<2){
printf("0000");
}else if(i<4){
printf("000");
}else if(i<8){
printf("00");
}else if(i<16){
printf("0");
}
f(i);
printf("\n");
}
return 0;
}
|
字母图形
问题描述
利用字母可以组成一些美丽的图形，下面给出了一个例子：
ABCDEFG
BABCDEF
CBABCDE
DCBABCD
EDCBABC
这是一个5行7列的图形，请找出这个图形的规律，并输出一个n行m列的图形。
输入格式
输入一行，包含两个整数n和m，分别表示你要输出的图形的行数的列数。
输出格式
输出n行，每个m个字符，为你的图形。
样例输入
5 7
样例输出
ABCDEFG
BABCDEF
CBABCDE
DCBABCD
EDCBABC
数据规模与约定
1 <= n, m <= 26。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int main()
{
int m,n;
scanf("%d%d",&n,&m);
int i,j,k;
char s[m+1];
for(i=0;i<m;i++){
s[i]='A'+(i%26);
}
for(i=0;i<n;i++){
for(j=0;j<m;j++){
printf("%c",s[j]);
}//打印每一行
printf("\n");
//temp=s[0];
for(k=j;k>=1;k--){
s[k]=s[k-1];
}//每一行的元素替换为这个元素之前的元素
s[0]='A'+(i%26+1);//行首元素一次递加
}
return 0;
}
|
杨辉三角形
问题描述
杨辉三角形又称Pascal三角形，它的第i+1行是(a+b)i的展开式的系数。
它的一个重要性质是：三角形中的每个数字等于它两肩上的数字相加。
下面给出了杨辉三角形的前4行：
1
1 1
1 2 1
1 3 3 1
给出n，输出它的前n行。
输入格式
输入包含一个数n。
输出格式
输出杨辉三角形的前n行。每一行从这一行的第一个数开始依次输出，中间使用一个空格分隔。请不要在前面输出多余的空格。
样例输入
4
样例输出
1
1 1
1 2 1
1 3 3 1
数据规模与约定
1 <= n <= 34。
思路：按照规律做就行了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int main()
{
int n;
scanf("%d",&n);
int a[n][n];
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=0;
a[0][1]=1;
for(i=1;i<n;i++)
for(j=1;j<=i+1;j++)
a[i][j]=a[i-1][j-1]+a[i-1][j];
for(i=0;i<n;i++){
for(j=1;j<=i+1;j++){
printf("%d",a[i][j]);
if(j!=i+1)printf(" ");
}
printf("\n");
}
return 0;
}
|
特殊回文数
问题描述
123321是一个非常特殊的数，它从左边读和从右边读是一样的。
输入一个正整数n， 编程求所有这样的五位和六位十进制数，满足各位数字之和等于n 。
输入格式
输入一行，包含一个正整数n。
输出格式
按从小到大的顺序输出满足条件的整数，每个整数占一行。
样例输入
52
样例输出
899998
989989
998899
数据规模和约定
1<=n<=54。
思路：这事一个很有意思的题目，看到这个题感觉和其他几个判断数字规律的题目会差不多，但是看到所求的数字被限制在5位、6位数字，这样一来数据的规模很大，如果采取暴力的方式，时间就被卡住了，只能分析回文数字的规律，首先我想到的是数字要求实对称的，那么6位的数字就可以分成一半来看了，这样问题就简化成求一个三位数字，满足个十百位的数字和等于n/2就好了，另一半只需倒序输出。而对于5位数字同样可以以中间第三个数字为分界线，个位十位分别和万位千位是对称的，那么问题同样可以简化为求一个两位数字满足之歌数字的个位十位的数字和为(n-5位数中间的数字)，另一半同样倒序输出。用这样的方法就可以避免超时的问题。题目还有一些可以进行优化的地方，比如五位数字各位数字之和<=45，大家有什么害的思路也可以给我留言或发邮件@me
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
//如果n是奇数的话，那么只能出现在5位数中，
//如果n是偶数的话，n/2之后，就可以把问题看成是找一个三位数abc(a、b、c分别代表这个三位数百、十、个位的数字)，满足a+b+c=n/2,
int main()
{
int i,j,k,g,s,b,q,w;
int n;
scanf("%d",&n);
if(n%2==1&&n<=45){
for(i=10000;i<100000;i++){
g=i%10;
s=(i/10)%10;
b=(i/100)%10;
q=(i/1000)%10;
w=i/10000;
if(g==w&&s==q&&(g+s+b+q+w)==n)
printf("%d\n",i);
}
}else if(n%2==0){
if(n<=45){
for(i=1;i<10;i++){
for(j=0;j<10;j++){
for(k=0;k<10;k=k+2){
if((i+j)==(n-k)/2)
printf("%d%d%d%d%d\n",i,j,k,j,i);
}
}
}
}
for(i=1;i<10;i++){
for(j=0;j<10;j++){
for(k=0;k<10;k++){
if((i+j+k)==n/2)
printf("%d%d%d%d%d%d\n",i,j,k,k,j,i);
}
}
}
}
return 0;
}
|
字符串对比
问题描述
给定两个仅由大写字母或小写字母组成的字符串(长度介于1到10之间)，它们之间的关系是以下4中情况之一：
1：两个字符串长度不等。比如 Beijing 和 Hebei
2：两个字符串不仅长度相等，而且相应位置上的字符完全一致(区分大小写)，比如 Beijing 和 Beijing
3：两个字符串长度相等，相应位置上的字符仅在不区分大小写的前提下才能达到完全一致（也就是说，它并不满足情况2）。比如 beijing 和 BEIjing
4：两个字符串长度相等，但是即使是不区分大小写也不能使这两个字符串一致。比如 Beijing 和 Nanjing
编程判断输入的两个字符串之间的关系属于这四类中的哪一类，给出所属的类的编号。
输入格式
包括两行，每行都是一个字符串
输出格式
仅有一个数字，表明这两个字符串的关系编号
样例输入
BEIjing
beiJing
样例输出
3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int main()
{
char str1[20],str2[20];
int i=0,j=0,flag=0;
scanf("%s %s",str1,str2);
i=strlen(str1);
j=strlen(str2);
if(i!=j){
printf("1\n");
}else {
for(i=0;i<j;i++){
if(str1[i]!=str2[i]){
flag=1;
break;
}
}
if(flag==0)
printf("2\n");
else {
flag=0;
for(i=0;i<j;i++){
if((str1[i]-str2[i])!=32&&(str1[i]-str2[i])!=-32&&(str1[i]-str2[i])!=0){
flag=1;
break;
}
}
if(flag==0)
printf("3\n");
else printf("4\n");
}
}
return 0;
}
|
分解质因数
问题描述
求出区间[a,b]中所有整数的质因数分解。
输入格式
输入两个整数a，b。
输出格式
每行输出一个数的分解，形如k=a1a2a3…(a1<=a2<=a3…，k也是从小到大的)(具体可看样例)
样例输入
3 10
样例输出
3=3
4=22
5=5
6=23
7=7
8=222
9=33
10=25
提示
先筛出所有素数，然后再分解。
数据规模和约定
2<=a<=b<=10000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| #include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int a[10004]={0},b[1230]={0};
int i,j,k,flag=1;
for(i=2;i<m;i++){
for(j=2;j<=(i/2);j++){
if(i%j==0){
flag=0;
break;
}
}
if(flag){
a[i]=1;
}
flag=1;
}
a[2]=1;
j=0;
for(i=1;i<m;i++){
if(a[i]){
b[j]=i;
j++;
}
} //求出质数表
/*for(i=0;b[i];i++){
printf("%d ",b[i]);
}
printf("\n%d\n",i);*/
for(i=n;i<=m;i++){//分解质因数
j=i;
printf("%d=",i);
while(j!=1){
k=0;
while(1){
if(j%b[k]==0){
j=j/b[k];
printf("%d",b[k]);
break;
}
else {
k++;
}
}
if(j!=1)
printf("*");
}
printf("\n");
}
return 0;
}
|
矩阵乘法
问题描述
给定一个N阶矩阵A，输出A的M次幂（M是非负整数）
例如：
A =
1 2
3 4
A的2次幂
7 10
15 22
输入格式
第一行是一个正整数N、M（1<=N<=30, 0<=M<=5），表示矩阵A的阶数和要求的幂数
接下来N行，每行N个绝对值不超过10的非负整数，描述矩阵A的值
输出格式
输出共N行，每行N个整数，表示A的M次幂所对应的矩阵。相邻的数之间用一个空格隔开
样例输入
2 2
1 2
3 4
样例输出
7 10
15 22
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int main()
{
int n,m;
int i,j,k,l;
scanf("%d%d",&n,&m);
int a[n][n];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=0;
for(i=0;i<n;i++)//输入矩阵a
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
/*for(i=0;i<n;i++){
for(j=0;j<n;j++)
printf("%d ",a[i][j]);
printf("\n");
}*/
if(m>0){//如果是非零次幂的情况
int b[n][n];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
b[i][j]=0;
int c[n][n];
for(i=0;i<n;i++)
for(j=0;j<n;j++)
c[i][j]=a[i][j];
for(k=0;k<m-1;k++){//循环m次
for(i=0;i<n;i++){//计算每一个b[i][j]
for(j=0;j<n;j++){
for(l=0;l<n;l++)//b[i][j]为a的第i行的每一个数乘以a的第j列的对应的每个数的累加和
b[i][j]+=(c[i][l]*a[l][j]);
}
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
c[i][j]=b[i][j];
for(i=0;i<n;i++)//将b[i][j]重新置零
for(j=0;j<n;j++)
b[i][j]=0;
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
printf("%d",c[i][j]);
if(j!=n)
printf(" ");
}
printf("\n");
}
}else {//如果是零次幂的情况
for(i=0;i<n;i++){//输入矩阵a
for(j=0;j<n;j++)
if(i==j)
a[i][j]=1;
else
a[i][j]=0;
}
for(i=0;i<n;i++){
for(j=0;j<n;j++){
printf("%d",a[i][j]);
if(j!=n)
printf(" ");
}
printf("\n");
}
}
return 0;
}
|
矩形面积交
问题描述
平面上有两个矩形，它们的边平行于直角坐标系的X轴或Y轴。对于每个矩形，我们给出它的一对相对顶点的坐标，请你编程算出两个矩形的交的面积。
输入格式
输入仅包含两行，每行描述一个矩形。
在每行中，给出矩形的一对相对顶点的坐标，每个点的坐标都用两个绝对值不超过10^7的实数表示。
输出格式
输出仅包含一个实数，为交的面积，保留到小数后两位。
样例输入
1 1 3 3
2 2 4 4
样例输出
1.00
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include<stdio.h>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
int main(){
double x1,y1,x2,y2; //矩形1
double x3,y3,x4,y4; //矩形2
double m1,n1; //交集左上角坐标.
double m2,n2; //交集右下角坐标.
scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);
scanf("%lf%lf%lf%lf",&x3,&y3,&x4,&y4);
m1 = max(min(x1,x2),min(x3,x4));
n1 = max(min(y1,y2),min(y3,y4));
m2 = min(max(x1,x2),max(x3,x4));
n2 = min(max(y1,y2),max(y3,y4));
if(m2>m1 && n2>n1)
printf("%.2f\n",(m2 - m1)*(n2 - n1));
else
printf("0.00\n");
return 0;
}
|
完美的代价
问题描述
回文串，是一种特殊的字符串，它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串，它不一定是回文的，请你计算最少的交换次数使得该串变成一个完美的回文串。
交换的定义是：交换两个相邻的字符
例如mamad
第一次交换 ad : mamda
第二次交换 md : madma
第三次交换 ma : madam (回文！完美！)
输入格式
第一行是一个整数N，表示接下来的字符串的长度(N <= 8000)
第二行是一个字符串，长度为N.只包含小写字母
输出格式
如果可能，输出最少的交换次数。
否则输出Impossible
样例输入
5
mamad
样例输出
3
思路：
贪心法，从左边起依次扫描，每记录一个字母，就寻找从右边起最近的与它相同的字母，移动到回文的位置，记录步数，如果最近的与它相同的字母是它本身，说明它在字串里单独存在，可以根据单独存在的字母的个数以及字串的长度来判断impossible的情况，如果排除impossible的情况，则记录它到字串中间的步数，并不需要移动它。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int main()
{
int n, flag = 0, ans = 0;
char *str;
scanf("%d", &n);
str = (char*)malloc(n * sizeof(char));
scanf("%s", str);
int j = n - 1, p = 0;
int i;
for(i = 0; i < j; i++)
{
int k;
for(k = j; k >= 0; k--)
{
if(k == i)
{
flag++;
if(n % 2 == 0 || flag > 1)
{
printf("Impossible\n");
return 0;
}
p = n/2 - i;
break;
}
else if(str[k] == str[i])
{
ans += j - k;
int f;
for(f = k; f < j; f++)
{
str[f] = str[f + 1];
}
str[j] = str[i];
j--;
break;
}
}
}
printf("%d\n", ans + p);
return 0;
}
|
声明：
文章标题：蓝桥杯在线练习
文章作者：h3h3da
文章链接：https://www.liucunzhan.com/p/4f54c54d-91f7-434b-96ed-cc0461e7512b
文章版权属本博主所有，有问题或者建议欢迎在下方评论。欢迎转载、引用，但请标明作者和原文地址，谢谢。
喜欢，就支持我一下吧~