[关闭]
@wwwqeqeqeqe 2019-04-26T12:55:04.000000Z 字数 5281 阅读 683

Codeforces Round #551 (div.2)

codeforces

A Serval and Bus

题目大意：

给你n个数据和Serval到达车站的时间。接下来n行，每行输出公交车第一班到车站的时间以及之后每隔t分钟就会再来一班，问Serval会上哪一种车？如果有多种答案，任意输出其中一种。

解题思路：

暴力算出每种车在Serval到达车站后的第一班车到车站的时间，再任意输出其中时间最早的那一班车的号数。

代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. const int INF=0x3f3f3f3f;
  5. const int maxn=1e5+5;
  7. int n,t,x,y,ans[maxn];
  9. int main()
  10. {
  11.     cin >> n >> t;
  12.     for(int i=0;i<n;i++)
  13.     {
  14.         cin >> x >> y;
  15.         if(x >= t)
  16.             ans[i]=x;
  17.         else
  18.         {
  19.             int p=t-x;
  20.             if(p%y)
  21.             {
  22.                 p/=y;
  23.                 p++;
  24.                 p*=y;
  25.                 p+=x;
  26.             }
  27.             else
  28.             {
  29.                 p=t;
  30.             }
  31.             ans[i]=p;
  32.         }
  33.     }
  34.     int cnt=INF,mark=0;
  35.     for(int i=0;i<n;i++)
  36.     {
  37.         if(ans[i]<cnt)
  38.         {
  39.             cnt=ans[i];
  40.             mark=i+1;
  41.         }
  42.     }
  43.     cout << mark << endl;
  44. }

B Serval and Toy Bricks

题目大意：

给出一个图形的长宽高，并给出前视图、左视图看到的这个图形每个位置的高度，再给出俯视图看到的每个方格内是否有物品，输出这个图形本来的模样。如有多个结果，任意输出其中一个

解题思路：

因为题目给出了这个图形的正视图和左视图，我们就能具体到第几行第几列最多有多少个格子，再通过俯视图给出的信息，删去其中不满足条件的，就能够得到我们需要的图形之一。

代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. const int maxn=1e2+5;
  6. int n,m,h;
  7. int x;
  8. int mp[maxn][maxn];
  10. int main()
  11. {
  12.     cin >> n >> m >> h;
  13.     memset(mp,0x3f,sizeof(mp));
  14.     for(int i=0;i<m;i++)
  15.     {
  16.         cin >> x;
  17.         for(int j=0;j<n;j++)
  18.         {
  19.             mp[j][i]=min(mp[j][i],x);
  20.         }
  21.     }
  22.     for(int i=0;i<n;i++)
  23.     {
  24.         cin >> x;
  25.         for(int j=0;j<m;j++)
  26.         {
  27.             mp[i][j]=min(mp[i][j],x);
  28.         }
  29.     }
  30.     for(int i=0;i<n;i++)
  31.     {
  32.         for(int j=0;j<m;j++)
  33.         {
  34.             cin >> x;
  35.             if(x == 0)
  36.             {
  37.                 mp[i][j]=0;
  38.             }
  39.         }
  40.     }
  41.     for(int i=0;i<n;i++)
  42.     {
  43.         for(int j=0;j<m-1;j++)
  44.         {
  45.             cout << mp[i][j] << " ";
  46.         }
  47.         cout << mp[i][m-1] << endl;
  48.     }
  49.     return 0;
  50. }

C Serval and Parenthesis Sequence

题目大意：

给出字符串的总长度n以及n个带'(',')','?'的字符串，问是否能通过改变其中的'?'，带得到前1，前2，前3......前n-1个左右括号都不满足括号匹配但整个字符串满足。

解题思路：

