Codeforce Round #547 div3

痛定思痛。 2022-01-21 01:57 322阅读 0赞

A.Game 23

1.题目

A

2.思路

直接考虑dfs即可，记录最小值，最后输出即可

  1. #include <stdio.h>
  2. const int maxn=1e9+7;
  3. int n,m;
  4. int min=maxn;
  5. void dfs(int n,int tar,int step)
  6. {
  7.     if(n>tar)
  8.     {
  9.         return;
  10.     }
  11.     if(n==tar)
  12.     {
  13.         min=min<step?min:step;
  14.     }
  15.     dfs(n*2,tar,step+1);
  16.     dfs(n*3,tar,step+1);    
  17. }
  19. int main()
  20. {
  21.     scanf("%d%d",&n,&m);
  22.     if(n==m)
  23.     {
  24.         printf("0\n");
  25.     }
  26.     else
  27.     {
  28.         dfs(n,m,0);
  29.         if(min!=maxn)
  30.         printf("%d\n",min);
  31.         else
  32.         printf("-1\n");
  33.     }
  34.     return 0;
  35. }#include <stdio.h>
  36. const int maxn=1e9+7;
  37. int n,m;
  38. int min=maxn;
  39. void dfs(int n,int tar,int step)
  40. {
  41.     if(n>tar)
  42.     {
  43.         return;
  44.     }
  45.     if(n==tar)
  46.     {
  47.         min=min<step?min:step;
  48.     }
  49.     dfs(n*2,tar,step+1);
  50.     dfs(n*3,tar,step+1);    
  51. }
  53. int main()
  54. {
  55.     scanf("%d%d",&n,&m);
  56.     if(n==m)
  57.     {
  58.         printf("0\n");
  59.     }
  60.     else
  61.     {
  62.         dfs(n,m,0);
  63.         if(min!=maxn)
  64.         printf("%d\n",min);
  65.         else
  66.         printf("-1\n");
  67.     }
  68.     return 0;
  69. }

B.Maximal Continuous Rest

1.题目

B

2.解答

问题看起来有点像循环数组，求最大连续字段的最大长度，只要加一个%n循环求最大长度即可。

  1. #include <stdio.h>
  2. const int maxn=2*1e5+7;
  3. int n;
  4. int time[maxn];
  5. int max=-1;
  6. int main()
  7. {
  8.     scanf("%d",&n);
  9.     for(int i=0;i<n;i++)
  10.     {
  11.         scanf("%d",&time[i]);
  12.     }
  13.     int count=1;
  14.     int i;
  15.     for(i=0;i<n;i++)
  16.     {
  17.         if(time[i])
  18.             break;
  19.     }
  20.     if(i==n)
  21.     {
  22.         printf("0\n");
  23.         return 0;
  24.     }
  25.     for(i=0;i<2*n;i++)
  26.     {
  27.         if(time[i%n]&&time[(i+1)%n])
  28.         {
  29.             count++;
  30.         }
  31.         else
  32.         {
  33.             max=max>count?max:count;
  34.             count=1;
  35.         }
  36.     }
  37.     max=max>count?max:count;
  38.     printf("%d\n",max);
  39.     return 0;
  40. }

C.Polycarp Restores Permutation

1.题目

C

2.解答

我们这样考虑，假设原来的序列为a,b,c,d…h.

现在我们有b-a,c-b,d-c…，那么现在我们将两两之间的差相加起来

会得到b-a,c-a,d-a,e-a,f-a…我们假设其中任意一个元素xi为1，那么我们可以知道，在xi的位置此时的和是最小的，由此我们可以找到1的位置。任何一个属于[1,n]的元素-a,不会比1-a更小（十分显然），找到一的位置，剩下的东西就十分好判断了

  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <string.h>
  4. using namespace std; 
  5. int n;
  6. const int maxn=2*1e5+7;
  7. long long int q[maxn];
  8. long long int sum[maxn];
  9. int main()
  10. {
  11.     scanf("%d",&n);
  12.     long long int low=99999999;
  13.     memset(sum,0,sizeof(sum));
  14.     int b[maxn]={0};
  15.     for(int i=1;i<=n-1;i++)
  16.     {
  17.         scanf("%lld",&q[i]);
  18.         sum[i]=sum[i-1]+q[i];
  19.     }
  20.     for(int i=0;i<=n-1;i++)
  21.     {
  22.         low=min(low,sum[i]);//寻找一    
  23.     }
  24.     for(int i=0;i<n;i++)
  25.     {
  26.         if(sum[i]-low+1>n||b[sum[i]-low]>=1)
  27.         {
  28.            //不满足情况的点有数值大于n
  29.             //或者中间出现0
  30.             printf("-1\n");
  31.             return 0;
  32.         }
  33.         b[sum[i]-low]=1;
  34.     }
  35.     for(int i=0;i<n;i++)
  36.     {
  37.         printf("%lld ",sum[i]-low+1);
  38.     }
  39.     puts("");
  40.     return 0;
  41. }

