2019年第十届蓝桥杯【省赛C/C++ A组】做题记录（附详细思路）

逃离我推掉我的手 2023-03-01 09:46 16阅读 0赞

### 第十届蓝桥杯【省赛C/C++ A组】 ###

*  试题A：平方和
 *  试题B：数列求值
 *  试题C：最大降雨量
 *  试题D：迷宫
 *  试题E：RSA解密
 *  试题F：完全二叉树的权值
 *  试题G：外卖店优先级
 *  试题H：修改数组
 *  试题I：糖果
 *  试题J：组合数问题
 *  总结

# 试题A：平方和 #

【问题描述】  
  小明对数位中含有 2、0、1、9 的数字很感兴趣，在 1 到 40 中这样的数包 括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574，平方和是 14362。 注意，平方和是指将每个数分别平方后求和。 请问，在 1 到 2019 中，所有这样的数的平方和是多少？  
  思路分析：**从1遍历到2019，先将遍历变量记录下来，接着对该变量进行分解，如果其中包含2019四个数字中的一个，就停止分解，累加平方至结果变量sum。**  
代码：

#include<bits/stdc++.h>
    using namespace std;
    
    int main() { 
    	long long sum=0;
    	for(int i=1;i<=2019;i++) { 
    		int j=i;
    		while(j) { 
    			if(j%10==2||j%10==0||j%10==1||j%10==9) { 
    				sum+=i*i;
    				break;
    			}
    			j/=10;
    		}
    	}
    	cout<<sum;//2658417853 
    	return 0;
    }

答案：2658417853

# 试题B：数列求值 #

【问题描述】  
  给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。求 第 20190324 项的最后 4 位数字。

思路分析：这道题其实就是考怎么防止溢出。求后四位数字，那就在每次求和之后都模上10000就好了。  
代码：

#include<bits/stdc++.h>
    using namespace std;
    
    const int mod=1e4;
    long long f[20190326];
    
    int main() { 
    	f[1]=f[2]=f[3]=1;
    	for(int i=4;i<=20190324;i++) { 
    		f[i]=(f[i-1]%mod+f[i-2]%mod+f[i-3]%mod)%mod;
    	}
    	cout<<f[20190324];
    	return 0;
    }

答案：4659

# 试题C：最大降雨量 #

【问题描述】  
  由于沙之国长年干旱，法师小明准备施展自己的一个神秘法术来求雨。 这个法术需要用到他手中的 49 张法术符，上面分别写着 1 至 49 这 49 个 数字。法术一共持续 7 周，每天小明都要使用一张法术符，法术符不能重复使 用。 每周，小明施展法术产生的能量为这周 7 张法术符上数字的中位数。法术 施展完 7 周后，求雨将获得成功，降雨量为 7 周能量的中位数。 由于干旱太久，小明希望这次求雨的降雨量尽可能大，请大最大值是多少？

思路分析：1到49四个数，分成7周，每周都有7个数，因此**中位数实际上就是第四周的中位数X。** 在第四周，还有三天要大于X，另外第五六七周各有4天大于X：这三周的中位数以及中位数后面的三天，因此一共有3\*4+3=15个数大于X，因此X=49-15=34。

答案：34

# 试题D：迷宫 #

详见：[第十届蓝桥杯省赛试题D：迷宫（BFS）][D_BFS]

# 试题E：RSA解密 #

详见：[【RSA解密】 蓝桥杯第十届省赛A组 扩展欧几里得算法（求逆元）+快速乘+快速幂][RSA_ _A_]

# 试题F：完全二叉树的权值 #

给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从上到下、从左到右的顺序依次是 A1, A2, ··· AN，如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]  
  现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点 权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。 注：根的深度是1。  
【输入格式】  
第一行包含一个整数 N。 第二行包含 N 个整数 A1, A2, ··· AN 。  
【输出格式】  
输出一个整数代表答案。  
【样例输入】  
7  
1 6 5 4 3 2 1  
【样例输出】  
2  
  思路分析：这道题的关键是**根据序号找到该节点对应的深度，** 代码如下：

// 获取下标为 n 的节点的深度 
    int getDepth(int n) { 
    	int res = 0;
    	while (n > 0) { 
    		n /= 2;
    		res++;
    	} 
    	return res;
    }

获得深度后就好做了，把每一层都累加起来就好了。  
代码：

