专栏文章

题解：P14199 [ICPC 2024 Hangzhou R] Make It Divisible

BBinah_cyc
P14199题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minkau94
此快照首次捕获于
2025/12/02 03:48
3 个月前
此快照最后确认于
2025/12/02 03:48
3 个月前
查看原文
一句话题解：建出来笛卡尔树，区间限制转变为父子限制。发现合法的 xx 不多，枚举判断即可。
首先发现 ada_d 必定是区间最小值。考虑建出笛卡尔树，设 fapfa_p 是节点 pp 在笛卡尔树上的父亲节点，则一个 xx 合法当且仅当 ∀p,(afap+x)∣(ap+x)\forall p,(a_{fa_p}+x)|(a_p+x)。
又有 (afap+x)∣(ap+x)⇔(afap+x)∣(ap−afap)(a_{fa_p}+x)|(a_p+x)\Leftrightarrow(a_{fa_p}+x)|(a_p-a_{fa_p})。因为 ap−afapa_p-a_{fa_p} 的因数在 V=109V=10^9 的时候只有 13441344 个，所以可以直接枚举所有的 xx 并判断是否合法。
接下来证明为什么区间上的限制可以转化为笛卡尔树上父子之间的限制。
显然所有不满足该限制的 xx 均不合法，故只需要证明所有的 xx 都满足该限制。发现整除关系可以传递，则笛卡尔树上一个节点能整除以它为根的所有节点。对于一个区间，找到区间最小值在笛卡尔树上的对应节点，这个节点的子树肯定包含该区间。故满足该性质的 xx 必然合法。
放个代码。
C
// Problem: P14199 [ICPC 2024 Hangzhou R] Make It Divisible
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P14199
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define itn int
#define retunr return
bool startmb;
constexpr int N=5e4+5;
int _,n,k,a[N];

pair<int,int> st[18][N];
pair<int,int> ask(int l,int r){if(l>r) return {0,0};int k=log2(r-l+1);return min(st[k][l],st[k][r-(1<<k)+1]);}

vector<int> vec;
int solve(int l,int r)
{
	if(l>r) return 0;
	int p=ask(l,r).second,ls=solve(l,p-1),rs=solve(p+1,r);
	vector<int> can;
	for(auto x:vec)
	{
		if(ls){if((a[ls]+x)%(a[p]+x)!=0) continue;}
		if(rs){if((a[rs]+x)%(a[p]+x)!=0) continue;}
		can.push_back(x);
	}
	vec.swap(can);
	return p;
}

bool endmb;
main()
{
	cerr<<((&startmb-&endmb)/1024.0/1024)<<endl;
	cin.tie(0)->sync_with_stdio(false);
	int cyc;
	cin>>_,cyc=_;
	for(int i=1;i<=_;i++)
	{
		cin>>n>>k;
		int maxn=LLONG_MIN,minn=LLONG_MAX;
		for(int i=1;i<=n;i++) cin>>a[i],maxn=max(maxn,a[i]),minn=min(minn,a[i]);
		if(maxn==minn) {cout<<k<<' '<<k*(k+1)/2<<'\n';continue;}
		for(int i=1;i<=n;i++) st[0][i]={a[i],i};
		for(int i=1;i<=17;i++) for(int j=1;j+(1<<(i-1))<=n;j++) st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
		for(int i=1;i<n;i++)
		{
			if(a[i]!=a[i+1])
			{
				int x=min(a[i],a[i+1]),y=max(a[i],a[i+1]),val=abs(a[i+1]-a[i]);
				for(int t=1;t*t<=val;t++)
				{
					if(val%t==0)
					{
						if(1<=t-x&&t-x<=k) vec.push_back(t-x);
						if(t*t!=val&&1<=val/t-x&&val/t-x<=k) vec.push_back(val/t-x);
					}
				}
				break;
			}
		}
		solve(1,n);
		int ans=0;
		for(auto x:vec) ans+=x;
		cout<<vec.size()<<' '<<ans<<'\n';
		vec.clear();
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...