2020十月份藍橋杯B組省賽題解大全(害!附題面檔案和部分代碼~)

百度網盤2020省賽藍橋杯題目提取碼:6666

A:門牌制作

簽到題,答案是 624 624 624

B:既約分數

這個沒什么好說的,兩重回圈列舉分子分母

計算 g c d gcd gcd即可

答案:2481215

C:蛇形填數

代碼就是硬模擬,一次往左下,一次往右上…

答案:761

#include <bits/stdc++.h>
using namespace std;
int a[50][50],cnt=1;
int main()
{
    for(int i = 1 ; i <= 40; i++)
	{
        if(i % 2==1 )
		{
            for(int x = i, y = 1; x >= 1 && y <= i; x--, y++)
                a[x][y] = cnt++;
        }
        else
		{
            for(int x = 1, y = i; x <= i && y >= 1; x++, y--)
                a[x][y] = cnt++;
        }
    }
    printf("%d\n", a[20][20]);
	return 0;
}

D:跑步鍛煉

開一個 a [ 13 ] a[13] a[13]的陣串列示每個月多少天

然后列舉每一年,列舉每一天

每一年的開頭判斷閏年,也很簡單

答案:8879

E:七段碼

有 7 7 7根管子,所有組合是 7 ! 7! 7!種,所以使用二進制列舉或 d f s dfs dfs爆搜所有可能

然后選擇了一些點，相鄰的兩個點有邊

可以使用并查集判斷是否在一個連通塊,也可以用搜索判斷

答案:80

F:成績統計

沒什么好說的,四舍五入加上 0.5 0.5 0.5轉化為 i n t int int就好了

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n; cin >> n;
	double q=0,w=0;
	for(int i=1;i<=n;i++)
	{
		int x; cin >> x;
		if( x>=60 )	q+=100;
		if( x>=85 )	w+=100;
	}
	q/=n; w/=n;
	cout << (int)(q+0.5) << "%\n";
	cout << (int)(w+0.5) << "%";
}

G:回文日期

仍然是暴力列舉每一年,確定了年份就確定了這年的回文數字

比如某一年是 a b c d abcd abcd,那么想構成回文就一定是 d c dc dc月 b a ba ba天

所以就看一下這年存不存在這一天就好了,記得判斷閏年

(開始漏掉了第一年的情況,現在改了)

#include <bits/stdc++.h>
using namespace std;
int x,q,w,b[5];
int a[14]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool isok(int x)//判斷閏年 
{
	if( x%400==0 )	return true;
	if( x%100==0 )	return false;
	if( x%4==0 )	return true;
	return false;
}
int main()
{
	cin >> x;
	int lday = x%100, lmonth = x%10000;//天,月份 
	x /= 10000;//年份 
	for(int i=x;;i++)
	{
		if( isok(i) )	a[2]=29;//判斷閏年 
		else	a[2]=28;
		int temp=i;
		for(int j=1;j<=4;j++)//分解年份的數字
			b[j]=temp%10,temp/=10;
		int month=b[1]*10+b[2];//月份
		int day=b[3]*10+b[4];
		if( i==x && lmonth>month )	continue;//特判第一年 
		if( i==x && lmonth==month && lday>=day )	continue;//特判第一年 
		if( month>=1&&month<=12&&day>=1&&day<=a[month] )//存在這一天 
		{
			if( q==0 )	q=i*10000+month*100+day;//最近的回文串
			if( b[1]==b[3]&&b[2]==b[4] )	w= i*10000+month*100+day;//最近的AB型回文 
		}
		if( q&&w )//都找到了 
		{
			cout << q << "\n" << w;
			return 0;	
		} 
	} 
}

H:子串分值和

暴力列舉每個子串再判斷復雜度是 O ( n 3 ) O(n^3) O(n3)的,非常夸張

考慮列舉以每個 i i i開頭的子串

顯而易見子串 [ i , i ] [i,i] [i,i]的貢獻是 1 1 1

我們往后找到一個最小的 j j j滿足 a [ i ] ! = a [ j ] a[i]!=a[j] a[i]!=a[j]

說明 [ i , i ] , [ i , i + 1 ] , [ i , i + 2 ] . . . . . [ i , j ? 1 ] [i,i],[i,i+1],[i,i+2].....[i,j-1] [i,i],[i,i+1],[i,i+2].....[i,j?1]的所有子串貢獻都是 1 1 1

但是一到 [ i , j ] [i,j] [i,j]貢獻變成 2 2 2,這時候我們可以再往后找一個 a [ q ] ! = a [ i ] a[q]!=a[i] a[q]!=a[i]且 a [ q ] ! = a [ j ] a[q]!=a[j] a[q]!=a[j]

