竞赛讨论区 > 【题解】牛客练习赛15
头像
牛客网小运营
发布于 2018-12-27 16:28
+ 关注

【题解】牛客练习赛15

(题解由比赛出题人提供,点击右侧“本文相关内容”的题目即可开始做题)

T1 吉姆的运算式
出这题的目的,主要是想要告诉大家,逗号也是个运算符。 有办法证明,对于一个只含逗号,括号,数字的合法算式,其结果就是就是算式里最右边的数字(可以用数学归纳法证)。
由于本题保证测试资料一定是合法算式,所以我们不用真的去解析算式的括号结构,而是直接去找字串中出现在最 右边的数字就行了。
如使用的程序语言是C++,我们可以把字串读入后,把括号和逗号都变成空白字元,最后再利用stringstream把新字 串再用数字读入,读到最后一个数字就是答案啦〜

T2 沃老师学生的成绩
由于「分数」这个词有歧义,题解内的作文分数都用score来表示。 若分数没有末尾零 若代表score的小数没有末尾零,我们就只要把score当作字串排序就可以了,可以使用trie来解它,甚至使用STL的排序直接排序字串也OK。
有末尾零的话,则...

T3 吉姆的奇思妙想
恩...这些某种程度上来说是在为同一场比赛的下下一题铺路...因为题目叙述里提到的时间复杂度( )以及复 杂度的证明方法和下一题是一模一样的!
倘若是一个比赛经验丰富的人看到这题...倘若是一个比赛经验丰富的人看到这题...马上就会猜到能够用三分搜解这题了吧XD
所以只要先在所有询问前预处理,把 图片说明 以及 图片说明 都预先记录下来。 当 图片说明 时 ,就等于图片说明
于是我们就可以用图片说明 的时间复杂度完成三分搜。
有一个小小的陷阱虽然题目里有特别强调,答案会在64位有号整数的范围内,但这可不代表计算过程也在呀XD
于是若真的要用上述公式三分搜,那就得使用大数或int128_t或python之类的东西了0.0
更干净的做法在追求更干净的做法前,先想想看为什么三分搜是对的能用三分搜求极小值的充分条件是:该函数在 我们会询问的定义域下,是先严格递减再严格递增。
于是我们来观察看看图片说明 和Ei时, 究竟是如何变化的。
掐指一算就能发现,它的变化量Δj是图片说明 图片说明 ,而图片说明 是随着j增加而严格递增的序列,故Δj确 实是先严格递减再严格递增。
谈到这里,其实更干净的作法已经冒出来了,我们只要找到最大的j使得 即可吧...因为找到这样的图片说明
j,就代表我们找到凹点了。

T4 队列重排
先考虑一个数列 代表有n个人排成一排后解排重排,而且重排后每个人前面的人都跟原本前面的人不一样。 假设一开始排列是1~n,重排后先不排1,把2~n按照我不在i+1前面的排列方式共有 种,1则有n-1个位置可以插
入,不然1然恰将i和i+1分开,i有n-2种选择。此时可以把i,1,i+1看做一个数,并跟其他n-3个数列,方法数为
图片说明
,于是可以得到递推式: 图片说明
接着假设恰有t个人的重排后前方跟原来一样,则对于每个这样的人,把他跟前面的人绑在一起排列,即把连续的:
数视为同一个数来做排列,于是方法数为 图片说明
对于原题目,可以O(n)预处理,总复杂度为O((n+k)logp),当然也可以预处理模逆元得到复杂度O(n+k+log p)。
验题者的评论这题也可以先暴力解出小数据,查OEIS以及观察规律,然后就莫名其妙做出来了。

