「置顶」5月做题记录

5月做题记录
最后一个5月份了,年份都不用写了;即使实力不强也希望这份题单能给后人一些帮助

又是喜闻乐见的补课件时间,题目质量理论上会高些

好题:「HNOI2010」 城市建设、51nod1260 排列与二叉树

因为没地方交不太确定,求路过dalao看看小弟有没有写错:动态SCC

CF848C Goodbye Souvenir

题意:单点修改,区间询问每种数在该区间内最晚和最早出现的坐标差之和,$n \le 1e5$

请先思考后再展开

最后-最前这种东西有个套路,就是看做是$\sum_{i,prei \in [l,r]} i-prei$,相当于$(i,prei)$是个带权点,然后每次询问$(l,l)-(r,r)$这个矩形和($(l,l)-(r,n)$,将bit询问次数从4变成2s)

因为加点删点满足可加性,离线按时间cdq分治,全局维护每种值的set以获得信息,处理分治时写个扫描线+树状数组即可,$O(nlog^2)$

「HNOI2010」 城市建设

题意:修改边权后输出MST边权和,$n \le 2e4,m,q \le 5e4$

请先思考后再展开

无脑做法是线段树分治+LCT,$O(nlog^2)$但常数巨大

注意到我们修改一条边的时候整个MST也只会变化一条边,说明变化量趋近于修改量,这启发我们考虑一棵大树上有少量修改时我们能否把不重要的信息去掉(缩小规模)。具体地,设修改边集为A,不修改边集为B,考虑下面两个过程:把A当做$+\infty$一起做MST,则不在MST1中的B边不会在真MST中,边数降低为$|A|+n$;把A当做$-\infty$一起做MST,则在MST2中的B边一定在真MST中,这些边把点缩起来,点数降低为$|A|$

注意到如果我们分治处理,n是上一层的点数,即点数和边数都是$O(r-l)$级别的,kruskal解决,$O(nlog^2)$

这个做法既不是cdq也不是线段树分治,就是个有脑子的缩小规模类型的分治

Gym102354B Yet Another Convolution

题意:给出序列a和b,求$c_k = \max\limits_{\gcd(i,j) = k} |a_i - b_j|$,$n \le 1e5$

请先思考后再展开

首先无论什么做法肯定有以下两点比较显然的思考:

  1. 因为是max绝对值,只要保证两数符号不同,等价于max 选两数求和。因为是两个序列间,+A-B和-A+B各做一次即可
  2. 这种求和方式通常要靠莫比乌斯函数做容斥,但本题是求max,因此考虑二分转为计数问题

接下来看到网上题解都在整体二分,复杂得不想看,提供一个简单做法:

直接一个个计算$c_D$,跑个二分,判定就是在长度为n/D的两个序列中,下标互质的两数和至少为T的对数为正数。枚举d系数为$\mu(d)$,那么我们需要的其实是$D*d$的倍数组成两个序列各自排好序,这个可以最初nlogn预处理好,现在拿出来跑两次2-point即可(还有一种写法是,枚举$D*d$再枚举其约数,这样就不用vc预处理,比较适合没有O2的环境,cf上无所谓了)

总复杂度$\sum_{D=1}^n 30*\frac{n}{D} *ln(\frac{n}{D})=O(30nln^2)$,跑了2s+

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vc<int> dd[N];pii a[N];vc<int> b[2][N];
void main()
{
pre();int n=qread();fo(d,1,n) for(int i=d;i<=n;i+=d) dd[i].PB(d);
fo(op,0,1){
fo(i,1,n) a[i]={qread(),i};sort(a+1,a+n+1);
fo(i,1,n) for(auto d:dd[a[i].SE]) b[op][d].PB(a[i].FR);
}
fo(D,1,n)
{
int fl=0,fr=1e9,ans=-1;
while(fl<=fr)
{
int mid=(fl+fr)/2;ll sum=0;
fo(d,1,n/D)
{
ll s2=0,j1=0,j2=0,siz=sz(b[1][D*d]);
for(auto i:b[0][D*d]){
while(j1<siz and b[1][D*d][j1]<=i-mid) j1++;s2+=j1;//i-j>=mid
while(j2<siz and b[1][D*d][j2]< mid+i) j2++;s2+=siz-j2;//j-i>=mid
}sum+=s2*mu[d];
}
if(sum>0) ans=mid,fl=mid+1; else fr=mid-1;
}write1(ans);
}
}

「IOI2013」 wombats

题意:$R \times C$的网格,$R \le 5e3,C \le 2e2$,下标从0开始,相邻两格间有边权但不能向上走,$m \le 500$次修改某条边权(始终在1e3内且非负),$q \le 2e5$次询问$(0,a)-(R-1,b)$最短路,时限20s,空间250M

请先思考后再展开

