2020年4月藍橋杯（軟體類）第二次模擬賽：題目+解答

1 容量單位

【問題描述】
在計算機存盤中，12.5MB是多少位元組？
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
答案
13107200
決議
12.5MB = 12.5x1024 KB = 12.5x1024x1024 B = 13107200B

2 最多邊數

【問題描述】
一個包含有2019個結點的有向圖，最多包含多少條邊？（不允許有重邊）
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
答案
4074342
決議
任意兩點組成邊，邊有向，一來一回算兩條邊 ，所以是 2 C n 2 = n ? ( n ? 1 ) 2C_n^2=n*(n-1) 2Cn2?=n?(n?1)

3 單詞重排

【問題描述】
將LANQIAO中的字母重新排列，可以得到不同的單詞，如LANQIAO、AAILNOQ等，注意這7個字母都要被用上，單詞不一定有具體的英文意義，
請問，總共能排列如多少個不同的單詞，
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
答案
2520
決議
求全排列，去重，計數， A 7 7 / 2 = 2520 A_7^7/2=2520 A77?/2=2520

4 括號序列

【問題描述】
由1對括號，可以組成一種合法括號序列：()，
由2對括號，可以組成兩種合法括號序列：()()、(())，
由4對括號組成的合法括號序列一共有多少種？
【答案提交】
這是一道結果填空的題，你只需要算出結果后提交即可，本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分，
答案
14
決議
深度為1的序列有1種：()()()()
深度為2的有7種：(())()()、()(())()、()()(())、(()()())、(()())()、()(()())、(())(())
深度為3的有5種：((()))()、()((()))、((())())、(()(()))、((()()))
深度為4的有1種：(((())))
所以答案為：1+7+5+1=14，

5 反倍數

【問題描述】
給定三個整數 a, b, c，如果一個整數既不是 a 的整數倍也不是 b 的整數倍還不是 c 的整數倍，則這個數稱為反倍數，
請問在 1 至 n 中有多少個反倍數，
【輸入格式】
輸入的第一行包含一個整數 n，
第二行包含三個整數 a, b, c，相鄰兩個數之間用一個空格分隔，
【輸出格式】
輸出一行包含一個整數，表示答案，
【樣例輸入】
30
2 3 6
【樣例輸出】
10
【樣例說明】
以下這些數滿足要求：1, 5, 7, 11, 13, 17, 19, 23, 25, 29，
【評測用例規模與約定】
對于 40% 的評測用例，1 <= n <= 10000，
對于 80% 的評測用例，1 <= n <= 100000，
對于所有評測用例，1 <= n <= 1000000，1 <= a <= n，1 <= b <= n，1 <= c <= n，
決議
迭代+判斷

代碼

#include<iostream>
using namespace std; 

int main(){
 int n=0;
 cin>>n;
 int a=0,b=0,c=0;
 cin>>a>>b>>c;
 int count = 0;
 for(int i=1; i<=n; i++){
  if(i%a!=0&&i%b!=0&&i%c!=0)
   count++;
 }
 cout<<count<<endl;
 return 0;
}

6 凱撒密碼

【問題描述】
給定一個單詞，請使用凱撒密碼將這個單詞加密，
凱撒密碼是一種替換加密的技術，單詞中的所有字母都在字母表上向后偏移3位后被替換成密文，即a變為d，b變為e，…，w變為z，x變為a，y變為b，z變為c，
例如，lanqiao會變成odqtldr，
【輸入格式】
輸入一行，包含一個單詞，單詞中只包含小寫英文字母，
【輸出格式】
輸出一行，表示加密后的密文，
【樣例輸入】
lanqiao
【樣例輸出】
odqtldr
【評測用例規模與約定】
對于所有評測用例，單詞中的字母個數不超過100，

決議
遍歷+轉換

代碼

#include<iostream>
using namespace std; 

int main(){
 string str;
 getline(cin, str);
 for(int i=0; i<str.size(); i++) 
 {
  if(str[i]<'x')
   str[i] = str[i] + 3;
  else
   str[i] = str[i] - 23; 
 }
 cout<<str<<endl;
 return 0;
}

7 螺旋