#include<bits/stdc++.h>
    using namespace std; 
    
    const int MAX_DEPTH = 18;
    long long temp[MAX_DEPTH + 3];
    
    // 获取下标为 n 的节点的深度 
    int getDepth(int n) { 
    	int res = 0;
    	while (n > 0) { 
    		n /= 2;
    		res++;
    	} 
    	return res;
    }
    
    int main() { 
    	int n, t;
    	cin >> n;
    	for (int i = 1; i <= n; i++) { 
    		cin>>t;
    		temp[getDepth(i)] += t;
    	} 
    	int res = 0, resDepth;
    	for (int i = 1; i <= MAX_DEPTH; i++) { 
    		if (temp[i] > res) { 
    			res = temp[i];
    			resDepth = i;
    		}
    	}
    	cout << resDepth << endl;
    	return 0;
    }

# 试题G：外卖店优先级 #

【问题描述】  
  “饱了么”外卖系统中维护着 N 家外卖店，编号 1 ∼ N。每家外卖店都有 一个优先级，初始时 (0 时刻) 优先级都为 0。  
   每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减 到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。  
   如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；如果 优先级小于等于 3，则会被清除出优先缓存。  
   给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优 先缓存中。  
【输入格式】  
第一行包含 3 个整数 N、M 和 T。 以下 M 行每行包含两个整数 ts 和 id，表示 ts 时刻编号 id 的外卖店收到 一个订单。  
【输出格式】  
输出一个整数代表答案。  
【样例输入】  
2 6 6  
1 1  
5 2  
3 1  
6 2  
2 1  
6 2  
【样例输出】  
1  
【样例解释】  
  6时刻时，1 号店优先级降到 3，被移除出优先缓存；2 号店优先级升到 6， 加入优先缓存。所以是有 1 家店 (2 号) 在优先缓存中。  
【评测用例规模与约定】  
  对于 80% 的评测用例，1≤ N,M,T ≤10000。 对于所有评测用例，1≤ N,M,T ≤100000，1≤ts≤T，1≤id ≤ N。

思路分析：答案：暴力求解还是蛮简单的，只不过这样大概率会超时。

暴力求解思路：先输入所有的订单信息，按照时间排好序。接着遍历所有的订单信息，并跟所有的外卖店进行匹配，如果收到订单优先级加2并判断要不要进入优先缓存，否则优先级减一，并判断是否需要踢出优先缓存。  
代码：

#include<bits/stdc++.h>
    using namespace std;
    
    const int maxn=1e5;
    int n,m,t;
    struct out { 
    	int id;
    	int prior;
    }a[maxn+5];
    
    struct order { 
    	int ts;
    	int id;
    }b[maxn+5];
    
    set<int> s;   //优先缓存 
    
    bool cmp(order x,order y) { 
    	return x.ts<y.ts;
    }
    
    int main() { 
    	cin>>n>>m>>t;
    	for(int i=1;i<=n;i++) {     //初始时刻 
    		a[i].id=i;
    		a[i].prior=0;
    	}
    	for(int i=1;i<=m;i++) {     //先输入所有订单 
    		cin>>b[i].ts>>b[i].id;
    	}
    	sort(b+1,b+1+m,cmp);  //按时间顺序排好 
    	for(int i=1;i<=t;i++) { 
    		for(int j=1;j<=m;j++) { 
    			if(a[i].id!=b[j].id&&a[i].prior>0) { 
    				a[i].prior--;
    				if(a[i].prior<=3&&s.find(a[i].id)!=s.end()) { 
    					s.erase(a[i].id);
    				}
    			}else { 
    				a[i].prior+=2;
    				if(a[i].prior>=5) { 
    					s.insert(a[i].id);
    				}
    			}
    		}
    	}
    	cout<<s.size();
    	return 0;
    }

暂时想不出优化的方法。。。

# 试题H：修改数组 #

【问题描述】  
  给定一个长度为 N 的数组 A = \[A1,A2,···AN\]，数组中有可能有重复出现的整数。  
  现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改 A2,A3,··· ,AN。 当修改 Ai 时，小明会检查 Ai 是否在 A1 ∼ Ai−1 中出现过。如果出现过，则 小明会给 Ai 加上 1 ；如果新的 Ai 仍在之前出现过，小明会持续给 Ai 加 1 ，直 到 Ai 没有在 A1 ∼ Ai−1 中出现过。 当 AN 也经过上述修改之后，显然 A 数组中就没有重复的整数了。 现在给定初始的 A 数组，请你计算出最终的 A 数组。  
【输入格式】  
第一行包含一个整数 N。 第二行包含 N 个整数 A1,A2,··· ,AN 。  
【输出格式】  
输出 N 个整数，依次是最终的 A1,A2,··· ,AN。  
【样例输入】  
5 2 1 1 3 4  
【样例输出】  
2 1 3 4 5

思路分析：考场上先别想那么多，暴力就完事了，说不定还能拿下一半分数。 暴力求解代码：