D.Colored Boots

1.题目

D

2.解答

首先我们先对两个字符数组进行排序，将’?’放在数组的最后边

然后我们分别从两个字符数组的开头开始比较，此处相当于寻找字串。寻找字串完毕后，剩下的元素就是互相不匹配的和’?’，那么之后我们从第一个数组的末尾开始，将‘?’与第二个数组从头开始剩下的元素进行匹配，再对第二个数组进行同样的操作，即可

  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <stack>
  5. using namespace std;
  6. const int maxn=15*1e4+7;
  7. vector<pair<int,int> >ans;
  8. struct node
  9. {
  10.     char c;
  11.     int num;
  12. };
  13. node d1[maxn];
  14. node d2[maxn];
  15. node s1[maxn];
  16. node s2[maxn];
  17. bool cmp(node a,node b)
  18. {
  19.     if(a.c=='?')
  20.     {
  21.         return false;
  22.     }
  23.     if(b.c=='?')
  24.     {
  25.         return true;
  26.     }    
  27.     return a.c<b.c;
  28. }//sort
  30. void read(int n,node *a)
  31. {
  32.     char c;
  33.     for(int i=1;i<=n;i++)
  34.     {
  35.         c=getchar();
  36.         a[i].c=c;
  37.         a[i].num=i;
  38.     }
  39.     return;
  40. }
  42. int main()
  43. {
  44.     int n;
  45.     scanf("%d",&n);
  46.     getchar();
  47.     char c;
  48.     ans=vector<pair<int,int> >(n);
  49.     read(n,d1);
  50.     getchar();
  51.     read(n,d2);
  52.     sort(d1+1,d1+1+n,cmp);
  53.     sort(d2+1,d2+1+n,cmp);
  54.     int c1=0;
  55.     int c2=0;
  56.     int i=1;
  57.     int j=1;
  58.     ans.clear(); 
  59.     while(1)
  60.     {
  61.         if(i>n||j>n)
  62.         {
  63.             break;
  64.         }
  65.         if(d1[i].c==d2[j].c)
  66.         {
  67.             ans.push_back(make_pair(d1[i].num,d2[j].num));
  68.             i++;
  69.             j++; 
  70.         }
  71.         else if(d1[i].c>d2[j].c)
  72.         {
  73.             s2[c2]=d2[j];//存入d2没有匹配的元素
  74.             c2++;
  75.             j++;
  76.         }
  77.         else if(d1[i].c<d2[j].c)
  78.         {
  79.             s1[c1]=d1[i];//存入d1没有匹配的元素
  80.             c1++;
  81.             i++;
  82.         }
  83.     }
  84.     for(i;i<=n;i++)
  85.     {
  86.         s1[c1]=d1[i];//放入剩下的元素
  87.         c1++;
  88.     }
  89.     for(j;j<=n;j++)
  90.     {
  91.         s2[c2]=d2[j];
  92.         c2++;
  93.     }
  94.     int c_2=0;//从d2的头开始匹配
  95.     for(i=c1-1;i>=0;i--)
  96.     {
  97.         if(s1[i].c=='?')
  98.         {
  99.             ans.push_back(make_pair(s1[i].num,s2[c_2].num));
  100.             c_2++;
  101.         }
  102.         else
  103.         {
  104.             break;
  105.         }
  106.     }
  107.     int c_1=0;//从d1的头开始匹配
  108.     for(j=c2-1;j>=c_2;j--)
  109.     {
  110.         if(s2[j].c=='?')
  111.         {
  112.             ans.push_back(make_pair(s1[c_1].num,s2[j].num));
  113.             c_1++;
  114.         }
  115.         else
  116.         {
  117.             break;
  118.         }
  119.     }
  120.     printf("%d\n",ans.size());
  121.     if(ans.size())
  122.     for(auto it:ans)
  123.     {
  124.         printf("%d %d\n",it.first,it.second);
  125.     }
  126.     return 0;
  127. }

