字串变换 (迭代加深加剪枝)

题目

题目

做法

这个做法用了38ms,比y总慢。

看到第一眼,嗯~ o( ̄▽ ̄)o,迭代加深,然后按着这个思路往下打,T飞了。

然后加了几个优化,过了????

首先还是那个迭代加深,但是我们还要加几个优化。

  1. 减少重复搜索。
    看这个规则:(a->b),还有字符串:(aa????),那么他很有可能会重复搜索,所以我们要通过指定搜索顺序的方法来减少重复,有人问,不是加个(pre)变量储存上一次时在哪个地方变化不就行了?但是有的时候使用这个规则是在某个规则用了的情况下实施的,所以就不行了(如:(a->b,b->c))。
    所以我们需要开一个(v)数组,记录时间戳,依旧是(pre),在这一层中我们就按照(pre)不断往后,同时有一个要求,就是被替换的区间当中一定要有一个(v)等于当前时间戳,具体实现看下面的代码。
  2. 可行性判断优化
    我们可以对一个字符串加上他们的ASCII码,记为这个字符串的(sum)值,然后用一个(check)判断在经过若干次规则后能不能等于(ed)(sum)值。

未用到的优化:

  1. Hash(字符串匹配)加前缀和优化((v)数组部分判断区间是否有相等的时间戳),但因为常数较大,且(check)用时更长,故不加。
  2. 在check函数中,加上长度这个变量,但是因为懒得打,所以没加。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define  N  40
using  namespace  std;
inline  int  zabs(int  x){return  x<0?-x:x;}
inline  int  mymin(int  x,int  y){return  x<y?x:y;}
inline  int  mymax(int  x,int  y){return  x>y?x:y;}
char  st[20][N],ed[N];int  v[20][N];
int  n,m;
struct  CHANGE
{
	char  a[N],b[N];
	int  alen,blen,score_cha;
}ch[10];int  top,ed_score;
inline  bool  cmp(CHANGE  x,CHANGE  y){return  x.score_cha>y.score_cha;}
inline  int  getscore(char  *a,int  len)//获取每个字符串的sum值
{
	int  ans=0;
	for(int  i=1;i<=len;i++)ans+=a[i];
	return  ans;
}
inline  bool  comp(char  *a,char  *b,int  len)
{
	for(int  i=1;i<=len;i++)
	{
		if(a[i]!=b[i])return  0;
	}
	return  1;
}
inline  bool  pd(int  *a,int  len,int  ti)
{
	for(int  i=1;i<=len;i++)
	{
		if(a[i]==ti)return  1;
	}
	return  0;
}
inline  bool  check_dfs(int  dep,int  val,int  res)
{
	if(!val)return  1;
	if(dep>top)return  0;
	if(dep>1  &&  ch[dep].score_cha==ch[dep-1].score_cha)return  check_dfs(dep+1,val,res);
	for(int  i=0;i<=res;i++)if(check_dfs(dep+1,val+ch[dep].score_cha*i,res-i)==1)return  1;
	return  0;
}
inline  bool  check(int  val,int  cnt/*剩余步数*/){return  check_dfs(1,val,cnt);}
int  limit;
bool  dfs(int  dep,int  ti/*时间戳*/,int  pre,bool  bk)
{
	if(strlen(ed+1)==strlen(st[dep]+1)  &&  comp(ed,st[dep],strlen(ed+1)))return  1;
	if(bk/*判断这个字符串是不是跑过了*/  &&  !check(getscore(st[dep],strlen(st[dep]+1))-ed_score,limit-dep))return  0;
	
	int  now=strlen(st[dep]+1);
	for(int  i=1;i<=top;i++)
	{
		int  ed=now-ch[i].alen+1;
		for(int  j=pre;j<=ed;j++)
		{
			if(comp(st[dep]+j-1,ch[i].a,ch[i].alen)==1  &&  pd(v[dep]+j-1,ch[i].alen,ti)==1)
			{
				memset(st[dep+1],0,sizeof(st[dep+1]));
				for(int  t=1;t<j;t++)st[dep+1][t]=st[dep][t];
				for(int  t=1;t<=ch[i].blen;t++)st[dep+1][j-1+t]=ch[i].b[t];
				for(int  t=j+ch[i].alen;t<=now;t++)st[dep+1][t-ch[i].alen+ch[i].blen]=st[dep][t];
				
				memset(v[dep+1],0,sizeof(v[dep+1]));
				for(int  t=1;t<j;t++)v[dep+1][t]=v[dep][t];
				for(int  t=1;t<=ch[i].blen;t++)v[dep+1][j-1+t]=ti+1;
				for(int  t=j+ch[i].alen;t<=now;t++)v[dep+1][t-ch[i].alen+ch[i].blen]=v[dep][t];
				
				if(dfs(dep+1,ti,j+ch[i].blen,1)==1)return  1;
			}
		}
	}
	//我们把时间戳加加
	if(pre!=1)return  dfs(dep,ti+1,1,0);
	return  0;
}