#include<bits/stdc++.h>
    using namespace std;
    
    const int maxn=1e5+5;
    int a[maxn];
    int n;
    
    bool check(int n,int x) {    //检查x有没有在A1到An中出现过 
    	for(int i=1;i<=n;i++) { 
    		if(a[i]==x) { 
    			return false;
    		}
    	}
    	return true;
    }
    
    int main() { 
    	int n;
    	cin>>n;
    	for(int i=1;i<=n;i++) { 
    		cin>>a[i];
    	}
    	for(int i=2;i<=n;i++) { 
    		while(!check(i-1,a[i])) { 
    			a[i]++;
    		}
    	}
    	for(int i=1;i<=n;i++) { 
    		cout<<a[i]<<' ';
    	} 
    	return 0;
    }

这个百分百会超时…暂时想不出优化思路。

# 试题I：糖果 #

【问题描述】  
  糖果店的老板一共有 M 种口味的糖果出售。为了方便描述，我们将 M 种 口味编号 1∼ M。 小明希望能品尝到所有口味的糖果。遗憾的是老板并不单独出售糖果，而 是 K 颗一包整包出售。 幸好糖果包装上注明了其中 K 颗糖果的口味，所以小明可以在买之前就知 道每包内的糖果口味。 给定 N 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖 果。  
【输入格式】  
第一行包含三个整数 N、M 和 K。 接下来 N 行每行 K 这整数 T1,T2,··· ,TK，代表一包糖果的口味。  
【输出格式】 一个整数表示答案。如果小明无法品尝所有口味，输出 −1。  
【样例输入】  
6 5 3  
1 1 2  
1 2 3  
1 1 3  
2 3 5  
5 4 2  
5 1 2  
【样例输出】  
2

思路分析：考场上先直接跳过！！

# 试题J：组合数问题 #

【问题描述】  
  给 n,m,k，求有多少对 (i, j) 满足 1 ≤ i ≤ n,0 ≤ j ≤ min(i,m) 且 Cj i ≡ 0(mod k)，k 是质数。其中 Cj i 是组合数，表示从 i 个不同的数中选出 j 个组成 一个集合的方案数。  
【输入格式】  
  第一行两个数 t,k，其中 t 代表该测试点包含 t 组询问，k 的意思与上文中 相同。 接下来 t 行每行两个整数 n,m，表示一组询问。  
【输出格式】  
  输出 t 行，每行一个整数表示对应的答案。由于答案可能很大，请输出答 案除以 10^9 + 7 的余数。  
【样例输入】  
1 2  
3 3  
【样例输出】  
1  
【样例说明】  
在所有可能的情况中，只有  C 1 2 C\_\{1\}^\{2\} C12= 2 是 2 的倍数。  
【样例输入】  
2 5  
4 5  
6 7  
【样例输出】  
0  
7  
【数据规模和约定】  
  对于所有评测用例， 1 ≤ k ≤ 1 0 8 , 1 ≤ t ≤ 1 0 5 , 1 ≤ n , m ≤ 1 0 18 1≤k≤10^8,1≤t≤10^5,1≤n,m≤10^\{18\} 1≤k≤108,1≤t≤105,1≤n,m≤1018，且 k 是质数。 评测时将使用 10 个评测用例测试你的程序，每个评测用例的限制如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]  
  思路分析：这个题很不好做，要是暴力求解的话应该能拿下评测用例1,2，20分在正式考试也蛮不错了，那就先暴力求解吧。  
我们都知道：  
![在这里插入图片描述][20200725214834654.gif]  
因此暴力求解代码就很简单了：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    const ll maxn=1e9+7;
    ll n,m,t,k;
    ll f[2005][2005];
    
    void init(int k) { 
    	 for(int i=1;i<=2000;i++) { 
            f[i][0]=f[i][i]=1;
            for(int j=1;j<i;j++) { 
                f[i][j]=(f[i-1][j]%k+f[i-1][j-1]%k)%k;
            }
        }
    }
    int main() { 
    	cin>>t>>k;
    	init(k);
    	while(t--) { 
    		cin>>n>>m;
    		ll ans=0;
    		for(ll i=1;i<=n;i++) { 
    			ll t=min(i,m);
    			for(ll j=0;j<=t;j++) { 
    				if(!f[i][j]) { 
    					ans=((ans+1)%maxn);
    				}
    			}
    		}
    		cout<<ans<<endl;
    	}
    	return 0;
    }

# 总结 #

只会暴力求解是不行的，还得加强自身的硬实力！！

[D_BFS]: https://blog.csdn.net/Cyril_KI/article/details/105979098
[RSA_ _A_]: https://blog.csdn.net/Cyril_KI/article/details/107542867
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]: /images/20230209/acb1e486b7444fd69f6e14db158be30e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]: /images/20230209/beac21700437402284ac4bca47ba6982.png
[20200725214834654.gif]: /images/20230209/0feb24322fc245c4b9437797535e4560.png