竞赛讨论区 > 【题解】牛客小白月赛15
头像
水宝宝
编辑于 2020-03-09 10:53
+ 关注

【题解】牛客小白月赛15

致歉:这次由于出题人的原因导致A题和H题重测,非常抱歉

A 斑羚飞渡

2个数组分别读入x[i],y[i],然后排序后配对,如果可以,就自己跳,如果不行,就v1自己配对,时间复杂度O(n lg n)

B 诡异的因数

暴力试除法,强力试除即可。

C 表单

由于数据的问题读入的操作可能不是1,2

一个预处理,每次清0即可

数据中可能有空行,请大家不要踩坑

D 分数的运算

加减法通分,乘除法直接做。

E 希望

就是一个01背包,如样例中的2 4 10就看做 2 10,3 10,4 10塞入背包,背包总容量为k,然后跑01背包就好了

因为n到10^5所以要用线段树之类的东东优化塞入背包的这个过程,时间复杂度O(n lg n),因为k很小,所以跑背包的时间可以忽略不计

总时间O(n lg n)

F 跳跃的旋律

分块,以k为模数分块,然后维护一下就好了

时间复杂度O(n sqrt n)

F题重配了数据,这次保证卡飞暴力

G ftos的测试

##题解

可以发现,只修改一个数,所以如果有解,这个数一定减少了的值,

又因为没有修改,所以我们可以在一开始预处理的值,然后我用的是分块,

对于这个差值我们进行块内排序处理,然后每次询问我可以块内二分upper和lower

然后在找到满足减少了的解的数量,对于边角料暴力就OK了

然后我们发现找到的这个数量有两种情况:

###情况一

这个数量=0,即无解

这好办,输出"Error"

###情况二

数量>0,有可能有唯一解,也有可能有多个解,如

因为比较小,所以我们桶排+块内二分判断头尾的是否相同。

如果做出来这些解的都是相同的输出"pass"

否则输出"INF"

这样做至少还有桶排清零的大常数,但是在内还是能卡过去的。

##关于数据

数据是随机的,但是为了不全是Error,我们手动修改了数据。

##其他解法

线段树应该也是可以的,我们维护,然后方法与分块差不多,时间复杂度

但是线段树代码太长了,本人懒得打(逃

如果有更好的解法敬请指出。

H 数据结构题

分块,块内排序二分找相同。很经典的题了。

线段树也同样可以。
数据不保证l<r,如遇到这种情况请swap l和r


I y大的字符串

这就是一个板子题啊,用trie统计能被解释的最长前缀,时间O(n lg n)用manacher统计能被解释的最长回文前缀中最长的回文串,时间O(n),为啥没人做捏


J 开挂

首先,我们发现

有没有觉得后面这个东西很熟?其实这个询问就是求区间的数两两相乘的和。

但是好像还是没法算啊!

我们再观察这个东西,又可以发现

其实就是区间和的平方减掉区间平方和的

对于区间加,线段树维护一下和与平方和就好了,时间复杂度小到爆炸(实际的话因为数据随机,后面个点每个点标程跑的不到,开都是出题人良心了)。

这个公式的来源其实就是

然后移项一下,提个式子,分解一下就是这道题了。


全部评论

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

等你来战

查看全部

热门推荐