P2377: First Accepted other than the writer after 9 years!
Gossip
模拟赛一道难过到我的题！——原题面
双倍经验：P3484。
这个双倍经验一看就是 UNowen 当年（2015）遇到的原题！
Algorithm
很明显，对于两个全等的图形
- 它们向量序列的「标准表示」相同。
- 把
G_2 的向量序列翻转（即\{\bm L_1,\bm L_2,\ldots,\bm L_n\} 变为\{-\bm L_n,-\bm L_{n-1},\ldots,-\bm L_1\} ）后，它们向量序列的「标准表示」相同。
此外，我们可以钦定
接下来，根据题意模拟即可：
- 根据字符串
S 反推出\{\bm L_n\} （即反推出\langle\bm L_1,\bm L_i\rangle ）； - 枚举
k=1,2,\ldots,n 进行修改； - 对于每个修改方案，枚举
l=1,2,\ldots,n 并比较，得到修改后的向量序列的「标准表示」（即这个修改方案的「修改结果」）； - 结合上面的结论，使用
set/map对等价的修改方案去重； - 使用
sort/priority_queue/set/map/...对「修改结果」排序后输出即可。
该算法的时间复杂度为
My Accepted Code (R176331039)
#include <bits/stdc++.h>
using namespace std;
char cv(int x)
{
return '0'+(x+600000)%6;
}
string mod(string s,int k)
{
int n=s.size()-1;
char x=cv(s[k]+1),y=cv(s[k]-1);
char xx,yy;
if(k==1) xx=s[n];
else xx=s[k-1];
if(k==n) yy=s[1];
else yy=s[k+1];
if(abs(xx-x)==3&&abs(yy-y)==3)
{
s[k]=' ';
if(k==1) s[n]=' ';
else s[k-1]=' ';
if(k==n) s[1]=' ';
else s[k+1]=' ';
}
if(abs(xx-x)==3&&abs(yy-y)!=3)
{
s[k]=y;
if(k==1) s[n]=' ';
else s[k-1]=' ';
}
if(abs(xx-x)!=3&&abs(yy-y)==3)
{
s[k]=x;
if(k==n) s[1]=' ';
else s[k+1]=' ';
}
if(abs(xx-x)!=3&&abs(yy-y)!=3)
{
s[k]=y;
string z=" ";
z[0]=x;
s.insert(k,z);
}
int p=s.size()-1;
string res="";
for(int i=0;i<=p;i++)
if(s[i]!=' ') res+=s[i];
return res;
}
bool check(string s)
{
stack<pair<char,int> > st;
st.push(make_pair('#',0));
map<int,bool> mp;
mp[0]=true;
int cur=0;
int n=s.size();
s=' '+s;
for(int i=1;i<=n-1;i++)
{
switch(s[i])
{
case '0': {cur++;break;}
case '1': {cur+=1001;break;}
case '2': {cur+=1000;break;}
case '3': {cur--;break;}
case '4': {cur-=1001;break;}
case '5': {cur-=1000;break;}
}
if(mp.count(cur)) return false;
else
{
st.push(make_pair(s[i],cur));
mp[cur]=true;
}
}
return true;
}
string diff(string s)
{
int n=s.size();
string res="";
for(int i=1;i<=n-1;i++)
switch(cv(s[i-1]-s[i]))
{
case '4': {res+='a';break;}
case '5': {res+='b';break;}
case '0': {res+='c';break;}
case '1': {res+='d';break;}
case '2': {res+='e';break;}
}
switch(cv(s[n-1]-s[0]))
{
case '4': {res+='a';break;}
case '5': {res+='b';break;}
case '0': {res+='c';break;}
case '1': {res+='d';break;}
case '2': {res+='e';break;}
}
return res;
}
string mins(string s)
{
string res=s;
int n=s.size();
for(int i=1;i<=n;i++)
{
char c=s[0];
s.erase(0,1);
s+=c;
if(s<res) res=s;
}
return res;
}
int man(string S)
{
int n=S.size();
S=' '+S;
string s=" 0";
int now=0;
for(int i=2;i<=n;i++)
{
switch(S[i-1])
{
case 'a': {now+=2;break;}
case 'b': {now++;break;}
case 'c': {break;}
case 'd': {now--;break;}
case 'e': {now-=2;break;}
}
s+=cv(now);
}
map<string,int> mp;
priority_queue<string,vector<string>,greater<string> > pq;
for(int i=1;i<=n;i++)
{
string rr=mod(s,i);
if(!check(rr)) continue;
string rr1=diff(rr);
string rr2=rr1;
reverse(rr2.begin(),rr2.end());
string res1=mins(rr1);
string res2=mins(rr2);
string res=res1;
if(res2<res1) res=res2;
if(!mp.count(res1)&&!mp.count(res2)) pq.push(res);
mp[res1]=1;
mp[res2]=1;
}
cout<<pq.size()<<endl;
while(!pq.empty())
{
cout<<pq.top()<<' ';
pq.pop();
}
cout<<endl;
cout<<endl;
return 0;
}
int main()
{
int T;
cin>>T;
while(T--)
{
string S;
cin>>S;
man(S);
}
return 0;
}Standard Code by the writer (R224712)
//DeathQuake
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
const int d[6][2]={ {0,-2},{-1,-1},{-1,1},{0,2},{1,1},{1,-1} };
int a[99],b[99],c[99],e[99],f[9999][99],p[99][2];
char st[99];
int TEST;
bool cmp(int a[],int b[])
{
int Len=min(a[0],b[0]),k;
for (k=1;k<=Len;++k)
if (a[k]<b[k]) return 0; else if (a[k]>b[k]) return 1;
if (a[0]>b[0]) return 1; else return 0;
}
bool check(int a[])
{
p[0][0]=p[0][1]=0;
for (int i=1,dire=3;i<=a[0];++i)
{
dire=(dire+a[i]+3)%6;
p[i][0]=p[i-1][0]+d[dire][0];
p[i][1]=p[i-1][1]+d[dire][1];
}
if (p[a[0]][0] || p[a[0]][1]) return 0;
for (int i=1;i<a[0];++i)
for (int j=0;j<i;++j)
if (p[i][0]==p[j][0] && p[i][1]==p[j][1]) return 0;
return 1;
}
int Min_Representation(int a[])
{
int i=1,j=2,k=0,Len=a[0];
for (;k<Len;)
if (a[(i+k-1)%Len+1]==a[(j+k-1)%Len+1]) ++k; else
{
if (a[(i+k-1)%Len+1]>a[(j+k-1)%Len+1]) i+=k+1; else j+=k+1;
if (i==j) ++j;
k=0;
}
return ((i-1)%Len<(j-1)%Len?(i-1)%Len+1:(j-1)%Len+1);
}
void Represent(int a[])
{
int Loca=Min_Representation(a);
for (int i=1;i<=a[0];++i) c[i]=a[(Loca+i-2)%a[0]+1];
for (int i=1;i<=a[0];++i) a[i]=c[i];
}
void AddAns(int a[])
{
for (int i=1;i<=a[0];++i) e[a[0]+1-i]=a[i]; e[0]=a[0];
Represent(a);
Represent(e);
if (cmp(a,e))
{
a[0]=e[0];
for (int i=1;i<=a[0];++i) a[i]=e[i];
}
for (int i=1;i<=f[0][0];++i)
{
if (f[i][0]!=a[0]) continue;
bool flag=1;
for (int j=1;j<=a[0] && flag;++j) if (f[i][j]!=a[j]) flag=0;
if (flag) return;
}
++f[0][0];
for (int i=0;i<=a[0];++i) f[f[0][0]][i]=a[i];
}
void Work(int a[])
{
int Len=a[0];
for (int i=1;i<=Len;++i) if (a[i]>1 && a[i%Len+1]>1)
{
b[0]=Len+1;
for (int j=1;j<i;++j) b[j]=a[j];
b[i]=a[(i+Len-1)%Len+1]-1; b[i%(Len+1)+1]=5; b[(i+1)%(Len+1)+1]=a[i%Len+1]-1;
for (int j=i+2;j<=Len;++j) b[j%(Len+1)+1]=a[j];
if (!check(b)) continue;
AddAns(b);
}
for (int i=1;i<=Len;++i) if (a[i]>1 && a[i%Len+1]==1 && a[(i+1)%Len+1]>1)
{
b[0]=Len-1;
for (int j=1;j<i;++j) b[(j-1)%(Len-1)+1]=a[j];
b[(i-1)%(Len-1)+1]=a[i]-1; b[i%(Len-1)+1]=a[(i+1)%Len+1]-1;
for (int j=i+3;j<=Len;++j) b[(j+Len-3)%(Len-1)+1]=a[j];
if (!check(b)) continue;
AddAns(b);
}
}
void Sort()
{
for (int i=1;i<=f[0][0];++i)
for (int j=i+1;j<=f[0][0];++j)
{
if (!cmp(f[i],f[j])) continue;
int Len=max(f[i][0],f[j][0]),Tmp;
for (int k=0;k<=Len;++k) swap(f[i][k],f[j][k]);
}
}
void Print()
{
printf("%d\n",f[0][0]);
for (int i=1;i<=f[0][0];++i)
{
for (int j=1;j<=f[i][0];++j) printf("%c",f[i][j]+96);
if (i==f[0][0]) puts(""); else printf(" ");
}
if (TEST) puts("");
}
int main()
{
for (scanf("%d",&TEST);TEST--;)
{
scanf("%s",st+1);
a[0]=strlen(st+1);
for (int i=1;i<=a[0];++i) a[i]=st[i]-96;
f[0][0]=0;
Work(a);
Sort();
Print();
}
return 0;
}