2019牛客ACM暑期多校第三场

B-Crazy Binary String （前缀和 +记录下标 On）

题目描述

ZYB loves binary strings (strings that only contains `0' and `1'). And he loves equal binary strings\textit{equal binary strings}equal binary strings more, where the number of `0' and the number of `1' in the string are equal.

ZYB wants to choose a substring from an original string  T\ T T so that it is an equal binary string\textit{equal binary string}equal binary string with the longest length possible. He also wants to choose a subsequence of  T\ T T which meets the same requirements.

A string  v\ v v is a substring of a string  w\ w w if  v\ v v is empty, or there are two integers  l\ l l and r (1≤l≤r≤∣w∣)r \ (1 \le l \le r \le |w|)r (1≤l≤r≤∣w∣) such that v=wlwl+1⋯wrv=w_lw_{l+1}\cdots w_rv=wl​wl+1​⋯wr​. A string  v\ v v is a subsequence of a string  w\ w w  if it can be derived from  w\ w w  by deleting any number (including zero) of characters without changing the order of the remaining characters. 

For simplicity, you only need to output the maximum possible length. Note that the empty string is both a substring and a subsequence of any string.

输入描述:

The first line of the input contains a single integer N (1≤N≤100000)N \ (1 \le N \leq 100000)N (1≤N≤100000), the length of the original string  T\ T T. The second line contains a binary string with exactly  N\ N N characters, the original string  T\ T T.

输出描述:

Print two integers  A\ A A and  B\ B B, denoting the answer for substring and subsequence respectively.

示例1

输入

复制

8
01001001

输出

复制

4 6

1.求连续的最长序列使0 1个数相等  2.求非连续的最长序列 使0 1个数相等

第二问并不难求，min(0的个数，1的个数)*2即可。

第一问不难想到前缀和，前缀和相同的两项索引相减 即子串长度，求最值。

n^2会T！n^2会T！n^2会T！

正解：On；扫一遍，记录每个前缀和数据对应的最小下标，不断更新ans。

注意：如果遇到字符0前缀和要减1的话，前缀和会出现负值，所以要把记录下标的数组开2倍大小，从中间操作。

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
int pre[2*N];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        memset(pre,inf,sizeof(pre));
        int tmp=N;
        pre[N]=0;
        int ans=0;
        int cnt=0;
        char c;
        getchar();
        for(int i=1;i<=n;i++)
        {
            c=getchar();
            if(c=='1')
            {
                tmp++;
                cnt++;
            }
            else
                tmp--;
            pre[tmp]=min(i,pre[tmp]);
            ans=max(i-pre[tmp],ans);
//            cout<<ans<<'\n';
        }
        cout<<ans<<' '<<min(cnt,n-cnt)*2<<'\n';
    }
    return 0;
}

E-Magic Line （几何水题）

题目描述

There are always some problems that seem simple but is difficult to solve.

ZYB got  N\ N N distinct points on a two-dimensional plane. He wants to draw a magic line so that the points will be divided into two parts, and the number of points in each part is the same. There is also a restriction: this line can not pass through any of the points.

Help him draw this magic line.

输入描述:

There are multiple cases. The first line of the input contains a single integer T (1≤T≤10000)T \ (1 \leq T \leq 10000)T (1≤T≤10000), indicating the number of cases. 

For each case, the first line of the input contains a single even integer N (2≤N≤1000)N \ (2 \leq N \leq 1000)N (2≤N≤1000), the number of points. The following $N$ lines each contains two integers xi,yi (∣xi,yi∣≤1000)x_i, y_i  \ (|x_i, y_i| \leq 1000)xi​,yi​ (∣xi​,yi​∣≤1000), denoting the x-coordinate and the y-coordinate of the  i\ i i-th point.

It is guaranteed that the sum of  N\ N N over all cases does not exceed 2×1052 \times 10^52×105.

输出描述:

For each case, print four integers x1,y1,x2,y2x_1, y_1, x_2, y_2x1​,y1​,x2​,y2​ in a line, representing a line passing through (x1,y1)(x_1, y_1)(x1​,y1​) and (x2,y2)(x_2, y_2)(x2​,y2​). Obviously the output must satisfy (x1,y1)≠(x2,y2)(x_1,y_1) \ne (x_2,y_2)(x1​,y1​)​=(x2​,y2​).

The absolute value of each coordinate must not exceed 10910^9109. It is guaranteed that at least one solution exists. If there are multiple solutions, print any of them.

示例1

输入

复制

1
4
0 1
-1 0
1 0
0 -1

输出

复制

-1 999000000 1 -999000001

仔细想想会发现这是一道水题

给一堆整点，求一条直线把这对点均分且这条直线不能压点。

由于可以随机输出任意一对点，还是整数，关键是这个题的x y还有范围！给你的一堆点的横纵坐标都在-1000~1000以内 

首先对点进行排序，x从小到大排，x相同时y从小到大排。然后让我们来看一下中间的两个点，假设一共n个点。

1.排序后第n/2个点和第n/2+1个点的横坐标如果不同的话 也就是说这些点可以按x坐标均分，并且中间两个点的横坐标至少差1（

因为都是整数），这时取第n/2个点的横坐标作为x1值和一个很大的数作为y1值（超出1000即可），取第n/2+1个点的横坐标作为x2值和-y1作为y2,得到两个点，输出就行。

2.如果中间两个点的横坐标相同，即这堆点不能按x坐标均分时，比较两点的纵坐标，如果相差大于1，可以直接选取第n/2个点的上面那个点和一个如同1中的点。如果相差小于1，取二者中间那个非整数点，分别向上加和向下减个相同的非整数（比如10000.5），得到两个纵坐标。

#include <bits/stdc++.h>
using namespace std;
struct point
{
    int x,y;
}s[1050];
bool cmp(point a,point b)
{
    if(a.x!=b.x)
        return a.x<b.x;
    else if(a.x==b.x&&a.y!=b.y)
        return a.y<b.y;
}
int main()
{
    int t,n,m;
    scanf("%d",&t);
    while(t--)
    {
        memset(s,0,sizeof(s));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d%d",&s[i].x,&s[i].y);
        sort(s+1,s+n+1,cmp);
        if(s[n/2].x!=s[n/2+1].x)
            cout<<s[n/2].x<<' '<<10000<<' '<<s[n/2+1].x<<' '<<-10000<<'\n';
        else
        {
            if(s[n/2+1].y-s[n/2].y>1)
                cout<<s[n/2].x-1<<' '<<10000<<' '<<s[n/2].x<<' '<<s[n/2].y+1<<'\n';
            else
                cout<<s[n/2].x-1<<' '<<s[n/2].y+10000<<' '<<s[n/2].x+1<<' '<<s[n/2].y-9999<<'\n';
        }
    }
    return 0;
}

F-Planting Trees 

题目描述

The semester is finally over and the summer holiday is coming. However, as part of your university's graduation requirement, you have to take part in some social service during the holiday. Eventually, you decided to join a volunteer group which will plant trees in a mountain.

To simplify the problem, let's represent the mountain where trees are to be planted with an N×NN \times NN×N grid. Let's number the rows 1\ 1 1 to N\ N N from top to bottom, and number the columns 1\ 1 1 to N\ N N from left to right. The elevation of the cell in the i\ i i-th row and j\ j j-th column is denoted by ai,ja_{i,j}ai,j​. Your leader decides that trees should be planted in a rectangular area within the mountain and that the maximum difference in elevation among the cells in that rectangle should not exceed M. In other words, if the coordinates of the top-left and the bottom-right corners of the rectangle are (x1,y1)(x_1,y_1)(x1​,y1​) and (x2,y2)(x_2,y_2)(x2​,y2​), then the condition ∣ai,j−ak,l∣≤M|a_{i,j} - a_{k,l}| \le M∣ai,j​−ak,l​∣≤M must hold for x1≤i,k≤x2, y1≤j,l≤y2x_1 \le i,k \le x_2, \ y_1 \le j,l \le y_2x1​≤i,k≤x2​, y1​≤j,l≤y2​. Please help your leader calculate the maximum possible number of cells in such a rectangle so that he'll know how many trees will be planted.

输入描述:

The input contains multiple cases. The first line of the input contains a single integer T (1≤T≤1000)T \ (1 \le T \le 1000)T (1≤T≤1000), the number of cases.
For each case, the first line of the input contains two integers N (1≤N≤500)N\ (1 \le N \le 500)N (1≤N≤500) and M (0≤M≤105)M\ (0 \le M \le 10^5)M (0≤M≤105). The following N lines each contain N integers, where the j\ j j-th integer in the i\ i i-th line denotes ai,j (1≤ai,j≤105)a_{i,j} \ (1 \le a_{i,j} \le 10^5)ai,j​ (1≤ai,j​≤105).
It is guaranteed that the sum of N3N^3N3 over all cases does not exceed 25⋅10725 \cdot 10^725⋅107.

输出描述:

For each case, print a single integer, the maximum number of cells in a valid rectangle.

示例1

输入

复制

2
2 0
1 2
2 1
3 1
1 3 2
2 3 1
3 2 1

输出

复制

1
4

待补。