2019牛客暑期多校训练营（第三场）B题、H题

àì夳堔傛蜴生んèń 2023-10-11 09:32 21阅读 0赞

[传送门][Link 1]

题意：

就是说给你一个由0或1组成的字符串，让你找出来一个0的数量和1的数量相等的子字符串

题解：

可以把0当作-1，把1当作1来计算字符串的前缀和

这样的话，当两个位置的前缀和的值相同的时候，那么这两个位置中间的部分就满足题意，除此之外前缀和为0的地方也满足题意

因为这是前缀和，当两个位置前缀和相同就可以让后一个减去前一个前缀和，那么这中间一段便是0和1相同的长度

为了防止出现负数下标，可以让计算出来的前缀和加上一个大正数

代码一：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<string.h>
     3 #include<stdlib.h>
     4 #include<algorithm>
     5 using namespace std;
     6 char a[100005];
     7 int ans[200005][2];
     8 int sum[100005];
     9 int main()
    10 {
    11     int n;
    12     int s1=0,s0=0,maxx=0;
    13     sum[0]=0;
    14     scanf("%d",&n);
    15     scanf("%s",a);
    16     ans[100000][0]=-1;
    17     for(int i=0;i<n;i++)
    18     {
    19         if(a[i]=='1')
    20         {
    21             s1++;
    22             sum[i]=sum[i-1]+1;
    23         }
    24         else
    25         {
    26             s0++;
    27             sum[i]=sum[i-1]-1;
    28         }
    29         if(ans[sum[i]+100000][0]==0)
    30         {
    31             ans[sum[i]+100000][0]=i;
    32         }
    33         else
    34         {
    35             ans[sum[i]+100000][1]=i;
    36 
    37             maxx=max(maxx,ans[sum[i]+100000][1]-ans[sum[i]+100000][0]);
    38         }
    39     }
    40     if(s0==s1)
    41     {
    42         printf("%d %d\n",s0+s1,s0+s1);
    43     }
    44     else if(s0<s1)
    45     {
    46         printf("%d %d\n",maxx,s0*2);
    47     }
    48     else if(s0>s1)
    49     {
    50         printf("%d %d\n",maxx,s1*2);
    51     }
    52     return 0;
    53 }

代码二：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 
     3 #define ll long long
     4 
     5 using namespace std;
     6 
     7 const int N=1e5+10;
     8 
     9 int pre[2*N];
    10 
    11 char s[N];
    12 
    13 int main(void)
    14 
    15 {
    16 
    17     int n,sum=0,cnt0=0,cnt1=0,ans=0;
    18 
    19     scanf("%d%s",&n,s+1);
    20 
    21     for(int i=1;i<=n;i++)
    22 
    23     {
    24 
    25         if(s[i]=='0') cnt0++,sum++;
    26 
    27         else cnt1++,sum--;
    28 
    29         if(sum==0)
    30 
    31         {
    32 
    33             if(ans<i) ans=i;
    34 
    35             continue;
    36 
    37         }
    38 
    39         if(pre[sum+n]==0) pre[sum+n]=i;
    40 
    41         else if(i-pre[sum+n]>ans)
    42 
    43              ans=i-pre[sum+n];
    44 
    45     }  
    46 
    47     printf("%d %d\n",ans,min(cnt0,cnt1)*2);
    48 
    49     return 0;
    50 
    51 }

H题：

原文：https://blog.csdn.net/code92007/article/details/97305323

给你N(N为偶数且N<=1e3)个不同的点(xi,yi)，|xi|,|yi|<=1e3

要求你输出两个整点，使之确定的直线，将平面划成两部分后，一边恰有一半

考虑按y增序排，y相同按x增序，也就是处理二维偏序的排序方式，

如果过n/2和n/2+1两个点的中点，画一条斜率为负，但近似水平的线，是可以将上下剖开的

但这个中点可能不是整点，所以直接用n/2和n/2+1两个点平移，

一个左移1e8单位，一个右移1e8单位，从而将直线拉平

但n/2和n/2+1两个点可能位于同一水平线上，这个时候，

左边的点再上移1单位，右边的点下移1单位，就可以使原来的两个点不重合了

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 
     3 using namespace std;
     4 
     5 const int N=1e3+5;
     6 
     7 const int off=1e8;
     8 
     9 int t,n;
    10 
    11 struct node
    12 
    13 {
    14 
    15     int x,y;
    16 
    17 }e[N],c,d;
    18 
    19 bool operator<(node a,node b)
    20 
    21 {
    22 
    23     return a.y<b.y||(a.y==b.y&&a.x<b.x);
    24 
    25 }
    26 
    27 int main()
    28 
    29 {
    30 
    31     scanf("%d",&t);
    32 
    33     while(t--)
    34 
    35     {
    36 
    37         scanf("%d",&n);
    38 
    39         for(int i=1;i<=n;++i)
    40 
    41         scanf("%d%d",&e[i].x,&e[i].y);
    42 
    43         sort(e+1,e+n+1);
    44 
    45         c=e[n/2];d=e[n/2+1];
    46 
    47         if(c.y==d.y)printf("%d %d %d %d\n",c.x+off,c.y-1,d.x-off,d.y+1);
    48 
    49         else printf("%d %d %d %d\n",c.x+off,c.y,d.x-off,d.y);
    50 
    51     }
    52 
    53     return 0;
    54 
    55 }

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11268230.html

[Link 1]: https://ac.nowcoder.com/acm/contest/883/B
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif