[关闭]
@Asuna 2017-05-22T12:36:53.000000Z 字数 5633 阅读 667

CQUPT 训练题题解 2017/5/15

题解

Problem B:XHXJ's LIS

题意：就是现在对于每个正整数可以将其每位视为一个数形成一个串, 那么这一组数就存在一个最长上升子序列, 对于每组给出的L, R 求出在区间[L, R]中有多少个数在视作这样的一组数后最长上升子序列的长度是K。

题解：用dp[bit][num][LIS]表示当前填到了第bit位, 填了num, 最长上升子序列的状况为LIS的情况有多少种。先预处理出LIS的转移trans[LIS][0~9]=?
注意这里LIS状态压缩的含义:
* 这个数的二进制第i个1的位置表示在当前的序列中, 长度为i的上升子序列结尾的数最小是多少
* 例如0110110010就表示当前LIS以8结尾, 当前长度为1, 2, 3, 4, 5的上升子序列最小的结尾分别是1, 2, 3, 4, 8
* 而这个二进制中的1的总个数就是LIS的长度
* 于是可以预处理LIS的转移

参考代码：

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<cmath>
  5. using namespace std;
  6. int n,m,k,t,a[20],pos,cas;
  7. long long dp[20][1<<10][11],p,q;
  8. long long dfs(int pos,int x,int y,bool limit,bool lead)
  9. {
  10.     if (pos==-1) return y==0;
  11.     if (y<0) return 0;
  12.     if (limit && lead && dp[pos][x][y]!=-1)
  13.         return dp[pos][x][y];
  14.     int top=limit?9:a[pos];
  15.     int i,j;
  16.     long long ans=0;
  17.     for (i=0; i<=top; i++)
  18.     {
  19.         for ( j=i; j<=9; j++)
  20.             if(x>>j&1) break;
  21.         if (!i && !lead) ans+=dfs(pos-1,x,y,limit||i<a[pos],lead||i);
  22.         else if (j==10) ans+=dfs(pos-1,x+(1<<i),y-1,limit||i<a[pos],lead||i);
  23.         else ans+=dfs(pos-1,x-(1<<j)^(1<<i),y,limit||i<a[pos],lead||i);
  24.     }
  25.     return limit && lead?dp[pos][x][y]=ans:ans;
  26. }
  28. long long solve(long long x)
  29. {
  30.     pos=0;
  31.     while(x) 
  32.     {
  33.         a[pos++]=x%10;
  34.         x/=10;
  35.     }
  36.     return dfs(pos-1,0,k,0,0);
  37. }
  39. int main()
  40. {
  41.     memset(dp,-1,sizeof(dp));
  42.     scanf("%d",&t);
  43.     while(t--)
  44.     {
  45.         scanf("%lld%lld%d",&p,&q,&k);
  46.         printf("Case #%d: %lld\n",++cas,solve(q)-solve(p-1));
  47.     }
  48.     return 0;
  49. }

Problem C:Brackets Sequence

题意： 给出一个由(、)、[、]组成的字符串，添加最少的括号使得所有的括号匹配，输出最后得到的字符串。

题解：区间dp,dp[i][j]表示 区间 i 到j之间的匹配数，区间两端的 字符是否可以刚好匹配,若可以匹配 状态转移就多了一个 dp[i][j] = max(dp[i][k]+dp[k+1][j],dp[i+1][j-1]+1),若不能匹配就是dp[i][j] = max(dp[i][j],dp[i][k]+dp[k+1][j]);若是两端可以匹配的，而且两端匹配了导致的dp值最大那么就标记一下，a[i][j]=-1,否则 就a[i][j]=k，这样把所有区间都dp一遍，回头再用DFS寻找，若是两端匹配导致值最大的 那么就直接输出这个字符标记一下，继续往更小的区间去搜索，否则 就分开两个区间搜索 [i,k],[k+1,j]

