专栏文章

题解：CF2039D Shohag Loves GCD

llgx57
CF2039D题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miqwvfkl
此快照首次捕获于
2025/12/04 12:03
3 个月前
此快照最后确认于
2025/12/04 12:03
3 个月前
查看原文
简单题。
注意到答案与数根本没有关系，从而想到先把数从大到小排序。
接下来我们一个一个填数，由于字典序要最大，所以第一位肯定填最大的数。
注意到 gcd⁡(x,y)≤min⁡(x,y)\gcd(x,y) \le \min(x,y)，于是可以在此基础上构造。令 ansi=比 max⁡j∣i,j<iansj 小的第一个数ans_i=\text{比 } \displaystyle\max_{j \mid i,j <i} ans_j \text{ 小的第一个数}。容易证明，这个构造合法并且是字典序最大的。
于是我们用 O(nn)O(n \sqrt n) 的复杂度解决了这个问题。
CPP
void sol(){
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=n;i++) ans[i]=0;
	for (int i=1;i<=m;i++) cin>>a[i];
	sort(a+1,a+m+1,greater<int>());
	ans[1]=1;
	for (int i=2;i<=n;i++){
		int ma=0;
		for (int j=1;j*j<=i;j++){
			if (i%j==0){
				ma=max(ma,max(ans[j],ans[i/j]));
			}
		}
		ans[i]=ma+1;
		if (ans[i]>m) return cout<<-1<<endl,void();
	}
	for (int i=1;i<=n;i++) cout<<a[ans[i]]<<' ';
	cout<<endl;
}

评论

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

正在加载评论...