[关闭]
@TryMyEdge 2017-04-22T12:27:36.000000Z 字数 4387 阅读 949

CQUPT 训练题 2017/4/3

题解

题目

A Country Roads

题目大意：

    有n(1<=n<=500)个点，m(0<=m<=16000)条无向边，每条边的权值为不超过20000的正整数，一条路径(由多条边首位连接组成)的权值为这些边中权值最大的那条边的权值。给定终点，问从每个点到终点的最小权值路径的权值是多少。
    T(T<=20)组数据。

解题思路：

    因为边是无向边，所以把终点作为起点，求起点到每个点的路径的最小权值即可。
    这里给出spfa的解法，只要简单地把更新路径权值的方式从dis[now]+maps[now][i]改为max(dis[now],maps[now][i])，其他不变，就可以解决这个特殊规则的“最短路”问题了。可以类似地去尝试一下用Dijkstra解决这道题，思考一下为什么可以。
    ps：注意重边的处理。这题n比较小，而且有重边，我就直接用邻接矩阵了。
    时间复杂度o(T*k*n^2)，空间复杂度o(n^2)。

AC代码：

  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define QC 1000000007
  5. #define INF 66666
  6. int dis[505];
  7. int maps[505][505];
  8. bool life[505];
  9. queue <int> q;
  10. int n;
  11. void init()
  12. {
  13.     for(int i=0;i<n;i++)
  14.         dis[i]=INF;
  15.     for(int i=0;i<n;i++)
  16.         for(int j=0;j<n;j++)
  17.         {
  18.             if(i!=j)
  19.                 maps[i][j]=INF;
  20.         }
  21. }
  22. void spfa(int x)
  23. {
  24.     int now;
  25.     q.push(x);
  26.     dis[x]=0;
  27.     life[x]=1;
  28.     while(!q.empty())
  29.     {
  30.         now=q.front();
  31.         q.pop();
  32.         for(int i=0;i<n;i++)
  33.         {
  34.             if(max(dis[now],maps[now][i])<dis[i])
  35.             {
  36.                 dis[i]=max(dis[now],maps[now][i]);
  37.                 if(!life[i])
  38.                 {
  39.                     life[i]=1;
  40.                     q.push(i);
  41.                 }
  42.             }
  43.         }
  44.         life[now]=0;
  45.     }
  46. }
  47. int main()
  48. {
  49.     int T,m;
  50.     int u,v,w,t;
  51.     scanf("%d",&T);
  52.     for(int cases=1;cases<=T;cases++)
  53.     {
  54.         scanf("%d",&n);
  55.         init();
  56.         scanf("%d",&m);
  57.         while(m--)
  58.         {
  59.             scanf("%d%d%d",&u,&v,&w);
  60.             maps[u][v]=min(maps[u][v],w);
  61.             maps[v][u]=maps[u][v];
  62.         }
  63.         scanf("%d",&t);
  64.         spfa(t);
  65.         printf("Case %d:\n",cases);
  66.         for(int i=0;i<n;i++)
  67.         {
  68.             if(dis[i]!=INF)
  69.                 printf("%d\n",dis[i]);
  70.             else
  71.                 printf("Impossible\n");
  72.         }
  73.     }
  74.     return 0;
  75. }

B How Many Zeroes?

题目大意：

    问[m，n]区间(m<=n，m和n都是无符号32位整数，上限大约4*10^9)的数共有多少个0，不包括前导0。
    T(T<=11000)组数据。

解题思路：

    第一眼看出是个数位dp，把区间转化为两个前缀和的差，然后用数位dp求<=x的数共有多少个0。
    思路很简单，但是写起来很麻烦。。。
    用了一万个特判。。。
    ps：mz的思路和代码都更简单一些，你们可以去参考一下。
    时间复杂度o(T*lg(n))，空间复杂度o(lg(n))。

AC代码：

  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define QC 1000000007
  5. int num[30];
  6. long long dp2[30],dp1[30],dp3[30];
  7. long long ask(long long x)
  8. {
  9.     int temp,now=0;
  10.     long long ans=0;
  11.     if(x>=10)
  12.     {
  13.         temp=0;
  14.         while(x)
  15.         {
  16.             num[++temp]=x%10;
  17.             x/=10;
  18.         }
  19.         ans=dp3[temp-1];
  20.         for(int i=1;i<num[temp];i++)
  21.             ans+=dp1[temp-1];
  22.         temp--;
  23.         while(temp)
  24.         {
  25.             for(int i=0;i<num[temp];i++)
  26.             {
  27.                 ans+=dp1[temp-1];
  28.                 if(!i)
  29.                     ans+=dp2[temp-1];
  30.                 ans+=dp2[temp-1]*now;
  31.             }
  32.             if(num[temp]==0)
  33.                 now++;
  34.             temp--;
  35.         }
  36.     }
  37.     if(x)
  38.         ans=1;
  39.     return ans;
  40. }
  41. int main()
  42. {
  43.     dp2[0]=1;
  44.     for(int i=1;i<25;i++)
  45.         dp2[i]=dp2[i-1]*10;
  46.     dp1[0]=0;
  47.     for(int i=1;i<25;i++)
  48.         dp1[i]=dp1[i-1]*10+dp2[i-1];
  49.     dp3[0]=0;
  50.     dp3[1]=1;
  51.     for(int i=2;i<25;i++)
  52.         dp3[i]=dp1[i-1]*9+dp3[i-1];
  53.     int T;
  54.     long long a,b;
  55.     scanf("%d",&T);
  56.     for(int cases=1;cases<=T;cases++)
  57.     {
  58.         scanf("%lld%lld",&a,&b);
  59.         printf("Case %d: %lld\n",cases,ask(b+1)-ask(a));
  60.     }
  61.     return 0;
  62. }