T5 无向图的弦
这是个衔接着同场比赛的上上一题"吉姆的奇思妙想"的题目,为什么会这样说呢?因为本题的参考做法和"吉姆的奇 思妙想"里提到的计算一个图里有多少三角形的做法很相似。
在"吉姆的奇思妙想"里提到的「计算一个图里有多少三角形」的解法是:选定某个常数后,把所有点分成度小于等 于s和大于s来分开处理。把相同概念套用到这题就会变成:把 图片说明图片说明 的情况分开处理。
如果我们知道有v条边的两端点都出现在第i组询问里的cycle上,那么该cycle就有v=ki 条「弦」。
图片说明
我们只要枚举 个点中的任两个点,看看该编存不存在即可,这样的做法时间复杂度是 图片说明 ,可以使用hash或
unordered_set甚至是set(用set时间复杂度会多了一个 图片说明 ),都是有办法获得AC。
有一个常数比较小的做法是:离线处理所有询问,对于每一个点,预先储存它有和哪些点相连以及它包含于哪些 图片说明 的询问,就可以使用阵列直接判断该点在那些询问里,有和哪些边相连,实作细节请参考附录代码。
图片说明
用一个阵列,纪录每个点是否有出现在此询问的cycle里,之后枚举每条边看看是否两端点都有出现在cycle里,即 时,复杂度为O(M) 。
在数一个还有多少「弦」时,记得使用每条「弦」只会被数一次的数法,否则你你光是数数的次数就高别人两倍, 再加上常数大,以及没有好好的调s值,执行时间就很有可能随随便便就高达标程的4,5倍以上,很容易TLE的。
相反的,若你少数一半的量,有机会这部分的cost就是标程的两倍快,常数写稍微大一点或s值取不够好,也不到
TLE。
如何精确决定s的值呢?
如何精准决定s的值这件事其实在"吉姆的奇思妙想"这题做了很多提示,我们可以在自己的电脑上生成一些测试资料 后,三分搜来决定s值!这么做的话可以减少AC前得到TLE的次数。
至于要生怎样的测试资料呢?这是要根据你选定的值来决定的,对于一个s值,要生两组测试资料,分别是全部 和全部 ,这两组一定有其中一组是有理论上的极限测资。另外要注意,所有询问的点要尽量散开, 增加记忆体中哪些取资料时*** miss的机率。
但如果是penatly不是很重要的比赛,大概就记得一个原则,若图片说明 ≤s的部分的常数比较大,那s就略小于图片说明 ,若相反,则取图片说明 略小于图片说明
本题的tester在小于等于s的部分是采用unorder_set这种常数偏大的资料结构,试了s=图片说明图片说明 都是TLE的,但 把s换成图片说明就AC了。

T6 最小生成树
解MST问题有个著名的算法叫做Kruskal'salgorithm,简要来说就是把所有边按照权重由小到大排序后,由权重小的 边一个试试看添加后是否仍不会形成cycle,不会形成则该编就会是MST中的一条边。
而本题出题者的做法也是套用Kruskal'salgorithm的概念。直接套用Kruskal'salgorithm的话...一个N个点的完全图 共有图片说明 条边,本题直接套用Krusal's algorithm肯定TLE的。
但先别急,我们就从「对于所有w =0~ 图片说明 ,该如何快速找到所有权重为w的边开始思考吧。找到所有权重为w的边
先给定义一些东西
对于两个非负整数a,b,若(a&b)= a,则称a是b的「位元子集元素」且b是a的「位元父集元素」。 并定义a的补集==a∧()(是把所有有位0,1互换的意思)剩余出现符号着依照C++里的定义。
现在我们目标是找到所有的(x,y),使得x&y =w。那么w一定是x的「位元子集元素」。
所以我们可以枚举所有w的「位元父集元素」作为x的候补,并对于给定x,y一定得是的「位元子集元素」,于 是我们再枚举所有 的「位元子集元素」作为满足边(x,y)权重为w的可能的y的候补,有了这样的概念我们可以写 出以下C++代码,就一定可以依序把所有边按照权重由小到大枚举出来。
观察一在上述代码枚举边的时候,也许会多枚举一些边,也就是那些(x&y)≠w的边,但可以发现虽然那些边权
重不等于w,但他一定满足(x&y)≤w,这意味着,若我们是在实做Kruskal's algorithm时,不把<w的边用if排除 掉,直接做union也没差。
观察二若把if((x&y)==w)除去,那么第三层for循环至多只有 种不同相近的行为:union mask2的所有存在的「位 元子集元素」和 x。其中,把mask2的所有存在的位元子集元素union起来这件事,第二次以后都可以省略,所以做 第二次或更多次时,就只要把该次的x和mask2的任一个存在的「位元子集元素」做union就行了。

其他疑问可加以下交流群(加入一个即可啦~)
牛客多校算法训练营1:453799454
牛客全国算法训练营2:330766563
牛客多校算法训练营3:934889305

全部评论

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

等你来战

查看全部

热门推荐