Scott's world.

蓝桥杯 基础练习(上)

Word count: 6.2kReading time: 28 min
2020/03/21 Share

蓝桥杯 基础练习(上)

BASIC-13 数列排序

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  给定一个长度为n的数列,将这个数列按从小到大的顺序排列。1<=n<=200

  • 输入格式

  第一行为一个整数n。
  第二行包含n个整数,为待排序的数,每个整数的绝对值小于10000。

  • 输出格式

  输出一行,按从小到大的顺序输出排序后的数列。

  • 样例输入

5
8 3 6 4 9

  • 样例输出

3 4 6 8 9

分析

直接使用Sort函数进行快排

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstdio>
#include <string.h>
#include <cstring>
#include <algorithm>
using namespace std;

int nums[201];

int main()
{
int num;
cin>>num;
for(int i=0;i<num;i++)
{
cin>>nums[i];
}
sort(nums,nums+num);
for(int i=0;i<num;i++)
{
printf("%d ",nums[i]);
}
}

BASIC-12 十六进制转八进制

资源限制

时间限制:1.0s 内存限制:512.0MB

问题描述
  给定n个十六进制正整数,输出它们对应的八进制数。

输入格式
  输入的第一行为一个正整数n (1<=n<=10)。
  接下来n行,每行一个由0~9、大写字母A~F组成的字符串,表示要转换的十六进制正整数,每个十六进制数长度不超过100000。

输出格式
  输出n行,每行为输入对应的八进制正整数。

  【注意
  输入的十六进制数不会有前导0,比如012A。
  输出的八进制数也不能有前导0。

样例输入
  2
  39
  123ABC

样例输出
  71
  4435274

【提示】
  先将十六进制数转换成某进制数,再由某进制数转换成八进制。

分析

可以通过转换十进制来解答这道题

但是这里的十六进制可能很长,转换为十进制可能会溢出,所以我们选择转换二进制来进行解答

这里为了避免列举出所有二进制的情况,我们采用3位十六进制来对应4位8进制,其中每一段生成的整数值内部也是为二进制即可以通过位运算来得到最右边的三位,然后通过位运算向右移动三位切换到下一个代表八进制的三位二进制数

如果会有剩余的十六进制数,就要进行重新遍历,并且要考虑前导0的情况

最后将生成的字符串进行倒置得到最终答案

代码

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
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <math.h>
using namespace std;



int main()
{
int num;
int HexSize;
int re;
int ptr;
int base;
cin>>num;

string* Hex = new string[num];
string* Oct = new string[num];
string tmp;

for(int i=0; i<num; i++)
{
cin>>Hex[i];
tmp="";
Oct[i]="";
ptr=0;
base=7;
HexSize = Hex[i].size();
for(int j=HexSize-3; j>=0; j-=3)
{
re=0;
for(int k=0; k<3; k++)
{
int t=j+k;
if(Hex[i][t]>='0'&&Hex[i][t]<='9')
ptr=Hex[i][t]-'0';
if(Hex[i][t]>='A'&&Hex[i][t]<='F')
ptr=Hex[i][t]-'A'+10;
re = re * 16 + ptr;
}
for(int k=0; k<4; k++)
{
tmp+=(char)((re & base) + '0');
re = re >>3;
}
}
int last=HexSize%3;
if(last!=0)
{
int rest=ceil(4.0 / 3.0 * last);
re = 0;
for(int j=0; j<last; j++)
{


if(Hex[i][j]>='0'&&Hex[i][j]<='9')
ptr=Hex[i][j]-'0';
if(Hex[i][j]>='A'&&Hex[i][j]<='F')
ptr=Hex[i][j]-'A'+10;
re = re * 16 + ptr;

}

for(int j=0; j<rest; j++)
{
if (j<rest-1||(((j==rest-1)&&(re&base)!=0)))
tmp+=char((re & base)+'0');
re = re>>3;
}
}


for(int j=tmp.size()-1; j>=0; j--)
{

Oct[i]+=tmp[j];
}

}


for(int i=0; i<num; i++)
cout<<Oct[i]<<endl;

return 0;

}

BASIC-11 十六进制转十进制

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  从键盘输入一个不超过8位的正的十六进制数字符串,将它转换为正的十进制数后输出。
  注:十六进制数中的10~15分别用大写的英文字母A、B、C、D、E、F表示。

  • 样例输入

FFFF

  • 样例输出

65535

分析

注意int类型的取值范围不够,所以这里通过更大的精度来输出十进制数,这里用的long long

代码

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 <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <math.h>
using namespace std;



