练习赛132题解

比赛链接

https://ac.nowcoder.com/acm/contest/96120#question

首先道歉

对于B题表述不清的地方出题人表示歉意

其中没有给出顺子可以随机、连续性、可交换性给出对应的明确定义

影响了各位的比赛体验

后续会优化题目表达

数据保证不卡常，如果被卡或者是运行时间大于1s均可以优化

A

题目链接

https://ac.nowcoder.com/acm/contest/96120/A

题意

求n根木棍下的最大面积（类似于积分）

思路

贪心

复杂度

n

解法

用on方法选出最短两根木棒，将最短的两根木根放置在左右两端即可

细节

特判1 以及 小数处理（保留2位小数）

B

题目链接

https://ac.nowcoder.com/acm/contest/9612/B

题意

有n张牌和k张任意牌，取其中任意张牌成不超过m的最大长度顺子（公差为的等差数列）

思路

贪心，二分/双指针

复杂度

nlogn

解法

原数组去重、排序得到数组L

依次枚举L中纸牌i作为顺子中最小纸牌，二分最大可以达到的顺子长度（或最大纸牌职位）并更新答案

最后答案对m取min即可

C

题目链接

https://ac.nowcoder.com/acm/contest/96120/C

题意

T组询问，询问圆上n点选k点，求有两点与圆心共线的概率

思路

数学、线性逆

复杂度

T

解法

显然n选k有 种情况

那么仅需要考虑能共线情况，显然n为奇数无解

当n为偶数时，考虑不与圆心共线情况：

则经过圆心的一组点最多只能选1个,共n/2组，每组有2钟可能

反之当k>n/2时，必定存在共线情况

综上所述：

此时需要使用线性逆和2的k次方打表维护，使得每次查询复杂度O1

D

题目链接

https://ac.nowcoder.com/acm/contest/96120/D

题意

T组询问，询问区间[l, r]中随便一个区间包含完全平方数的区间数*2

思路

数字

复杂度

T*O(求sqrt的复杂度)

解法

std解法（不一定最简单）:

求最大的正整数a,b满足l<=a*a,b*b<=r

若a>b,输出0；continue

反之，必存在包含区间[a*a,b*b]的区间存在平方数

令F[x, y] 表示区间[x, y]中  包含平方数的区间数

令G[x, y] 表示区间[x, y]中不包含平方数的区间数

有F[x, y]+G[x, y] = [x, y]中的区间总数 = (y-x+2)*(y-x+1)/2

左端点在[l, a*a-1], 右端点在[a*a, r]的区间必包含平方数：

左端点在[a*a, b*b], 右端点在[b*b+1, r]的区间必包含平方数：

区间总数性质：

显然：

则：

其中，G[1, x]可以用递推求和公式（自己推，我写了也有人会问为什么）或者前缀和优化（但前缀和可能会被卡）

最终结果可以带入上述式子解决

如果被 hack 请参考一下取模计算

细节

计算细节，以及对取mod为负数等把控

E

题目链接

https://ac.nowcoder.com/acm/contest/96120/E

题意

矩阵每个数会被周围数更新，求最后结果

思路

考虑到使用魔法顺序不会影响最终结果，直接计算最终结果即可

（不会存在不同的过程而产生不同终态）

复杂度

n*m*log(n*m)

解法

用堆（优先队列）维护当前最小值和最小值的位置

初始将外围边界的(值，位置)全部进堆

然后每次选出堆最小值，并尝试更新附近值，并将附近的数重新进堆

当堆被清空时，达到最终状态

F

题目链接

https://ac.nowcoder.com/acm/contest/96120/F

题意

T组询问求三边化为直角直角三角形的最小代价

思路

考虑到3e5内直角三角形数不是特别多，打表即可

细节

最终答案的斜边有可能大于2e5，但应该小于sqrt(2)*2e5；打表到3e5比较合适

总结：

啊？？？反正也没什么人看到这里...

1. 题目（春/江/水/暖鸭/先知）出自于一句诗中出现的5个名词

2. 对于题目创新性，感觉BE出得还行（但可惜B没表述清楚...）这个E通过率属实有点低

3. 对于难度把控...

pass：这场比赛原本是用来出小白赛的

4. 感觉题目代码不太重要，就不放了

有问题私信出题人：懒得改了

5. 不知道为什么每次我出的BFS好像都看起来很难？

https://ac.nowcoder.com/acm/contest/88878/D

6. 感慨下就业好难，不知道下一次出题是什么时候了...

7. 88