【問題描述】
對于一個 n 行 m 列的表格，我們可以使用螺旋的方式給表格依次填上正整數，我們稱填好的表格為一個螺旋矩陣，
例如，一個 4 行 5 列的螺旋矩陣如下：
1 2 3 4 5
14 15 16 17 6
13 20 19 18 7
12 11 10 9 8
【輸入格式】
輸入的第一行包含兩個整數 n, m，分別表示螺旋矩陣的行數和列數，
第二行包含兩個整數 r, c，表示要求的行號和列號，
【輸出格式】
輸出一個整數，表示螺旋矩陣中第 r 行第 c 列的元素的值，
【樣例輸入】
4 5
2 2
【樣例輸出】
15
【評測用例規模與約定】
對于 30% 的評測用例，2 <= n, m <= 20，
對于 70% 的評測用例，2 <= n, m <= 100，
對于所有評測用例，2 <= n, m <= 1000，1 <= r <= n，1 <= c <= m，

分析
先確定矩陣的上下左右邊界，然后按順時針依次存入每條邊界，存完一輪邊界后（一圈四次），更新邊界，直到存入的元素數=n*m時，結束回圈，

代碼

#include<iostream>
#include<vector>
using namespace std; 

int main(){
 int n=0,m=0,r=0,c=0;
 cin>>n>>m;
 cin>>r>>c;
 vector<vector<int> > M(n, vector<int>(m,0));
 
 int count=0;
 //初始化上、下、左、右的邊界 
 int top=0, bottle=n-1, left=0, right=m-1;
 
 while(count<m*n){
  //上 
  for(int j=left; j<=right&&count<m*n; j++)
   M[top][j] = ++count;
  //右 
  for(int i=top+1; i<=bottle&&count<m*n; i++)
   M[i][right] = ++count;
  //下 
  for(int j=right-1; j>=left&&count<m*n; j--)
   M[bottle][j] = ++count;
  //左 
  for(int i=bottle-1; i>=top+1&&count<m*n; i--)
   M[i][left] = ++count;
  //更新邊界 
  top++;
  bottle--;
  left++;
  right--;
 }
 
 cout<<M[r-1][c-1]<<endl;; 
 return 0;
}

8 擺動序列

【問題描述】
如果一個序列的奇數項都比前一項大，偶數項都比前一項小，則稱為一個擺動序列，即 a[2i]<a[2i-1], a[2i+1]>a[2i]，
小明想知道，長度為 m，每個數都是 1 到 n 之間的正整數的擺動序列一共有多少個，
【輸入格式】
輸入一行包含兩個整數 m，n，
【輸出格式】
輸出一個整數，表示答案，答案可能很大，請輸出答案除以10000的余數，
【樣例輸入】
3 4
【樣例輸出】
14
【樣例說明】
以下是符合要求的擺動序列：
2 1 2
2 1 3
2 1 4
3 1 2
3 1 3
3 1 4
3 2 3
3 2 4
4 1 2
4 1 3
4 1 4
4 2 3
4 2 4
4 3 4
【評測用例規模與約定】
對于 20% 的評測用例，1 <= n, m <= 5；
對于 50% 的評測用例，1 <= n, m <= 10；
對于 80% 的評測用例，1 <= n, m <= 100；
對于所有評測用例，1 <= n, m <= 1000，

思路
深度優先搜索，實作時間復雜度：O(n^3)，解題步驟如下：

(1) 確定題目要求
奇數項>偶數項，偶數項<奇數項，組成搖擺數列，
因此，第一項last1可以是：2 ~ n
第二項last2可以是：1 ~ last-1
第三項last3可以是：last3+1 ~ n
…
第k項lastk可以時：

• 若k為奇數，lastk可以是：last(k-1)+1 ~ n
• 若k為偶數，lastk可以是：1 ~ last(k-1)-1

(2) 設定遞回函式f()，確定遞回公式
假設：當第k個數確定為last時，該序列所有的情況數是f(k, last)

則f(1, 2) ：表示當第1個數是2時，序列的所有情況數
f(1, 3)：表示當第1個數是3時，序列的所有情況數

因此所有的情況數：f(1, 2) + f(1, 3) + … + f(1, m)
現在分別求出：f(1, 2) 、f(1, 3)、…、f(1, m)即可

