我的代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
#define exam(A) (M.count(A)&&M[A])
const int N=2e5+10, LEN=4e6+10;
int ans[N];
string s[N];
bool used[N], f[N];//是否相等
map<string,int> M;
void SingleRev(int w, int *cnt)
{
reverse(s[w].begin(),s[w].end());
ans[(*cnt)++]=w;
return;
}
void PreRev(int i, int *cnt, int *last)
{
memset(used,false,sizeof(used));
for(int j=0; j<*cnt; ++j) used[ans[j]]=true;
*cnt=0;
for(int j=1; j<=i; ++j) if(!used[j])
{
ans[(*cnt)++]=j;
M[s[j]]=0;
reverse(s[j].begin(),s[j].end());
M[s[j]]=1;
}
*last^=1;
return;
}
void Print(int cnt)
{
printf("%d\n", cnt);
if(cnt)
{
printf("%d", ans[0]);
for(int j=1; j<cnt; ++j) printf(" %d", ans[j]);
}
puts("");
return;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
M.erase(M.begin(),M.end());
int n; bool ok=true;
scanf("%d", &n); getchar();
for(int i=1; i<=n; ++i)
{
cin>>s[i];
f[i]=(s[i][0]!=s[i][s[i].length()-1]);//differ 1 same 0
}
int last=s[1][0], cnt=0, i;
// first segment
for(i=1; i<=n; ++i)
{
if(f[i])
{
if(last!=s[i][0]) SingleRev(i,&cnt);
if(exam(s[i])) { ok=false; break; }
M[s[i]]=1;
last^=1;
}else
{
if(s[i][0]!=last) PreRev(i-1,&cnt,&last);
i++;
break;
}
}
// latter segment
if(!ok) puts("-1");
else if(i>n)
{
if(cnt>n-cnt) PreRev(n,&cnt,&last);
Print(cnt);
}else
{
for(; i<=n; ++i)
{
if(!f[i])
{
if(last!=s[i][0]) { ok=false; break; }
if(exam(s[i]))
{
SingleRev(i,&cnt);
if(exam(s[i])) { ok=false; break; }
}
M[s[i]]=1;
}else
{
if(last!=s[i][0]) SingleRev(i,&cnt);
if(exam(s[i])) { ok=false; break; }
last^=1;
}
}
if(!ok) puts("-1");
else Print(cnt);
}
}
return 0;
}
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
#define exam(A) (M.count(A)&&M[A])
const int N=2e5+10, LEN=4e6+10;
int ans[N];
string s[N];
bool used[N], f[N];//是否相等
map<string,int> M;
void SingleRev(int w, int *cnt)
{
reverse(s[w].begin(),s[w].end());
ans[(*cnt)++]=w;
return;
}
void PreRev(int i, int *cnt, int *last)
{
memset(used,false,sizeof(used));
for(int j=0; j<*cnt; ++j) used[ans[j]]=true;
*cnt=0;
for(int j=1; j<=i; ++j) if(!used[j])
{
ans[(*cnt)++]=j;
M[s[j]]=0;
reverse(s[j].begin(),s[j].end());
M[s[j]]=1;
}
*last^=1;
return;
}
void Print(int cnt)
{
printf("%d\n", cnt);
if(cnt)
{
printf("%d", ans[0]);
for(int j=1; j<cnt; ++j) printf(" %d", ans[j]);
}
puts("");
return;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
M.erase(M.begin(),M.end());
int n; bool ok=true;
scanf("%d", &n); getchar();
for(int i=1; i<=n; ++i)
{
cin>>s[i];
f[i]=(s[i][0]!=s[i][s[i].length()-1]);//differ 1 same 0
}
int last=s[1][0], cnt=0, i;
// first segment
for(i=1; i<=n; ++i)
{
if(f[i])
{
if(last!=s[i][0]) SingleRev(i,&cnt);
if(exam(s[i])) { ok=false; break; }
M[s[i]]=1;
last^=1;
}else
{
if(s[i][0]!=last) PreRev(i-1,&cnt,&last);
i++;
break;
}
}
// latter segment
if(!ok) puts("-1");
else if(i>n)
{
if(cnt>n-cnt) PreRev(n,&cnt,&last);
Print(cnt);
}else
{
for(; i<=n; ++i)
{
if(!f[i])
{
if(last!=s[i][0]) { ok=false; break; }
if(exam(s[i]))
{
SingleRev(i,&cnt);
if(exam(s[i])) { ok=false; break; }
}
M[s[i]]=1;
}else
{
if(last!=s[i][0]) SingleRev(i,&cnt);
if(exam(s[i])) { ok=false; break; }
last^=1;
}
}
if(!ok) puts("-1");
else Print(cnt);
}
}
return 0;
}