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个节点高度为h的AVL树的个数。
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)。
注意，这里用一维枚举子树的大小，因为和式中m1与m3互不影响，保证dp[n][h]可以取到所有m1,m3的情况.
每一项都是卷积的形式，故可以用fft(快速傅立叶变换)，降低复杂度！
百度之星 初赛第一轮 1002 Sitting in Line
n个数的排列，其中一些数有特定的位置.确定其它数的位置，最大化所有相邻两数乘积的和，即输出
max{a1⋅a2+a2⋅a3+......+aN−1⋅aN}。
评论 (0)
