题解：AT_abc252_h [ABC252Ex] K-th beautiful Necklace

· · 题解

怎么有人这题写了 221 行？

第一个要考虑的问题是答案的上限。根据小学奥数，要把一个数拆成若干个等于它的数，应当尽最大努力拆 3，最多拆两个 2，绝不拆 1。

将 70 这样拆分能够得到的最大答案上限 \le 2\times 10^{11}，所以 k 的实际范围是 1\sim 2\times 10^{11}。以下令总方案数为 m。

考虑根号分治，把数分成两个大小接近 \sqrt m 的部分。令其分别为 a_i, b_j，答案即为 a_i\oplus b_j 的 k 大值。

如果朴素二分答案，会发现是 O(\sqrt m \log^2 V) 的。发现这很像线段树二分的形式，考虑逐位确定答案变为 O(\sqrt m\log V)。

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

inline int read(){
    int a=0,b=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')  b=-1;
        c=getchar();
    }
    while(isdigit(c)){
        a=(a<<1)+(a<<3)+(c-'0');
        c=getchar();
    }
    return a*b;
} 
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>=10)   write(x/10);
    putchar(x%10+48);
}
inline void write1(int x){
    write(x),putchar(' ');
}
inline void write2(int x){
    write(x),putchar('\n');
}
int n,col,k;    //代表宝石总数 颜色数 第 k 大 
//枚举 前 k 大的分数线 字典树二分实现即可 
int colin[509]; //谭总的世界 IOI2025 金牌线 
vector<int> g[78]; 

struct node{
    int sum;
    int id;
    friend bool operator <(node a,node b){
        return a.sum>b.sum;
    }
}col1[509]; 

int C[509]; //属于第一类还是第二类  

int a[1919810],b[1919810];  //把 a 全部插入 Trie 让 b 在 Trie 上跑 
int aidx=0,bidx=0;  //代表目前的情况  

