题解:P11008 『STA - R7』异或生成序列
Solution
序列 \(p\) 是 \(1\) ~ \(n\) 的排列,因此考虑搜索回溯。
由 \(\sum n \le 2 \times 10^6\) 得知 \(O(n^2)\) 会炸,深感遗憾但仍考虑剪枝。
坚信深搜过百万的蒟蒻。。。
原 \(b\) 序列为长度 \(n-1\) 的序列:
{ \(b_1,b_2,b_3 \cdots b_n-1\) }
将其前面插入一个元素 \(x\) ,得到长度为 \(n\) 的序列 \(b'\) :
{ \(x,b_1,b_2,b_3 \cdots b_n-1\) }
若 \(f(i)\) 表示原 \(b\) 序列从第 \(1\) 位到第 \(i\) 位的异或前缀和,\(f'(i)\)表示后 \(b'\) 序列从第 \(1\) 到第 \(i+1\) 位的异或前缀和,则有:
\(f'(i)=f(i)\) xor \(b'_1\)
当 \(b'_1\) 可行时,根据题目中异或运算性质将其做异或前缀和便得到了所要求的 \(p\) 序列,此时 \(p_i=f'(i)\) ,这样保证了 \(b_i=p_i\) \(xor\) \(p_{i+1}\) 。
此时有一个浅显的可行性剪枝,因为 \(1 \le f'(i) \le n\) , 所以当存在一个 \(b'_1\) 使任意一个\(f'(i)\) 满足如下条件时,此时序列 \(b'\) 第一个数字不可行 。:
\(f'(i)\) = \(f(i)\) \(xor\) \(b'_1 = n+1\) 或 \(0\)
因此可以一边输入 \(b\) 序列一边存异或前缀和,每一位筛掉一个如此的 \(b'_1\) 。
(这实际上把一部分不可行搜索给提前筛掉,剩下的不可行搜索仍继续判断并剪枝,这样便能大大降低复杂度,将那些把搜索代码卡到趋近 \(O(n^2)\) 的数据削弱成\(O(n \log n)\)。不写快读不加\(O2\), \(800ms\) 险胜)
综上,我们便完成(水过)了这一题。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+1;
int t,n,fl,b[N],p[N],mp[N],sum;
//mp存是否填过该数字
unordered_map<int,int> vis;
//vis存可行性,true表示不可行,map的初始化比数组稍快亿点点,不用TLE
void dfs(int x,int dep){
if(x<1||x>n||mp[x])return;//可行性剪枝,当P[i]大于n 或 小于1 或 数字重复时不可行
if(dep==n){//可行
for(int i=1;i<n;++i)printf("%d ",p[i]);//输出答案
printf("%d\n",x);
fl=0;//已经输出答案,打上标记避免再次搜索
return;
}
p[dep]=x;
//搜索回溯
++mp[x];
dfs(b[dep]^x,dep+1);
--mp[x];
}
int main() {
scanf("%d",&t);
while(t--){
scanf("%d",&n);
vis.clear();//初始化
fl=1,sum=0;
for(int i=1;i<n;++i){
scanf("%d",b+i);
sum^=b[i];//做异或前缀和
++vis[sum];//剪枝:第一个数字的选择中筛掉0^sum即sum(序列p中仅有1~n,没有0)
// ++vis[(n+1)^sum]; 剪枝:第一个数字的选择中筛掉(n+1)^sum(序列p中仅有1~n,没有n+1)
// 做其中一个剪枝就行,两个剪枝一起做速度更慢
}
for(int i=1;i<=n;++i){
if(!fl) break;//如果可行
if(!vis[i]) dfs(i,1);//如果且尚未输出答案,搜索第一个数为i的情况
}
}
return 0;
}
快读压行代码
加了快读的代码( \(600\) 多\(ms\) 险胜,压行,码风稍怪,轻喷):
#include<bits/stdc++.h>
using namespace std;
#define to(x,y) for(int x=1;x<=y;++x)
#define fr(x,y) for(int x=0;x<y;++x)
inline void wrt(int x) {if (x < 0) {x = -x;putchar('-');}if (x > 9) wrt(x / 10);putchar(x % 10 + '0');}
inline int read(){int x=0,f=1;char ch=getchar();while(ch<48||ch>57){if(ch=='-')f=-1;ch=getchar();}while(ch>=48&&ch<=57)x=x*10+ch-48,ch=getchar();return x*f;}
const int N=2e6+1;
int t,n,fl,b[N],p[N],mp[N],sum;
unordered_map<int,int> vis;
void dfs(int x,int dep){
if(x==0||x>n||mp[x])return;
if(dep==n){
to(i,n-1)wrt(p[i]),putchar(' ');
wrt(x),putchar('\n');
fl=0;
return;
}
p[dep]=x,++mp[x];
dfs(b[dep]^x,dep+1);
--mp[x];
}
int main() {
for(t=read();t--;){
vis.clear();
n=read();
fl=1;sum=0;
to (i,n - 1)b[i]=read(),sum^=b[i],++vis[sum];
to(i,n){
if(!fl)break;
if(!vis[i]){
dfs(i,1);
}
}
}
return 0;
}