P15651 题解
把题目中给定的操作想象成环上有一个分界点，每次可以把它往一边动两个位置，然后把经过的两个数异或起来。
那么我们得到第一个观察：需要把
首先有些情况下我们无法做到把一整段异或起来之后变成一个数。具体地，考虑分界点上那一段，我们发现：
对于外面的段，可以用类似的分析说明它的长度不能是
接下来我们考虑一个合法的操作序列。首先经过一系列操作之后分界点一定会从它一开始所在的那个段里面走出来，走到它的两个端点之一。这样可以大大简化之后的讨论。
根据之前的分析，我们发现此时每一段的长度都不是
考虑把之后的操作分成若干阶段，每一阶段的内容是走到某一个环上的分段里面，经过一些操作再走出来。
不难得到如下的观察：如果分界点从某个分段的一端走到另一端，那么它的长度模
所以我们不用关心每一阶段的具体内容，只需要关心它从哪一头进去，从哪一头出来。
接下来的部分中，我们用“一次操作”代指这里的“一个阶段”。
对于每个长度
现在把操作分成两类：
也就是说，我们可以对操作序列进一步简化：每一次操作是从一个分段的一端走到另一端。我们先不关心这个玩意具体的实现。
容易发现，在这种极端抽象的模型中，我们不需要关心走的方向，所以可以把这个有向路径改写成无向图。这个无向图的任意一条欧拉路径都是合法的。而根据欧拉路径的性质，如果一条边重复了至少三次，那就可以去掉两次。也就是说，存在一个方案使得每段至多经过两次。
这是一个很强的性质。如果一段经过次数非常多，那它的长度一定需要足够长。而如果一段只需要经过一次或者两次，那么它对长度几乎没有限制——事实上，在
接下来枚举分界点最后的位置。在这种情况下，可能的欧拉路径只有一种，如下所示：
其余情况都是它的镜像或者退化版本。
把路径按照
分界点的情况需要特殊处理，不过事实上对它的限制除了两侧
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=257;
ll T,n,m,pos,flip;
ll a[N],b[N];
namespace A{
ll a[N],b[N];
bool f[N][N][4];
bool check_zero(int l,int r){
return l==0&&r==1||l==1&&r==2||l==2&&r==0;
}
bool check(int type,int dis){
if (type==0){
return dis%3==2;
}
if (type==2){
return dis==1;
}
return dis>=4&&dis%3==1;
}
bool solve(){
memset(f,0,sizeof(f));
f[0][0][pos==0]=1;
for (int i=0;i<m;++i) for (int j=0;j<n;++j){
f[i][j][2]|=f[i][j][1];f[i][j][3]|=f[i][j][2];
for (int k=0;k<4;++k) if (f[i][j][k]){
for (int l=j+1;l<=n;++l) if (a[l]==b[i+1]){
if (j<pos&&pos<l){
if (check_zero((pos-j)%3,(l-pos)%3)){
f[i+1][l][1]=1;
}
}
else if (check(k,l-j)){
f[i+1][l][k|(l==pos)]=1;
}
}
}
}
if (f[m][n][1]||f[m][n][2]||f[m][n][3]){
cout<<"Yes\n";
for (int i=1;i<=n-m;++i) cout<<"1 ";cout<<'\n';
return 1;
}
return 0;
}
}
bool solve2(){
for (int i=1;i<=n;++i){
A::a[i]=A::a[i-1]^a[i];
}
for (int i=1;i<=m;++i){
A::b[i]=A::b[i-1]^b[i];
}
return A::solve();
}
void solve(){
for (int i=1;i<=n;++i){
if (solve2()){
return;
}
++pos;
ll tmp=a[n];
for (int i=n;i>1;--i){
a[i]=a[i-1];
}
a[1]=tmp;
}
if (solve2()){
return;
}
pos=0;flip=1;
reverse(a+1,a+1+n);reverse(b+1,b+1+m);
for (int i=1;i<=n;++i){
if (solve2()){
return;
}
++pos;
ll tmp=a[n];
for (int i=n;i>1;--i){
a[i]=a[i-1];
}
a[1]=tmp;
}
if (solve2()){
return;
}
cout<<"No\n";
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>T>>T;
while(T--){
cin>>n>>m;pos=0;flip=0;
for (int i=1;i<=n;++i){
cin>>a[i];
}
for (int i=1;i<=m;++i){
cin>>b[i];
}
solve();
// cout<<T<<endl;
}
return 0;
}（代码不包含构造部分。）
至于往正解优化也很简单：发现从前到后每一段都可以贪心选取。由于第一、第二和第四段长度不固定，所以这里的贪心是简单的。第三段需要预处理一下匹配长度，所以总复杂度是
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=257;
ll T,n,m,pos,flip;
ll a[N],b[N];
namespace A{
ll a[N],b[N],f1[N],f2[N],f3[N],match[N][N],p2[N],p3[N];
vector<ll> ans,L,M,R;
void left(){
ans.emplace_back(2);
}
void right(){
ans.emplace_back(1);
}
void construct(){
ans.clear();L.clear();M.clear();R.clear();
int stat=3,pl=0,pr=0;
for (int i=m;i;--i){
if (stat==1){
M.emplace_back(f1[i]-f1[i-1]);
}
else if (stat==2){
if (p2[i]){
pl=pos-f1[i-1];pr=f2[i]-pos;
stat=1;
}
else{
R.emplace_back(f2[i]-f2[i-1]);
}
}
else{
if (p3[i]!=-1){
f2[i-p3[i]]=f3[i]-p3[i];
i-=p3[i]-1;
stat=2;
}
else{
L.emplace_back(f3[i]-f3[i-1]);
}
}
}
if (pl||pr){
if (pr&1){
if (pl==1){
pr-=2;++pl;
right();
}
left();
pl-=2;++pr;
}
while(pr){
pr-=2;++pl;
right();
}
M.insert(M.begin(),pl);
}
reverse(R.begin(),R.end());
for (auto x:R){
int p=(x-4)/3;
while(p--){
right();right();left();
}
right();right();
}
for (auto x:R){
left();
}
for (auto x:M){
int p=(x-2)/3;
while(p--){
left();left();right();
}
left();
}
for (auto x:L){
int p=(x-4)/3;
while(p--){
left();left();right();
}
left();left();
}
for (auto x:L){
right();
}
assert(ans.size()==n-m);
for (auto x:ans){
cout<<(flip*3^x)<<' ';
}
cout<<'\n';
}
bool solve(){
if (a[n]!=b[m]){
return 0;
}
if (pos==0&&(n-m)%3){
return 0;
}
for (int i=m;i;--i){
for (int j=n;j;--j){
match[i][j]=(b[i]==a[j])?match[i+1][j+1]+1:0;
}
}
memset(f1,-1,sizeof(f1));
memset(f2,-1,sizeof(f2));
memset(f3,-1,sizeof(f3));
memset(p2,0,sizeof(p2));
memset(p3,-1,sizeof(p3));
f1[0]=(pos==0?-1:0);
f2[0]=(pos==0?0:-1);
for (int i=1,p=1;i<pos&&p<=m;++i){
if ((i-2*p)%3==0&&a[i]==b[p]){
f1[p++]=i;
}
}
for (int i=1;i<=m;++i){
if (f1[i-1]==-1){
continue;
}
int tot=n-((i-1)*2+(m-i));tot=(tot%3+3)%3;
if ((4-tot+(i-1)*2-pos)%3){
continue;
}
for (int o=pos+(2-tot);o<=n;o+=3){
if (a[o]==b[i]){
f2[i]=o;
p2[i]=1;
break;
}
}
}
for (int i=0;i<m;++i){
if (f2[i]==-1||f2[i+1]!=-1){
continue;
}
for (int j=f2[i]+4;j<=n;j+=3){
if (a[j]==b[i+1]){
f2[i+1]=j;break;
}
}
}
for (int i=0;i<=m;++i){
if (f2[i]==-1){
continue;
}
int r=(i==0?0:n);
for (int j=f2[i];j<=r;j+=3){
if (a[j]==b[i]){
int k=match[i+1][j+1];
if (f3[i+k]==-1||f3[i+k]>j+k){
f3[i+k]=j+k;
p3[i+k]=k;
}
}
}
}
for (int i=0;i<m;++i){
if (f3[i]==-1){
continue;
}
for (int j=f3[i]+4;j<=n;j+=3){
if (a[j]==b[i+1]){
if (f3[i+1]==-1||f3[i+1]>j){
f3[i+1]=j;
p3[i+1]=-1;
}
break;
}
}
}
if (f3[m]!=-1){
if (f3[m]<n){
if (p3[m]==-1){
f3[m]=n;
}
else if (p3[m]){
f3[m-1]=f3[m]-1;
p3[m-1]=p3[m]-1;
f3[m]=n;p3[m]=-1;
}
else{
f2[m]=f3[m]=n;
}
}
cout<<"Yes\n";
construct();
return 1;
}
return 0;
}
}
bool solve2(){
for (int i=1;i<=n;++i){
A::a[i]=A::a[i-1]^a[i];
}
for (int i=1;i<=m;++i){
A::b[i]=A::b[i-1]^b[i];
}
return A::solve();
}
void solve(){
for (int i=0;i<=m+1;++i){
for (int j=0;j<=n+1;++j){
A::match[i][j]=0;
}
}
for (int i=1;i<=n;++i){
if (solve2()){
return;
}
++pos;
ll tmp=a[n];
for (int i=n;i>1;--i){
a[i]=a[i-1];
}
a[1]=tmp;
}
if (solve2()){
return;
}
pos=0;flip=1;
reverse(a+1,a+1+n);reverse(b+1,b+1+m);
for (int i=1;i<=n;++i){
if (solve2()){
return;
}
++pos;
ll tmp=a[n];
for (int i=n;i>1;--i){
a[i]=a[i-1];
}
a[1]=tmp;
}
if (solve2()){
return;
}
cout<<"No\n";
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>T>>T;
for (int t=1;t<=T;++t){
// cerr<<t<<endl;
cin>>n>>m;pos=0;flip=0;
for (int i=1;i<=n;++i){
cin>>a[i];
}
for (int i=1;i<=m;++i){
cin>>b[i];
}
solve();
// cout<<T<<endl;
}
return 0;
}