Codeforces Round #178 (Div. 2)

举报
xindoo 发表于 2022/04/15 23:34:07 2022/04/15
【摘要】 A. Shaass and Oskols 题意:在n条电线上有不同数量的鸟, Shaass开了m枪,每一枪打的是第xi条电线上的第yi只鸟,然后被打中的这只鸟左边的飞到第i-1条电线上,右边的飞到i+1条电线上,没有落脚点的鸟会飞走。 #include <stdio.h>int a[105]; int main(){ ...

A. Shaass and Oskols

题意:在n条电线上有不同数量的鸟, Shaass开了m枪,每一枪打的是第xi条电线上的第yi只鸟,然后被打中的这只鸟左边的飞到第i-1条电线上,右边的飞到i+1条电线上,没有落脚点的鸟会飞走。


  
  1. #include <stdio.h>
  2. int a[105];
  3. int main()
  4. {
  5. int n, m, x, y;
  6. while (scanf("%d",&n) != EOF)
  7. {
  8. for (int i = 1; i <= n; i++)
  9. scanf("%d",&a[i]);
  10. scanf("%d",&m);
  11. while (m--)
  12. {
  13. scanf("%d%d",&x,&y);
  14. a[x-1] += (y-1);
  15. a[x+1] += (a[x]-y+1);
  16. a[x] = 0;
  17. }
  18. for (int j = 1; j <= n; j++)
  19. printf("%d\n",a[j]);
  20. }
  21. return 0;
  22. }


B.Shaass and Bookshelf

题意:Shaass有n本书。每本书都有厚度t和宽度w,t只能为1或2,然后他想做一个书架,我们可以将一本书放在其他书的上面,如题目中的图,然后尽可能的使他们的总厚度最小,输出最小值。

     这道题我不会做,感觉是dp,有点像01背包,和01背包不同的是它的厚度是随着放上面书的书面和宽度而变化的。感觉数据量也不大,我觉得可以用暴力来求解。看了别然的博客,发现此题用暴力会tle,我就不试了。还有记忆化搜索的方法解此题,摘自xieshimao的博客,直接看他解题代码。


  
  1. #include<stdio.h>
  2. #include<string.h>
  3. int w[105],t[105],n;
  4. int mem[105][205][205];
  5. int min(int a,int b)
  6. {
  7. if(a>b)
  8. return b;
  9. else
  10. return a;
  11. }
  12. int dfs(int pos,int thi,int whi)
  13. {
  14. if(pos==n)
  15. return thi;
  16. if(mem[pos][thi][whi]!=-1)
  17. return mem[pos][thi][whi];
  18. if(thi-t[pos]>=whi+w[pos])
  19. return mem[pos][thi][whi]=min(dfs(pos+1,thi-t[pos],whi+w[pos]),dfs(pos+1,thi,whi));
  20. return mem[pos][thi][whi]=dfs(pos+1,thi,whi);
  21. }
  22. int main()
  23. {
  24. int i,sum;
  25. while(scanf("%d",&n)!=EOF)
  26. {
  27. memset(mem,-1,sizeof(mem));
  28. sum=0;
  29. for(i=0;i<n;i++)
  30. {
  31. scanf("%d%d",&t[i],&w[i]);
  32. sum=sum+t[i];
  33. }
  34. printf("%d\n",dfs(0,sum,0));
  35. }
  36. return 0;
  37. }

以下几题来自haha593572013的博客

C.Shaass and Lights

蛮有意思的,给你m个位置,现在要从这m个位置往位置的两边扩展,问你把所有的数都扩展到总共有多少种方法。

在两个位置中间的那些数的可能的排列数应该是2^(k-1),因为每次都有两种选择,要么左端点,要么右端点。

然后从所有的间隔中各取出一种排列,a1 a2 a3 b1 b2 b3 c1 c2 c3,现在就是求这个序列的总排列数,要求同类的先后顺序不能变,很容易发现这个其实就是类似于多重集合的排列,ans=n!/(p1!*p2!*p3!)   ,然后分子再乘上一个2^(k-1)就好了


  
  1. #include <cstdio>
  2. #include <vector>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  6. typedef long long lld;
  7. const int inf = ~0u>>2;
  8. const int mod = 1000000007 ;
  9. const int maxn = 1010;
  10. int pos[maxn];
  11. lld Pow(lld a,lld b) {
  12. lld ans = 1;
  13. while(b) {
  14. if(b&1) ans = ans * a % mod;
  15. a = a * a % mod;
  16. b >>= 1;
  17. }
  18. return ans ;
  19. }
  20. lld fac[maxn],two[maxn];
  21. vector<int> rec;
  22. void solve(int n) {
  23. fac[0] = 1; two[0] = 1;
  24. for(int i = 1; i <= 1000; i++) fac[i] = fac[i-1] * i % mod;
  25. for(int i = 1; i <= 1000; i++) two[i] = two[i-1] * 2 % mod;
  26. int sum = 0;
  27. for(int i = 0; i < rec.size(); i++) sum += rec[i];
  28. // printf("sum=%d\n",sum);
  29. lld ans = fac[sum];
  30. for(int i = 0; i < rec.size(); i++) {
  31. ans = ans * Pow(fac[rec[i]],mod-2) % mod;
  32. }
  33. for(int i = 1; i < rec.size()-1;i++) {
  34. if(rec[i]>0) ans = ans * two[rec[i]-1] % mod;
  35. }
  36. printf("%I64d\n",ans);
  37. }
  38. int main() {
  39. int n , m;
  40. scanf("%d%d",&n,&m);
  41. for(int i = 0; i < m; i++) {
  42. scanf("%d",&pos[i]);
  43. }
  44. sort(pos,pos+m);
  45. rec.push_back(pos[0]-1);
  46. for(int i = 1; i < m ; i++) {
  47. rec.push_back(pos[i]-pos[i-1]-1);
  48. }
  49. rec.push_back(n-pos[m-1]);
  50. solve(n);
  51. return 0;
  52. }


 

