题意

分析

这个数据范围容易使人想到折半搜索。

我们将字符串分为前后两部分。如果前半部分中搜得的前缀串为{S1, S2}，那么后半部分中搜得的后缀串必须为{rev(S2), rev(S1)}，且为有序对。对于两侧分别枚举每个字符的归属情况，hash后用map计数即可。

代码

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<ctime>

#include<iostream>

#include<string>

#include<vector>

#include<list>

#include<deque>

#include<stack>

#include<queue>

#include<map>

#include<set>

#include<bitset>

#include<algorithm>

#include<complex>

#pragma GCC optimize ("O0")

using namespace std;

template<class T> inline T read(T&x)

{

    T data=0;

	int w=1;

    char ch=getchar();

    while(!isdigit(ch))

    {

		if(ch=='-')

			w=-1;

		ch=getchar();

	}

    while(isdigit(ch))

        data=10*data+ch-'0',ch=getchar();

    return x=data*w;

}

typedef long long ll;

const int INF=0x7fffffff;

int n;

string S;

string S1,S2;

map<string,ll>M;

int main()

{

  freopen("string.in","r",stdin);

  freopen("string.out","w",stdout);

	cin>>n>>S;

	int ms=1<<n;

	for(int s=0;s<ms;++s)

	{

		S1.clear(); // s1

		S2.clear(); // s2

		for(int i=0;i<n;++i)

		{

			if(s&(1<<i))

				S1.push_back(S[i]);

			else

				S2.push_back(S[i]);

		}

		reverse(S2.begin(),S2.end());

		++M[S1+'$'+S2]; // s1+revs2

	}

	ll ans=0;

	for(int s=0;s<ms;++s)

	{

		S1.clear(); // revs1

		S2.clear(); // revs2

		for(int i=0;i<n;++i)

		{

			if(s&(1<<i))

				S1.push_back(S[i+n]);

			else

				S2.push_back(S[i+n]);

		}

		reverse(S1.begin(),S1.end());

		ans+=M[S1+'$'+S2]; // s1+revs2

	}

	cout<<ans/2<<endl;

//  fclose(stdin);

//  fclose(stdout);

    return 0;

}

巴特西

test20180922 交错的字符串

题意

分析

代码

最新文章

热门文章