自动搬运

查看原文

来自洛谷，原作者为

	cybermage_liu 十年星空见，一剑天地开。

搬运于2025-08-24 23:15:45，当前版本为作者最后更新于2025-05-10 13:02:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

好像是新思路？

题意简化

每次从 $1$ 到 $n$ 的范围内，找到一个最小的值，使得其与 $S$ 集合内的数的最小差最大且大于 $1$。

思路

我们可以把找这个值看作一个在 $1$ 到 $n$ 的区间内选数的过程。

很明显，首先 $n$ 是必须要选的。

然后使用 dfs 用二分的方式搜索，类比快速幂：

设 dfs 返回值为当前长度为 $r$，且必须选第一个，必须不选最后一个的按题意在当前区间内选数的数的个数。

如果可以选中位数，就选中位数，并以中位数为界限将原区间划分为 $2$ 个子区间。

• 当原区间长为奇数时，$dfs(r)=dfs(r-mid)+dfs(mid)$。

• 当原区间长为偶数时，$dfs(r)=dfs(mid)\times 2$。

如果连中位数都不能选：

• 不可选第一个，原区间长为 $1$，直接返回 $0$。

• 可以选第一个，原区间长为 $2$ 或 $3$，直接返回 $1$。

这样就可以得到 $40$ 分。

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
struct node{
	int x,y;
};
int dfs(int r){
	if(r==0) return 0;
	if(r==1) return 0;
	if(r==2) return 1;
	if(r==3) return 1;//边界四个条件
	int mid=1+r>>1;//r-mid 小于等于 mid。
	if((1+r)%2==0) return dfs(mid)+dfs(r-mid);//区间长为奇
	else return dfs(mid)*2;//区间长为偶
}
signed main(){
	int n;
	cin>>n;
	cout<<dfs(n-1)+1;
//除去最后一个 n 算出来的 dfs 值需要再选上 n 。
}

为什么只有 $40$ 分呢？

因为多次搜索到区间是奇数时，时间复杂度会大幅度退化。

不一样的地方

易发现规律 $dfs(r+1)-dfs(r)$ 为 $0$ 或 $1$。

我们将原定义的返回值改成 $x$，并新增一个 $y$，表示如果将当前区间长度加 $1$，$x$ 值是否要加 $1$。

如果其两个子区间中较小的子区间需要加 $1$，那么当前区间也需要加 $1$。

• 当区间长度为偶数时显然。

• 当区间长度为奇数时，如果给区间长度加 $1$，必然划到小区间。

不用记忆化，少开一个 map。

时间复杂度严格 $O(\log n)$。

AC code

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
struct node{int x,y;};
node dfs(int r){
    if(r==0) return {0,0};
	if(r==1) return {0,1};
	if(r==2) return {1,0};
	if(r==3) return {1,1};//边界四个条件。
	int mid=1+r>>1;
	node res=dfs(r-mid);//r-mid 小于等于 mid。
	if(r%2) return {res.x*2+res.y,res.y};//区间长为奇
	else return {res.x*2,res.y};//区间长为偶
}
signed main(){
	int n;
	cin>>n;
	cout<<dfs(n-1).x+1;
//除去最后一个 n 算出来的 dfs 值需要再选上 n 。
}