int pow2[78];
void dfs1(int now,int xor_){
//  cout<<'#'<<now<<' '<<xor_<<endl;
    if(now==col+1){
        a[++aidx]=xor_;
//      cout<<'$'<<aidx<<' '<<xor_<<endl;
        return;
    }
    if(C[now]==2){
        dfs1(now+1,xor_);
        return;
    }
    for(int i=0;i<g[now].size();i++){
        int x=g[now][i];
        dfs1(now+1,xor_^x);
    }
} 
int b1[1919810];
void dfs2(int now,int xor_){
//  cout<<'!'<<now<<' '<<xor_<<endl;
    if(now==col+1){
        b[++bidx]=xor_,b1[bidx]=1;  //代表初始在 1 号点  
        return;
    }
    if(C[now]==1){
        dfs2(now+1,xor_);
        return;
    }
    for(int i=0;i<g[now].size();i++){
        int x=g[now][i];
        dfs2(now+1,xor_^x);
    }
}
const int M=3e7+15;
struct tree{
    int tot;
    int lson,rson;  //代表两边的答案 规定 rson  
}Trie[M];
int Trie_idx=1; //代表目前的解  以一为根 
//int b1[1919810]; 
void insert(int sum){
    int now=1;  //目前所在节点 
    Trie[1].tot++;  //代表这就是目前节点  
    for(int i=59;i>=0;i--){
//      cout<<'*'<<sum<<endl;
        if(sum>=pow2[i]){
//          cout<<'!'<<' '<<i<<' '<<sum<<' ';
            sum-=pow2[i];
//          cout<<sum<<endl;
            if(Trie[now].rson==0)   Trie[now].rson=++Trie_idx;
//          Trie[now].tot++;
            now=Trie[now].rson;
            Trie[now].tot++;
        } 
        else{
            if(Trie[now].lson==0)   Trie[now].lson=++Trie_idx;
            now=Trie[now].lson;
            Trie[now].tot++;
        }
    } 
//  cout<<"终点结构"<<' '<<now<<endl; 
} 
void init(){
    pow2[0]=1;
    for(int i=1;i<=59;i++)  pow2[i]=pow2[i-1]*2;
} 
signed main(){
    init();
//  for(int i=1;i<=59;i++){
//      
//  }
//  cout<<endl;
//  write(558);
    n=read(),col=read(),k=read();
    for(int i=1;i<=n;i++){
        int col1=read(),a=read();
        g[col1].push_back(a);
        colin[col1]++;  //或许改一种方式更好  
    }
    for(int i=1;i<=col;i++){
        col1[i]=(node){colin[i],i};
    }
    sort(col1+1,col1+col+1);    //代表之后还要分组 ！ 
    int a_=1,b_=1;  //分组的处理法！
    for(int i=1;i<=col;i++){
        int x=col1[i].sum,id=col1[i].id;
        if(a_>b_){
            b_*=x;
            C[id]=2; 
        }
        else{
            a_*=x; 
            C[id]=1;
        }
    } 
//  for(int i=1;i<=col;i++){
//      cout<<'!'<<C[i]<<endl;
//  }
    dfs1(1,0);  //代表目前的情况  
    dfs2(1,0); 
//  cout<<aidx<<endl; 
//  for(int i=1;i<=aidx;i++){
//      cout<<a[i]<<' ';
//  }
//  cout<<endl;
//  cout<<bidx<<endl;
//  for(int i=1;i<=bidx;i++){
//      cout<<b[i]<<' ';
//  }
//  cout<<endl;
    for(int i=1;i<=aidx;i++){
        insert(a[i]); 
    }
//  for(int i=1;i<=Trie_idx;i++){
//      cout<<'^'<<i<<' '<<Trie[i].lson<<' '<<Trie[i].rson<<' '<<Trie[i].tot<<endl;
//  }
//  cout<<endl;
    //考虑 k 的特性  
    int include13=0; 
//  cout<<"谭总的世界-040"<<endl;
    for(int i=59;i>=0;i--){
        //确定答案 ！
//      if(i<=4)    cout<<"谭总的世界-041"<<endl; 
        int cal=0;  //代表 取 1 的情况数  
        for(int j=1;j<=bidx;j++){
            if(b[j]&pow2[i]){
                //代表选 0 的一方 
                cal+=Trie[Trie[b1[j]].lson].tot; 
            } 
            else    cal+=Trie[Trie[b1[j]].rson].tot;
//          if(i<=4){
//              cout<<cal<<' ';
//          } 
        } 
//      cout<<endl;
//      cout<<'#'<<cal<<' '<<k<<endl;
        if(cal<k){  //代表能够凑出这一位的方案小于等于 k 种 这里加不上去！  
            k-=cal;
//          cout<<'A';
            for(int j=1;j<=bidx;j++){
                if(b[j]&pow2[i]){
                    //往同向方向走  
                    b1[j]=Trie[b1[j]].rson;
                }
                else    b1[j]=Trie[b1[j]].lson; //走路上朝！  
//              cout<<b1[j]<<' ';
            }
//          cout<<endl;
        }
        else{
//          cout<<'B';
            for(int j=1;j<=bidx;j++){
                if(b[j]&pow2[i])    b1[j]=Trie[b1[j]].lson;
                else    b1[j]=Trie[b1[j]].rson;
//              cout<<b1[j]<<' ';
            } 
//          cout<<endl;
            include13+=pow2[i];
        } 
//      cout<<'&'<<include13<<endl;
//      cout<<"谭总的世界-017"<<endl;
//      for(int j=1;j<=bidx;j++){
//          cout<<b1[j]<<' ';
//      }
//      cout<<endl;
    }
//  cout<<include13<<endl;
    write2(include13);
//  for(int i=1;i<=bidx;i++){
//      cout<<b[i]<<' ';
//  }
//  cout<<endl;
    return 0;
}//一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的！