第十三届蓝桥杯大赛软件赛全国决赛C++A组题解
试题 A: 小蓝与钥匙
数学废物,暂时不会。
试题 B: 排列距离
暂时不会,只记得有个算法求全排列。
试题 C: 内存空间
预计得分:100%
模拟即可
代码如下:
1 |
|
试题 D: 最大公约数
预计得分:100%
如果数组中已经有$1$,那么直接用$1$平铺即可。
否则找出最小区间满足区间$GCD=1$,用这个$1$进行平铺。
寻找方法可以使用二分+RMQ。
代码如下:
1 |
|
试题 E: owo
预计得分:10%
应该是个DP,刚开始没什么思路,后面也没时间想了,交了暴力。
代码如下:
1 |
|
试题 F: 环境治理
预计得分:100%
比较简单的一个题,二分+FLOYD求最短路。时间复杂度$n^3logm$,其中m为把所有路径清理到下限的所需天数(开个$1e8、1e9$都行)。
代码如下:
1 |
|
试题 G: 选素数
预计得分:30%
数学废物,没思路,交了暴力。
代码如下:
1 |
|
试题 H: 替换字符
预计得分:40%
感觉需要神奇的数据结构来维护,并不会,交了暴力。
1 |
|
试题 I: 三角序列
预计得分:40%
单独维护每个三角形, 类似于分块的思想,边界单独维护一下。
时间复杂度:$nmlognlogn$
代码如下:
1 |
|
试题 J: 括号序列树
树的最大匹配的定义?