[关闭]
@Asuna 2017-04-14T17:53:20.000000Z 字数 4460 阅读 973

CQUPT 训练题题解 2017/4/3

题解

Problem A:Country Roads

题意：求某个点到各点的代价，两点间某条路径的代价定义为路径上权值最大的边的权值，而两点间的权值表示为它们之间所有路径代价的最小值。

题解：dist[u]表示从原点到点u的路径的代价，用Dijkstra。最后注意判断重边。

参考代码：

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<cmath>
  5. #include<cstdlib>
  6. #include<vector>
  7. #include<queue>
  8. using namespace std;
  9. typedef pair <int, int> p;
  10. int dist[510];
  11. priority_queue < p, vector<p>, greater<p> > qu;
  12. struct node 
  13. {
  14.     int nxt;
  15.     int w;
  16.     int to;
  17. }edge[40000];
  18. bool vis[510];
  19. int head[510],tot;
  21. void addedge(int from, int to, int w) 
  22. {
  23.     edge[tot].to=to;
  24.     edge[tot].w=w;
  25.     edge[tot].nxt=head[from];
  26.     head[from]=tot++;
  27. }
  29. void Dijkstra(int u, int n) 
  30. {
  31.     while (!qu.empty()) 
  32.     {
  33.         qu.pop();
  34.     }
  35.     for (int i=0; i<n; i++)
  36.     {
  37.         dist[i]=100000000;
  38.     }
  39.     dist[u]=0;
  40.     qu.push(make_pair(dist[u], u));
  41.     while (!qu.empty()) 
  42.     {
  43.         p tmp=qu.top();
  44.         qu.pop();
  45.         int s=tmp.second;
  46.         int d=tmp.first;
  47.         for (int i=head[s]; ~i; i=edge[i].nxt) 
  48.         {
  49.             int t=edge[i].to;
  50.             int w=edge[i].w;
  51.             if (dist[t]>max(d, w)) 
  52.             {
  53.                 dist[t]=max(d, w);
  54.                 qu.push(make_pair(dist[t], t));
  55.             }
  56.         }
  57.     }
  58. }
  60. int main() {
  61.     int t, icase=1;
  62.     scanf("%d", &t);
  63.     while (t--) 
  64.     {
  65.         int n, m;
  66.         scanf("%d%d", &n, &m);
  67.         for (int i=0; i<n; i++)
  68.         {
  69.             head[i]=-1;
  70.         }
  71.         tot=0;
  72.         int u, v, w;
  73.         for (int i=1; i<=m; i++)
  74.         {
  75.             scanf("%d%d%d", &u, &v, &w);
  76.             addedge(u, v, w);
  77.             addedge(v, u, w);
  78.         }
  79.         scanf("%d", &u);
  80.         Dijkstra(u, n);
  81.         printf("Case %d:\n", icase++);
  82.         for (int i=0; i<n; i++)
  83.         {
  84.             if (dist[i]==100000000)
  85.             {
  86.                 printf("Impossible\n");
  87.             }
  88.             else 
  89.             {
  90.                 printf("%d\n", dist[i]);
  91.             }
  92.         }
  93.     }
  94.     return 0;
  95. }

Problem B:How Many Zeroes?

题意：给定两个数a，b，求a到b所有数的0的个数。

题解：dp[位数][0~9][0的个数]; 然后记忆化搜索的时候 dfs(第几位,前面有没有非0的数,取数的限制,0的个数);

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. long long n, m;
  8. long long cal(long long x) 
  9. {
  10.     if (x<0) return 0;
  11.     long long ans=1, cnt=1, tmp=0;
  12.     while (x>=10) 
  13.        {
  14.         long long cur=x%10;
  15.         x/=10;
  16.         if (cur!=0) ans+=x*cnt;
  17.         else ans+=(x-1)*cnt+tmp+1;
  18.         tmp+=cur*cnt;
  19.         cnt*=10;
  20.     }
  21.     return ans;
  22. }
  24. int main() 
  25. {
  26.        int t,icase=1;
  27.        cin>>t;
  28.        while(t--)
  29.        {
  30.               scanf("%d%d",&n,&m);
  31.         printf("Case %d: %lld\n", icase++,cal(m)-cal(n-1)); 
  32.     }   
  33.     return 0;
  34. }

Problem D：Summing up Powers

题意：求(1^K + 2^K + 3^K + ... + N^K)%2^32

