专栏文章

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

iinclude13_fAKe
AT_abc252_h题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio37q5z
此快照首次捕获于
2025/12/02 12:37
3 个月前
此快照最后确认于
2025/12/02 12:37
3 个月前
查看原文
怎么有人这题写了 221221 行？
第一个要考虑的问题是答案的上限。根据小学奥数，要把一个数拆成若干个等于它的数，应当尽最大努力拆 33，最多拆两个 22，绝不拆 11。
将 7070 这样拆分能够得到的最大答案上限 ≤2×1011\le 2\times 10^{11}，所以 kk 的实际范围是 1∼2×10111\sim 2\times 10^{11}。以下令总方案数为 mm。
考虑根号分治，把数分成两个大小接近 m\sqrt m 的部分。令其分别为 ai,bja_i, b_j，答案即为 ai⊕bja_i\oplus b_j 的 kk 大值。
如果朴素二分答案，会发现是 O(mlog⁡2V)O(\sqrt m \log^2 V) 的。发现这很像线段树二分的形式，考虑逐位确定答案变为 O(mlog⁡V)O(\sqrt m\log V)。
  • 实现细节：
    • 考虑到在字典树上会遍历到空节点，所以如果不想特判就要从 11 开始排序。
    • 尽量不要使用 1<<i\texttt{1<<i}，会挂。
CPP
#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;
}//一定要挽回罗琪钧的遗憾啊，一定会挽回罗琪钧的遗憾的！

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...