第十三届蓝桥杯C/C++A组部分题解
不保证正确性
试题A:裁纸刀
答案为 $n*m-1+4$
443
试题B:灭鼠先锋
LLLV
试题C:求和
预计得分100%
思路:维护一个前缀$sum$即可。
总时间复杂度$O(n)$
参考代码:
1 |
|
试题 D: 选数异或
预计得分100%
对于每个位置$i$ ,设$y = a[i]$ ^ $x$,找到最近的一个 $y$的下标 $idx$,记作$b[i]$。再用线段树维护$b$数组的区间最大值$maxx$,如果$maxx >= L$,那么为$yes$。
总时间复杂度$O(nlogn)$
参考代码:
1 |
|
试题 E: 爬树的甲壳虫
暂时不会。
试题 F: 青蛙过河
预计得分100%
二分经典题改编题,一眼二分,check有点难写。
check思路:
可以令$dp[i]$表示跳到第$i$个石头的最大次数。
把最后$mid$个石头的$dp[i]$加起来,$sum>= 2*x$即合法。
总时间复杂度$O(nlogn)$
参考代码:
1 |
|
试题 G: 最长不下降子序列
预计得分10% ~ 30%
暴力思路:
枚举修改位置,二分法$O(nlogn)$求最长不下降子序列,(跳过中间那段长度为$k$的数组)
总时间复杂度$O(n^2logn)$
参考代码:
1 |
|
试题 H: 扫描游戏
预计得分10% ~ 30%
暴力思路:
极角排序。之后每次暴力扫描,循环直到扫描不到物品。
总时间复杂度$O(n^2)$
参考代码:
1 |
|
试题 I: 数的拆分
预计得分10%
暴力思路:筛出所有质因子,不能有出现次数只有一次的质因子,并且最多有两个出现次数为奇数次的质因子(出现偶数次只需均分给$x_1$和$y_1$)
总时间复杂度$O(tsqrt(n))$
参考代码:
1 |
|
试题 J: 推导部分和
暂时不会。