竞赛讨论区 > 【题解】wannafly挑战赛9
头像
牛客网小运营
编辑于 2018-12-27 14:54
+ 关注

【题解】wannafly挑战赛9

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

统计一下1到1000000的数字分别有多少个。对于每个数字,看看原来的集合中有没有他的倍数,若有就更新答案。复杂度O(nlogn)。

T2 数一数

假如一个字符串的长度不是所有字符串中最短的,那么其答案一定为0,因为它在最短的字符串中没有出现过。找出任意一个长度最短的字符串,用kmp算法把它和每个串进行匹配,求出它在每个串中出现了多少次,乘起来就是答案。所有长度最短的字符串答案都相同,不需要重复匹配。


T3 列一列

选择一些素数,计算输入的数模这些素数的值,再一个一个计算斐波那契数列的每一项模这些素数的值,直到找到第一个完全一样的就是答案。

T4 造一造
要求第m个元素入栈后栈中恰有k个元素,也就是在此之前出栈过m-k个元素。所以在这个共计2n次操作中,第2m-k个操作是入栈。

而前面有m-1次入栈和m-k次出栈,后面有n-m次入栈和n-m+k次出栈,则可以两边先分别计算。而求n次入栈m次出栈的合法排列次数则可参考卡特兰数公式,C(n+m,n)-C(n+m,m-1)


T5 组一组

对于每一位分开考虑

问题简化如下:

有一个长为 n的01串,记Sum[]为前缀和,有四种限制:

1、对于[l,r]按位与和为x,且x的当前位为1,则区间[l,r]全为1

(Sum[r] - Sum[l - 1] == r - l + 1)

2、对于[l,r]按位或和为x,且x的当前位为0,则区间[l,r]全为0

(Sum[r] - Sum[l - 1] == 0)

3、对于[l,r]按位或和为x,且x的当前位为1,则区间[l,r]存在1

(Sum[r] >= Sum[l - 1] + 1)

4、对于[l,r]按位与和为x,且x的当前位为0,则区间[l,r]存在0

(Sum[r] <= Sum[l - 1] + r - l)

这个可以用差分约束系统 +最短路来求一组解,由于题目保证有解,所以不用判负环,即无解的情况。

T6导一导
先考虑只有一项的情况

那么可以把求导理解成你每一轮选择两种操作中的一种,要么是把自己从变成,并且当前权值乘上,要么分母上从变成,并且当前权值乘上i,n阶导就是所有操作的和。

那么易知求n阶导对的贡献为

的贡献形式也类似,都是可以用fft来求的.

所以时间复杂度O((n+k)log(n+k))

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

全部评论

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

等你来战

查看全部

热门推荐