专栏文章

题解：P13686 【MX-X16-T4】「DLESS-3」XOR and Split

PPJM2008
P13686题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mioepq6h
此快照首次捕获于
2025/12/02 17:59
3 个月前
此快照最后确认于
2025/12/02 17:59
3 个月前
查看原文

主要思路

又是一道（可以直接求出答案的）思维题。
n≤3n\le3 时手动枚举，n=1,2,3n=1,2,3 时答案分别为 1,3,21,3,2。
n≥4n\ge4 时，测试点 44 提示我们思考 n=2k(k∈N)n=2^k(k\in\N) 时情形。
n=2kn=2^k 时，显然每个数单独划分为一段权值最大（否则所有 aia_i 均不超过 2k−12^k-1，从而异或和不超过 2k−12^k-1）。
此时权值为 1⊕2⊕⋯⊕2k=2k1\oplus2\oplus\dots\oplus2^k=2^k （熟知 k≥2k\ge2 时 1⊕2⊕⋯⊕(2k−1)=01\oplus2\oplus\dots\oplus(2^k-1)=0）。
进一步，2k+1≤n≤2k+1−12^k+1\le n\le2^{k+1}-1 时，仍可分为 2k2^k 组，只需在 1⊕2⊕⋯⊕2k=2k1\oplus2\oplus\cdots\oplus2^k=2^k 的基础上加入 n−2kn-2^k 个元素，保证异或和为 2k−12^k-1 即可（容易保证），权值为 2k+1−12^{k+1}-1。且由于所有 aia_i 均不超过 2k+1−12^{k+1}-1 知 2k+1−12^{k+1}-1 最优。
综上所述，答案为 {2kn=2k2k+1−12k+1≤n≤2k+1−1\begin{cases}2^k&n=2^k\\2^{k+1}-1&2^k+1\le n\le 2^{k+1}-1\end{cases}。

考场抽象代码：

CPP
#include <bits/stdc++.h>
using namespace std;
long long t,n,p=1;
int main(){
	cin>>t;
	while(t--){
		cin>>n; p=1;
		if(n<=3){
			if(n==1) cout<<1<<endl;
			else if(n==2) cout<<3<<endl;
			else cout<<2<<endl;
			continue;
		}
		while(p<n) p*=2;
		if(n==p-1||n==p) cout<<n<<endl;
		else cout<<p-1<<endl;
	}
	return 0;
}

评论

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

正在加载评论...