int  main()
{
//	freopen("1.in","r",stdin);
	scanf("%s%s",st[0]+1,ed+1);ed_score=getscore(ed,strlen(ed+1));
	while(scanf("%s%s",ch[top+1].a+1,ch[top+1].b+1)!=EOF)
	{
		top++,ch[top].alen=strlen(ch[top].a+1),ch[top].blen=strlen(ch[top].b+1);
		ch[top].score_cha=getscore(ch[top].b,ch[top].blen)-getscore(ch[top].a,ch[top].alen);
	}
	sort(ch+1,ch+top+1,cmp);//排序只是为了方便check_dfs中的ch[dep].score_cha==ch[dep-1].score_cha判断
	for(int  i=1;i<=10;i++)
	{
		limit=i;
		if(dfs(0,0,1,1)==1)
		{
			printf("%d
",i);
			return  0;
		}
	}
	printf("NO ANSWER!
");
	return  0;
}

那么有人会问:(check)_(dfs)这个函数会不会特别慢呢?

其实不会,我们讨论函数状态((i,j)),表示第(i)层,并且位于第(j)个规则,要么(j++),要么(i++),所以时间复杂度:(C_{16}^6=8008)

其实还是很大

但事实上,你可以选择在(dep)大一点的时候执行(check)函数,例如,如果(cnt>=1)再执行,就会变成:(C_{15}^6=5005),合理选择,反正数据弱

当然,还有可以优化的地方,看这个:

inline  int  getscore(char  *a,int  len)//获取每个字符串的sum值
{
	int  ans=0;
	for(int  i=1;i<=len;i++)ans+=a[i];
	return  ans;
}

当你把(a[i])换成(a[i]-'a'+1)时会在最后一个点光荣去世,T到爆炸,为什么,因为:(1+1=2)啊,也就是说("aa"="b"),啊这。。。。

再看看原来:(98-97=1),在不相同的长度下,在不同的长短下,基本上是不会相同的,也就是隐含了长度信息。(但实际上这道题目其实不止小写字母,所以他用一些神奇的符号,也是可以让我们的(sum)不再包含位置信息的,或者专门卡差值也是可以的,但是我们只要给每一个位置加上一个较大的数字就可以了。)

继续深入的思考,那么在相同的长度下呢?

("ad=bc")?不难发现,这个我们是可以解决的,怎么解决?我们只要把(a[i])换成(a[i]*a[i])即可,当然这样子干说不定会出一些其他问题(时间问题,不是答案问题),比如原本("at"≠"bd"),但是现在等于了(只是单纯的举个例子,现实中不一定相等),这样子搞就想Hash一样,让出题人更难卡,但是减慢了随机数据的速度。

那有没有究极的优化方法呢?

有,前提是要加上长度变量判断,我们为什么会怕("ad"="bc"),还不是因为每一个字母的区分度是在是太小了,所以我们要是用一个更有区分度的方法就好了,例如上文的(a[i]^2),当然,我们直接弄成(\%)意义下的(2^{a[i]})次幂,这样区分度绝对很高。这不就是Hash吗。

但实际上,不管怎么优化,都优化不了一个软肋,就是:("ab"="ba"),他是我们这个数值判断最大的弊端,也是很难被改动的,因为这就是这个优化根本上存在的问题,但是速度已经够快了,不管他了。

但是由于是玄学的判断,实际效果好不好我是真的不知道,反正不加也能A

【推广】 免费学中医,健康全家人
原文地址:https://www.cnblogs.com/zhangjianjunab/p/13762363.html