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

传送门

题意：

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

题解：

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

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

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

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

代码一：

 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 }

代码二：

 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单位，就可以使原来的两个点不重合了

代码：

 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 }

巴特西

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

最新文章

热门文章