您的位置: 首页  >  文章  >  C++ [poj 1699] Best Sequence : DFS+字符串处理+减枝

C++ [poj 1699] Best Sequence : DFS+字符串处理+减枝

分类: 文章 • 2023-11-19 20:43:10

最近在做 关于 搜索 的练习。AC了这道题 就来 写题解了。
C++ [poj 1699] Best Sequence : DFS+字符串处理+减枝
首先，我们可以 用一个dis的 二维数组 来储存 每一对 字符串 中首尾相同 的 字符串 的个数。
（对于测试样例，dis[3][2]=2,而dis[2][3]=0。）
(字符串的 预处理 这里 我搞了 一段时间，建议 读者也去 实践一下）。

处理出来 dis数组后 剩下的 就很好办了，可以 纯枚举深搜。

以每一个 字符串 为起点，将它尝试 与 每个 还没有 被vis标记过的 字符串 相连。step用来 记录 总步数。

这里 有一个 小 减枝。设 我们 目前 已经求到的 最优解 为 ans。如果 当前 的 step已经 大于了ans，则可以直接return。

具体实现见代码。

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

#define N 20
#define inf 0x7f7f7f7f

string a[N];
int T,ans=inf,n,dis[N][N],vis[N];

int _oper(int x,int y) {
	int sum=0,len1=a[x].length(),len2=a[y].length(),len=min(len1,len2);
	for(int l=0;l<len;l++) {
		int flag=0;
		for(int i=0;i<=l;i++)
			if(a[x][len1-i-1]!=a[y][l-i])  {
				flag=1;
				break;
			}
		if(!flag) sum=l+1;
	}
	return sum;			
}

void dfs(int step,int now,int k) {
	if(k==n) {
		ans=min(ans,step);
		return ;
	}
	if(step>ans) return ;
	for(int i=1;i<=n;i++) {
		if(vis[i]) continue;
		vis[i]=1;
		dfs(step+a[i].length()-dis[now][i],i,k+1);
		vis[i]=0;
	}
}

int main() {
	cin>>T;
	while(T--) {
		ans=inf;
		memset(dis,0,sizeof(dis));
		cin>>n;
		for(int i=1;i<=n;i++)
			cin>>a[i];
		for(int i=1;i<=n;i++)	
			for(int j=1;j<=n;j++) {
				if(i==j) continue;
				dis[i][j]=_oper(i,j);
			}
		for(int i=1;i<=n;i++) {
			memset(vis,0,sizeof(vis));
			vis[i]=1;
			dfs(a[i].length(),i,1);
		}
		cout<<ans<<endl;
	}
	
}

附：各种数论模板：

卡常必备！快速读入

int read() {
    int s=0,f=1;char a=getchar();
    while(a<'0' || a>'9') { if(a=='-') f=-1; a=getchar(); }
    while(a>='0' && a<='9') { s=s*10+a-'0'; a=getchar() ; }
    return f*s; 
}

数论基础：扩展欧几里得算法（解二元一次不等式及求最大公因数）

int exgcd (int a,int b ,int& x,int& y) {//函数将返回（gcd(a,b)）
    if(b==0) {
        x=1,y=0;
        return a;
    }    
    int sum=exgcd(b,a%b,y,x)
    y-=(a/b)*x;
    return sum;

求逆元（扩展欧几里得法）

int exgcd (int a,int b ,int& x,int& y) {//函数将返回（gcd(a,b)）
    if(b==0) {
        x=1,y=0;
        return a;
    }    
    int sum=exgcd(b,a%b,y,x)
    y-=(a/b)*x;
    return sum;
}


int inv(int sum,int mod) {//注意：sum与mod必须互质
    int x,y;
    exgcd(sum,mod,x,y);
    return (x%mod+mod)%mod;
}

快速幂（求逆元的费马小定理方法用得到）

LL qkpow(LL base,LL indexx)//MOD为模数，题目不要去去掉即可
{
    LL sum=1;
    while(indexx>0)
    {
        if(indexx&1)
            sum=sum*a%MOD;
        base=base*base%MOD;
        indexx>>=1;
    }
    return sum%MOD;
}

费马小定理求逆元（MOD要为素数）

LL qkpow(LL base,LL indexx,LL MOD){//改了一下
    LL sum=1;
    while(indexx>0)
    {
        if(indexx&1)
            sum=sum*base%MOD;
        base=base*base%MOD;
        indexx>>=1;
    }
    return sum%MOD;
}

LL inv(LL sum,LL mod) {
    return qkpow(sum,mod-2,mod);
}

线性递推法求逆元（适用于数据较集中，但模数要为素数）
给一下同校大佬的证明方法

    rfac[0]=rfac[1]=1;
    for(int i=2;i<=n;i++)
        rfac[i]=1ll*rfac[MOD%i]*(P-P/i)%P;
}   
//rfac[i]为i的逆元，MOD必须为质数

补充！预处理阶乘的逆元来快速求组合数：

void prepare() {
   fac[0]=fac[1]=rfac[0]=rfac[1]=1;
   for(int i=2;i<=n;i++) {
       fac[i]=1ll*fac[i]*fac[i-1]%MOD;
       rfac[i]=1ll*rfac[P%i]*(P-P/i)%P;
   }
   for(int i=2;i<=n;i++)
       rfac[i]=1ll*rfac[i]*rfac[i-1]%P;
}

int C(int n,int m) {
   return 1ll*fac[n]*rfac[m]%P*rfac[n-m]%P;
}

既然讲到了组合数，那就再多讲一点

Lucas定理模板！
Lucas定理:

int Lucas(int n,int m) {
    if(m==0 || m==n) return 1;
    return 1ll*C(n%MOD,m%MOD)*Lucas(n/MOD,m/MOD)%MOD;
}

补充一个定理，具体实现请看我的博客：

https://blog.****.net/weixin_44049566/article/details/87914975#comments

下面只是组合数的用法，重点是上半部分。

下面有请重点嘉宾：
CRTpro(扩展中国剩余定理）

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
 
#define N 100000001
#define LL long long

LL exgcd(LL a,LL b,LL &x,LL &y){
    if(b==0){
		x=1,y=0;
		return a;
	}
    LL sum=exgcd(b,a%b,y,x);
    y-=(a/b)*x;
    return sum;
}

LL T,m[N],a[N];

int main() {
    while(cin>>T) {
    	LL m1,r1,flag=0;
    	cin>>m1>>r1;
		T--;
		while(T--) {
			LL x,y,d,m2,r2,tx,sum;
			cin>>m2>>r2;
			sum=r2-r1;
			d=exgcd(m1,m2,x,y);
			if(sum%d) flag=1;
			x*=sum/d;
			tx=(x%(m2/d)+m2/d)%(m2/d);
			r1=m1*tx+r1;
			m1=m1/d*m2;
		}
		if(flag) {	cout<<-1<<endl; continue; }
		cout<<r1<<endl;
	}
}

具体原理请看我的博客，自以为讲的很详细：

https://blog.****.net/weixin_44049566/article/details/88841843

另一个重点内容：欧拉函数（顺便找出了n以内的素数）

void Euler(int n) {
	phi[1]=1;
	for(int i=2;i<=n;i++) {
		if(vis[i]==0)  {
			phi[i]=i-1;
			prime[++cnt]=i;
		}
		for(int j=1;j<=cnt && i*prime[j]<=n;j++) {
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)  {
				phi[i*prime[j]]=phi[i]*prime[j];
				break;
			}
			else phi[i*prime[j]]=phi[i]*phi[prime[j]];
		}
	}	
}

上面的适用于数据较小且集中的题，范围大用这个

int phi(int x) {
	int p=x;
	for(int i=2;i*i<=x;i++) {
		if(x%i==0) {
			p-=p/i;
			while(x%i==0)
				x/=i;
		}
	}
	if(x>1) p-=p/x;
	return p;
}

矩阵乘法

struct Matrix {
    LL n,m,c[N][N];
    Matrix() { memset(c,0,sizeof(c)); };
    void _read() {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%lld",&c[i][j]);
    }
    Matrix operator * (const Matrix& a) {
        Matrix r;
        r.n=n;r.m=a.m;
        for(int i=1;i<=r.n;i++)
            for(int j=1;j<=r.m;j++)
                for(int k=1;k<=m;k++)
                    r.c[i][j]= (r.c[i][j]+ (c[i][k] * a.c[k][j])%mod)%mod;
        return r;
    }
    void _print() {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                if(j!=1) cout<<" ";
                cout<<c[i][j];
            }
            if(i!=n) puts("");
        }
    }
    Matrix _power(int indexx) {
        Matrix tmp,sum;tmp._pre1();sum._pre1();
        while(indexx>0) {
            if(indexx&1) sum=sum*tmp;
            tmp=tmp*tmp;
            indexx/=2;
        }
        return sum;
    }
}

相关推荐