参考代码：

  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<cstring>
  7. using namespace std;
  8. char str[510];
  9. int dp[510][510],a[510][510],pr[510];
  10. void dfs(int i ,int j)
  11. {
  12.     if (i>=j) return ;
  13.     if (a[i][j]==-1)
  14.         dfs(i+1,j);
  15.     if (a[i][j]>0)
  16.     {
  17.         pr[i]=1;
  18.         pr[a[i][j]]=1;
  19.         dfs(i+1,a[i][j]-1);
  20.         dfs(a[i][j],j);
  21.     }
  22. }
  24. int main()
  25. {
  26.     int len;
  27.     while(gets(str+1))
  28.     {
  29.         len=strlen(str+1);
  30.         memset(dp,0,sizeof(dp));
  31.         memset(a,-1,sizeof(a));
  32.         memset(pr,0,sizeof(pr));
  33.         for (int i=0; i<=len; i++)
  34.         {
  35.             dp[i][i]=1;
  36.         }
  37.         for (int i=len-1; i>=1; i--)
  38.         {
  39.             for (int j=i+1; j<=len; j++)
  40.             {
  41.                 dp[i][j]=dp[i+1][j]+1;
  42.                 a[i][j]=-1;
  43.                 if (str[i]=='(' || str[i]=='[')
  44.                 {
  45.                     for (int k=i+1; k<=j; k++)
  46.                     {
  47.                         if (str[k]==')' && str[i]=='(')
  48.                         {
  49.                             if (dp[i][j]>dp[i+1][k-1]+dp[k][j]-1)
  50.                             {
  51.                                 a[i][j]=k;
  52.                                 dp[i][j]=dp[i+1][k-1]+dp[k][j]-1;
  53.                             }
  54.                         }
  55.                         if (str[k]==']' && str[i]=='[')
  56.                         {
  57.                             if (dp[i][j]>dp[i+1][k-1]+dp[k][j]-1)
  58.                             {
  59.                                 a[i][j]=k;
  60.                                 dp[i][j]=dp[i+1][k-1]+dp[k][j]-1;
  61.                             }
  62.                         }
  63.                     }
  64.                 }
  65.             }
  66.         }
  67.         dfs(1,len);
  68.         for (int i=1; i<=len; i++)
  69.         {
  70.             if (pr[i]==1) printf("%c",str[i]);
  71.             else
  72.             {
  73.                 if (str[i]=='(' || str[i]==')')
  74.                     printf("()");
  75.                 else if (str[i]=='[' || str[i]==']')
  76.                     printf("[]");
  77.             }
  78.         }
  79.         printf("\n");
  80.     }
  81.     return 0;
  82. }

Problem E:Little Elephant and Elections

题意：规定4,7为lucky数。给一个数m，求1~m中的七个数字的排列中，满足下列条件的排列有多少个：第七个数中含有的lucky数的数量大于前六个含有的lucky数的总和。

题解：先 数位dp计算出包含n个7或4的数个有多少个，然后dfs一边找出来就行了。dp[cur][S][K]表示处理到当前为止，有S个7或者4，一共有K个7或者4的有多少个。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. using namespace std;
  5. int dig[20],len,m;
  6. long long dp[20][20][20],sum[20];
  7. long long dfs(int now,int e,int S,int K)
  8. {
  9.     if (now<0) return (S==K);
  10.     if (!e && dp[now][S][K]!=-1) return dp[now][S][K];
  11.     int top=(e?dig[now]:9); //上界
  12.     long long ans=0;
  13.     for (int i=0; i<=top; i++)
  14.     {
  15.         ans+=dfs(now-1,e && i==top,S+(i==4 || i==7),K)%1000000007;
  16.     }
  17.     if (!e) dp[now][S][K]=ans;
  18.     return ans;
  19. }
  21. long long solve(int num,int pos)
  22. {
  23.     if (pos<=0) return 1;
  24.     long long ans=0;
  25.     for (int i=0; i<=num; i++)
  26.     {
  27.         if (sum[i]<=0) continue;
  28.         sum[i]--;
  29.         ans=(ans+(1+sum[i])*solve(num-i,pos-1))%1000000007;
  30.         sum[i]++;
  31.     }
  32.     return ans;
  33. }
  34. int main()
  35. {
  36.     cin>>m;
  37.     len=0;
  38.     memset(dp,-1,sizeof(dp));
  39.     while(m)
  40.     {
  41.         dig[len++]=m%10;
  42.         m/=10;
  43.     }
  44.     for (int i=0; i<=len; i++)
  45.         sum[i]=dfs(len-1,1,0,i);
  46.     sum[0]--;  //去掉0
  47.     long long ans=0;
  48.     for (int i=1; i<=len; i++)
  49.         ans=(ans+sum[i]*solve(i-1,6))%1000000007;
  50.     cout<<ans<<endl;
  51.     return 0;
  52. }

Problem F:Mondriaan's Dream

题意：输入n和m表示一个n*m的矩形，用1*2的方块进行覆盖，不能重叠，不能越出矩形边界，问完全覆盖完整个矩形有多少种不同的方案