E.Shaass the Great

给你一棵树,5000个点,每条边有边权,可以删掉一条边再将这条边换个位置,要保证改变后仍然是树的形状,现在问你所有点对的距离之和最小是多少。

5000个点,马上想到n^2..然后就是暴力枚举去掉每条边 ,剩下的就是两棵树,然后重新连接一条边,稍微想一下,这条边肯定就是将两棵树的重心连起来,所以,接下来的事情就简单了。。。

比赛的时候看错了题,以为边可以修改很多次。。。然后各种YY,不够仔细啊。。。


  
  1. #include <cstdio>
  2. #include <vector>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  6. const int inf = ~0u>>2;
  7. const int mod = 1000000007 ;
  8. const int maxn = 5010;
  9. int son[maxn] ;
  10. long long dp[maxn];
  11. int n ;
  12. int mp[maxn][maxn];
  13. vector<int> edge[maxn];
  14. int node;
  15. struct Edge{
  16. int s,t,w;
  17. Edge(){}
  18. Edge(int a,int b,int c)
  19. {
  20. s = a;
  21. t = b;
  22. w = c;
  23. }
  24. }in[maxn];
  25. int dep[maxn];
  26. void dfs(int u,int f) {
  27. son[u] = 1;
  28. dep[u] = dep[f] + 1;
  29. int sz = edge[u].size();
  30. for(int i = 0; i < sz; i++) {
  31. int v = edge[u][i];
  32. if(v==f) continue;
  33. dfs(v,u);
  34. son[u] += son[v];
  35. }
  36. }
  37. int cen;
  38. int S[maxn];
  39. void DFS(int u,int f) {
  40. S[u] = 1;
  41. int sz = edge[u].size();
  42. for(int i = 0; i < sz; i++) {
  43. int v = edge[u][i];
  44. if(v == f || v == node) continue;
  45. DFS(v,u);
  46. S[u] += S[v];
  47. }
  48. }
  49. long long sum;
  50. void dfs1(int u,int f,int rt) {
  51. dp[u] = 0;
  52. int sz = edge[u].size();
  53. for(int i = 0; i < sz; i++) {
  54. int v = edge[u][i];
  55. if(v == f || v == node) continue;
  56. dfs1(v,u,rt);
  57. sum += (long long ) S[v] * (S[rt]-S[v]) * mp[u][v];
  58. dp[u] += dp[v] + (long long)S[v] * mp[u][v];
  59. }
  60. }
  61. long long Mi;
  62. void dfs2(int u,int f,int rt) {
  63. if(u==rt) {
  64. Mi = min(dp[u],Mi);
  65. } else {
  66. long long tmp = dp[f] - dp[u] - (long long)S[u] * mp[f][u];
  67. dp[u] += (long long)mp[f][u] * (S[rt] - S[u]) + tmp;
  68. Mi = min(dp[u],Mi);
  69. }
  70. int sz = edge[u].size();
  71. for(int i = 0; i < sz; i++) {
  72. int v = edge[u][i];
  73. if(v == f || v == node) continue;
  74. dfs2(v,u,rt) ;
  75. }
  76. }
  77. int main() {
  78. scanf("%d",&n);
  79. int a,b,c;
  80. int tot = 0;
  81. for(int i=1;i<n;i++) {
  82. scanf("%d%d%d",&a,&b,&c);
  83. edge[a].push_back(b);
  84. edge[b].push_back(a);
  85. mp[a][b] = mp[b][a] = c;
  86. in[tot++] = Edge(a,b,c);
  87. }
  88. dfs(1,0);
  89. long long INF = (long long)1000000000*(long long)1000000000;
  90. long long ans = INF;
  91. for(int i=0;i<tot;i++) {
  92. int u = in[i].s , v = in[i].t;
  93. if(dep[u] > dep[v]) swap(u,v);
  94. node = v;
  95. Mi = INF; sum = 0;
  96. DFS(1,0);
  97. dfs1(1,0,1);
  98. dfs2(1,0,1);
  99. long long tmp = (long long)(son[1]-son[node])*(son[node])*in[i].w;
  100. tmp += Mi * (son[node]) ;
  101. tmp += sum;
  102. Mi = INF; sum = 0;
  103. DFS(node,u);
  104. dfs1(node,u,node);
  105. dfs2(node,u,node);
  106. tmp += Mi * (son[1]-son[node]);
  107. tmp += sum;
  108. if(tmp < ans) ans = tmp;
  109. }
  110. printf("%I64d\n",ans);
  111. return 0;
  112. }


 

 

文章来源: xindoo.blog.csdn.net,作者:xindoo,版权归原作者所有,如需转载,请联系作者。

原文链接:xindoo.blog.csdn.net/article/details/8770371

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。