5
26
2015
0

最近做的一些题目

比较懒不想分开写了,就都写到这里面吧QAQ

BZOJ1194: [HNOI2006]潘多拉的盒子

我们首先考虑如何判断一个自动机$A$是否是另一个自动机$t$的升级版。

我们考虑一个二元组$(x,y)$表示走了某个字符串后到达了$A$自动机的$x$号节点,到了$B$自动机的$y$号节点。

那么如果此时$x$是非输出节点而$y$是输出节点,那么说明不成立。否则我们继续遍历他们的后继$(go[x][0],go[y][0])$和$(go[x][1],go[y][1])$。

因为一个二元组是否满足关系只与$(x,y)$有关,与走过怎样的字符串到达该节点无关。所以我们只需要遍历$O(n^2)$个二元组判断即可。

然后我们建出有向图,发现可能会有环。这样求最长链并不好搞,但是因为如果有环的话,那么说明这个环内的所有自动机能产生的串都是一样的。

所以我们可以用tarjan算法把环缩起来作为一个大小为s[x]的点,然后在这张DAG上求最长链。当然也可以用并查集直接将原图缩成DAG。

然后套用经典的DAG上dp的方法求出最长链即可。

 

【弱省胡策】Round #0 Luv Letter  

 

首先知道,如果我们有两个自动机$A$和$B$,那么要找出$A$自动机能产生而$B$自动机不能产生的串的个数/最小值这个是可以$O(n^2)$求出来的。

还是利用上面的二元组的方法。之所以能用一个二元组来代表一个状态,因为这之后的转移都是一样的。而与如何到达这个二元组无关。

不妨认为$ans[x][y]$表示到达$(x,y)$的答案,那么当y=0的时候$ans[x][y]=f[x]$,其中$f[x]$表示从x点开始能产生的所有串的数量。

否则$ans[x][y]=\sum_{i=0}^{25}ans[go[x][i]][go[y][i]]$

而考虑如何求$f[x]$。

对于SAM来说,这是个DAG,直接按拓扑序DP即可。

对于子序列组成的自动机。其实很简单,我们每个点x连go[x][i]到距离x最近的i字符的位置。

这样也是个DAG。也可以递推求解。

所以我们把A,B的子串自动机和子序列自动机分别建出来然后dfs即可。复杂度都是$O(n^2)$的

代码大概长这样:

char s[maxn];
struct SAM
{
	int last,cnt,go[maxn][26],fa[maxn],l[maxn],f[maxn],c[maxn],sa[maxn];
	SAM(){last=cnt=1;}
	inline void add(int x)
	{
		int p=last,np=last=++cnt;l[np]=l[p]+1;
		for(;p&&!go[p][x];p=fa[p])go[p][x]=np;
		if(!p)fa[np]=1;
		else
		{
			int q=go[p][x];
			if(l[q]==l[p]+1)fa[np]=q;
			else
			{
				int nq=++cnt;l[nq]=l[p]+1;
				memcpy(go[nq],go[q],sizeof(go[q]));
				fa[nq]=fa[q];
				fa[q]=fa[np]=nq;
				for(;p&&go[p][x]==q;p=fa[p])go[p][x]=nq;
			}
		}
	}
	void build()
	{
		int n=strlen(s);
		for0(i,n-1)add(s[i]-'a');
		for1(i,cnt)c[l[i]]++;
		for1(i,n)c[i]+=c[i-1];
		for1(i,cnt)sa[c[l[i]]--]=i;
		for1(i,cnt)f[i]=1;
		for3(i,cnt,1)for0(j,25)(f[sa[i]]+=f[go[sa[i]][j]])%=mod;
	}
}A,C;
bool v[maxn][maxn];
int ans[maxn][maxn];
struct QAQ
{
	int v[26],go[maxn][26],f[maxn];
	inline void build()
	{
		int n=strlen(s);
		for3(i,n+1,1)
		{
			for0(j,25)go[i][j]=v[j];
			if(i==1)continue;
			v[s[i-2]-'a']=i;
		}
		for1(i,n+1)f[i]=1;
		for3(i,n+1,1)for0(j,25)(f[i]+=f[go[i][j]])%=mod;
	}
}B,D;
inline int dfs1(int x,int y)
{
	if(x&&!y)return A.f[x];
	if(v[x][y])return ans[x][y];
	v[x][y]=1;ans[x][y]=0;
	for0(i,25)(ans[x][y]+=dfs1(A.go[x][i],C.go[y][i]))%=mod;
	return ans[x][y];
}
inline int dfs2(int x,int y)
{
	if(x&&!y)return A.f[x];
	if(v[x][y])return ans[x][y];
	v[x][y]=1;ans[x][y]=0;
	for0(i,25)(ans[x][y]+=dfs2(A.go[x][i],D.go[y][i]))%=mod;
	return ans[x][y];
}
inline int dfs3(int x,int y)
{
	if(x&&!y)return B.f[x];
	if(v[x][y])return ans[x][y];
	v[x][y]=1;ans[x][y]=0;
	for0(i,25)(ans[x][y]+=dfs3(B.go[x][i],C.go[y][i]))%=mod;
	return ans[x][y];
}
inline int dfs4(int x,int y)
{
	if(x&&!y)return B.f[x];
	if(v[x][y])return ans[x][y];
	v[x][y]=1;ans[x][y]=0;
	for0(i,25)(ans[x][y]+=dfs4(B.go[x][i],D.go[y][i]))%=mod;
	return ans[x][y];
}
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
    scanf("%s",s);A.build();B.build();
    scanf("%s",s);C.build();D.build();
    memset(v,0,sizeof(v));
    printf("%d\n",dfs1(1,1));
    memset(v,0,sizeof(v));
    printf("%d\n",dfs2(1,1));
    memset(v,0,sizeof(v));
    printf("%d\n",dfs3(1,1));
    memset(v,0,sizeof(v));
    printf("%d\n",dfs4(1,1));
    return 0;
}

 

