专栏文章

题解：P12402 [COI 2025] 贪腐 / Korupcija

RRainbow_qwqCrystal
P12402题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@mip72rh8
此快照首次捕获于
2025/12/03 07:13
3 个月前
此快照最后确认于
2025/12/03 07:13
3 个月前
查看原文
怎么没人做，写个题解好了。 upd:发完题解一下就有一堆人做了
首先打表发现，只要 bib_i 全是偶数就能构造。注意 n=1n=1 要特判。
考虑归纳构造。考虑去掉 bn−1b_{n-1}。
我们可以做若干次 bn−1→bn−1−2,bi→bi+2(i<n−1)b_{n-1} \to b_{n-1} - 2,b_i \to b_i+2 (i<n-1) 的操作，直到 bn−1b_{n-1} 变为 00。
如果此时 bib_i 能够做到全是 44 的倍数，把 bi→bi2b_i\to \dfrac{b_i}{2} 递归构造一个方案，然后对于这个子方案，每个 pair (x,y)(x,y) 可以变成 (x,y),(x+2n−1,y+2n−1)(x,y),(x+2^{n-1},y+2^{n-1})，也可以变成 (x,x+2n−1),(y,y+2n−1)(x,x+2^{n-1}),(y,y+2^{n-1})。把一个第一种变成第二种就可以使得 n−1n-1 多 22 个，ii 减少 22 个。
那么能否做到呢？事实上只要保证能把前面每个 bi2\frac{b_i}{2} 是奇数的必须要 +2+2，也就是 bn−1b_{n-1} 如果足够大就满足了。
将 bib_i 从小到大排序，此时 bn−1b_{n-1} 是最大的，且至少有 2n−1n\frac{2^{n-1}}{n} 级别。对于 nn 大的情况就一定能归纳，不能归纳的情况最大的是 2,6,6,6,6,6，暴力找方案即可。
CPP
int n;
pii b[maxn];
bool vis[maxn];

namespace br{

int n;
int z[maxn],nd[maxn],lim;
bool ok=0;
vector<vector<pii>>qwq;
void dfs(int u){
	if(ok) return;
	while(vis[u])++u;
	if(u==(1<<n)){
		bool ook=1;
		For(i,0,n-1) ook&=(z[i]==nd[i]);
		if(ook) ok=1;
//		For(i,0,n-1) cout<<z[i]<<" "; cout<<"\n";
		return;
	}
	For(i,0,n-1){
		int v=(u^(1<<i));
		if(!vis[v]){
			vis[u]=vis[v]=1;
			++z[i]; qwq[i].pb({u,v});
			dfs(u+1);
			if(ok) return;
			vis[u]=vis[v]=0;
			--z[i]; qwq[i].pop_back();
		}
	}
}

vector<vector<pii>>brute(vi o){
	vi bs1={2,6,6,6,6,6};
	n=o.size();
	qwq.resize(n);
	if(o==bs1){
		vector<pii>res= {{0,1},{32,33},{16,18},{48,50},{8,10},{40,42},{24,26},{56,58},{2,6},{34,38},{17,21},{49,53},{9,13},{41,45},{4,12},{36,44},{20,28},{52,60},{22,30},{54,62},{3,19},{35,51},{11,27},{43,59},{7,23},{39,55},{14,46},{25,57},{5,37},{29,61},{15,47},{31,63}};
		for(auto [x,y]:res){
			int k=__lg(x^y);
			qwq[k].pb({x,y});
		}
		return qwq;
	}
	For(i,0,n-1) nd[i]=o[i];
	ok=0;
	dfs(0);
//	cout<<"??? "<<ok<<endl;
	return qwq;
}

}

vector<vector<pii>>solve(vector<int>o){
	int n=o.size();
//	cout<<"solve "<<n<<"\n";
//	for(int x:o)cout<<x<<" "; cout<<" \n";
	if(n==1) return br::brute(o);
	vi o2=o;
	int x=o2.back(); o2.pop_back();
	vi dl(n-1);
	For(i,0,n-2) if(o2[i]/2%2==1) o2[i]+=2,dl[i]++,x-=2;
	if(x<0) return br::brute(o);
	o2.back()+=x,dl.back()+=x/2;
	For(i,0,n-2) o2[i]/=2;
	vector<vector<pii>>res(n),pre=solve(o2);
	For(i,0,n-2){
		For(j,0,o2[i]-1){
			if(dl[i]){
				res[n-1].pb({pre[i][j].fi,pre[i][j].fi|(1<<(n-1))});
				res[n-1].pb({pre[i][j].se,pre[i][j].se|(1<<(n-1))});
				--dl[i];
			} 
			else{
				res[i].pb(pre[i][j]);
				res[i].pb({pre[i][j].fi|(1<<(n-1)),pre[i][j].se|(1<<(n-1))});
			}
		}
	}
	return res;
}

void work()
{
	n=read();
	For(i,0,n-1)b[i].fi=read(),b[i].se=i;
	if(n==1){
		puts("0 1");
		exit(0);
	}
	For(i,0,n-1)if(b[i].fi%2==0); else puts("-1"),exit(0);
	sort(b,b+n);
	
	vi o;
	For(i,0,n-1) o.pb(b[i].fi);
	vector<vector<pii>>res=solve(o);
	
	auto trs=[&](int x){
		int y=0;
		For(i,0,n-1)if(x>>i&1)y|=(1<<b[i].se);
		return y;
	};
	for(auto it:res) for(auto [x,y]:it) cout<<trs(x)<<" "<<trs(y)<<endl;
//	dfs(0);
//	for(auto it:s){
//		for(int x:it)cout<<x<<" ";
//		cout<<"\n";
//	}
}

signed main()
{
	int T=1;
	while(T--)work();
	return 0;
}
/*

*/

评论

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

正在加载评论...