题目链接
题目思路
如果所有元素出现都是偶数次,那么就有办法,否则就没有办法
这个题目感觉构造方法不是很难想
就是每次假设出现了 \(A B CA\)
那么每次消去两个\(A\)然后中间的字符翻转
如何写很巧妙,我是参考一位大佬的代码
采用从后往前遍历,因为如果从前往后很麻烦
具体实现看代码
代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=2e5+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n;
int a[maxn];
int tmp[maxn];
signed main(){
int _;scanf("%d",&_);
while(_--){
map<int,int> cnt;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
cnt[a[i]]++;
}
bool flag=0;
for(auto x:cnt){
if(x.se%2==1){
flag=1;
break;
}
}
if(flag){
printf("-1\n");
continue;
}
vector<int> ans1;
vector<pair<int,int> > ans2;
for(int i=n;i>=1;i-=2){
int j=i-1;
while(j>=1&&a[j]!=a[i]){
j--;
}
int p=j-1;
ans1.push_back(2*(i-j));
for(int k=i-1;k>=j+1;k--){
ans2.push_back({p,a[k]});
p++;
tmp[p]=a[k];
}
for(int k=j;k<=i-2;k++){
a[k]=tmp[k];
}
}
printf("%d\n",ans2.size());
for(auto x:ans2){
printf("%d %d\n",x.fi,x.se);
}
printf("%d\n",ans1.size());
reverse(ans1.begin(),ans1.end());
for(auto x:ans1){
printf("%d ",x);
}
printf("\n");
}
return 0;
}