然后相同計算貢獻為 2 2 2的子串即可

這樣跳躍計算最多只需要跳躍 26 26 26次,因為每個字母最多跳躍一次

所以開個 i d [ 27 ] [ ] id[27][] id[27][]的二維陣列儲存每個字母的出現下標即可

補充,模擬一組樣例來體會一下這個思想

比如串 a a b a b c b b aababcbb aababcbb

現在列舉子串的左端點是 1 1 1,可以快速計算這類子串的總分

我們知道下一個最快出現的新字母在位置 3 3 3,是 b b b

所以左端點 1 1 1,右端點 ∈ [ 1 , 3 ? 1 ] \in[1,3-1] ∈[1,3?1]的子串分數都是 1 1 1

我們知道下一個最快出現的新字母在位置 6 6 6,是 c c c

所以左端點 1 1 1,右端點 ∈ [ 3 , 6 ? 1 ] \in[3,6-1] ∈[3,6?1]的子串分數都是 2 2 2

下面沒有新字母了,所以左端點 1 1 1,右端點 ∈ [ 6 , 8 ] \in[6,8] ∈[6,8]的子串分數都是 3 3 3

這樣列舉左端點,可以在最壞 O ( 26 n ) O(26n) O(26n)的復雜度計算答案

相信配合代碼很容易理解了

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;
int id[27][maxn],nu[27],b[27];//下標
char a[maxn]; 
long long ans;
int main()
{
	cin >> (a+1);
	int len=strlen(a+1);
	for(int i=1;i<=len;i++)
		id[a[i]-'a'][++nu[a[i]-'a']]=i;//記錄每個字母出現的下標 
	for(int i=1;i<=len;i++)//計算以i開頭的子串的貢獻 
	{
		int top=0;
		for(int j=0;j<=25;j++)//記錄每個字母最快出現在i之后的下標
		{
		 	if( id[j][ nu[j] ] >= i )//假如出現最晚的這個字母比i大才去查找,而且需要是第一次出現 
		 	{
				int index = lower_bound(id[j],id[j]+1+nu[j],i)-id[j];//二分查找加速 
				b[++top] = id[j][index];
			}
		}
		sort(b+1,b+1+top);//對每個字母的出現時間排序
		int last = i;
		for(int j=2;j<=top;j++)
		{
			ans += ( b[j]-last )*(j-1) ;
			last = b[j];	
		}
		ans += ( len-last+1 )*top;	
	} 
	cout << ans;
}

I.平面切分(這個是自己找的規律,僅供參考)

在圖上畫一畫發現直線若兩兩不平行,且沒有三點相交情況下

2 4 7 11 16 22 29 37…

就是一直加 2 2 2,加 3 3 3,加 4 4 4,加 5 5 5,加 6 6 6…

假設有一個點被 x x x條直線經過,形成的平面個數會少 x ? 1 x-1 x?1個

假如一種斜率有 x ( x > = 2 ) x(x>=2) x(x>=2)條直線,形成的平面會少 1 + 2 + . . . ( x ? 1 ) 1+2+...(x-1) 1+2+...(x?1)

代碼不放了,畢竟只是規律而已.

J.字串排序

參考隊友的話:(我太菜了居然沒寫出來??!!)

顯然要使長度最短，我們就不能浪費每一個字母，所以，一定有字母是遞減的順序的，

要使字典序最短，每個字母出現的數量一定是要遞減的，這樣就好了，，

限制一下每個字母最多出現的次數然后就是d f s dfsdfs爆搜，

//Author : lifehappy的墊腳石 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
char ans[N], res[N];
int n, len;
bool judge() 
{
	int i = len;
	while(ans[i] == res[i] && i) i--;
	return res[i] < ans[i];
}
void dfs(int now, int maxn, int m, int sum) {
	if(sum == n) 
	{
		if(m < len || (m == len && judge()))
		{
			len = m;
			for(int i = 1; i <= len; i++) 	ans[i] = res[i];
		}
		return;
	}
	if(now >= 26) return ;
	for(int i = 1; i <= maxn; i++) 
	{
		int temp = sum + m * i;
		if(temp > n) return ;
		res[m + i] = char(now + 'a');
		dfs(now + 1, i, m + i, temp);
	}
}

int main()
{
    len = 0x3f3f3f3f;
    scanf("%d", &n);
    dfs(0, 8, 0, 0);
    for(int i = len; i >= 1; i--)
		putchar(ans[i]);
	return 0;
}