专栏文章

CF1469D

DDDF_
CF1469D题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mio13ots
此快照首次捕获于
2025/12/02 11:38
3 个月前
此快照最后确认于
2025/12/02 11:38
3 个月前
查看原文

题面

一个长为 nn 数组 aa，初始满足 ai=ia_{i}=i。
可以做不超过 n+5n+5 次操作：每次选定满足 x≠yx \neq y 的两个下标 x,yx,y，令 ax=⌈axay⌉a_{x}=\lceil \frac{a_{x}}{a_{y}} \rceil。
问是否可以将 aa 数组变为含 n−1n-1 个 11 和 11 个 22 的数组。

题解

不知道，只会暴力。
∀i<n\forall i < n，对 ii 进行一次操作可以使得 ai=1a_{i}=1。
然后要处理这个 nn，在 [2,n−1][2,n-1] 里找一个数 xx，对 nn 和 xx 做操作，每次大除以小直到一个数为 11，特判另一个数是否为 22，如果为 22 那么这个方案是合法的。
上面这个可以直接模拟。
然后从 22 到 n−1n-1 暴力枚举找到做操作次数最小的 xx。在 [1,n][1,n] 中所有数，除了 11，xx 和 nn 全都直接除以 nn，然后 xx 和 nn 照上面那个模拟互相除。
时间复杂度 O(nlog⁡n)O(n \log n)。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
int _;
int n;
int main() {
	scanf("%d",&_);
	while(_--) {
		scanf("%d",&n);
		if(n<3) {puts("0");continue;}
		int ans=30000,s=0;
		for(int i=2;i<n;i++) {
			int x1=i,x2=n,cnt=0;
			while(x1>1&&x2>1) {
				if(x2>x1) x2=(x2+x1-1)/x1,cnt++;
				else x1=(x1+x2-1)/x2,cnt++;
			}
			if(cnt<ans&&(x1==2||x2==2)) ans=cnt,s=i;
		}
		printf("%d\n",n-3+ans);
		for(int i=2;i<n;i++) if(i!=s) printf("%d %d\n",i,n);
//		for(int i=n;i>=3;i--) printf("%d %d\n",i,i/2+1);
		int x1=s,x2=n;
		while(x1>1&&x2>1) {
			if(x2>x1) x2=(x2+x1-1)/x1,printf("%d %d\n",n,s);
			else x1=(x1+x2-1)/x2,printf("%d %d\n",s,n);
		}
	}
	return 0;
}

评论

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

正在加载评论...