竞赛讨论区 > 【题解】2023牛客寒假算法基础集训营6
头像
荆酌鲙
编辑于 2023-02-04 21:26 北京
+ 关注

【题解】2023牛客寒假算法基础集训营6

前言

先感谢一波,感谢qcjj、出题组、验题组、参赛者。

知识点

模拟、调和级数、二分、贪心、杨辉三角、prim、质数距离、概率、博弈、容斥、组合数、bfs、枚举

难度预估

个人认为整体难度不高。 在兰子评价为创死萌新,我也深刻的感受难度,于是加了DHE。

(感觉还是不好说(Θ﹏Θ))

(希望不会创死人。)

由于预测"阿宁指指点点"可能非常难(正赛中变最难的题了),因此挪到了比较靠后。

预测难度:

等级 题号
签到 A、H
简单 C、F、G
中等 D、B、E
困难 J、K、L

alt

(上图题号是内测时的题号)

题解

A. 阿宁的签到题

知识点

一门编程语言 输入输出ifelse应该没啥好讲的

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783227

B. 阿宁的倍数

知识点

因子、判质数、二分

思路1

离线做法

开值域数量那么多的桶。 将输入的数组aa的每一个元素的下标扔到对于值的桶(下标ii扔到aia_i的桶),包括修改操作插到数组末尾的数。

两重循环i,ji,j,第二重循环jj遍历ii的倍数,往桶ii插入所有桶jj的元素。桶ii插入完之后,排序一下。 因为一开始桶ii的倍数桶jj,没有重复元素,所以桶ii插入完,也不会有重复元素。 虽然是两重循环,但因为只遍历倍数,复杂度是O(NlogN)O(NlogN)。(调和级数)

上面操作完之后,每个桶存就是它的所有倍数的下标(位置),而且是有序的。这样就可以二分在桶中找到下标。

每次询问的具体操作:假设当前询问,数组的长度是mm,要询问的位置是xx,位置xx的值是pp(就是p=axp=a_x)。那么在桶pp通过二分查询,找到xxmm的位置,假设位置分别是LLRR,那么答案就是RLR-L

(在2×1052\times 10^5内因子数最多是160。)

代码1

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783872

思路2

在线做法

暴力枚举当前数的因子,在因子的桶vv对应位置+1。 并且记录,前缀中有多少个当前数,记在桶uu里。 (预处理数组和修改数组都做这事情)

询问时,答案就是这个数的个数,减去前缀这个数的个数,分别在桶v,uv,u找到。

代码2

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783845

C. 阿宁的大背包

知识点

杨辉三角 模拟、贪心

思路

预期做法:大家想出/猜出大的放中间、小的放两边,然后模拟,即可通过。

alt

反过来看,将最后一轮的大背包拆解: 第44轮用了第33轮的背包数量分别是1,11,1。 用了第22轮的背包数量分别是1,2,11,2,1。 用了第11轮的背包数量分别是1,3,3,11,3,3,1alt

刚好对应杨辉三角,初始背包对最终影响的个数,也就是第nn层组合数。组合数特点是中间大、两边小,因此让大的背包放到中间,使最终背包更大。

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783830

D. 阿宁的毒瘤题

知识点

前缀和

子序列、枚举

思路

首先计算出每个位置的字符,有多少个和它关联"udu"子序列。 明显,"udu"子序列个数最多的字符,把这个字符改掉(改成不是'u'和'd'比较方便),就少了这么多"udu"子序列。

对于字符'd',它和它两边各找一个的'u'字符,组成"udu"子序列,因此,将左右两边的'u'的数量相乘。 对于字符'u',它和它左边的"ud"子序列组成"udu"子序列,和右边的"du"子序列组成"udu"子序列。这里通过循环找出来。

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783804

E. 阿宁的生成树

知识点

最小生成树(prim)、质数距离 lcm、gcd (有验题人写nlogn的筛...)

思路

考虑prim求最小生成树的过程,节点11作为初始连通块。 (对于最终的生成树,把边权存到djd_j里)

对于一个节点i(i2)i(i\ge 2): ①和节点11连边,如果有lcmlcm的边,边权是ii,否则有一条gcdgcd的边权11。与节点11相连作为保底,使得边权最多不超过ii。 ②为了使边权更小,在gcdgcd的边权终找到一个权值最小的。

  1. 首先将di(i2)d_i(i\ge2)初始化为ii
  2. 显然节点11和节点i(ik+2)i(i\ge k+2)连一下,因为有gcd(i,1)=1gcd(i,1)=1的边权。
  3. 对于节点j(1jnk1)j(1\le j\le n-k-1),可能在有节点i(ijk,ji)i(i-j\le k,j\le i)gcd(i,j)gcd(i,j)更小。这一部分暴力即可,当找到一个ii是质数,djd_j都被更新成了11,可以直接break。 这部分的时间复杂度为O(dist×n+nn)O(dist \times n + n\sqrt{n})distdist2×1052\times 10^5以内最大的质数距离,大约100100

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783774

