CF1626D 题解
貌似题解区没有这种解法。
题面
CF1626D Martial Arts Tournament - 洛谷 (luogu.com.cn)
思路
问题就是把 \(a\) 分成 \(3\) 个子集（可以为空），每两个子集里的数并不重复，把每个子集的大小补到 \(2^x\) 最少要补的数的个数。
先把 \(a\) 给排序，那么就可以转化为给 \(a\) 选择两个满足 \(a_i\neq a_{i+1}\) 的 \(i\) 后面切两刀（\(i\) 可以相同），分成 \(3\) 段，求把 \(3\) 段补成 \(2^x\) 最少要补的数的个数。
考虑二分答案，然后判断是否可以只用补小于等于 \(mid\) 的个数的数。
考虑枚举第一个断点，然后枚举第二段的长度，这里我们贪心地选择 \(2^x,x\in\mathbb{Z}\)，但是这个点不一定能作为断点，则我们就要把这个点左边第一个能断的点作为第二个断点、以及右边第一个能断的点作为第二个断点的答案都给算上，遇到小于等于 \(mid\) 的直接返回，注意判边界。
时间复杂度 \(O(n\log^2n)\)。
代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
// #define gc getchar
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#define FILE(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout);
#define FIN(s) freopen(s".in","r",stdin);
#define FOUT(s) freopen(s".out","w",stdout);
#define ll long long
#define re register int
#define rl register ll
#define il inline
using namespace std;
const int MN=2e5+5;
ll n,a[MN],l[MN],r[MN];
char buf[1<<23],*p1=buf,*p2=buf;
il void write(rl n){if(n<0){putchar('-');write(-n);return;}if(n>9)write(n/10);putchar(n%10+'0');}
il ll read(){ll x=0,f=1;char ch=gc();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}return x*f;}
il ll gs(rl x){if(!x)return 1;if((1<<__lg(x))==x)return 0;return (1<<__lg(x)+1)-x;}
il bool check(rl num){for(re i=1; i<=n; ++i) if(a[i]!=a[i+1]||i==n){if(gs(i)+gs(n-i)+1<=num) return true;for(re j=0; i+(1<<j)+1<=n; ++j){ll L=l[i+(1<<j)+1],R=r[i+(1<<j)+1]-1;if(L<=i) continue;if(gs(i)+gs(L-i)+gs(n-L)<=num) return true;if(R>n) continue;if(gs(i)+gs(R-i)+gs(n-R)<=num) return true;}}return false;
}
il void solve(){n=read();for(re i=1; i<=n; ++i) a[i]=read();sort(a+1,a+1+n);for(re i=1; i<=n; ++i) if(a[i]!=a[i-1]||i==1) l[i]=i-1;else l[i]=l[i-1];for(re i=n; i; --i) if(a[i]!=a[i+1]||i==n) r[i]=i+1;else r[i]=r[i+1];ll l=0,r=gs(n)+2;while(l<r){ll mid=l+r>>1;if(check(mid)) r=mid;else l=mid+1;}write(l);putchar('\n');
}
int main(){// ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll T=read();while(T--)solve();return 0;
}//250915