第十一屆藍橋杯大賽軟體類省賽第二場C/C++大學A組

第一題：門牌制作（5分）

問題描述

小藍要為一條街的住戶制作門牌号。

這條街一共有 2020 位住戶，門牌号從 1 到 2020 編号。

小藍制作門牌的方法是先制作 0 到 9 這幾個數字字元，最後根據需要将字元粘貼到門牌上，例如門牌 1017 需要依次粘貼字元 1、0、1、7，即需要 1 個字元 0，2 個字元 1，1 個字元 7。請問要制作所有的 1 到 2020 号門牌，總共需要多少個字元 2？

題目分析

暴力搜尋，判斷每個位置的字元是否滿足條件

#include<iostream>
using namespace std;
//判斷num上有幾個2
int calu(int num)
{
	int ans = 0;
	while (num)
	{
		if (num % 10 == 2)
		{
			ans++;
		}
		num /= 10;
	}
	return ans;
}
int main()
{
	int cnt = 0;
	暴力搜尋
	for (int i = 1; i <= 2020; i++)
	{
		cnt += calu(i);
	}
	cout << cnt << endl;
	return 0;
}
           

題目答案：624

第二題：既約分數（5分）

問題描述

如果一個分數的分子和分母的最大公約數是 1，這個分數稱為既約分數。

例如，3/4 , 5/2 , 1/8 , 7/1 都是既約分數。

請問，有多少個既約分數，分子和分母都是 1 到 2020 之間的整數（包括 1 和 2020）？

題目分析

暴力搜尋，通過最大公約數判斷

#include<iostream>
using namespace std;
//求a，b的最大公約數
int gcd(int a, int b)
{
	int temp;
	temp = (a > b) ? b : a;//a>b成立，temp=b，否則temp=a
	while (temp > 0)
	{
		if (a % temp == 0 && b % temp == 0)
		{
			break;
		}
		temp--;
	}
	return temp;
}
//這種算法更快，輾轉相除法，目前沒看懂
int gcd(int a, int b)
{
	if (a % b == 0)
		return b;
	else
		return gcd(b, a % b);
}
int main()
{
	int sum = 0;
	for (int i = 1; i <= 2020; i++)
	{
		for (int j = 1; j <= 2020; j++)
		{
			if (gcd(i, j) == 1)
			{
				sum++;
			}
		}
	}
	cout << sum << endl;
	return 0;
}
           

題目答案：2481215

第三題：蛇形填數（10分）

題目描述

如下圖所示，小明用從 1 開始的正整數“蛇形”填充無限大的矩陣。

1 2 6 7 15 …

3 5 8 14 …

4 9 13 …

10 12 …

11 …

…

容易看出矩陣第二行第二列中的數是 5。請你計算矩陣中第 20 行第 20 列的數是多少？

題目分析

可以将圖形順時針旋轉45度，我們可以發現20行20列應該位于第39層的中間一個（2n-1）

1行1列	       1
	  	      3 2
2行2列	     4 5 6
	        10 9 8 7
3行3列	 11 12 13 14 15
           

題目代碼

#include<iostream>
using namespace std;
int main()
{
	int sum = 0, ans = 0;
	//第20行第20列為轉換後的第39行中間的數（2*n-1）
	int n=20;
	n = 2 * n - 1;
	//先計算第39行最後一個數sum，然後（2sum-n+1）/2為ans
	for (int i = 1; i <= n; i++)//看規律，每一行最大的數為前面的行數相加
	{
		sum += i;
	}
	ans = (2 * sum - n + 1) / 2;
	cout << ans << endl;
}
           

題目答案：761

第四題：七段碼（10分）–看不懂

題目描述

小藍要用七段碼數位管來表示一種特殊的文字。

七段碼上圖給出了七段碼數位管的一個圖示，數位管中一共有 7 段可以發光的二極管，分别标記為 a, b, c, d, e, f, g。小藍要選擇一部分二極管（至少要有一個）發光來表達字元。在設計字元的表達時，要求所有發光的二極管是連成一片的。

例如：b 發光，其他二極管不發光可以用來表達一種字元。

例如：c 發光，其他二極管不發光可以用來表達一種字元。這種方案與上一行的方案可以用來表示不同的字元，盡管看上去比較相似。

例如：a, b, c, d, e 發光，f, g 不發光可以用來表達一種字元。

例如：b, f 發光，其他二極管不發光則不能用來表達一種字元，因為發光的二極管沒有連成一片。

請問，小藍可以用七段碼數位管表達多少種不同的字元？