F. 阿宁的二进制

知识点

二进制性质、贪心、排序

思路

f(x)f(x)就是将xx变小(除了11)。而且最多44次变成11

当整个数组全11的时候,就该结束操作了,即便还有操作次数剩余。

对于每次询问,为了使最大值最小,最好就是kk次操作都选最大的数变小。

具体做法: 将整个数组都变成11中间出现过的数,都存到bb数组里面,然后排序。假设bb数组的长度是tt。 当ktk\ge t,说明整个数组都变成11,直接输出11。 否则输出第k+1k+1大的数。(前kk大的数都变小了)

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783727

G. 阿宁的整数配对

知识点

贪心、数的性质

思路

正数乘以负数结果是负数; 正数乘以正数结果是正数; 负数乘以负数结果是正数。

因此尽量同号的配一对。这里尽量让绝对值大的优先配对。 如果有剩余的正数或负数,则让它们和0先配一对。 最后正负数还有剩余,正负数配一对。

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783703

H. 阿宁讨伐虚空

知识点

概率

思路

分类讨论一下就行了。

  • xLx \le L时,脆皮都死完了,虚空蛇肯定不会被打到。
  • x>Rx \gt R时,脆皮怎么都死不玩,虚空蛇肯定会被打到。
  • Lx<RL \le x \lt R时,如果y[L,x)y \in [L, x),那么脆皮没有死完,区间[L,x)[L, x)长度是xLx-L,因此概率是xLRL+1\frac {x-L}{R-L+1}

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783680

I. 阿宁前往沙城

upd:看到有对大部分题面描述方式和重边、自环有意见。还有数据弱了(已加强)。 对于题面描述方式,那应该就是我表达能力问题。 感觉重边和自环都是符合题意的,不在题目里写上,我觉得是可以。

知识点

bfs

思路

可以走一条边,将刚走的这一条边毁灭,下一条边的通过时间改为11。 因此,除了要走的第一条边,剩下的边通过时间都可以改成11

为了使第一条的通过时间也改成11,找到一条多余的边毁灭即可。 为了找到多余的边,从终点开始bfs,所有的边权当作11。 如果11nn的距离是m1m-1,那么没有多余的边。否则有多余的边。

没有多余的边的情况下,11nn的路径就是一条链。于是路径上第一条边只能耗费原来的通过时间。

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783624

J. 阿宁指指点点

知识点

模拟、自定义排序

思路

定义一个队列qq,按照时间升序排序,同一时刻的事件按照题面要求的顺序排序。

  1. 对于每一个类型11的事件:①把一个查询放到队列qq中;②把时刻tT×T\lfloor \frac{t}{T}\rfloor \times T的更新放到队列qq中,tT×T\lfloor \frac{t}{T}\rfloor \times T是在tt时刻之前,离tt时刻最近的更新;③把时刻t+Rt +R的更新放到队列qq中。
  2. 对于每一个类型11的事件,把一个题数更新放到队列qq中。

x\lfloor x \rfloor 是小于等于xx最大整数,比如23.3=23,23=23\lfloor 23.3 \rfloor =23,\lfloor 23 \rfloor =23tT×T\lfloor \frac{t}{T}\rfloor \times T:可以理解为时刻tt前面更新了tT+1\lfloor \frac{t}{T}\rfloor+1次(第一次在时刻00),因此前面更新用了tT×T\lfloor \frac{t}{T}\rfloor \times T的时间。

然后使用两个mapmapcount1count1记录在propro的题数,count2count2记录在rankrank的题数。 把队列qq中的每个事件都取出来,再按类型做对应操作(具体可以看代码)。

代码1

priority_queue版: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783323 sort版: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783306 python: https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783374

K. 阿宁大战小红

知识点

博弈的必胜态必败态

思路

初始值是nn。 因为题目要求不能出现曾经出现的数字,一旦除以22下取整,那么必定可以结束游戏。 所以对于第一次除以22下取整,需要当前这个人pp除以22下取整,pp一定能赢,否则不如选择加11。 可以发现如果一直加11,当前变成2n2n,就没有除以22下取整,只能无限加11,平局。