题解：矩阵快速幂，由于不知道怎么搞数学公式在这个上面。。。找了篇网上写的比较详细的题解。。http://blog.csdn.net/kg20006/article/details/51057305需要注意的就是转移矩阵还有mod 2^32可以用自然溢出完成。
ps：似乎是伯努利数？有兴趣可以baidu一下伯努利数的相关题目，似乎还蛮多的好像也有点用但是我看不怎么懂。。。。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>  
  3. #include<cstdlib>  
  4. #include<cstring>  
  5. using namespace std;   
  6. const long long mod=((long long)1<<32);   
  7. long long k,siz,n,C[60][60];  
  8. struct Matrix  
  9. {  
  10.     long long a[53][53]; 
  11.     Matrix()  
  12.     {  
  13.         memset(a, 0, sizeof(a));  
  14.         for(int i=1; i<=52; i++)  
  15.         {  
  16.             a[i][i]=1;  
  17.         } 
  18.     } 
  19. };  
  21. Matrix operator * (const Matrix & m1, const Matrix & m2)  
  22. {  
  23.     Matrix m;  
  24.     for(int i=1; i<=siz; i++)  
  25.     {  
  26.         for(int j=1; j<=siz; j++)  
  27.         {  
  28.             m.a[i][j]=0;  
  29.             for(int k=1; k<=siz; k++)  
  30.             {  
  31.                 m.a[i][j]=(m.a[i][j]+(m1.a[i][k]*m2.a[k][j])%mod)%mod;  
  32.             }  
  33.         }  
  34.     }  
  35.     return m;  
  36. }  
  38. Matrix quick_pow(Matrix base, long long pow)  
  39. {  
  40.     Matrix A; 
  41.     while(pow)  
  42.     {  
  43.         if(pow&1)  
  44.         {  
  45.             A=A*base;  
  46.         }  
  47.         base=base*base;  
  48.         pow>>=1;  
  49.     }  
  50.     return A;  
  51. }  
  53. int main()  
  54. {  
  55.     long long t;    
  56.     memset(C,0,sizeof(C));  
  57.     C[0][0]=1;  
  58.     C[1][0]=C[1][1]=1;  
  59.     for(int i=2; i<=50; i++)  
  60.     {  
  61.         for(int j=0; j<=i; j++)  
  62.         { 
  63.             if (j==0)  
  64.             {  
  65.                 C[i][j]=1;  
  66.             }  
  67.             else  
  68.             {  
  69.                 C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;  
  70.             } 
  71.         }  
  72.     }  
  73.     scanf("%lld",&t);  
  74.     for (long long cas=1; cas<=t; cas++)  
  75.     {  
  76.         scanf("%lld%lld",&n,&k);  
  77.         siz=k+2;  
  78.         Matrix tran;  
  79.         memset(tran.a, 0, sizeof(tran.a));  
  80.         for(int i=1; i<=k+1; i++)  
  81.         {  
  82.             for(int j=1; j<=k+1; j++)  
  83.             {  
  84.                 if(i<=j)  
  85.                 {  
  86.                     tran.a[i][j]=C[k+1-i][j-i];  
  87.                 }  
  88.             }  
  89.         }  
  90.         for(int i=1; i<=k+1; i++)  
  91.         {  
  92.             tran.a[k+2][i]=C[k][i-1];  
  93.         }  
  94.         tran.a[k+2][k+2]=1;  
  95.         Matrix ans=quick_pow(tran,n-1);  
  96.         long long ans1=0;  
  97.         for(int i=1; i<=k+2; i++)  
  98.         {  
  99.             ans1=(ans1+ans.a[k+2][i])%mod;  
  100.         }  
  101.         printf("Case %lld: %lld\n",cas,ans1);  
  102.     }  
  103.     return 0;  
  104. }

Problem F：Diablo

题意：给一个动态的序列，每次询问序列中第k个元素是啥，询问完以后，就删除这个元素，同时可以在结尾添加元素，如果当前位置没有元素，就输出“none”。

题解：区间修改+区间询问+单点修改的线段树。一开始毫无头绪，好在mzjj和js提示了许多。。总的来说树上维护的东西是当前区间内还有多少个元素没被删除，这样当询问到某一棵子树的时候，如果左子树的元素个数大于k，那么元素必定在左子树当中，否则就在右子树当中，在左子树当中固然好，就是左子树区间内第k个，在右子树的话就应该是第k减去左子树元素个数个，同时在叶子结点维护元素值。

参考代码：

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. #include<cmath>
  6. #include<algorithm>
  7. using namespace std;
  8. int num[800010],id[800010],ans;
  9. void pushup(int rt)
  10. {
  11.     num[rt]=num[rt*2]+num[rt*2+1];
  12. }
  14. void build(int l,int r,int rt)
  15. {
  16.     num[rt]=0;
  17.     id[rt]=-1;
  18.     if (l==r) return;
  19.     int mid=(l+r)/2;
  20.     build(l,mid,rt*2);
  21.     build(mid+1,r,rt*2+1);
  22. }
  24. void update(int x,int c,int l,int r,int rt)
  25. {
  26.     if (l==r)
  27.     {
  28.         num[rt]=1;
  29.         id[rt]=c;
  30.         return;
  31.     }
  32.     int mid=(l+r)/2;
  33.     if (x<=mid) update(x,c,l,mid,rt*2);
  34.     else update(x,c,mid+1,r,rt*2+1);
  35.     pushup(rt);
  36. }
  38. void query(int k, int l, int r, int rt)
  39. {
  40.     num[rt]-=1;
  41.     if (l==r)
  42.     {
  43.         ans=id[rt];
  44.         id[rt]=-1;
  45.         return;
  46.     }
  47.     int mid=(l+r)/2;
  48.     if (num[rt*2]>=k) query(k,l,mid,rt*2);
  49.     else
  50.     {
  51.         k-=num[rt*2];
  52.         query(k,mid+1,r,rt*2+1);
  53.     }
  54. }
  56. int main()
  57. {
  58.     int t,icase=1;;
  59.     scanf("%d",&t);
  60.     while(t--)
  61.     {
  62.         int n,m,sum;
  63.         scanf("%d%d",&n,&m);
  64.         sum=n+m;
  65.         build(1,sum,1);
  66.         printf("Case %d:\n",icase++);
  67.         for (int i=1; i<=n; i++)
  68.         {
  69.             int x;
  70.             scanf("%d",&x);
  71.             update(i,x,1,sum,1);
  72.         }
  73.         while (m--)
  74.         {
  75.             char s[2];
  76.             int x;
  77.             scanf("%s%d",s,&x);
  78.             if (s[0]=='a')
  79.             {
  80.                 n+=1;
  81.                 update(n,x,1,sum,1);
  82.             }
  83.             else
  84.             {
  85.                 query(x,1,sum,1);
  86.                 if (ans==-1) printf("none\n");
  87.                 else printf("%d\n",ans);
  88.             }
  89.         }
  90.     }
  91.     return 0;
  92. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注