您的位置: 首页  >  IT文章  >  2019牛客暑期多校训练营（第三场）B题、H题

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

分类: IT文章 • 2024-12-28 21:37:01

传送门

题意：

就是说给你一个由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
",s0+s1,s0+s1);
43     }
44     else if(s0<s1)
45     {
46         printf("%d %d
",maxx,s0*2);
47     }
48     else if(s0>s1)
49     {
50         printf("%d %d
",maxx,s1*2);
51     }
52     return 0;
53 }
View Code

代码二：

 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
",ans,min(cnt0,cnt1)*2);
48 
49     return 0;
50 
51 }
View Code

H题：

原文：https://blog.****.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
",c.x+off,c.y-1,d.x-off,d.y+1);
48 
49         else printf("%d %d %d %d
",c.x+off,c.y,d.x-off,d.y);
50 
51     }
52 
53     return 0;
54 
55 }
View Code

相关推荐