//a-1,b-2,c-3,d-4,e-5,f-6,g-7
#include<iostream>
using namespace std;
bool con[8][8];
int father[8];
int sum = 0;
bool vis[8];
int find(int n)//并查集
{
	if (father[n] == n)
	{
		return n;
	}
	else {
		father[n] = find(father[n]);//路徑壓縮
		return father[n];
	}
}
void dfs(int t)//枚舉過程
{
	if (t > 7)
	{
		for (int i = 1; i <= 7; i++)
		{
			father[i] = i;
		}
		for (int i = 1; i <= 7; i++)
			for (int j = 1; j <= 7; j++)
			{
				if (vis[i] && vis[j] && con[i][j])
				{
					int x = find(i), y = find(j);
					if (x != y)
					{
						father[x] = y;//改變父類
					}
				}
			}
		int k = 0;
		for (int i = 1; i <= 7; i++)
		{
			if (vis[i] && father[i] == i) k++;//全體元素隻有一個根
		}
		if (k == 1) sum++;
		return;
	}
	//DFS中典型的二叉樹形搜尋樹
	vis[t] = 1;
	dfs(t + 1);
	vis[t] = 0;
	dfs(t + 1);
}
int main()
{
	con[1][2] = con[1][6] = 1;
	con[2][1] = con[2][7] = con[2][3] = 1;
	con[3][7] = con[3][4] = con[3][2] = 1;
	con[4][5] = con[4][3] = 1;
	con[5][4] = con[5][7] = con[5][6] = 1;
	con[6][1] = con[6][7] = con[6][5] = 1;
	con[7][6] = con[7][5] = con[7][2] = con[7][3] = 1;
	dfs(1);
	cout << sum << endl;
	return 0;
}
           

題目答案：80

第五題：平面分割（15分）

題目描述

20 個圓和20 條直線最多能把平面分成多少個部分？

題目分析

畫圖找規律，列出計算式，遞歸

題目代碼

#include<iostream>
using namespace std;
//畫圖找規律
int f1(int x)
{
	if (x == 1)
	{
		return 2;//一個圓把平面分為2部分
	}
	/*每個圓都與其它 x-1 個圓各交于 2(x-1) 個點，
	是以每個圓上都有 2(x-1) 個交點，
	則每個圓都被分割成了 2(x-1) 個小段，
	是以 x 個圓有 2x(x-1) 個小段
	每增加一個圓弧小段就增加 2 個區域，
	是以第 x 個圓使平面增加了 2(x-1) 個區域*/
	else if(x > 1)
	{
		return f1(x - 1) + 2 * (x - 1);
		x--;
	}
}
int f2(int x, int y)
{
	if (y == 1)
	{
		return f1(x)+2*x;//一條直線把x個圓分為：x個圓分割的個數 + 2*圓的個數
	}
	/*第 y 條直線與其它 y-1 條直線最多交于 y-1 個點，
	與 x 個圓最多交于 2x 個點,交點增加了 2x+y-1 個點，區域個數加1*/
	else if (y > 1)
	{
		return f2(x, y - 1) + 2 * x + y;
		y--;
	}
}


int main()
{
	cout << f2(20, 20) << endl;
	return 0;
}
           

題目答案：1391

第六題：成績統計（15分）

題目描述

小藍給學生們組織了一場考試，卷面總分為100 分，每個學生的得分都是一個0 到100 的整數。請計算這次考試的最高分、最低分和平均分。

【輸入格式】

輸入的第一行包含一個整數n，表示考試人數。

接下來n 行，每行包含一個0 至100 的整數，表示一個學生的得分。

【輸出格式】

輸出三行。

第一行包含一個整數，表示最高分。

第二行包含一個整數，表示最低分。

第三行包含一個實數，四舍五入保留正好兩位小數，表示平均分。

【樣例輸入】

7

80

92

56

74

88

99

10

【樣例輸出】

99

10

71.29

【評測用例規模與約定】

對于50% 的評測用例， 1 ≤ n ≤ 100。

對于所有評測用例，1 ≤ n ≤10000。

題目代碼

#include<iostream>
#include <iomanip>
using namespace std;
int main()
{
	int n,grade;
	cin >> n;
	int max = 0;
	int sum = 0;
	int min = 105;
	for (int i = 0; i < n; i++)
	{
		cin >> grade;
		if (grade > max)
		{
			max = grade;
		}
		if (grade < min)
		{
			min = grade;
		}
		sum += grade;
	}
	double aver = (sum *1.0 / n )+ 0.005;//+0.005目的為四舍五入
	cout << max << endl;
	cout << min << endl;
	//cout << fixed << setprecision(2);//隻輸出兩位小數，不要忘了頭檔案
	//cout << aver << endl;
	printf("%.2f\n", aver);
	return 0;
}
           

第七題：回文日期（20分）

題目描述

2020 年春節期間，有一個特殊的日期引起了大家的注意：2020年2月2日。因為如果将這個日期按“yyyymmdd” 的格式寫成一個8 位數是20200202，

恰好是一個回文數。我們稱這樣的日期是回文日期。

