scimoon

编辑于 2020-09-13 14:46

【题解】牛客练习赛69 精

A 时间复杂度

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

B 划分

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

记这 $i \times j$ 个数中，第 i 个数的下标为 $pos_i$

可以划分区间为 $[1,pos_j],[pos_j+1,pos_{2j}]....[pos_{(i-1)j+1},n]$

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

C 旅行

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

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

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

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

D 火柴排队

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

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

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

发现这就是一个分组背包，可以 $\operatorname{O}(n^2)$ 处理

E 子串

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

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

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

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

注意特判两种情况：

$g[x]\le r$ ，即区间 [x,r] 里面有比 r 更大的数

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

那么现在要求 $\sum\limits_{i=f[x]+1}^x[min(i,r)=i]$

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 ，满足 $\max\limits_{i=l}^ra_i=r$ 的左端点 l 的范围；对于一个左端点 l ，满足

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

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

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

F 解方程

众所周知 $\sigma_k=\mathbf{Id_k}*\mathbf{1}$ ，所以我们得到

$\sum\limits_{i|n}f(i)\dfrac{n^p}{i^p}=n^q$

$\sum\limits_{i|n}\dfrac{f(i)}{i^p}=n^{q-p}$

反演得

$\dfrac{f(n)}{n^p}=\sum\limits_{i|n}\mu(i)\dfrac{n^{q-p}}{i^{q-p}}$

$\dfrac{f(n)}{n^q}=\sum\limits_{i|n}\dfrac{\mu(i)}{i^{q-p}}$

显然 $\dfrac{f(n)}{n^q}$ 积性，考虑与 n 互质的质数 d，我们观察 $f(d^k)$

$\dfrac{f(d^k)}{d^{kq}}=1-\dfrac{[k\neq 0]}{d^{q-p}}$

也就是

$\dfrac{f(n)}{n^q}=\prod\limits_{p\text{ is a prime},p|n}(1-\dfrac{1}{d^{q-p}})$

欧拉筛即可

2025最新求职资料大礼包领取

大家都在关注

校招日程表笔试日历 ai模拟面试面试宝典剑指offer 知识点专项练习

已采纳

采纳

精彩回帖

精彩

全部评论

(7) 回帖

加载中...

话题同步到我的动态回帖