第一反应是以行为下标建线段树维护行区间顶部到底部两点最短路,状态合并为$O(C^3)$故总复杂度为$O((R+mlogR)C^3+q)$

发现除了状态合并其他没法优化了,要么优化掉这个,要么换个做法,好像也想不出能换啥

然后想想网格图的性质利用得不是特别充分啊,进而发现对于一个出发点,不可能存在两条路径先分离后重合再分离,因为可以都使用出发点到重合点间最短路径。于是这个合并非常像一个有决策单调性的dp,对于每个起始点做一次决策单调性那个经典分治,$O((R+mlogR)C^2logC+q)$,或许可以信仰

能否把logC也去掉呢?众所周知二维决策单调性有个经典不等式,尝试套上去,那我们需要证明的是随着起始点单向移动,同一个终止点的转移点不会往反方向移动,明显挺对的,$O((R+mlogR)C^2+q)$也明显在接受范围内

然而空间有点炸,但在区间长度较小时,我们可以不记录到数组里,修改时线段树到根路径上,如果区间没记录就暴力再重新算,也就是以时间换空间。具体怎么开我没写代码没资格说,大家可以看看luogu题解区,他好像跑得飞快

Circular edit distance

题意:edit distance自行上网搜,现在将相等条件改为循环同构也行

请先思考后再展开

edit distance本质上就是$n^2$个点的网格图,每个点向3个方向转移的最短路。现在将其中一个串复制一遍,相当于一个$2n^2$的网格图,多次询问$(0,j)-(n,n+j)$的最短路,和上题类似,暴力求出$(0,\frac{l+r}{2})$的方案,将表格分为两半,一定是log层,每层复杂度是$O(n^2)$,总复杂度为$O(n^2log)$

「IOI2014」 holiday

题意:长为$n \le 2e5$的序列a,给定指针所在,做最多d次操作,每次移动指针到相邻或获得当前数,一个数只能获得一次,最大化收益

请先思考后再展开

$\max_{i=0}^d 左回*i+右*{m-i},右回*i+左*{m-i}$,例如$左回*i=\sum*{j=1}^{st} [j,st]中前i-(st-j)*2大$,感受一下应该是决策单调的,分治+主席树,$O(nlog^2)$

CF566C Logistical Questions

题意:$n \le 2e5$的树,定义两点距离$dis=路径边权和^{1.5}$,边权正,点权非负,求带权重心

请先思考后再展开

*似乎是GDOI2019前chd搬过*