BZOJ4032: [HEOI2015]最短不公共子串

这题其实和上一题差不多,我们令$ans[x][y]$表示从初始点到达二元组$(x,y)$走的字符串的最短长度。

那么我们就可以按拓扑序bfs+DP了。

值得一提的是,这四个子问题也都是可以直接用DP解决的。

而仔细一想又会发现这两种做法其实是一样的。

可以参见:jiry_2  

 

A1295. necklace

先考虑一下比较容易想到的dp。令$dp[i][j][k]$表示前i个字符,最长同色长度为j,然后最后一个字符是k。那么这个概率可以通过枚举k字符的长度来得到。

具体来说有$$\begin{aligned}dp[i][j][k]=&\sum_{l=i-j}^{i-1}\sum_{p!=k}dp[l][j][p]*g[l+1][i][k]\\&+\sum_{p!=k}dp[i-j][j-1][p]*g[i-j+1][i][k]\end{aligned}$$

其中g[i][j][k]表示i-j全为k颜色的概率,这个显然可以$O(n^2m)$预处理出来。

然后直接这样做是$O(n^3m^2)$的,可以拿到$60$分。

如果状态表达式还是这样的话,并不容易优化。

我们考虑用$dp[i][j][k]$表示前i个字符,最长同色长度<=j,最后一个字符是k。那么可以去掉后面那个单独的一项。这样状态转移方程是这样的

$$dp[i][j][k]=\sum_{l=i-j}^{i-1}\sum_{p!=k}dp[l][j][p]*g[l+1][i][k]$$

还有不同的地方就是初值的变化。

然后继续优化,因为状态数是$O(n^2m)$的。所以内层不支持我们枚举$l$,顶多枚举一个$p$。

考虑将l这一维搞成前缀和,但与之带来的问题就是每个dp值乘的东西是不一样的。

但是我们可以搞搞搞!我们让它乘的东西一样。也就是说我们直接维护

$$f[i][j][k]=\sum_{l=0}^{i}dp[l][j][k]*g[l+1][i][k]$$

这样要得出一个前缀dp值的贡献就直接乘以一个相同的数就好了。也就是把不一样的补齐到一块儿。

复杂度$O(n^2m^2)$,亲测可过。。。

代码大概长这样:

int n,m;
double p[maxn][maxm],f[maxn][maxn][maxm],g[maxn][maxn][maxm];
int main()
{
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
    n=read();m=read();
    for1(i,n)for1(j,m)scanf("%lf",&p[i][j]);
    for1(k,m)for1(i,n)
    {
    	g[i][i][k]=p[i][k];
    	for2(j,i+1,n)g[i][j][k]=g[i][j-1][k]*p[j][k];
    }
    for1(i,n)f[0][i][0]=1.0;
    for1(i,n)for1(j,n)for0(k,m)
    {
    	for0(l,m)if(l!=k)f[i][j][k]+=f[i-1][j][l]*g[i][i][k]-(i-j-1>=0?f[i-j-1][j][l]*g[i-j][i][k]:0);
        f[i][j][k]+=f[i-1][j][k]*g[i][i][k];
    }
    double ans=0.0;
    for1(i,n)for1(j,m)ans+=(f[n][i][j]-f[n][i-1][j])*i;
    printf("%.6f\n",ans);
    return 0;
}

UPD:这题还有一种复杂度更低以及思考难度更低的做法。

     我们令$$s[i][j]=\sum_{k=1}^{m}dp[i][j][k]$$

     我们不再限制上一个的结尾与该结尾颜色不同,我们用全部的概率减去长度一定超过j的概率就好了。

     那么$$dp[i][j][k]=s[i-1][j]*g[i][i][k]\\-(s[i-j-1][j]-dp[i-j-1][j][k])*g[i-j][i][k]$$

     我们来看看这个公式是怎么得到的。

     首先如果令$dp[i][j][k]=s[i-1][j]*g[i][i][k]$$的话出现的不合法的情况只有可能是产生了连续的j+1个k颜色的。

     而且位置是从i-j到i。

     这样我们需要把这个概率减掉。这个概率是就是i-j-1位置不是k的最长同色<=j的概率*g[i-j][i][k]

     这样我们就得到了一个复杂度为$O(n^2m)$的优秀算法。

 

百度之星测试赛C

n个点的带权树,要求从n个点中选出k个点,使得这k个点两两之间的距离最小。n<=2000 k<=50

其实是个傻逼题。

把状态$dp[i][j]$的含义设为在i子树中选择j个点,并且这j个点两两之间的距离+这j个点到i的距离之和最小是多少。

然后就直接树形背包辣

 

Category: 杂题 | Tags: | Read Count: 675

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com