可以定义状态(x,y,z),yx<z(x,y,z), y\le x \lt z,表示当前的数是xx,曾经最小是yy,最大不能变成zz。 对于(x,y,z)(x,y,z),曾经没出现过的数区间是[1,y)(x,z)[1,y) \cup(x, z)。加11操作不能达到zz。曾经出现过的数有区间[y,x][y,x],因此要除以22下取整,需要小于yy

  • x+1<zx+1\lt z,可以加11操作x+1x+1,也就是(x,y,z)(x,y,z)可以变成(x+1,y,z)(x+1,y,z)
  • x2<y\lfloor \frac{x}{2} \rfloor \lt y 并且x2>0\lfloor \frac{x}{2} \rfloor \gt 0 ,可以除以22操作x2\lfloor \frac{x}{2} \rfloor,也就是(x,y,z)(x,y,z)可以变成(x2,x2,y)(\lfloor \frac{x}{2} \rfloor,\lfloor \frac{x}{2} \rfloor,y)
  • 如果上面两个操作都没有那么就是必败态。
  • 如果上面至少一个操作,并且至少有一个操作后必败态,那么当前就是必胜态。没有操作后是必败态,那么当前就是必败态。

找每一个状态是必胜态还是必败,通过记忆化搜索实现。 谁先在必胜态除以22下取整,那就谁赢。

n=500n=500状态数最多,大约不超过4e54e5,将x,y,zx,y,z用一个mapmap存一下就行了。

(有验题人巨巨直接本地打表500个,O1查表过了......应该他们常数比较大......)

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60783549

L. 阿宁睡大觉

知识点

预期:容斥(状压实现)+组合数 复杂度m×2mm\times 2^m

进阶11m2m^2 (CF559C)

进阶22mnm \sqrt{n}(可能是吧,反正大概是这样)

有两个进阶是因为验题大佬分别发现一个类型的题和一个莫队求组合数。 没选择加强,是因为感觉变成拼拼题,没什么意思。

思路

每行最后一个格子是终点。

首先,假设噩梦格子都能经过。从(1,1)(1,1)走到任意一个终点的方案数是2n12^{n-1},因为每一步都有向下或向右走两种选择。

再分别考虑经过哪些噩梦格子的路径。

定义cnticnt_i为经过ii个噩梦格子的路径数。 这里的经过ii个噩梦格子,从(1,1)(1,1)mmii个噩梦格子 到 终点,路径之间存在包含关系,因此存在重复计算。 因此容斥原理的思想,多了就减少了补回去,最终答案为2n1cnt1+cnt2cnt3+cnt4...2^{n-1}-cnt_1+cnt_2-cnt_3+cnt_4...

从输入中选tt个噩梦格子(x1,y1)>(x2,y2)>(x3,y3)>...>(xt,yt)(x_1,y_1)>(x_2,y_2)>(x_3,y_3)>...>(x_t,y_t)。需要满足x1x2x3...xt,y1y2y3...ytx_1\le x_2\le x_3 \le ... \le x_t,y_1\le y_2\le y_3 \le ... \le y_t。如果不满足,说明不存在路径包含这tt个格子。

路径(1,1)>(x2,y2)>(x3,y3)>...>(xt,yt)>(1,1)>(x_2,y_2)>(x_3,y_3)>...>(x_t,y_t)>终点。 (1,1)>(x2,y2)(1,1)>(x_2,y_2)有很多条路径。 (xi,yi)>(xi+1,yi+1)(x_i,y_i)>(x_{i+1},y_{i+1})有很多条路径。 (xt,yt)>(x_t,y_t)>终点。

(1,1)>(x2,y2)(1,1)>(x_2,y_2)(xi,yi)>(xi+1,yi+1)(x_i,y_i)>(x_{i+1},y_{i+1})归为一类,都是左上角走到右下角。

alt

(x,y)(x,y)(x,y)(x',y')的路径数实际上是一个组合数,杨辉三角旋转45度(看上图感觉一下)。假设dx=xx+1,dy=yy+1dx=x'-x+1,dy=y'-y+1这个组合数是第dx+dy2dx+dy-2层第dx1dx-1(或者dy1dy-1)的组合数,也就是路径数等于Cdx+dy2dx1C_{dx+dy-2}^{dx-1}

(xt,yt)>(x_t,y_t)>终点这类路径和从(1,1)(1,1)走到一个终点的求法一样。路径数就是2n1(xt+yt2)2^{n-1-(x_t+y_t-2)}

(对于组合数求法,这里使用了线性的预处理)

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60801754

全部评论

(4) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