再次补充，不要相信cjx的话，他上午比赛时已经AC了然而交错了代码
上午
</
T1 没用哈希注意到所谓的反对称串其实就是类似回文串的东西，只是把判定改成非而已，所以就用类似回文求解的方法来收拾这题。枚举出一个反对称串的对称中心，然后从这个点开始向两边搜索,时间复杂度为O(n2)，理论上按这个数据范围只有65分，然而数据太水了,赛时拿了80分。
T3 没用哈希注意到每种编码方式只会出现一次，直接对字符串进行暴力匹配，遇到不同字符就加入到编码方式中，直到编码方式出现冲突或者字符串匹配完成。理论复杂度为O(n2),然而只有一个点是超时的，剩下的点是忘了在更新编码后将后续字符按编码来匹配。赛时得分60.（其实按那数据范围2*10^5是有7个点会超时的总共10个点）
代码如下
#include
using namespace std;
char v[30];
bool vp[30];
int a[200005];
int n,m,ans,poi;
string s,t;
int main()
{
freopen("encoding.in","r",stdin);
freopen("encoding.out","w",stdout);
cin>>n>>m;
cin>>s>>t;
for(int i=0;i<=n-m;i++)
{
for(int j=0;j<=26;j++)
{
vp[j]=0;
}
poi++;
ans++;
a[poi]=i+1;
for(int j=i,p=0;j<i+m;j++,p++)
{
if(s[j]!=t[p])
{
if(vp[int(t[p]-'a')]==1)
{
if(v[int(t[p]-'a')]!=s[j])
{
poi--;
ans--;
break;
}
}
else
if(vp[int(t[p]-'a')]==0)
{
vp[int(t[p]-'a')]=1;
v[int(t[p]-'a')]=s[j];
v[int(s[j]-'a')]=t[p];
vp[int(s[j]-'a')]=1;
}
}
}
}
cout<<ans<<endl;
for(int i=1;i<=ans;i++)
{
cout<<a[i]<<" ";
}
}
下午
T1 没用KMP看了一眼题目直接先O(n2)枚举每一个子串，在O(n)枚举AA与BB的分界点，然后再O(n)进行比对和判断，所以，总时间复杂度是O(n4),更离谱的是这个时间复杂度拿了90分，剩下的见代码吧
#include
using namespace std;
int n,ts,m,v;
long long int ans;
string a;
char ss;
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
cin>>n;
for(int ii=1;ii>a;
ans=0;
ts=1;
m=a.size();
ss=a[0];
for(int i=1;i<m;i++)
{
if(ss!=a[i])
{
ts=0;
break;
}
}
// cout<<m<<endl;
for(int i=0;i<=m-4;i++)
{
for(int j=i+3;j<m;j+=2)
{
// cout<<"d"<<endl;
if(ts==1)
{
ans+=(j-i-1)/2;
}
else
{
for(int k=i+2;k<j;k+=2)
{
v=1;
// cout<<i+1<<" "<<j+1<<" "<<k+1<<endl;
for(int l=i,nb=0;l<(k+i)/2;l++,nb++)
{
if(a[l]!=a[(k+i)/2+nb])
{
v=0;
// cout<<l+1<<" --1-- "<<(k+i)/2+l+1<<endl;
break;
}
}
for(int l=k,nb=1;l<=(k+j-1)/2;l++,nb++)
{
if(a[l]!=a[(k+j-1)/2+nb])
{
v=0;
// cout<<l+1<<" --2-- "<<(k+j-1)/2+nb+1<<endl;
break;
}
}
if(v==1)
{
ans++;
// cout<<i+1<<" "<<j+1<<" "<<k+1<<endl;
// cout<<" ans++ "<<endl;
}
}
}
}
}
cout<<ans<<endl;
}
}
T2 没用KMP没什么好说的，DFS拿下30分走人，直接上代码
#include
using namespace std;
int n,m,a[30],k,b[1005],ans,p,v;
string c;
int dfs(int e)
{
// cout<<"e= "<<e<<endl;
if(e==n+1)
{
// for(int i=1;i<=n;i++)
// {
// cout<<b[i];
// }
// cout<<endl;
// cout<<"D"<<endl;
ans++;
// ans%=k;
v=0;
for(int i=1;i<=n-m+1;i++)
{
// cout<<i<<endl;
p=1;
for(int j=1,nb=0;j<=m;j++,nb++)
{
// cout<<j<<endl;
if(a[j]!=b[i+j-1])
{
if(b[1]==1&&b[2]==1&&b[3]==1)
{
;
}
// cout<<a[j]<<" "<<
p=0;
break;
}
}
if(p==1&&v==0)
{
// cout<<i<<" "<<j<<" "<<i+j-1<n>>m>>k;
cin>>c;
for(int i=0;i<m;i++)
{
a[i+1]=int(c[i]-'0');
// cout<<a[i+1]<<endl;
}
dfs(1);
cout<<ans%k<<endl;
}
写完博客，开始改题