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

【题解】牛客练习赛69

头像
scimoon
编辑于 2020-09-13 14:46:18 APP内打开
赞 5 | 收藏 1 | 回复6 | 浏览1045

A 时间复杂度


直接根据题意模拟,注意要求较小的角度,先减再四舍五入即可

B 划分


显然可以取得前 大的数,作为 val(i,j)

记这 个数中,第 i 个数的下标为 pos_i

可以划分区间为

故 val(i,j) 就是前 大的数的和,实现复杂度 O(xy)=O(n)

C 旅行


可以发现,对答案有贡献的边肯定是最大生成树上的边,那么可以将这些边先拉出来,每条边至少会被贡献一次

对于当前的一个联通块,找到最小的一条边,那么这个联通块肯定被分成了两个联通块

考虑怎么样才能使答案最优,显然先将一个联通块内选完以后在经过当前边到另一个联通块最优(因为两边的边比当前边要大),可以看出这条边只对答案贡献了一次

这样分治下去就可以得到:将所有生成树上的边的权值加起来就是答案

D 火柴排队


一个选手的分数 a_i 加 d 会导致区间 中的数必须被操作

发现如果只令 a_i 影响区间 中的最小数,也可以得到同样的效果

此时影响的关系会形成链状,并且一条链里可以选择一个选手将其加 d ,其后所有的选手都必须加 d,当然一条链里也可以不选

发现这就是一个分组背包,可以 处理

E 子串


我们给出了两种方法来解决这道题目

约定 f[x],g[x] 分别为左、右侧第一个比 a[x] 大的数的下标, min(l,r) 为区间 [l,r] 的最小值

考虑固定右端点 r ,利用辅助数组得到 x ,使得 p[x]=r

那么显然 合法的左端点一定在区间 [f[x]+1,x] 内,即保证最后选择的区间最大值一定是 r

注意特判两种情况:

,即区间 [x,r] 里面有比 r 更大的数

x>i ,即权值为 r 的数的下标在 r 后面

那么现在要求

Ps: 暴力数据结构跳转 Solution2


Solution 1


考虑 一个一个插入并且维护后缀最小值

假设我们已经得到前 r-1 个数的后缀最小值 s[x]=min(x,r-1)

维护 tot 个块,每个块中的 s[x] 相等

它是这个样子的:


那么,加入一个 r,要么 p[r]>s[x] ,此时直接加入一个新块

否则必然有若干个 整块被 p[r] 更新

那么我们维护一个类似单调栈的东西,每次将若干个整块弹出、合并,记录一些信息即可

因为总权值数为 n ,所以弹出次数一共为 n

下图是一个例子


好的,我们现在实现了更新,考虑怎么查询

如下图,红线 y=x 发现一个块被穿过即为存在 x=s[x] ,也就是存在一个答案

那么一个块显然最多只能有一个答案

维护与 y=x 相交的的块的个数的前缀和 (因为要查询区间内有多少个答案)

放一段那个单调栈的代码,l,r 为左右端点,c 为上一句话那个东西,bool 表达式即为判断是否与直线相交
int x=p[i];
while(cnt && x<s[cnt])cnt--;
cnt++;l[cnt]=r[cnt-1]+1;r[cnt]=i;s[cnt]=x;
c[cnt]=c[cnt-1]+(x>=l[cnt] && x<=r[cnt]);


我们现在要查询一个区间 有多少个(注意都是在前 个意义下的,所以可以直接查 )

我们直接二分出查询区间所在的块,对于整块,直接前缀和

其余边角所在的块再判断一下答案是否落在查询区间内就好了

int L=upper_bound(l+1,l+cnt+1,f[x]+1)-l-1;
int R=upper_bound(l+1,l+cnt+1,x)-l-1;
if(L==R)ans+=(s[L]>=f[x]+1 && s[L]<=x);
else ans+=(s[L]>=f[x]+1 && s[L]<=r[L])+(s[R]>=l[R] && s[R]<=x)+c[R-1]-c[L];

至此,我们就做完了这题

完结撒花!

Solution 2

利用单调栈与二分求出:对于一个右端点 r ,满足 的左端点 l 的范围;对于一个左端点 l ,满足

一对 [l,r] 满足条件当且仅当:l 在 r 的合法区间内,r 在 l 的合法区间内

可以利用主席树+差分解决这样的数点问题

扫描线+树状数组+差分也能做

F 解方程


众所周知 ,所以我们得到





反演得





显然 积性,考虑与 n 互质的质数 d,我们观察



也就是



欧拉筛即可

6条回帖

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

近期热帖

等你来战

查看全部

热门推荐