好像是新思路？

题意简化

每次从

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

分。

CPP

#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

CPP

#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 。
}

P12464 『FCRT / 1 - 1』Seats 题解

文章操作

题意简化

思路

不一样的地方

AC code

相关推荐

评论

P12464 『FCRT / 1 - 1』Seats 题解