题解：
最上面的为第1行，最下面为第n行，从上到下按行DP，其中一行的状态我们用一个二进制表示，0表示没有被覆盖，1表示被覆盖了，最后得到一个01串，这个串变回十进制就是一个状态。
定义状态dp[i][s]，表示前i-1行已经放满，第i行的状态为s的方案数
状态转移方程为 dp[i][s]=sum{ dp[i-1][ss] } ，其中状态s与状态ss兼容
这个状态转移方程的内涵在于理解s和ss何为兼容
首先我们约定一个放置方法，就是竖着放的时候，我们暂且将其称为“上凸型摆放”
因为竖放必然占据第i-1行和第i行，我们约定这个方块是属于第i行的，也就是说它凸上去了
那么要在第i行的第j列竖放一个方块的话，第i-1行第j列必须没有方块
也就是说，第i行的放置是受到第i-1行的限制的，反过来说在第i行竖放了方块，也会影响第i-1行的状态
所以这样就可以讲解一下状态转移方程了，前i-2行已经放满了，第i-1行的状态为ss(dp[i-1][ss])
此时在第i行开始放一些方块，放的方法不定，可能横放可能竖放，但是按这个方案放完后
第i-1行刚好被填满，且第i行的状态变为了s，所以不难想到第i-1行的状态ss到第i行的状态s这个转移是唯一的
所以有 dp[i][s]=sum{ dp[i-1][ss] }
最后我们详细讨论一下s和ss在什么情况下是兼容的

  1. 第i行的第j列为1，第i-1行的第j列为1，这样的话，说明第i行的第j列一定不是竖放而是横放否则会与第i-1行的第j列冲突
    所以马上紧接着判断第i行第j+1列，如果是1，那么满足横放的规则，同时也要第i-1行第j+1列也要为1，否则的话这个格子没办法填充，
    成立后向左移动两格 不满足上述条件的，就是两个不兼容或者不合法的状态
  2. 第i行第j列为1，第i-1行第j列为0，那么说明第i行第j列应该竖放并填充第i-1行第j列，成立后向左移动一格
  3. 第i行第j列为0，说明不放方块，那么第i-1行第j列必须为1，否则没法填充这个格子。若第i-1行第j列也为0，不兼容不合法 (至于第i行第j列这个格子空着干什么，其实就是留出来给第i+1行竖放的时候插进来的)

那么目标状态是什么，就是dp[n][maxs]，maxs表示全部是1的串，即第n-1行以上全部覆盖满，第n行的状态为maxs，即没有空着的格子，也全部覆盖满了，即整个矩形全部被覆盖满了的状态。
最后是第1行的初始化问题，因为约定了“上凸型摆放”，所以第1行是不能竖放方格的，只能横放方格，
每横放一个必定占据两个格子，所以在判断一个状态（那个01串）的时候，连着的1的个数必定为偶数，如果出现了单独的1，说明不合法。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<cstdlib>
  5. #include<cmath>
  6. #include<algorithm>
  7. #include<vector>
  8. using namespace std;
  9. int n,m;
  10. long long dp[20][100010];
  11. bool init(int s)
  12. {
  13.     int j=0;
  14.     while(j<m)
  15.     {
  16.         if (s & (1<<j))
  17.         {
  18.             if (j==m-1)
  19.                 return false;
  20.             if (s & (1<<(j+1)))
  21.                 j+=2;
  22.             else
  23.                 return false;
  24.         }
  25.         else
  26.             j++;
  27.     }
  28.     return true;
  29. }
  31. bool check(int ns,int ps)
  32. {
  33.     int j=0;
  34.     while (j<m)
  35.     {
  36.         if (ns & (1<<j))
  37.         {
  38.             if (ps & (1<<j))
  39.             {
  40.                 if (j==m-1 || !(ns & 1<<(j+1)) || !(ps & 1<<(j+1)))
  41.                     return false;
  42.                 else
  43.                     j+=2;
  44.             }
  45.             else
  46.                 j++;
  47.         }
  48.         else
  49.         {
  50.             if (ps & (1<<j))
  51.                 j++;
  52.             else
  53.                 return false;
  54.         }
  55.     }
  56.     return true;
  57. }
  59. int main()
  60. {
  61.     while (scanf("%d%d",&n,&m))
  62.     {
  63.         if (n==0 && m==0) break;
  64.         if (n&1 && m&1)
  65.         {
  66.             printf("0\n");
  67.             continue;
  68.         }
  69.         if (n<m) swap(n,m);
  70.         int tot=(1<<m)-1;
  71.         memset(dp, 0, sizeof(dp));
  72.         for (int s=0; s<=tot; s++)
  73.             if (init(s)) dp[1][s]=1;
  74.         for (int i=2; i<=n; i++)
  75.         {
  76.             for (int j=0; j<=tot; j++)
  77.             {
  78.                 for (int k=0; k<=tot; k++)
  79.                 {
  80.                     if (check(j,k))
  81.                         dp[i][j]+=dp[i-1][k];
  82.                 }
  83.             }
  84.         }
  85.         printf("%lld\n",dp[n][tot]);
  86.     }
  87.     return 0;
  88. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注