5
26
2016
0

【合集】Dp

BC#81 1002CA Loves GCD

在一个没有重复元素的集合中选取一个子集,求出子集中元素的gcd.求所有子集的gcd之和.

思路一:

有点像数位递推的感觉? 总之和01背包毛线关系都没. 
1)状态设置不一定直接表示答案,间接合并转化 
仔细理解dp过程,优化时不可随意缩行 
由于采用填表法,如果将读入与递推过程合并,无法读取到a[i+1]
由于gcd为j的集合可能由多个集合转化而来,故一定要+
 
2)预处理 O(n^2logn)-->O(n^2)
3)剪枝:单个元素的情况已处理为1 常数优化
4)空间优化:降维O(n^2)-->O(n) 
const int N=1000+10;
int n,a[N],mx,g[N][N];
LL f[N][N],ans;
int GCD(int a,int b)
{
	if(!b) return a;
	return GCD(b,a%b);
}
int main()
{
	freopen("1002.txt","r",stdin);
	int tt=read();
	F(i,1,N) F(j,1,N) g[i][j]=GCD(i,j);
	while(tt--){
		mec(f,0);mx=0;ans=0;
		n=read();
		F(i,1,n){
			a[i]=read();
			mx=max(mx,a[i]);
		}
		F(i,1,n) f[i][a[i]]=1;
		F(i,1,n) 
			F(j,1,mx) if(f[i][j]){//剪枝,否则会超时 
//				int v=GCD(a[i+1],j);
				int v=g[a[i+1]][j];
				f[i+1][v]=(f[i+1][v]+f[i][j])%MOD;
				f[i+1][j]=(f[i+1][j]+f[i][j])%MOD;
			}
		F(i,1,mx) ans=(ans%MOD+1LL*i*f[n][i]%MOD)%MOD;
		printf("%lld\n",ans);
	}
	return 0;
}

降维:

        scanf("%d",&N);
        M=0;
        For(i,1,N) scanf("%d",&A[i]);
        For(i,1,N) M=max(M,A[i]);
        For(i,0,M) F[i]=0;
        For(i,1,N) 
        {
            For(j,1,M)
            {
                if (F[j]==0) continue;
                int d=gcd(j,A[i]);
                F[d]=(F[d]+F[j]) %modd;
            }
            F[A[i]]=(F[A[i]]+1) %modd;
        }
        int ans=0;
        For(i,1,M) ans=((bll)i*F[i]+ans) %modd;
        printf("%d\n",ans);

思路二:

const int N=1000+10;
int n,a[N],mx,g[N][N];
LL f[N],ans;//当前gcd为j的集合的个数 
int GCD(int a,int b)
{
	if(!b) return a;
	return GCD(b,a%b);
}
int main()
{
//	freopen("1002.txt","r",stdin);
	int tt=read();
	F(i,1,N) F(j,1,N) g[i][j]=GCD(i,j);
	while(tt--){
		mec(f,0);mx=0;ans=0;
		n=read();
		F(i,1,n){
			a[i]=read();
			mx=max(mx,a[i]);
		}
		F(i,1,n){
//			f[a[i]]=1;
			F(j,1,mx){
				int v=g[a[i]][j];
				f[v]=(f[v]+f[j])%MOD;
				//情况二:f[j]不变 
			}
			f[a[i]]++;
		}
		F(i,1,mx) ans=(ans%MOD+1LL*i*f[i]%MOD)%MOD;
		printf("%lld\n",ans);
	}
	return 0;
}

思路三:

1)注意由f推g时的顺序
2)LL Pow(int,int) 注意要强制转化!否则会WA
为什么用位运算会WA?——无法取模啊笨蛋!
3)枚举倍数:调和级数复杂度
const int N=1000+10;
int n,a[N],mx,c[N];
LL f[N],g[N],ans;
LL Pow(int a,int x)
{
	LL res=1;
	while(x){
		if(x&1) res=(LL)res*a%MOD;
		a=(LL)a*a%MOD;
		x>>=1;
	}
	return res; 
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("1002.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	#endif
	int tt=read();
	while(tt--){
		n=read();
		mec(f,0);mec(g,0);mec(c,0);
		mx=0;ans=0;
		F(i,1,n){
			a[i]=read();
			mx=max(mx,a[i]);
			c[a[i]]++;
		}
		D(i,mx,1){
			int cnt=0;
			for(int j=i;j<=mx;j+=i) cnt+=c[j];
			f[i]=Pow(2,cnt)-1;
//			f[i]=(LL)((1<<cnt)-1);
			g[i]=f[i];
			for(int j=i*2;j<=mx;j+=i) g[i]=(g[i]-g[j]+MOD)%MOD;
			ans=(ans+1LL*i*g[i]%MOD)%MOD;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

BSG白山极客挑战赛 B AVL树的种类

给定AVL树的节点个数n,求有多少种形态的AVL树恰好有n个节点。

平衡二叉树(AVL树),是指左右子树高度差至多为1的二叉树,并且该树的左右两个子树也均为AVL树。

 

(0 < n <= 2000)结果对1000000007取余

 

经典dp

dp[n][h]表示n个节点高度为hAVL树的个数。

dp[n][h] = dp[m1][h - 1] * dp[m2][h - 1] + 2 * dp[m3][h] * dp[m4][h - 1]

其中  m1 + m2 = n

          m3 + m4 = n

注意h实际上是logn级别的(当然可以循环大一点),所以时间复杂度大概是O(n ^ 2 logn)

注意,这里用一维枚举子树的大小,因为和式中m1m3互不影响,保证dp[n][h]可以取到所有m1,m3的情况.

每一项都是卷积的形式,故可以用fft(快速傅立叶变换),降低复杂度!


百度之星 初赛第一轮 1002 Sitting in Line

n个数的排列,其中一些数有特定的位置.确定其它数的位置,最大化所有相邻两数乘积的和,即输出

max{a​1​​a​2​​+a​2​​a​3​​+......+aN1​​aN​​}

 

Category: 树套树 | Tags: | Read Count: 96

登录 *


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

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com