因为他要保证前面的括号都不满足括号匹配单最后结果满足，我们可以利用贪心的方法，将最左边的几个？变为(，使整个字符串的(数量等于n/2，再将剩下的？变为)，最后判断变完后的字符串是否满足题目要求。

代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. const int maxn=3e5+5;
  6. int n,l,r;
  7. char s[maxn];
  9. int main()
  10. {
  11.     cin >> n;
  12.     cin >> s;
  13.     if(n%2)
  14.     {
  15.         cout << ":(" << endl;
  16.     }
  17.     else
  18.     {
  19.         l=r=n/2;
  20.         for(int i=0; i<n; i++)
  21.         {
  22.             if(s[i] == '(')
  23.             {
  24.                 l--;
  25.             }
  26.             else if(s[i] == ')')
  27.                 r--;
  28.         }
  29.         if(l<0 || r<0)
  30.         {
  31.             cout << ":(" << endl;
  32.         }
  33.         else
  34.         {
  35.             for(int i=0; i<n; i++)
  36.             {
  37.                 if(s[i] == '?')
  38.                 {
  39.                     if(l)
  40.                     {
  41.                         l--;
  42.                         s[i]='(';
  43.                     }
  44.                     else
  45.                     {
  46.                         r--;
  47.                         s[i]=')';
  48.                     }
  49.                 }
  50.             }
  51.             l=0;
  52.             int mark=0;
  53.             for(int i=0; i<n; i++)
  54.             {
  55.                 if(s[i] == '(')
  56.                     l++;
  57.                 else
  58.                     l--;
  59.                 if(i!=n-1 && l <= 0)
  60.                 {
  61.                     mark=1;
  62.                     break;
  63.                 }
  64.             }
  65.             if(mark == 0)
  66.                 cout << s << endl;
  67.             else
  68.                 cout << ":(" << endl;
  69.         }
  70.     }
  71.     return 0;
  72. }

D Serval and Rooted Tree

题目大意：

给出一棵树，并且这棵树存在k个叶子节点，然后对这k个叶子节点赋予1~k之间的数字，不能重复。在普通节点上，有0、1两个权值，1表示对当前节点所有的孩子节点求最大值，0取最小值。最后使1节点的值最大。

解题思路：

设d[x]=k表示节点x能够到达的x的子树中最大的叶子节点为第k大，如果x为叶子节点，那么显然d[x]=1，如果x节点的权值为1（及取最大值），那么x取他子节点中最大的那个，及d[x]=min(d[y])(y为x的子节点)。如果x节点的权值为0（及取最小值）那么没有办法，我们只能取所有x子节点的和才能使x取到的最小值最大，即d[x]=∑d[y]。

代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. const int INF=0x3f3f3f3f;
  5. const int maxn=3e5+5;
  7. int n;
  8. int mark[maxn],x,d[maxn];
  9. vector<int> t[maxn];
  10. int cnt=0;
  12. void dfs(int p)
  13. {
  14.     if(t[p].size() == 0)
  15.     {
  16.         d[p]=1;
  17.         cnt++;
  18.         return;
  19.     }
  20.     if(mark[p] == 1)
  21.     {
  22.         d[p]=INF;
  23.         for(int i=0;i<t[p].size();i++)
  24.         {
  26.             dfs(t[p][i]);
  27.             d[p]=min(d[p],d[t[p][i]]);
  28.         }
  29.     }
  30.     else
  31.     {
  32.         for(int i=0;i<t[p].size();i++)
  33.         {
  34.             dfs(t[p][i]);
  35.             d[p]+=d[t[p][i]];
  36.         }
  37.     }
  38. }
  40. int main()
  41. {
  42.     cin >> n;
  43.     for(int i=1;i<=n;i++)
  44.     {
  45.         cin >> mark[i];
  46.     }
  47.     for(int i=2;i<=n;i++)
  48.     {
  49.         cin >> x;
  50.         t[x].push_back(i);
  51.     }
  52.     dfs(1);
  53.     cout << cnt+1-d[1] << endl;
  54.     return 0;
  55. }

E Serval and Snake

题目大意：

这个题是一道交互题。题目给你一个n*n的图，图中有一条蛇，你可以通过最多2019次查找，查询任意一个矩形，系统会告诉你蛇身穿过矩形边界的次数。你最后告诉系统，你找到的蛇的头尾分别在哪。

解题思路：

根据题目，我们可以知道，如果我们查询的结果为偶数，那么说明蛇的头尾都在矩形内或者都在矩形外。当查询结果为奇数时，则头尾一外一内。那么，我们先从列开始，设矩形的一个角为(1,1),另一个点为(n,i)，当我们对i进行枚举，查询到刚好使结果为奇数时，说明这里有一个点的列坐标为当前的i，同理，我们反向进行搜索，得到另一个列坐标i2，即为另一个点的列坐标。找到两个点的列坐标后，我们通过二分查找在寻找两个点的行坐标（同样按照返回值的奇偶数值来判断）。最后确定两个点，即为我们的答案。如果一开始查找列坐标是，没有找到满足条件的列坐标，那么，我们可以确定，蛇的头尾列坐标是同一个，我们就另外通过行坐标来进行相同操作判断两个点的行坐标分别是多少，最后同样通过二分查找来寻找我们需要的列坐标。

代码：

  1. #include<bits/stdc++.h>
  2. using namespace std;
  4. int n;
  5. int ax1,ax2,ay1,ay2;
  6. int x,i,j;
  8. int main()
  9. {
  10.     cin >> n;
  11.     for(i=1; i<n; i++)
  12.     {
  13.         printf("? 1 1 %d %d\n",n,i);
  14.         fflush(stdout);
  15.         scanf("%d",&x);
  16.         if(x&1)
  17.             break;
  18.     }
  19.     if(i != n)
  20.     {
  21.         for(j=n; j>1; j--)
  22.         {
  23.             printf("? 1 %d %d %d\n",j,n,n);
  24.             fflush(stdout);
  25.             scanf("%d",&x);
  26.             if(x&1)
  27.                 break;
  28.         }
  29.         int l=1,r=n;
  30.         while(l<r)
  31.         {
  32.             int mid=(l+r+1) >> 1;
  33.             printf("? %d %d %d %d\n",mid,i,n,i);
  34.             fflush(stdout);
  35.             scanf("%d",&x);
  36.             if(x&1)
  37.                 l=mid;
  38.             else
  39.                 r=mid-1;
  40.         }
  41.         ax1=r,ay1=i;
  42.         l=1,r=n;
  43.         while(l<r)
  44.         {
  45.             int mid=(l+r+1) >> 1;
  46.             printf("? %d %d %d %d\n",mid,j,n,j);
  47.             fflush(stdout);
  48.             scanf("%d",&x);
  49.             if(x&1)
  50.                 l=mid;
  51.             else
  52.                 r=mid-1;
  53.         }
  54.         ax2=r,ay2=j;
  55.     }
  56.     else
  57.     {
  58.         for(i=1; i<n; i++)
  59.         {
  60.             printf("? 1 1 %d %d\n",i,n);
  61.             fflush(stdout);
  62.             scanf("%d",&x);
  63.             if(x&1)
  64.                 break;
  65.         }
  66.         for(j=n; j>1; j--)
  67.         {
  68.             printf("? %d 1 %d %d\n",j,n,n);
  69.             fflush(stdout);
  70.             scanf("%d",&x);
  71.             if(x&1)
  72.                 break;
  73.         }
  74.         int l=1,r=n;
  75.         while(l<r)
  76.         {
  77.             int mid=(l+r+1) >> 1;
  78.             printf("? %d %d %d %d\n",i,mid,i,n);
  79.             fflush(stdout);
  80.             scanf("%d",&x);
  81.             if(x&1)
  82.                 l=mid;
  83.             else
  84.                 r=mid-1;
  85.         }
  86.         ax1=i,ay1=r;
  87.         l=1,r=n;
  88.         while(l<r)
  89.         {
  90.             int mid=(l+r+1) >> 1;
  91.             printf("? %d %d %d %d\n",j,mid,j,n);
  92.             fflush(stdout);
  93.             scanf("%d",&x);
  94.             if(x&1)
  95.                 l=mid;
  96.             else
  97.                 r=mid-1;
  98.         }
  99.         ax2=j,ay2=r;
  100.     }
  101.     printf("! %d %d %d %d\n",ax1,ay1,ax2,ay2);
  102.     return 0;
  103. }

F Serval and Bonus Problem

题目大意：

在一条长度为L的数列上随机放n个线段，求被至少k条线段覆盖的区间的总长度期望。

解题思路：

首先可以发现，这n个线段的2*n个端点可以把线段分成2*n+1段，因为端点是随机的，所以每一段期望是相同的，都是l/(2*n+1)。所以，只需要计算每一段被至少k段区间覆盖的概率。我们假设区间长度为1，最后结果乘以l，设d[i][j][k]表示前i个点中有j个点还没有匹配成线段，k只有0或1,表示x点放了还是没放。那么，我们可以得到：
dp[i+1][j+1][k]+=dp[i][j][k](该点作为左端点)
dp[i+1][j-1][k]+=dp[i][j][k](该点作为右端点)
dp[i+1][j][1]+=dp[i][j][0](j>=k)(该点作为x，保证至少被k条线段覆盖)
最后，我们要将方案数除以总数才是期望。

代码：

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. typedef long long ll;
  5. const int maxn = 4e3 + 5;
  6. const int mod = 998244353;
  8. ll fac[maxn];
  9. int dp[maxn][maxn][2];
  11. void add(int &x,int y)
  12. {
  13.     x = (x+y)%mod;
  14. }
  16. ll quick_pow(ll x,ll y)
  17. {
  18.     ll ans = 1;
  19.     while(y)
  20.     {
  21.         if(y&1)
  22.             ans = ans*x%mod;
  23.         y >>= 1;
  24.         x = x*x%mod;
  25.     }
  26.     return ans;
  27. }
  29. int main()
  30. {
  31.     int n,k,L;
  32.     cin >> n >> k >> L;
  33.     fac[0] = dp[0][0][0] = 1;
  34.     for(int i=1; i<maxn; i++)
  35.         fac[i] = fac[i-1]*i%mod;
  36.     int c = 2*n + 1;
  37.     for(int i=0; i<c; i++)
  38.     {
  39.         for(int j=0; j<=i; j++)
  40.         {
  41.             add(dp[i+1][j+1][0],dp[i][j][0]);
  42.             add(dp[i+1][j+1][1],dp[i][j][1]);
  43.             if(j)
  44.             {
  45.                 add(dp[i+1][j-1][0],1ll*dp[i][j][0]*j%mod);
  46.                 add(dp[i+1][j-1][1],1ll*dp[i][j][1]*j%mod);
  47.             }
  48.             if(j>=k) add(dp[i+1][j][1],dp[i][j][0]);
  49.         }
  50.     }
  51.     ll ans = fac[n]*quick_pow(2,n)%mod*dp[c][0][1]%mod*L%mod;
  52.     cout << ans*quick_pow(fac[c],mod-2)%mod << endl;
  53.     return 0;
  54. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注