E.Superhero Battle

1.题目

E

2.解答

首先我们先判断一个回合，一个回合的特殊情况是

1.回合时间尚未结束，直接就打死了

2.一个回合所造成的伤害，为0或者小于0，那么此时就是没有办法打死的情况

接着，我们要求出一个回合能够造成的伤害D，以及一个回合内所能造成伤害的最大值dmax,我们用总的血量H/D，可得到一个大致的回合数R，但是由于可能dmax要大于D，所以可能在R回合之前，H就已经小于等于0了，我们应当调整R为R-dmax/D,这样可以解决上面问题，然后在这个回合的基础上，累计每分钟的伤害值，直到H小于或者等于0即可

  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <math.h>
  4. using namespace std;
  5. const int maxn=4*1e5+7;
  6. int damage[maxn];
  7. long long int sum[maxn]={0};
  8. long long int low=maxn;
  9. int main()
  10. {
  11.     long long int H;
  12.     long long int n;
  13.     scanf("%lld%lld",&H,&n);
  14.     long long int sum=0;
  15.     for(long long int i=0;i<n;i++)
  16.     {
  17.         scanf("%d",&damage[i]);
  18.         sum+=damage[i];
  19.         low=min(low,sum);
  20.     }
  21.     long long int oH=H;
  22.     for(long long int i=0;i<n;i++)
  23.     {
  24.         H+=damage[i];
  25.         if(H<=0)
  26.         {
  27.             printf("%d\n",i+1);
  28.             return 0;
  29.         }
  30.     }//判断第一个回合
  31.     long long int round=1;
  32.     long long int minute=0;
  33.     if(H>=oH)
  34.     {
  35.         printf("-1");
  36.     }
  37.     else
  38.     {
  39.         H=oH;
  40.         round=H/abs(sum);
  41.         long long int base=abs(low/sum);
  42.         H+=(round-base)*sum;
  43.         round-=base;
  44.         long long int result=round*n;
  45.         for(int i=0;;i++)
  46.         {
  47.             H+=damage[i%n];
  48.             result++;
  49.             if(H<=0)
  50.             {
  51.                 printf("%lld",result);
  52.                 break;
  53.             }
  54.         }
  55.     }
  56.     return 0;
  57. }

F.Same Sum Blocks

1.题目

F

2.解答

由于F1和F2的题目几乎是一样的，所以我们放在一起来讲了。

首先我们记录下，从数组开头开始，所有和的可能的情况。并对其按照值的大小进行排列，如果值相同则会按照，右边节点从小到大排列，这里应用了贪心的思想，如果保证右边节点最小，那么右边的序列会更长一点，相同的可能也会更大一点。然后剩下的问题就相当于是，数组，求最大连续相同值的长度。

  1. #include <stdio.h>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <map>
  5. using namespace std;
  6. const int maxn=1507;
  7. vector<pair<int,int> >ans;
  8. vector<pair<int,int> >ans1;
  9. struct node
  10. {
  11.     int num;
  12.     int left;
  13.     int right;
  14. };
  15. node test[maxn];
  16. node sum[1000*maxn];
  17. bool cmp(node a,node b)
  18. {
  19.     if(a.num==b.num)
  20.     {
  21.         return a.right<b.right;
  22.     }
  23.     return a.num<b.num;
  24. }
  26. int main()
  27. {
  28.     int n;
  29.     scanf("%d",&n);
  30.     for(int i=1;i<=n;i++)
  31.     {
  32.         scanf("%d",&test[i].num);
  33.         test[i].left=i;
  34.         test[i].right=i;
  35.     }
  36.     int count=1;
  37.     for(int i=0;i<n;i++)
  38.         for(int j=1;j+i<=n;j++)
  39.         {
  40.             for(int k=i;k>=0;k--)
  41.             {
  42.                 sum[count].num+=test[j+k].num;//求所有的段的和
  43.             }
  44.             sum[count].left=j;
  45.             sum[count].right=j+i;
  46.             count++;
  47.         }
  48.     ans1=vector<pair<int,int> >(n);
  49.     ans1.clear();
  50.     sort(sum+1,sum+count,cmp);
  51.     //for(int i=1;i<count;i++)
  52.     //{
  53.         //printf("%d %d %d\n",sum[i].num,sum[i].left,sum[i].right);
  54.     //} 
  55.     int high=-1;
  56.     for(int i=1;i<count;i++)
  57.     {
  58.         int tar=sum[i].num;
  59.         int r=sum[i].right;
  60.         int count=1;
  61.         ans1.push_back({sum[i].left,sum[i].right});
  62.         for(int j=1;;j++)
  63.         {
  64.             if(sum[i+j].num==tar)
  65.             {
  66.                 if(sum[i+j].left>r)//必须满足这个条件
  67.                 {
  68.                     r=sum[i+j].right;
  69.                     count++;
  70.                     ans1.push_back({sum[i+j].left,sum[i+j].right});
  71.                 }
  72.             }
  73.             else
  74.             {
  75.                 if(count>high)
  76.                 {
  77.                     high=count;
  78.                     ans=ans1;
  79.                 }
  80.                 ans1.clear();
  81.                 count=1;
  82.                 i=i+j-1;
  83.                 break;
  84.             }
  85.         }
  86.     }
  87.     printf("%d\n",ans.size());
  88.     for(auto it:ans)
  89.     {
  90.         printf("%d %d\n",it.first,it.second);
  91.     } 
  92.     return 0;
  93. }