int main()
{
string Hex;
long long result=0;
cin>>Hex;
int HexSize=Hex.size();
for(int i=0;i<HexSize;i++)
{
int temp;
if(Hex[i]>='0'&&Hex[i]<='9')temp=Hex[i]-'0';
if(Hex[i]>='A'&&Hex[i]<='F')temp=Hex[i]-'A'+10;
result = result * 16 + temp;
}
cout<<result<<endl;

return 0;

}

BASIC-10 十进制转十六进制

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  十六进制数是在程序设计时经常要使用到的一种整数的表示方式。它有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

分析

首先可以看到0<=a<=2147483647即可用int类型作为输入类型整数

考虑十进制转十六进制,我们可以通过二进制来进行转换

我们知道每4位2进制即代表十六进制的一位

这里我们可以通过位运算来直接进行转换会方便很多

代码

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
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <math.h>
using namespace std;
char Ptr(int x)
{
char y;
if(x>=0&&x<=9)
y=x+'0';
if(x>=10)
y=x-10+'A';
return y;
}



int main()
{
int input;
int a;
char b;
string TmpHex="";
string Hex="";
cin>>input;
int base=15;
do
{
TmpHex+=Ptr(input&base);
input=input>>4;
}
while(input/base!=0);

if(input!=0)
{
TmpHex+=Ptr(input&base);
}

for(int j=TmpHex.size()-1; j>=0; j--)
{
Hex+=TmpHex[j];
}
cout<<Hex<<endl;

return 0;

}

BASIC-9 特殊回文数

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  123321是一个非常特殊的数,它从左边读和从右边读是一样的。
  输入一个正整数n, 编程求所有这样的五位和六位十进制数,满足各位数字之和等于n 。

  • 输入格式

  输入一行,包含一个正整数n。

  • 输出格式

  按从小到大的顺序输出满足条件的整数,每个整数占一行。

  • 样例输入

52

  • 样例输出

899998
989989
998899

  • 数据规模和约定

  1<=n<=54。

分析

题意容易理解,要注意一下数据规模和约定,五位和六位都要考虑,且按从小到大的顺序输出

五位和六位的回文数就代表最多有3个不同的数,最少为1个

这道题直接暴力求解,但重点是如何把代码写的优雅

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
for (int i1 = 1; i1 <= 9; i1++)
for (int i2 = 0; i2 <= 9; i2++)
for (int i3 = 0; i3 <= 9; i3++) {
if ((i1 + i2 + i3 + i2 + i1) == n)
cout << i1 << i2 << i3 << i2 << i1 << endl;
}
for (int i1 = 1; i1 <= 9; i1++)
for (int i2 = 0; i2 <= 9; i2++)
for (int i3 = 0; i3 <= 9; i3++) {
if ((i1 + i2 + i3 + i3 + i2 + i1) == n)
cout << i1 << i2 << i3 << i3 << i2 << i1 << endl;
}
return 0;
}

BASIC-8 回文数

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  1221是一个非常特殊的数,它从左边读和从右边读是一样的,编程求所有这样的四位十进制数。

  • 输出格式

  按从小到大的顺序输出满足条件的四位十进制数。

分析

直接暴力求解,非常愉悦

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <strstream>
#include <cstdio>
#include <string.h>
#include <string>
#include <math.h>
using namespace std;

int main()
{
for (int i1 = 1; i1 <= 9; i1++)
for (int i2 = 0; i2 <= 9; i2++){
cout<<i1<<i2<<i2<<i1<<endl;
}

return 0;

}

BASIC-7 特殊的数字

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  153是一个非常特殊的数,它等于它的每位数字的立方和,即153=111+555+333。编程求所有满足这种条件的三位十进制数。

  • 输出格式

  按从小到大的顺序输出满足条件的三位十进制数,每个数占一行。

分析

重点在于优雅的暴力代码

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <strstream>
#include <cstdio>
#include <string.h>
#include <string>
#include <math.h>
using namespace std;


int main()
{
for (int i1 = 1; i1 <= 9; i1++)
for (int i2 = 0; i2 <= 9; i2++)
for (int i3 = 0; i3 <= 9; i3++) {
if ((pow(i1,3)+pow(i2,3)+pow(i3,3))==(i1*100+i2*10+i3))
cout << i1 << i2 << i3<< endl;
}

return 0;

}

BASIC-6 杨辉三角形

  • 资源限制

时间限制:1.0s 内存限制:256.0MB

  • 问题描述

杨辉三角形又称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
30
31
32
33
34
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <math.h>
using namespace std;


