第十一届蓝桥杯国赛题解A~D

所有题目链接：https://acm.sicnu.edu.cn/contest/99/problems

美丽的2（5分 暴力）扩散（10分 bfs）阶乘约数（10分 数论）本质上升序列（10分 dp）

题目：

思路：
直接一个一个找就行了 easy
代码：

#include
using namespace std;
bool check(int x){
	while(x){
		int res = x%10;
		if(res == 2) return 1;
		x /= 10;
	}
	
	return 0;
}
int main(){
	int ans = 0;
	for(int i = 2;i<=2020;i++){
		if(check(i)) ans++;
	}
	cout< 
 
扩散（10分 bfs） 
题目：
 
 思路：
 设置有多个起始状态的广搜（bfs）
 过题代码：
 
#include
#include
using namespace std;
int dx[5] = {-1,0,1,0},dy[5] = {0,1,0,-1};
char g[10000][10000];
int dist[10000][10000];//同时记录距离  和   是否走过了 
struct node{
	int x,y;
};
void bfs(){
	memset(dist,-1,sizeof dist);
	queue q;
    g[3000][3000] = '*';g[5020][3011] = '*';
	g[3011][3014] = '*';g[5000][5000] = '*';
	q.push({3000,3000});dist[3000][3000]=0;
	q.push({5020,3011});dist[5020][3011]=0;
	q.push({3011,3014});dist[3011][3014]=0;
	q.push({5000,5000});dist[5000][5000]=0;
	while(q.size()){ 
		node t = q.front();//每次取队列头
		q.pop();
		if(dist[t.x ][t.y]==2020) return;   //如果当前已经达到时间了  就返回
		 
		for(int i = 0; i < 4; i++){
			
			int x = t.x  + dx[i],y = t.y + dy[i];
			if(x < 0||y < 0||x > 10000||y > 10000) continue;
			//越界剪枝 
			if(g[x][y] == '*'||dist[x][y] != -1) continue;			
			//不用变色和   已经走过了 
			g[x][y] = '*';
			q.push({x,y});
			dist[x][y] = dist[t.x][t.y] + 1;
		} 
	}
} 
int main(){
	int ans = 0;
	bfs();
	for(int i = 0; i < 10000;i++){
		for(int j = 0;j<10000;j++){
			if(g[i][j]=='*') ans++;
		}
	}
	cout< 
 
阶乘约数（10分 数论） 
题目：
 
 思路：（分解质因数+约数定理）
 
 
 
每一个数都可以变成若干个质数相乘 ——> 分解质因数
 1.找到一个 最小的能整除的数
 2. 一直除一直除这个数 --> 确保这个下面的质因数 分解完了！！ 厉害！
 3.直到除不动 被除数加加 直到除不动的时候
 
 
约数定理： ——来源百度百科
 
 所以只需要记录每一个质因素的次数就能，就能算出100的阶乘有多少个约数了。
 
#include 
using namespace std;
int arr[105];
int main()
{ 
	//分解质因数
	int n = 100;
	for(int i = 2; i <= n; i++){
		int a = i;
			for(int j =  2; j <= a/j; j++){
				while(a%j==0){
					arr[j] += 1;
					a /= j;
				}  
			}
			if(a>1) arr[a] += 1;
	}
	//求因数
	long long res = 1;
	for(int i = 2; i <= 100;i++){
		if(arr[i]>0) res *= (arr[i]+1);
	}
	cout< 
 
本质上升序列（10分 dp） 

 解题思路：
 对于一个字符 ch ，要使用 ch 组成递增序列，必须将 ch 接在末尾字符比 ch 小的字符串之后，或者 ch 单独作为递增序列
 所以，以字符 ch 为末尾的递增序列的个数，是所有末尾字符比 ch 小的递增序列个数之和再加 1
 即 dp[ch] = dp[a] + dp[b] + ……+ dp[ch - 2] + dp[ch - 1] +1
 最后，以各个字符为末尾的递增序列的个数之和，就是答案
 
比如，输入字符串 “abc”，则有
 dp[a] = 1
 dp[b] = dp[a] + 1 = 2
 dp[c] = dp[a] + dp[b] + 1 = 4
 ans = dp[a] + dp[b] + dp[c] = 7
 
要注意时刻更新数值，比如输入 “acbdc”，顺序为
 dp[a] = 1
 dp[c] = dp[a] + dp[b] + 1 = 2
 dp[b] = dp[a] + 1 = 2
 dp[d] = dp[a] + dp[b] + dp[c] + 1 = 6
 dp[c] = dp[a] + dp[b] + 1 = 4
 ans = 1 + 2 + 4 + 6 = 13
 
而遇到连续相同的字符时可以跳过，避免重复运算
 
解题代码：
 
#include
using namespace std;
string s = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl" ;
int ans = 0;
int a[27] = {0};
int main(){
	for(int i = 0; i < 200;i++){
		//if (i > 0 && s[i] == s[i - 1]) continue; //剪枝
		int idx = s[i] - 'a'; 
		a[idx] = 1;
		for(int i = 0; i < idx; i++)	a[idx] += a[i];
	}		
	for(int i = 0; i < 26;i++)	ans += a[i];
	cout< 
字符的种类一共才26个。 完全可以跑出来。