G.Privatization of Roads in Treeland

1.题目

G

2.解答

这道题说实话，是真的没搞懂。所以去看了题解。整体来分析题目的意思就是说，在n个城市中最多有k个城市的两条或者两条以上的道路被同一个公司承包。我们将道路被一个公司承包想象为为这条道路染色。根据Dirichlet’s principle。当给图的边染色的时候，如果染色的种类小于最大度数，那么至少有一个点的两条边会染上相同的颜色。这一点还是比较容易证明的。同时我们还可以得到，度数高于颜色的种类的点，都至少会有两条边被染上相同的颜色。(解题的关键所在)。剩下的内容就是dfs的内容。具体见代码注释。(codeforces给的标程)

  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. using namespace std;
  5. int n, k, r;
  6. vector<vector<pair<int,int>>> g;
  7. int D;
  8. vector<int> col;
  10. void dfs(int u, int p, int f) {
  11.     //u代表着当前遍历的点，
  12.     //p代表着遍历的上一个点，
  13.     //f表示进入该点的颜色是什么 
  14.     int color = 0;
  15.     //每一个点的边的颜色从0开始，
  16.     //其实从多少开始都一样 
  17.     for (auto e: g[u])
  18.         //遍历与该点向连的所有点 
  19.         if (p != e.first) {
  20.         //去掉回到上一个点的情况 
  21.             if (color == f) {
  22.                 color = (color + 1) % D;
  23.         //第一次要避免边的颜色与上一条重复 
  24.         //尽量为从该点出发的边上的颜色多一点 
  25.                 f = -1;
  26.             }
  27.             col[e.second] = color;
  28.         //为边染色 
  29.             dfs(e.first, u, color);
  30.             color = (color + 1) % D;
  31.         //下一条边要染不同的颜色
  32.         //因为只有D种
  33.         //所以要去循环 
  34.         }         
  35. }
  37. int main() {
  38.     cin >> n >> k;
  39.     g.resize(n);
  40.     vector<int> d(n);
  41.     for (int i = 0; i + 1 < n; i++) {
  42.         int x, y;
  43.         cin >> x >> y;
  44.         x--, y--;
  45.         g[x].push_back({y, i});
  46.         //此处为记录与该点相连的所有边的信息; 
  47.         g[y].push_back({x, i});
  48.         d[x]++, d[y]++;
  49.         //存储度数 
  50.     }
  51.     map<int,int> cnt;
  52.     for (int dd: d)
  53.         cnt[dd]++;
  54.     //记录度数为dd的点有几个 
  55.     int kk = n;
  56.     D = 0;
  57.     for (auto p: cnt)
  58.         if (kk > k)
  59.             D = p.first,
  60.             //p.first为度数 
  61.             kk -= p.second;
  62.             //p.second为个数，
  63.             //表示剩下的度数顶点中，
  64.             //比现在颜色多的个数，
  65.             //要保证这一部分的数量不超过k 
  66.         else
  67.             break;
  68.     col = vector<int>(n - 1);
  69.     dfs(0, -1, -1);    
  70.     cout << D << endl;
  71.     for (int i = 0; i + 1 < n; i++)
  72.         cout << col[i] + 1 << " ";
  73.     return 0; 
  74. }

发表评论

表情：
评论列表 （有 0 条评论，322人围观）

还没有评论，来说两句吧...

相关阅读