int main()
{
int n;
int result[35][35];
cin>>n;
result[0][0]=1;
for(int i=1;i<n;i++)
{
result[i][0]=1;
for(int j=1;j<i;j++)
{
result[i][j]=result[i-1][j]+result[i-1][j-1];
}
result[i][i]=1;
}
for(int i=0;i<n;i++)
{
for(int j=0;j<i+1;j++)
{
printf("%d ",result[i][j]);
}
printf("\n");
}
return 0;

}

BASIC-5 查找整数

  • 资源限制

时间限制:1.0s 内存限制:256.0MB

  • 问题描述

给出一个包含n个整数的数列,问整数a在数列中的第一次出现是第几个。

  • 输入格式

第一行包含一个整数n。

第二行包含n个非负整数,为给定的数列,数列中的每个数都不大于10000。

第三行包含一个整数a,为待查找的数。

  • 输出格式

如果a在数列中出现了,输出它第一次出现的位置(位置从1开始编号),否则输出-1。

  • 样例输入

6
1 9 4 8 3 9
9

  • 样例输出

2

  • 数据规模与约定

1 <= n <= 1000。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int a[n];
for (int i = 0; i < n; i++)
cin >> a[i];
int t;
cin >> t;
int i;
for (i = 0; i < n; i++)
if (t == a[i]) break;
if (i == n)
cout << "-1";
else
cout << i + 1;
return 0;
}

BASIC-4 数列特征

  • 资源限制

时间限制:1.0s 内存限制:256.0MB

  • 问题描述

给出n个数,找出这n个数的最大值,最小值,和。

  • 输入格式

第一行为整数n,表示数的个数。

第二行有n个数,为给定的n个数,每个数的绝对值都小于10000。

  • 输出格式

输出三行,每行一个整数。第一行表示这些数中的最大值,第二行表示这些数中的最小值,第三行表示这些数的和。

  • 样例输入

5
1 3 -2 4 5

  • 样例输出

5
-2
11

  • 数据规模与约定

1 <= n <= 10000。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>

using namespace std;
int main() {
int n;
int num=0;
int MinNum=10000;
int MaxNum=-10000;
cin >> n;
for (int i = 0; i < n; i++)
{
int temp;
cin>>temp;
num+=temp;
if(temp<MinNum)MinNum=temp;
if(temp>MaxNum)MaxNum=temp;
}
printf("%d\n%d\n%d\n",MaxNum,MinNum,num);
}

BASIC-3 字母图形

  • 资源限制

时间限制:1.0s 内存限制:256.0MB

  • 问题描述

利用字母可以组成一些美丽的图形,下面给出了一个例子:

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
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << char('A' + abs(i - j));
}
cout << endl;
}
return 0;
}

BASIC-2 01字串

  • 问题描述

对于长度为5位的一个01串,每一位都可能是0或1,一共有32种可能。它们的前几个是:

00000

00001

00010

00011

00100

请按从小到大的顺序输出这32种01串。

代码

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;
int main() {
for (int i = 0; i <= 1; i++)
for (int j = 0; j <= 1; j++)
for (int k = 0; k <= 1; k++)
for (int l = 0; l <= 1; l++)
for (int m = 0; m <= 1; m++) {
cout << i << j << k << l << m << endl;
}
return 0;
}

BASIC-1 闰年判断

代码

1
2
3
4
5
6
7
8
9
10
11
 #include <iostream>
using namespace std;
int main() {
int y;
cin >> y;
if ((y % 4 == 0 && y %100 != 0) || y % 400 == 0)
cout << "yes";
else
cout << "no";
return 0;
}

BASIC-14 时间转换

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  给定一个以秒为单位的时间t,要求用“::”的格式来表示这个时间。表示时间,表示分钟,而表示秒,它们都是整数且没有前导的“0”。例如,若t=0,则应输出是“0:0:0”;若t=3661,则输出“1:1:1”。

  • 输入格式

  输入只有一行,是一个整数t(0<=t<=86399)。

  • 输出格式

  输出只有一行,是以“::”的格式所表示的时间,不包括引号。

  • 样例输入

0

  • 样例输出

0:0:0

  • 样例输入

5436

  • 样例输出

1:30:36

分析

仔细一点即可

代码

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
#include <iostream>

using namespace std;


int main()
{
int n;
cin >> n;
int h=0,m=0,s=0;
if(n/3600>0)
{
h=n/3600;
n-=h*3600;
}
if(n/60>0)
{
m=n/60;
n-=m*60;
}
s=n;


cout<<h<<":"<<m<<":"<<s<<endl;
return 0;
}

