A

略

B

略

C

略

D(构造分形)

题意：

　　给出一个由n个点的组成的树，你可以加一些点形成一个更大的树。对于新树中的两个点i和j，如果以i为根的树与以j为根的树是同构的那么i和j颜色可以相同。问最少需要多少颜色，在颜色最少的情况下，最少需要多少叶子节点。

　　n<=100

分析：

　　根据给的样例画一画，就明白是需要把树补成一个“分形”的结构，那么离分形中心距离一样的点就是同颜色的，于是我们希望最小化离中心最大的点的距离

　　也就是说最少颜色一定是树的直径的一半，于是我们自然想到把直径拉出来，取中间的那个点为分形中心

　　但良心的样例告诉我们，这样取不一定会让叶子节点的个数最少，你可以把一条边作为分形中心，分成左右两个分形，而且这个边可能也不在直径上

　　考虑到n<=100，我们不妨枚举哪个点作为中心，枚举哪个边作为中心，去取一个最小值即可

　　时间复杂度O(n^2)

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=;

 vector<int> g[maxn+];

 int n,s,t;

 int fa[maxn+],dep[maxn+],a[maxn+];

 long long ans;

 void dfs(int k,int last)

 {

     dep[k]=dep[last]+;

     fa[k]=last;

     int d=;

     for(auto u:g[k])

     {

         if(u==last) continue;

         dfs(u,k);

         ++d;

     }

     a[dep[k]]=max(a[dep[k]],d);

 }

 int main()

 {

     scanf("%d",&n);

     for(int i=;i<n;++i)

     {

         int u,v;

         scanf("%d%d",&u,&v);

         g[u].push_back(v),g[v].push_back(u);

     }

     dfs(,);

     for(int i=;i<=n;++i)

         if(dep[i]>dep[s]) s=i;

     dfs(s,);

     for(int i=;i<=n;++i)

         if(dep[i]>dep[t]) t=i;

     //printf("%d %d\n",s,t);

     int ans1=(dep[t]+)/;

     printf("%d ",ans1);

     for(int i=;i<=n;++i)

     {

         memset(a,,sizeof(a));

         a[]=;

         dfs(i,);

         long long res=;

         for(int j=;j<=n;++j)

             if(a[j]==) break;else res=res*a[j];

         if(a[ans1]!=) continue;

         if(ans==||res<ans) ans=res;

     }

     for(int u=;u<=n;++u)

         for(auto v:g[u])

         {

             memset(a,,sizeof(a));

             a[]=;

             dep[u]=;

             dfs(v,u);

             dep[v]=;

             dfs(u,v);

             long long res=;

             for(int j=;j<=n;++j)

                 if(a[j]==) break;else res=res*a[j];

             if(a[ans1]!=) continue;

             if(ans==||res<ans) ans=res;

         }

     printf("%lld\n",ans);

     return ;

 }

E(计数)

题意：

　　给定一个n和k，我们构造一组A0,A1,...,An

　　其中Ai是一个有i个元素的数列，每个数的范围是1~k

　　若Ai-1是Ai的子序列且字典序满足Ai>Ai-1，则我们称这一组A是合法的，问一共有多少种合法的A，答案对M取模。

　　n,k<=300,m<=1e9

分析：

　　我们考虑第i次操作，加入一个编号为i的点，这个点的权值就是Ai中多加的数字x，把其放到Ai-1中哪个位置的前面，就把这个点的父亲连到那个点

　　然后我们考虑字典序限制，x必须放到一个比x小的数字前面（如果放到相同的前面，实际上等价于放在连续段的最后一个）

　　于是就变成了一个有n+1个节点的树，然后每个点的权值都比孩子的权值大，每个点的编号都比孩子的编号小，一个树和一个A是一一对应的，于是我们对这个树计数就行了

　　dp[i][j]表示有i个点的树，root的权值是j情况下的方案数，那怎么转移呢？

　　我们去枚举1号点所在的子树的节点个数和1号点的权值去转移