我們知道

• 若k為偶數，f(k, last) 可以分成第k+1個數是：last+1、last+2、、、n 這么多種情況，即有：f(k, last) = f(k+1, last+1) + f(k+1, last+2) + … + f(k+1, n)
• 若k為奇數，f(k, last)可以分成：f(k, last) = f(k+1, 1) + f(k+1, 2) + … + f(k+1, last-1)

因此，可一總結出遞推公式：

• 若k為奇數

for(int i=1; i<last; i++)
	dfs(k, last) += dfs(k+1, i) 

• 若k為偶數

for(int i=last+1; i<n+1; i++)
	dfs(k, last) += dfs(k+1, i) 

(3) 確定遞回起點
而遞回起點（選定第一位，可選是2 to n）也是一個回圈：

for i in range(2, n + 1):
    ans = (ans + dfs(i, 1)) % MOD

代碼

#include<iostream>
using namespace std;

int MOD =10000;
int mem[1001][1001]; 
int m=0, n=0;

//第k個數確定為last時，序列的總數 
int dfs(int k, int last){
	if(k==m)
		return 1;
	if(mem[k][last]!=0)
		return mem[k][last]; 
	if(k%2==1) //奇數 
		for(int i=1; i<last; i++)
			mem[k][last] = (mem[k][last] + dfs(k+1, i))%MOD;
	else    //偶數 
		for(int i=last+1; i<n+1; i++)
			mem[k][last] = (mem[k][last] + dfs(k+1, i))%MOD;
	return mem[k][last];
}

int main()
{
	cin>>m>>n;
	int ans = 0;
	for(int j=2; j<n+1; j++)
		ans = (ans + dfs(1, j))%MOD;
	cout<<ans<<endl;
	
	return 0; 
} 

9 通電

【問題描述】
2015年，全中國實作了戶戶通電，作為一名電力建設者，小明正在幫助一帶一路上的國家通電，
這一次，小明要幫助 n 個村莊通電，其中 1 號村莊正好可以建立一個發電站，所發的電足夠所有村莊使用，
現在，這 n 個村莊之間都沒有電線相連，小明主要要做的是架設電線連接這些村莊，使得所有村莊都直接或間接的與發電站相通，
小明測量了所有村莊的位置（坐標）和高度，如果要連接兩個村莊，小明需要花費兩個村莊之間的坐標距離加上高度差的平方，形式化描述為坐標為 (x_1, y_1) 高度為 h_1 的村莊與坐標為 (x_2, y_2) 高度為 h_2 的村莊之間連接的費用為
s q r t ( ( x 1 ? x 2 ) ? ( x 1 ? x 2 ) + ( y 1 ? y 2 ) ? ( y 1 ? y 2 ) ) + ( h 1 ? h 2 ) ? ( h 1 ? h 2 ) sqrt((x_1-x_2)*(x_1-x_2)+(y_1-y_2)*(y_1-y_2)) + (h_1-h_2)*(h_1-h_2) sqrt((x1??x2?)?(x1??x2?)+(y1??y2?)?(y1??y2?))+(h1??h2?)?(h1??h2?)，
在上式中 sqrt 表示取括號內的平方根，請注意括號的位置，高度的計算方式與橫縱坐標的計算方式不同，
由于經費有限，請幫助小明計算他至少要花費多少費用才能使這 n 個村莊都通電，
【輸入格式】
輸入的第一行包含一個整數 n ，表示村莊的數量，
接下來 n 行，每個三個整數 x, y, h，分別表示一個村莊的橫、縱坐標和高度，其中第一個村莊可以建立發電站，
【輸出格式】
輸出一行，包含一個實數，四舍五入保留 2 位小數，表示答案，
【樣例輸入】
4
1 1 3
9 9 7
8 8 6
4 5 4
【樣例輸出】
17.41
【評測用例規模與約定】
對于 30% 的評測用例，1 <= n <= 10；
對于 60% 的評測用例，1 <= n <= 100；
對于所有評測用例，1 <= n <= 1000，0 <= x, y, h <= 10000，

思路

本題考查的是MST（Minimum Spanning Tree，最小生成樹），對于該類問題，一般有兩種解決方法：Prim和Kruskal，

