P12464 『FCRT / 1 - 1』Seats 题解

cybermage_liu · 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 。
}