2015年蓝桥杯B组C/C++决赛题解

2015年第六届蓝桥杯B组C/C++决赛题解

点击查看2015年第六届蓝桥杯B组C/C++国赛题目(不含答案)
 
 

1.积分之迷

三重循环 枚举A,B,C的值,如果满足两个条件:3个A + 7个B + 1个C = 15 ,4个A + 10个B + 1个C = 420 就是一组合法的解。 输出A+B+C就是答案
 
 

2.完美正方形

一开始以为很难,看了题解 都是用dfs暴力搜出来的
国赛第二题永远是用dfs解决。。

思路:dfs(x,y) 正方形想象成边长是47+46+61的网格(每个网格边长为1),
还剩下19个小正方形;
从 (0,0) 网格点开始搜,作为小正方形的(左上角的顶点),枚举19个小正方形放在当前网格里
搜索过程中标记是否使用过这块网格、是否使用过这个小正方形
 
 

3.关联账户

并查集思想
 
 

4.密文搜索 30%数据点:

按题目要求 全排列子串,用STL内置函数在主串中查找,string.find(s) != string::npos;

30-50%数据:

参考博客:https://blog.csdn.net/u014552756/article/details/51398775

100%数据点:

对于每个子串,先对它排序,从主串中依次截取8位,如果这8位对应的字母个数 等于 子串的各个字母个数,说明匹配上(因为子串顺序可以任意排列的,对比字符出现的次数就能比较是否匹配),可以用哈希表优化查找
参考博客:https://blog.csdn.net/weixin_42765557/article/details/89402941

5.居民集会 10%数据点:

先想到暴力枚举,题目让我们找3个位置当作集会点,那我们就在1~l-1区间内枚举3个集会点,三重循环
参考博客:https://www.cnblogs.com/zhazhaacmer/p/9020089.html

上面博客的做法中,我们有两点我们可以在优化时用到:
1.前三个集合地点肯定是要建在某个人的家里,这样可能更加省时
2.前缀和预处理,sum[i] 表示 1号家庭 到距离起点i 之间 所有家庭到i集会的花费总和,那么sum[i] - sum[j] (j < i) 就可以算出 从j到i之间所有家庭到i集会的花费总和,我们可以在时间复杂度O(n)下完成预处理!

另外,如果没想到暴力枚举和预处理,我们可以用dfs搜索来做这10%的数据,我自己用dfs做的。先不放上代码。

10%-30%数据点:

分治 + 预处理时间复杂度O(l^2n),如果数据比较弱可以过30%数据
参考博客:https://blog.csdn.net/the_best_man/article/details/72472919
上面博客做法,值得参考的点:分治算法。具体怎么分治呢?题目让我们选3个位置当作集会点,也就等于让我们把1~L区域划分成4段,例如样例1~10,我们从1~10中划分4段即可。
缺点:预处理时间复杂度太高了O(l^2n)

100%数据点:

上面博客做法的缺点:作者没有意识到前面我们说的 集会点在某个人家里更省时间,我们把作者的对距离1~L区间分治 改为对家庭1~n分治,再用前缀和预处理sum[i] 就可以完成
我不知道分治算法的时间复杂度怎么分析。。大概能过100%数据,如果过不了,当我没说。。

正常人的做法:DP动规,首先我认为这题和 BZOJ 叶子合并 很像。
dp[i][j]表示前i个家庭建立了j个集会点时的最小花费, 自己想的状态转移方程:dp[i][j] = min(dp[i][j], dp[0~i-1][j-1] + sum[i] - sum[0~i-1]) 但是题目中数据n最大达到1e6,两层循环dp肯定不行,那怎么做呢。。我也不知道
 
 

6.模型染色

读不懂样例,不写了

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpgsgd.html