BASIC-15 字符串对比

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  给定两个仅由大写字母或小写字母组成的字符串(长度介于1到10之间),它们之间的关系是以下4中情况之一:
  1:两个字符串长度不等。比如 Beijing 和 Hebei
  2:两个字符串不仅长度相等,而且相应位置上的字符完全一致(区分大小写),比如 Beijing 和 Beijing
  3:两个字符串长度相等,相应位置上的字符仅在不区分大小写的前提下才能达到完全一致(也就是说,它并不满足情况2)。比如 beijing 和 BEIjing
  4:两个字符串长度相等,但是即使是不区分大小写也不能使这两个字符串一致。比如 Beijing 和 Nanjing
  编程判断输入的两个字符串之间的关系属于这四类中的哪一类,给出所属的类的编号。

  • 输入格式

  包括两行,每行都是一个字符串

  • 输出格式

  仅有一个数字,表明这两个字符串的关系编号

分析

仔细即可

代码

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
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;


int main()
{
string a;
string b;
cin>>a;
cin>>b;
if(a.size()==b.size())
{
if(a==b)
{
cout<<2<<endl;
return 0;
}
transform(a.begin(), a.end(), a.begin(), ::toupper);
transform(b.begin(), b.end(), b.begin(), ::toupper);
if(a==b)
{
cout<<3<<endl;
}
else
{
cout<<4<<endl;
}
}
else
{
cout<<1<<endl;
}
return 0;
}

BASIC-16 分解质因数

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  求出区间[a,b]中所有整数的质因数分解。

  • 输入格式

  输入两个整数a,b。

  • 输出格式

  每行输出一个数的分解,形如k=a1a2a3…(a1<=a2<=a3…,k也是从小到大的)(具体可看样例)

  • 样例输入

3 10

  • 样例输出

3=3
4=22
5=5
6=2
3
7=7
8=222
9=33
10=2
5

  • 数据规模和约定

  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
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;

int isPrime(int n)
{
if(n<=1)return 0;
else if(n==2 || n == 3 )return 1;
else{
for(int i=2;i*i<n;i++){
if(n%i==0)return 0;
}
}
return 1;
}

int main()
{
int a,b;
cin>>a>>b;
for(int i=a;i<=b;i++)
{
int temp=i;
int flag=0;
cout<<temp<<"=";
while(temp!=1)
{
for(int j=2;j<=temp;j++){
if(isPrime(j)&& temp % j==0){
temp/=j;
if(flag==1)
cout<<"*";
cout<<j;
flag=1;
break;
}
}
}
cout<<endl;
}
return 0;
}

BASIC-17 矩阵乘法

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  给定一个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

分析

如题意用编程实现矩阵乘法

若幂为0则为单位矩阵

代码

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
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;

long long int temp[35][35];

int main()
{
int n,m;
cin>>n>>m;
long long int input[35][35];
long long int result[35][35];
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
{
cin>>input[i][j];
result[i][j] = input[i][j];
}
if(m==0)
{
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
if(i!=j)
cout<<0<<" ";
else
cout<<1<<" ";
}
cout<<endl;
}
}
else
{
while(--m)
{
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
{
int a=n;
while(a--)
{
temp[i][j] += input[i][a] * result[a][j];
}
}
}
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
{
result[i][j] = temp[i][j];
temp[i][j]=0;
}
}
for(int i=0; i<n; i++)
{
for(int j=0; j<n; j++)
cout<<result[i][j]<<" ";
cout<<endl;
}
}

return 0;
}

BASIC-18 矩形面积交

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  平面上有两个矩形,它们的边平行于直角坐标系的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
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;



int main()
{

double x1,y1,x2,y2;
double x3,y3,x4,y4;
cin>>x1>>y1>>x2>>y2;
cin>>x3>>y3>>x4>>y4;
if(x1 > x2)
swap(x1, x2);
if(y1 > y2)
swap(y1, y2);
if(x3 > x4)
swap(x3, x4);
if(y3 > y4)
swap(y3, y4);
double x=0.0,y=0.0;
if(x3<=x1&&x4<=x2&&x4>=x1)x=x4-x1;
else if(x3>=x1&&x4<=x2)x=x4-x3;
else if(x3>=x1&&x4>=x2&&x3<=x2)x=x2-x3;
else if(x3<=x1&&x4>=x2)x=x2-x1;
if(y3<=y1&&y4<=y2&&y4>=y1)y=y4-y1;
else if(y3>=y1&&y4<=y2)y=y4-y3;
else if(y3>=y1&&y4>=y2&&y3<=y2)y=y2-y3;
else if(y3<=y1&&y4>=y2)y=y2-y1;
printf("%.2f",x*y);


return 0;
}

