NOI2009管道取珠

2014年12月17日3,5920

Description

Input

第一行包含两个整数n, m，分别表示上下两个管道中球的数目。第二行为一个AB字符串，长度为n，表示上管道中从左到右球的类型。其中A表示浅色球，B表示深色球。第三行为一个AB字符串，长度为m，表示下管道中的情形。

Output

仅包含一行，即为 Sigma(Ai^2) i从1到k 除以1024523的余数。

Sample Input

2 1
AB
B

Sample Output

HINT

样例即为文中(图3)。共有两种不同的输出序列形式，序列BAB有1种产生方式，而序列BBA有2种产生方式，因此答案为5。
「大致数据规模」
约30%的数据满足 n, m ≤ 12；
约100%的数据满足n, m ≤ 500。

题解

这题怎么想的。。。

byvoid：

状态F[i₁,j₁,i₂,j₂]可以表示为取珠方法X状态为(i₁,j₁)，取珠方法Y状态为(i₂,j₂)，X,Y的输出序列相同的有序对(X,Y)的数量。设U[i]为上管道第i个珠子，L[i]为下管道第j个珠子。则状态F[i₁,j₁,i₂,j₂]可以更新的状态

由于X,Y应当同步，所以当i₁,j₁,i₂都确定以后j₂可以被表示为i₁+ j₁ – i₂，于是状态表示可以减少一维。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#define pa pair<int,int>
#define inf 1000000000
#define ll long long 
#define mod 1024523
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m;
int f[505][505][505];
char a[505],b[505];
inline void add(int &x,int y)
{
	x+=y;
	if(x>mod)x-=mod;
}
int main()
{
	n=read();m=read();
	scanf("%s",a+1);scanf("%s",b+1);
	reverse(a+1,a+n+1);
	reverse(b+1,b+m+1);
	f[0][0][0]=1;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=m;j++)
			for(int k=0;k<=n;k++)
			{
				int l=i+j-k,t=f[i][j][k];
				if(l<0||l>m)continue;
				if(a[i+1]==a[k+1])add(f[i+1][j][k+1],t);
				if(a[i+1]==b[l+1])add(f[i+1][j][k],t);
				if(b[j+1]==a[k+1])add(f[i][j+1][k+1],t);
				if(b[j+1]==b[l+1])add(f[i][j+1][k],t);
			}
	printf("%d",f[n][m][n]);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#define pa pair<int,int>

#define inf 1000000000

#define ll long long

#define mod 1024523

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m;

int f[505][505][505];

char a[505],b[505];

inline void add(int &x,int y)

{

x+=y;

if(x>mod)x-=mod;

}

int main()

{

n=read();m=read();

scanf("%s",a+1);scanf("%s",b+1);

reverse(a+1,a+n+1);

reverse(b+1,b+m+1);

f[0][0][0]=1;

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

for(int j=0;j<=m;j++)

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

{

int l=i+j-k,t=f[i][j][k];

if(l<0||l>m)continue;

if(a[i+1]==a[k+1])add(f[i+1][j][k+1],t);

if(a[i+1]==b[l+1])add(f[i+1][j][k],t);

if(b[j+1]==a[k+1])add(f[i][j+1][k+1],t);

if(b[j+1]==b[l+1])add(f[i][j+1][k],t);

}

printf("%d",f[n][m][n]);

return 0;

}

« 「BZOJ2431」[HAOI2009] 逆序对数列「BZOJ1924」[SDOI2010] 所驼门王的宝藏 »

hzwer.com _ Home | http://hzwer.com

NOI2009管道取珠

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论