因为任意多个凸函数(二阶导数非负,任意左右翻转、叠加后依然是个凸函数,取出任意一条链,横坐标定义为距离某个端点的距离,纵坐标定义为这个点作为中心时$\sum dis^{1.5}$,就会得到链到函数的映射。如果将函数定义域看做不连续的一些整数会毫无性质,但如果定义域看做连续实数域,则是个凸函数。对于整棵树最小的某个位置(如果是在边上,判断旁边两点即可得到答案),其他位置往这个方向上的链构成的函数上,是单调过来的,所以整棵树这样的位置唯一

然后思路也挺自然的,链上就是直接二分,树上因为度数的问题,点分治时不能枚举每个孩子判断,需要借助导数的力量

*怎么用导数加速这部分,当时问了他半天也听不懂,我校又没人会(可惜当时聊天记录没了),现在又在这个部分卡了半天,并不知道为什么所有人都觉得显然*

其实这是因为我忘记了导数的一种不常用理解(因为导数是瞎jb自学的,你们理解就好):往某个方向跳$\epsilon$的变化,且只保留一阶无穷小的系数。具体地,从rt跳向某个儿子y,y子树内是$\frac{(dis-\epsilon)^{1.5}-dis^{1.5}}{\epsilon}=-1.5dis^{0.5}$(牛顿二项式定理),其他点则是$\frac{(dis+\epsilon)^{1.5}-dis^{1.5}}{\epsilon}=1.5dis^{0.5}$,求和后如果是负的,就表示最小位置在这条边上或y子树内。这个就很明显好维护多了,$O(nlogn)$

动态SCC

题意:$m \le 1e5$次操作,每次是加有向边,然后询问多少点对相互可达

请先思考后再展开

只要求出每条边什么时候被合并到SCC内,就能并查集处理询问合并具有单调性可以二分,因此考虑整体二分

1
2
3
4
5
6
void solve(l,r,边集E)
{
if l=r : E加入全局并查集
EE=tarjan( for E:时间在[l,mid]内的边 )发现已经合起来的边
solve(l,mid,EE),solve(l,mid+1,E-EE)
}//nlogn*并查集

CF765F Souvenirs

题意:询问区间内最近数对,即$|a_i-a_j|,i \ne j$,$n \le 1e5$

请先思考后再展开

离线,右移右端点维护此时左端点答案,以$a_j \ge a_i$为例,找到左边最近的$比a_i大的j更新[1,j]$,那么再左边只需要考虑$<\frac{a_i+a_j}{2}$的(否则会与j先贡献),就这样一步步跳,差/2所以最多跳log次,找这个东西可以用个权值线段树维护出现位置找最大值,总复杂度为$O(nlog^2)$

牛客练习赛64E 红色的樱花

请先思考后再展开

如果不用操作1,两个坐标独立,两次拓展欧几里得就行了;如果用了,设两维分别走q、w步,则利用操作1实现两个同时减1直到某个变成0显然一定不劣,所以接下来只要考虑,只使用操作1和2,另一种类似(判断无解也只需要这样搞,搞不出就是无解)

问题转化为方程$dx+ny+mz=(e_x-s_x)-(e_y-s_y)$,求x的最小正整数解

这个就是个裴蜀定理,先把右边两个合并为$dx+gcd(n,m)y=(e_x-s_x)-(e_y-s_y)$,然后再解方程即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ll exgcd(ll A,ll B,ll &x,ll &y)
{
if(B==0){ x=1,y=0;return A; }
ll tx,ty,ret=exgcd(B,A%B,tx,ty);
x=ty,y=tx-(A/B)*ty;return ret;
}
ll solve(ll A,ll B,ll C)
{
ll x,y,d=exgcd(A,B,x,y);
if(C%d) return -1;x*=(C/d),y*=(C/d);
ll t=B/d,ret=(x%t+t)%t;return ret;
}
void main()
{
fo(T,1,qread())
{
int n,m,D,sx,sy,ex,ey,a,b,c;scanf("%d%d%d %d%d%d%d %d%d%d",&n,&m,&D,&sx,&sy,&ex,&ey,&a,&b,&c);
int wtx=(ex-sx+n)%n,wty=(ey-sy+m)%m;
ll q=solve(D,n,wtx),w=solve(D,m,wty);
ll ans=min(q,w)<0?bin(62):b*q+c*w;
q=solve(D,gcd(n,m),wtx+m-wty);if(q>=0) chmin(ans,a+q*b);
w=solve(D,gcd(n,m),wty+m-wtx);if(w>=0) chmin(ans,a+w*c);
write2(ans==bin(62)?-1:ans);
}
}

51nod1260 排列与二叉树

题意:有多少个$n \le 1e6$的排列,能够建立一棵二叉树,使得其先序遍历得到的叶子顺序为该排列,且能够通过交换若干左右子树将其排序为递增

请先思考后再展开

首先最基本的性质是,任意一棵子树内叶子值域必须是连续区间,请务必牢记

我的第一想法是,合法排列容易计重,那我就考虑计算非法排列,然而并没有想到什么方法……只好想办法让合法排列只被统计一次

每次一定将值域区间分为两部分,然后分给两侧子树,那么我们记录$f_n$表示值域区间大小为n,左孩子的值域区间为较大那个的方案数,$g_n$表示左孩子的值域区间为较大那个的方案数,$ans=f_n+g_n$

先考虑$f$的计算,如果排列最小值在最左边,或者排列最大值在最右边,那么钦定划分为大小1和n-1;
否则两侧大小显然都不可能是1,设计一种唯一分割的方案为,总是使得左右孩子的增减性不同,即$f_{i+j} \leftarrow f_ig_j+g_if_j$;
以左增右减为例说明,也就是形如(1<2)+(4>3),考虑到2和4间有断层,如果将2划到左边,不可能还能划分成下降的,于是划分唯一

得到$f_i=1*g_{i-1}+f_{i-1}*1+\sum_{j=2}^{i-2} f_j g_{i-j}+g_jf_{i-j}$,考虑到f和g其实是对称的(翻转一下是双射),可以简化为,$f_0=0,f_1=1/2,f_{i>1}=f_{i-1}+2\sum_{j=0}^{i} f_jf_{i-j}$

$$
F=xF+2F^2+x/2,求根公式得F=\frac{ (1-x) \pm \sqrt{x^2-6x+1} }{4}
\\
x^n+1)^{1/2}=[x^n]\sum_{i=0}^{\infty} C_{1/2}^{i} x^i(x-6)^i=[x^n] C_{1/2}^i C_{i}^{n-i} (-6)^{2i-n}
$$

1
2
3
4
5
6
PRE();int n=qread();ll ans=0,now=1,inv2=invm(2),six=qpower(MOD-6,MOD-1-n);
fo(i,0,n)
{
add(ans, six*now%MOD*facinv[i]%MOD*C(i,n-i)%MOD );
now=now*(MOD+1-i-i)%MOD*inv2%MOD,six=six*36%MOD;
} ans=MOD-ans;if(n==1) ans=MOD+ans-1;write(ans*invm(4)*2%MOD);

事实上,该序列恰为小施罗德数(超级卡特兰数),我不知道怎么和其他组合意义联系在一起,不过这与解题无关

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/38bb3cb9.html
转载请注明出处,谢谢!