Prim演算法是從點的方面考慮構建一顆MST，大致思想是：

• 設圖G頂點集合為U，首先任意選擇圖G中的一點作為起始點a，將該點加入集合V，此時集合V={a}；
• 再從集合U - V中找到另一點b使得點b到V中任意一點的權值最小，此時將b點也加入集合V，現在的集合V={a，b}；
• 再從集合U - V中找到另一點c使得點c到V中任意一點的權值最小，此時將c點加入集合V，此時V={a，b，c}；
• 以此類推，直至所有頂點全部被加入V，此時就構建出了一顆MST，因為有N個頂點，所以該MST就有N-1條邊，每一次向集合V中加入一個點，就意味著找到一條MST的邊，

代碼

#include<iostream>
#include<vector>
#include<cmath>
#include<stdio.h>
using namespace std;

//初始化 
const static int N = 1010;
double dis[N];
bool vis[N];

//計算距離 
double get_dist(int x1, int y1, int h1, int x2, int y2, int h2){
    return sqrt( (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) ) + (h1 - h2) * (h1 - h2);
}

//最小樹 
double minCostConnectPoints(vector<vector<int>>& points) {
    int n = points.size();
    for(int i = 0; i < n; i ++){
        dis[i] = 1e8;
    }
    dis[0] = 0;
    for(int i = 0; i < n; i ++)
    {
        int t = -1;
        int minn = 1e8;
        for(int j = 0; j < n; j ++)
            if(! vis[j] && (t == -1 || dis[j] < minn))
                t = j,minn = dis[j];
        vis[t] = true;
        
        for(int j = 0; j < n; j ++)
            if(! vis[j])
                dis[j] = min(dis[j], get_dist(points[j][0],points[j][1],points[j][2],points[t][0],points[t][1],points[t][2]));
    }
    
    double ans = 0;
    for(int i = 0; i < n; i ++)
        if(vis[i]) ans += dis[i];
    return ans;
}

int main(){
	
	// 輸入n個村莊的位置 
	int n=0;
	cin>>n;
	vector<vector<int> > Points(n, vector<int>(3,0));
	for(int i=0; i<n; ++i){
		for(int j=0; j<3; ++j){
			cin>>Points[i][j]; 
		}
	}
	
	//計算最小代價
	double ans = minCostConnectPoints(Points);
	printf("%.2f", ans);
	
	return 0;
}

10 植樹

【問題描述】
小明和朋友們一起去郊外植樹，他們帶了一些在自己實驗室精心研究出的小樹苗，
小明和朋友們一共有 n 個人，他們經過精心挑選，在一塊空地上每個人挑選了一個適合植樹的位置，總共 n 個，他們準備把自己帶的樹苗都植下去，
然而，他們遇到了一個困難：有的樹苗比較大，而有的位置挨太近，導致兩棵樹植下去后會撞在一起，
他們將樹看成一個圓，圓心在他們找的位置上，如果兩棵樹對應的圓相交，這兩棵樹就不適合同時植下（相切不受影響），稱為兩棵樹沖突，
小明和朋友們決定先合計合計，只將其中的一部分樹植下去，保證沒有互相沖突的樹，他們同時希望這些樹所能覆寫的面積和（圓面積和）最大，
【輸入格式】
輸入的第一行包含一個整數 n ，表示人數，即準備植樹的位置數，
接下來 n 行，每行三個整數 x, y, r，表示一棵樹在空地上的橫、縱坐標和半徑，
【輸出格式】
輸出一行包含一個整數，表示在不沖突下可以植樹的面積和，由于每棵樹的面積都是圓周率的整數倍，請輸出答案除以圓周率后的值（應當是一個整數），
【樣例輸入】
6
1 1 2
1 4 2
1 7 2
4 1 2
4 4 2
4 7 2
【樣例輸出】
12
【評測用例規模與約定】
對于 30% 的評測用例，1 <= n <= 10；
對于 60% 的評測用例，1 <= n <= 20；
對于所有評測用例，1 <= n <= 30，0 <= x, y <= 1000，1 <= r <= 1000，

決議
博主正在努力更新中，，，

相關文章
2020年3月藍橋杯（軟體類）第一次模擬賽：題目+解答