有人表示20200202 是“千年一遇” 的特殊日子。對此小明很不認同，因為不到2年之後就是下一個回文日期：20211202 即2021年12月2日。

也有人表示20200202 并不僅僅是一個回文日期，還是一個ABABBABA型的回文日期。對此小明也不認同，因為大約100 年後就能遇到下一個ABABBABA 型的回文日期：21211212 即2121 年12 月12 日。算不上“千年一遇”，頂多算“千年兩遇”。

給定一個8 位數的日期，請你計算該日期之後下一個回文日期和下一個ABABBABA型的回文日期各是哪一天。

【輸入格式】

輸入包含一個八位整數N，表示日期。

【輸出格式】

輸出兩行，每行1 個八位數。第一行表示下一個回文日期，第二行表示下

一個ABABBABA 型的回文日期。

【樣例輸入】

20200202

【樣例輸出】

20211202

21211212

【評測用例規模與約定】

對于所有評測用例，10000101 ≤ N ≤ 89991231，保證N 是一個合法日期的8位數表示。

題目分析

需要用到的知識點：reverse翻轉字元串，int類型轉換為string，判斷回文數，年月日++；

題目代碼

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int m[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
int year, month, day;
//将int轉換為字元串型
string change(int year, int month, int day)
{
	string ans = "";
	ans = ans + char(year / 1000 + '0') + char(year % 1000 / 100 + '0') + char(year % 100 / 10 + '0') + char(year % 10 + '0');
	ans = ans + char(month / 10 + '0') + char(month % 10 + '0');
	ans = ans + char(day / 10 + '0') + char(day % 10 + '0');
	return ans;
}
//判斷是否為閏年
bool isrun(int year)
{
	if (year % 400 == 0 || year % 100 != 0 && year % 4 == 0)
	{
		m[2] = 29;
		return true;
	}
	else
	{
		return false;
	}
}
//判斷是否是回文數
bool judge1(string s)
{
	string s1 = s;
	reverse(s.begin(), s.end());
	if (s1 == s)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//判斷是否為AB型的回文數
bool judge2(string s)
{
	if (s[0] == s[2] && s[1] == s[3] && s[1] != s[0])
	{
		return true;
	}
	else
	{
		return false;
	}
}

string ans, cnt;
int main()
{
	int n;
	cin >> n;
	year = n / 10000;
	month = n / 100 % 100;//注意
	day = n % 100;
	bool b1 = 1, b2 = 1;//輔助變量
	while (1)
	{
		day++;
		if (day == 32 && month == 12)
		{
			day = 1;
			month = 1;
			year++;
		}
		if (day == 31 && (month == 4 || month == 6 || month == 9 || month == 11))
		{
			day = 1;
			month++;
		}
		if ((day == 29 && month == 2 && !isrun(year)) || day == 30 && month == 2 && isrun(year))
		{
			day = 1;
			month = 3;
		}
		if (day == 32 && (month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10))
		{
			day = 1;
			month++;
		}
		string temp = change(year, month, day);
		//cout << temp;
		if (judge1(temp))
		{
			if (b1)
			{
				ans = temp;
				b1 = 0;
			}
			if (b2)
			{
				if (judge2(temp))
				{
					cnt = temp;
					b2 = 0;
					break;
				}
			}
		}
	}
	cout << ans << endl << cnt << endl;
	return 0;
}
           

題目輸出：20211202

21211212

第八題：子串分值

題目描述

對于一個字元串S，我們定義S 的分值 f(S) 為S中恰好出現一次的字元個數。例如f (”aba”) = 1，f (”abc”) = 3, f (”aaa”) = 0。

現在給定一個字元串S[0…n-1]（長度為n），請你計算對于所有S的非空子串S[i…j](0 ≤ i ≤ j < n)， f (S[i… j]) 的和是多少。

【輸入格式】

輸入一行包含一個由小寫字母組成的字元串S。

【輸出格式】

輸出一個整數表示答案。

【樣例輸入】

ababc

【樣例輸出】

21

【樣例說明】

子串 f值：

a 1

ab 2

aba 1

abab 0

ababc 1

b 1

ba 2

bab 1

babc 2

a 1

ab 2

abc 3

b 1

bc 2

c 1

【評測用例規模與約定】

對于20% 的評測用例，1 ≤ n ≤ 10；

對于40% 的評測用例，1 ≤ n ≤ 100；

對于50% 的評測用例，1 ≤ n ≤ 1000；

對于60% 的評測用例，1 ≤ n ≤ 10000；

對于所有評測用例，1 ≤ n ≤ 100000。

題目分析

暴力搜尋了解較容易，但不能滿分，下面連結是較快算法，目前沒看懂。

字串分值和

題目代碼

#include<bits/stdc++.h>//萬能頭檔案
using namespace std;
typedef long long int ll;
ll ans = 0;
int a[26];
string s;
void getval(int x, int y)
{
	memset(a, 0, sizeof(a));//把數組a全部指派為0
	for (int i = x; i <= y; i++)
	{
		a[s[i] - 'a']++;//字母的個數
	}
	for (int i = 0; i < 26; i++)
	{
		if (a[i] == 1)
		{
			ans++;
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	//cin，cout之是以效率低，是因為先把要輸出的東西存入緩沖區，再輸出，
	//導緻效率降低，而這段語句可以來打消iostream的輸入 輸出緩存，
	//可以節省許多時間，使效率與scanf與printf相差無幾
	cin >> s;
	int len = s.length();
	for (int i = 0; i < len; i++)
	{
		for (int j = i; j < len; j++)
		{
			getval(i, j);
		}
	}
	cout << ans << endl;
	return 0;
}
           

第九題：荒島探測

題目描述

科學家小藍來到了一個荒島，準備對這個荒島進行探測考察。小藍使用了一個超聲定位裝置來對自己進行定位。為了使用這個裝置，小藍需要在不同的點分别安裝一個固定的發射器和一個固定的接收器。小藍手中還有一個移動裝置。定位裝置需要從發射器發射一個信号到移動裝置，移動裝置收到後馬上轉發，最後由接收器接收，根據這些裝置之間傳遞的時間差就能計算出移動裝置距離發射器和接收器的兩個距離，進而實作定位。

小藍在兩個位置已經安裝了發射器和接收器，其中發射器安裝在坐标 ( x A , y A ) (x_A, y_A) (xA?,yA?)，接收器安裝在坐标 ( x B , y B ) (x_B, y_B) (xB?,yB?)。小藍的發射器和接收器可能在島上，也可能不在島上。小藍的定位裝置設計有些缺陷，當發射器到移動裝置的距離加上移動裝置到接收器的距離之和大于L 時，定位裝置工作不正常。當和小于等于L 時，定位裝置工作正常。為了安全，小藍隻在定位裝置工作正常的區域探測考察。

已知荒島是一個三角形，三個頂點的坐标分别為 ( x 1 , y 1 ) (x_1, y_1) (x1?,y1?), ( x 2 , y 2 ) (x_2, y_2) (x2?,y2?), ( x 3 , y 3 ) (x_3, y_3) (x3?,y3?)。

請計算，小藍在荒島上可以探測到的面積有多大？

【輸入格式】

輸入的第一行包含五個整數，分别為 x A , y A , x B , y B , L x_A, y_A, x_B, y_B, L xA?,yA?,xB?,yB?,L。

第二行包含六個整數，分别為 x 1 , y 1 , x 2 , y 2 , x 3 , y 3 x_1, y_1, x_2, y_2, x_3, y_3 x1?,y1?,x2?,y2?,x3?,y3?。

【輸出格式】

輸出一行，包含一個實數，四舍五入保留2位小數，表示答案。

考慮到計算中的誤差，隻要你的輸出與參考輸出相差不超過0.01即可得分。

【樣例輸入】

10 6 4 12 12

0 2 13 2 13 15

【樣例輸出】

39.99

【樣例說明】

當輸出為39.98、39.99或40.00時可以得分。

題目分析

沒看懂荒島探測

第十題：字串排序

題目描述

小藍最近學習了一些排序算法，其中冒泡排序讓他印象深刻。在冒泡排序中，每次隻能交換相鄰的兩個元素。小藍發現，如果對一個字元串中的字元排序，隻允許交換相鄰的兩個字元，則在所有可能的排序方案中，冒泡排序的總交換次數是最少的。

例如，對于字元串 lan 排序，隻需要 1 次交換。對于字元串 qiao 排序，

總共需要 4 次交換。小藍找到了很多字元串試圖排序，他恰巧碰到一個字元串，需要 V 次交換，可是他忘了把這個字元串記下來，現在找不到了。

請幫助小藍找一個隻包含小寫英文字母且沒有字母重複出現的字元串，對該串的字元排序，正好需要 V 次交換。如果可能找到多個，請告訴小藍最短的那個。如果最短的仍然有多個，請告訴小藍字典序最小的那個。請注意字元串中可以包含相同的字元。

【輸入格式】

輸入的第一行包含一個整數V，小藍的幸運數字。

【輸出格式】

題面要求的一行字元串。

【樣例輸入】

4

【樣例輸出】

bbaa

【樣例輸入】

100

【樣例輸出】

jihkfeeddccbbaa

【評測用例規模與約定】

對于20% 的評測用例，1 ≤ n ≤ 20；

對于50% 的評測用例，1 ≤ n ≤ 100；

對于100% 的評測用例，1 ≤ n ≤ 10000；

題目分析

dfs+剪枝

dp