竞赛讨论区 > 【题解】牛客练习赛63

【题解】牛客练习赛63

头像
四糸智乃
发布于 2020-05-08 22:01:24 APP内打开
赞 13 | 收藏 2 | 回复14 | 浏览2510

A 牛牛的三角形

难度:签到题
大力for,或者一个更优的算法,先sort然后枚举相邻的三项判断是否构成三角形。

B 牛牛的鱼缸

难度:签到题
初中数学题,利用相似三角形求解。
注意分情况讨论以及h和l不要看反了(看反了也能过样例)。

C 牛牛的揠苗助长

难度:中等题
先考虑一个简单的版本,假设水稻不会生长,问最少操作几次使得所有的水稻高度相同?
这个就是一个经典题了,首先结论是:最优策略一定是将所有水稻都向某一个水稻看齐,也就是至少有一颗水稻是不用动的。
原因如下图:

首先按照水稻的高度大小排序,假设你将所有水稻都调整到的值为x,且x不与任何一颗初始输入的水稻高度相同,那么要么你将其调整到x-1更优,要么你将其调整到x+1更优。
当然也有特例,也就是n为偶数,且x整好在(a[n/2],a[n/2+1])范围内调整时,不过此时范围内所有的x都是最优解,也不影响此结论的正确性。
有个这个结论就好求解最小次数了

如图,求阴影部分面积,

回到这道题目水稻会生长了怎么办。
首先想这么一点,假设经过无限长的时间后,我终于将所有水稻都调整到了一样高,这个同样高的高度是否能持续保持?
显然是可以的对吧,因为每一天都仅有一个水稻的高度长高,所以我只要将自然长的水稻给他摁回去,就能一直保持他们都是同样高的。

也就是说明,此问题在答案天数上面具有单调性,若在水稻生长的条件下,仅用ans天就能够使得所有水稻都保持同样的高度,那么比ans多的天也一定可以。
所以就二分答案天数,检查是否能够全部调整成一样的就好。

因为已经确定了天数,那么我们就知道第i颗水稻一定生长了ans/n+[i<=ans%n],所以就给每个水稻都先加上,但是因为大家都加了ans/n,所以反倒别加不然会爆掉。
既然水稻的高度已经确定,那么利用前面说的,用前缀和就可以求出此天数下的最小操作次数。
只要最小操作次数<=答案天数,就是合法的。

D 牛牛的01限定串

难度:中等题
这道题直接写DP就行了,也没什么难点。
说是这么说,但是实际上新手或者一些DP苦手的选手在写这种DP的时候还是可能会找不到突破口。
多做DP积累模型是学习DP一个很重要的部分。
这里就介绍一种模型吧,这种模型多用于01串,括号串,这种字符集为2的字符串,最好它的个数再给定。
先简化一下问题,假设下面给的t串全部为"?",也就是只有“0”,“1”的个数有限制,对于放在哪里无限制。
假设现在有n个0,m个1让你填。
首先,拿出你的草稿纸,在上面画出一个n+1行m+1列的棋盘,行列下标从0开始计算,左上角为(0,0)。
我们就用题目中的样例1举例吧。
8 6 2 1 1
10110011
????????
样例1中n=6,m=0。
所以如图所示,画一个6+1行3+1列的棋盘,行列下标从0开始计算,左上角为(0,0)。

现在我问你,从左上角走到右下角有多少种走法?好的,是C(8,6)种。
那用6个0和2个1组成本质不同的字符串,有多少种?巧了,也是C(8,6)种。
所以假设你手中有一支笔一开始划在最左上角,然后你从头开始,每放一个0你就同时往下划,每放一个1你就同时往右划。
显然的是,如果你当前在棋盘中的位置坐标是(x,y),那么我就非常清楚你已经放了x个0和y个1。
那么题目中的“前缀相似”,就可以在棋盘中先按照这个给出的s串走一遍

那么这条路径路上的点,只要我在构造01串时经过,就会获得权值。
同理“后缀相似”只要我倒着爬一边,就能知道哪些格子上的权值需要增加了。

那这个问题就又变成了经典的“过河卒”或者“传纸条”问题。
也就是从左上角走到右下角最多/最少能够获得多少权值,的问题。
那有01限制条件必须放0或者必须放1的位置,你就可以理解成“过河卒”问题中必须往下走或者必须往右走。
这个题目在使用此模型转化后变成了最最最简单的DP。

E 牛牛的斐波那契字符串

难度:中难题
先说一个神仙解法...神仙一看,斐波那契数列是线性递推,那斐波那契字符串匹配也可能是线性递推。
所以写了个暴力,外面接了一个杜教BM,然后就...AC了。

那说一下这个为什么是线性的吧,首先假设我们进行了足够多的“斐波那契”操作之后
观察字符串的前缀发现

观察字符串的后缀发现

仅有两种前缀和一种后缀
然后如果字符串足够长(比t串还要长)的时候。
fib_i中t串出现的次数就是他在中出现的次数+他在中出现的次数+的后缀与的前缀后匹配t的次数。
那显然因为只有一种后缀和两种前缀,所以转移方程为
dp[i]=dp[i-1]+dp[i-2]+c_1(i为奇数)
dp[i]=dp[i-1]+dp[i-2]+c_2(i为偶数)
c_1c_2利用kmp求的。

如果WA了的话,此题的坑点在于,无论fib_1fib_2是不是一开始就远长与t串,你都要先接一次。
因为只有fib_1的后缀为A,而非...BBAB,也就是此时转移方程是不适用的。

F 牛牛的树行棋

难度:中难题
树上的问题,有一种切题的切入点是将树分成两种情况。
1、单链  2、分叉
本题也使用这种思路,首先只考虑胜负,分成两种情况。

1、单链


如图,在树仅有单链时,可以等效成nim博弈,可以把棋子看成是堆,把棋子还能向下走几步看成是这堆物品还有多少。

2、分叉


做这种题一定要注意“等效”,对于有分叉的节点,假设分叉之后是单链。
那么现在下边的节点被等效成nim博弈中的几堆已经确定了,我们来看棋子放在最上边的节点时等效成一堆几个?
你发现你可以通过你的操作,将其转化成等效“一堆0个”,“一堆1个”,“一堆2个”,“一堆3个”。
问题来了,那一开始它等效几堆?显然,“一堆4个”。
因为只有一堆4堆才能通过取走一个或者多个物品,转移到一堆0个,一堆1个,一堆2个,一堆3个。
那么“等效几堆”就可以用树形dp求的,转移方程为

这个定义其实也就是“子树的深度maxdeep”的定义。
所以先求maxdeep,就转化为普通的nim博弈了。
普通的nim博弈怎么求方案数呢?nim博弈说,如果所有数字的亦或和不为0,先手只要找一堆取走Xorsum个,就是必胜的策略。
问的题来了,现在只有“等效几堆”,那我还得知道“等效取走”了几个。
那其实也简单,如果我通过某种操作使得,棋子的状态从“等效一堆x个”,转移到了“等效一堆y个”。那实际上这个操作等效取走几个?
这个操作也就等效“取走了x-y”个。
也就是说方案数等于
枚举每个节点覆盖的子树范围,求子树中maxdeep等于xor_sum^max_deep[x]的数目。
前提是能够取得走,也就是必须保证max_deep[x]>=(xor_sum^max_deep[x])。

接下来问题就转化成了“查询子树中权值等于x”的节点数目。
用dsu on tree来统计再合适不过了。.


另一种思路就是大部分选手使用的SG函数,然后我本人是不会SG函数的(平时碰到直接扔sjf了),可能需要各位大佬在评论区补充一下。

14条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