BASIC-19 完美的代价

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  回文串,是一种特殊的字符串,它从左往右读和从右往左读是一样的。小龙龙认为回文串才是完美的。现在给你一个串,它不一定是回文的,请你计算最少的交换次数使得该串变成一个完美的回文串。
  交换的定义是:交换两个相邻的字符
  例如mamad
  第一次交换 ad : mamda
  第二次交换 md : madma
  第三次交换 ma : madam (回文!完美!)

  • 输入格式

  第一行是一个整数N,表示接下来的字符串的长度(N <= 8000)
  第二行是一个字符串,长度为N.只包含小写字母

  • 输出格式

  如果可能,输出最少的交换次数。
  否则输出Impossible

  • 样例输入

5
mamad

  • 样例输出

3

分析

这道题首先一开始我就先考虑Impossible的情况,即不能构成回文数的情况

然后想了半天,并没有想到如何解决回文串相邻交换的最优解,所以谷歌一下

参考了柳诺大神的题解,才找到一些思路

首先我们考虑Impossible的两种情况

  • 如果n是偶数,若有一个字符出现的次数是奇数次数,那么不可能构成回文串
  • 如果n是奇数,但是已经有一个字符出现的次数是奇数次数了,若出现另一个字符是奇数次数,就不可能构成回文

然后解决回文串相邻交换最优解的情况,这里运用到了类似双指针的概念,即运用头尾指针移动进行比较

  • 我们运用头尾指针向中间移动,找到头指针字符相等的尾指针,就将尾指针的字符移动到相对头指针末尾的位置,并且记录移动的次数,这就是不考虑奇数字符的最优交换解

  • 如果考虑奇数字符的交换,若先将奇数字符交换到中间位置,那么在其他偶数字符交换的情况下,移动次数每次都会加1,这样就会浪费交换次数,我们只需要在最后将奇数字符交换到中间,这样才能保证次数最少

代码

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
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;

int main()
{
int n;
string input;
cin>>n;
cin>>input;
int flag=0;
int result=0;
int Size=input.size()-1;
for(int i=0;i<Size;i++){
for(int j=Size;j>=i;j--){
if(j==i){
if(n%2==0||flag==1){
cout<<"Impossible"<<endl;
return 0;
}
flag=1;
result+=n/2-i;
}else if(input[i]==input[j]){
for(int k=j;k<Size;k++){
swap(input[k],input[k+1]);
result++;
}
Size--;
break;
}
}
}
cout<<result<<endl;
return 0;
}
CATALOG
  1. 1. 蓝桥杯 基础练习(上)
    1. 1.1. BASIC-13 数列排序
      1. 1.1.1. 分析
      2. 1.1.2. 代码
    2. 1.2. BASIC-12 十六进制转八进制
      1. 1.2.1. 分析
      2. 1.2.2. 代码
    3. 1.3. BASIC-11 十六进制转十进制
      1. 1.3.1. 分析
      2. 1.3.2. 代码
    4. 1.4. BASIC-10 十进制转十六进制
      1. 1.4.1. 分析
      2. 1.4.2. 代码
    5. 1.5. BASIC-9 特殊回文数
      1. 1.5.1. 分析
      2. 1.5.2. 代码
    6. 1.6. BASIC-8 回文数
      1. 1.6.1. 分析
      2. 1.6.2. 代码
    7. 1.7. BASIC-7 特殊的数字
      1. 1.7.1. 分析
      2. 1.7.2. 代码
    8. 1.8. BASIC-6 杨辉三角形
      1. 1.8.1. 分析
      2. 1.8.2. 代码
    9. 1.9. BASIC-5 查找整数
      1. 1.9.1. 代码
    10. 1.10. BASIC-4 数列特征
      1. 1.10.1. 代码
    11. 1.11. BASIC-3 字母图形
      1. 1.11.1. 代码
    12. 1.12. BASIC-2 01字串
      1. 1.12.1. 代码
    13. 1.13. BASIC-1 闰年判断
      1. 1.13.1. 代码
    14. 1.14. BASIC-14 时间转换
      1. 1.14.1. 分析
      2. 1.14.2. 代码
    15. 1.15. BASIC-15 字符串对比
      1. 1.15.1. 分析
      2. 1.15.2. 代码
    16. 1.16. BASIC-16 分解质因数
      1. 1.16.1. 分析
      2. 1.16.2. 代码
    17. 1.17. BASIC-17 矩阵乘法
      1. 1.17.1. 分析
      2. 1.17.2. 代码
    18. 1.18. BASIC-18 矩形面积交
      1. 1.18.1. 分析
      2. 1.18.2. 代码
    19. 1.19. BASIC-19 完美的代价
      1. 1.19.1. 分析
      2. 1.19.2. 代码