　　这样是四次方的，但写出式子发现可以前缀和优化，于是就是O(n^3)

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=;

 typedef long long ll;

 int n,m,mod;

 ll dp[maxn+][maxn+],sum[maxn+][maxn+],c[maxn+][maxn+];

 void work(ll &a,ll b)

 {

     a=(a+b)%mod;

     if(a<) a+=mod;

 }

 int main()

 {

     scanf("%d%d%d",&n,&m,&mod);

     c[][]=;

     for(int i=;i<=n+;++i)

     {

         c[i][]=;

         for(int j=;j<=i;++j) c[i][j]=(c[i-][j]+c[i-][j-])%mod;

     }

     for(int i=;i<=m;++i) dp[][i]=;

     sum[][]=;

     for(int i=;i<=m;++i) sum[][i]=(sum[][i-]+dp[][i])%mod;

     for(int i=;i<=n+;++i)

     {

         for(int j=;j<=m;++j)

             for(int k=;k<i;++k)

                 work(dp[i][j],dp[i-k][j]*c[i-][k-]%mod*(sum[k][m]-sum[k][j])%mod);

         sum[i][]=dp[i][];

         for(int j=;j<=m;++j) sum[i][j]=(sum[i][j-]+dp[i][j])%mod;

     }

     printf("%lld\n",dp[n+][]);

     return ;

 }

F(DAG图dp)

题意：

　　给定一些01字符串，现在你找一个01字符串s，如果给定的这些01字符串里至少有m个字符串包含s作为子序列，那么s就是合法的。对于所有合法的s，找到长度最长的（在这基础上找字典序最小的）

　　01字符串的给定方式见题面

分析：

　　如果我们可以求出长度<=n的所有字符串被多少个给定字符串包含作为子序列，那么这个问题就能轻松解决了

　　我们如何描述一个字符串的所有子序列呢？

　　我们用s[t]表示已经固定了s，然后取t中的子序列

　　那么s[t]可以转移到s0[t'] s1[t']

　　并且这个dag有一个性质，就是任意两个点的路径个数<=1

　　所以就可以在这个dag图上进行dp

　　时间复杂度O(2^n*n^2)

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=;

 int dp[][+][<<maxn],nx[+][<<maxn][];

 char s[<<maxn];

 int n,m,ans,len;

 int main()

 {

     scanf("%d%d",&n,&m);

     int now=;

     for(int i=;i<=n;++i)

     {

         scanf("%s",s);

         for(int j=;j<(<<i);++j)

             if(s[j]=='') dp[now][i][j]=;

     }

     for(int i=;i<=n;++i)

         for(int j=;j<(<<i);++j)

         {

             nx[i][j][]=nx[i][j][]=-;

             for(int k=i-;k>=;--k)

                 if((j>>k)&)

                 {

                     nx[i][j][]=k;

                     break;

                 }

             for(int k=i-;k>=;--k)

                 if(((j>>k)&)==)

                 {

                     nx[i][j][]=k;

                     break;

                 }

         }

     for(int i=;i<n;++i)

     {

         for(int j=n-i;j>=;--j)

             for(int s=(<<(i+j))-;s>=;--s)

             {

                 if(!dp[now][i+j][s]) continue;

                 int t=nx[j][s&((<<j)-)][];

                 if(t!=-)

                     dp[now^][i+t+][(s>>j<<t+)|(s&(<<(t+))-)]+=dp[now][i+j][s];

                 t=nx[j][s&((<<j)-)][];

                 if(t!=-)

                     dp[now^][i+t+][(s>>j<<t+)|(s&(<<(t+))-)]+=dp[now][i+j][s];

             }

         memset(dp[now],,sizeof(dp[now]));

         now^=;

         for(int j=;i++j<=n;++j)

             for(int s=;s<<<(i++j);++s)

                 dp[now][i+][s>>j]+=dp[now][i++j][s];

         for(int s=(<<(i+))-;s>=;--s)

         {

             if(dp[now][i+][s]>=m) len=i+,ans=s;

         }

     }

     for(int i=len-;i>=;--i)

         if(ans&(<<i)) printf("");else printf("");

     return ;

 }

巴特西

Atcoder Grand Contest 024

A

B

C

D(构造分形)

E(计数)

F(DAG图dp)

最新文章

热门文章