E Dice (I)

题目大意：

    有N(1<=N<=1000)个骰子，每个骰子可以显示1~K(1<=K<=1000)的数字，问有多少种方法可以让这N个骰子显示的数字的和为S(0<=S<=15000)。
    T(T<=25)组数据。

解题思路：

    用dp[i][j]表示考虑到第i个骰子，和为j的方案数，我们很容易想到一个N*S*K的状态转移：
    dp[i][j]=dp[i][j-1]+dp[j-2]+...dp[i][max(0，j-K)]
    但是N*S*K的时间复杂度显然是行不通的。
    我们发现实际上dp[i][j]=∑dp[i-1][x](max(1，j-K)<x<j)，于是我们可以维护sum[i][j]=∑dp[i-1][x](1<x<j)，用前缀和求差表示区间和的思想，这样复杂度就降到了N*S。
    ps：我的dp数组是一维的，可以研究一下我是怎么做到的~
    时间复杂度o(N*S)，空间复杂度o(S)。

AC代码：

  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define QC 100000007
  5. int sum[15005];
  6. int dp[15005];
  7. int main()
  8. {
  9.     int T;
  10.     scanf("%d",&T);
  11.     int n,k,s;
  12.     for(int t=1;t<=T;t++)
  13.     {
  14.         scanf("%d%d%d",&n,&k,&s);
  15.         dp[0]=sum[0]=0;
  16.         for(int i=1;i<=s;i++)
  17.         {
  19.             if(i<=k)
  20.             {
  21.                 dp[i]=1;
  22.                 sum[i]=i;
  23.             }
  24.             else
  25.             {
  26.                 dp[i]=0;
  27.                 sum[i]=sum[i-1];
  28.             }
  29.         }
  30.         for(int i=2;i<=n;i++)
  31.         {
  32.             for(int j=s;j;j--)
  33.                 dp[j]=(sum[j-1]-sum[max(0,j-k-1)]+QC)%QC;
  34.             for(int j=1;j<=s;j++)
  35.                 sum[j]=(sum[j-1]+dp[j])%QC;
  36.         }
  37.         printf("Case %d: %d\n",t,dp[s]);
  38.     }
  39.     return 0;
  40. }

F Diablo

题目大意：

    每只恶魔有一个属性值。一开始有n(0<=n<=100000)个恶魔从左到右站成一排，有q(1<=q<=50000)个操作，操作分为两种:在最右边添加一只恶魔，或者让左边的某一只恶魔离开，并且输出这只恶魔的属性值。
    T(T<=5)组数据。

解题思路：

    第一眼很容易让人想到平衡树或者是伸展树之类支持添加和删除的数据结构，事实上这两种数据结构也确实可以做这题，似乎分块之类的数据结构也可以过这题，不过这里提供一种用线段树的解法。
    线段树维护区间现存点数。每次添加就在对应的区间加点，查询就去找这个点的实际位置，然后删除这个点。
    ps：记得线段树对应的原数列点数=n+q，因为最遭的情况可能q个操作都是加点操作。
    时间复杂度o(q*log(n+q))，空间复杂度o(n+q)。

AC代码：

  1. #include<iostream>
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. #define QC 1000000007
  5. struct Node
  6. {
  7.     int sum;
  8.     int l,r,mid;
  9. }tre[600005];
  10. int num[150005];
  11. void build(int x,int l,int r)
  12. {
  13.     tre[x].l=l;
  14.     tre[x].r=r;
  15.     tre[x].mid=(l+r)>>1;
  16.     tre[x].sum=0;
  17.     if(l!=r)
  18.     {
  19.         build(x*2,tre[x].l,tre[x].mid);
  20.         build(x*2+1,tre[x].mid+1,tre[x].r);
  21.     }
  22. }
  23. void add(int x,int y,int flag)
  24. {
  25.     tre[x].sum+=flag;
  26.     if(tre[x].l!=tre[x].r)
  27.     {
  28.         if(y<=tre[x].mid)
  29.             add(x*2,y,flag);
  30.         else
  31.             add(x*2+1,y,flag);
  32.     }
  33. }
  34. int ask(int x,int y)
  35. {
  36.     if(tre[x].sum<y)
  37.         return 0;
  38.     if(tre[x].l==tre[x].r)
  39.         return tre[x].mid;
  40.     if(tre[x*2].sum<y)
  41.         return ask(x*2+1,y-tre[x*2].sum);
  42.     else
  43.         return ask(x*2,y);
  44. }
  45. int main()
  46. {
  47.     int T;
  48.     char s[6];
  49.     scanf("%d",&T);
  50.     int n,q;
  51.     int temp,now;
  52.     for(int t=1;t<=T;t++)
  53.     {
  54.         scanf("%d%d",&n,&q);
  55.         build(1,1,n+q);
  56.         for(int i=1;i<=n;i++)
  57.         {
  58.             scanf("%d",num+i);
  59.             add(1,i,1);
  60.         }
  61.         printf("Case %d:\n",t);
  62.         while(q--)
  63.         {
  64.             scanf("%s",s);
  65.             scanf("%d",&now);
  66.             if(s[0]=='c')
  67.             {
  68.                 temp=ask(1,now);
  69.                 if(temp)
  70.                 {
  71.                     printf("%d\n",num[temp]);
  72.                     add(1,temp,-1);
  73.                 }
  74.                 else
  75.                     printf("none\n");
  76.             }
  77.             else
  78.             {
  79.                 n++;
  80.                 num[n]=now;
  81.                 add(1,n,1);
  82.             }
  83.         }
  84.     }
  85.     return 0;
  86. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注