Tag:Two points
Article From:https://www.cnblogs.com/sleepiest/p/9061661.html

0. is up to the door”

Two minutes and six companies

\(a\),Seek an integer\(x\) So that any length is greater than any one.\(x\) String\(b\) stay\(a\) There are up to 1 times in the number of times.
Two points + match. I’m using hash.
Core part: Judgment\(x\) Whether or not it is legal.

bool Check(reg int x){
    int tmp=0,m=1;
    for(reg int i=1;i<x;i++)
        m=m*27%Mod;
    for(reg int i=1;i<x;i++)
        tmp=(tmp*27+(A[i]-'a'+1))%Mod;
    for(reg int i=x;i<=len;i++){
        tmp=(tmp*27+(A[i]-'a'+1))%Mod;
        if(B[tmp])return 0;
        B[tmp]=1;
        tmp=((tmp-(A[i-x+1]-'a'+1)*m)%Mod+Mod)%Mod;
    }
    return 1;
}

2. [NOIP Fujian summer camp” series segmentation

For a given length of length,\(N\) Positive integer number series\(A\) ,It is now to be divided into\(M(M\le N)\) Segment and require each segment to be continuous, and the maximum value of each segment is minimum.
Two points + greed.

3.” with higher accuracy Division

If you don’t want to write high precision division, you can get two points, and then you need to write high precision multiplication.

4. TMZJZ8

Given total area length\(n\),And the required length of a single interval\(k\)(No interval can overlap and edges can not be intersected.\(q\) A second inquiry,\(q_i\) It is indicated that the point is not covered by any interval, and the minimum number of queries is required so that the interval number is less than the prescribed interval number.\(m\)。(Transfer from the school chief
Two points.
The core part: to judge whether the answer is legitimate.

bool vis[200005];
bool Check(int u){
    for(reg int i=1;i<=Q;i++)
        if(i>u)vis[A[i]]=0;
        else vis[A[i]]=1;
    int cnt=0,len=0;bool nei=0;
    for(reg int i=1;i<=N;i++){
        if(!vis[i]&&!nei)len++;
        else{
            if(nei)nei=0;
            len=0;
        }
        if(len==K){
            len=0;
            cnt++;
            nei=1;
        }
    }
    if(cnt<M)return 1;
    else return 0;
}

5. [2016NOIP Fujian summer camp” matrix

Given a given\(N\) That’s ok\(M\) A non negative integer matrix of a column to find the largest square submatrix, which satisfies:
The weight of each element in the matrix is more than 0.
On the premise that the above conditions are satisfied, the area of the matrix is the largest.
On the premise of meeting the above conditions, we choose the elements and the smallest ones.
Two points square side length, handle prefix and.
You can save a 01 matrix to save each number, (1) no (0) greater than 0. Then, when calculating, determine whether all the numbers of the selected intervals add up to the corresponding perfect square numbers.
My method is to set 0 to infinity.

6. water pour Supervisor

seek\(1<=i\dots j<=n\) bring\(a[j]>a[i]\) also\(a[j]%a[i]\) Maximum, output maximum.
This question…
You can do it without two points. (Orz nealchen)

#include<cstdio>
#define reg register
#define cmax(_,__) ((_)<(__)?(_)=(__),1:0)
using namespace std;
int N,M,A[200005],B[2000005],res;
int main(){
    scanf("%d",&N);
    for(reg int i=1;i<=N;i++){
        scanf("%d",&A[i]);
        cmax(M,A[i]);
        B[A[i]]=A[i];
    }
    for(reg int i=1;i<=M*2;i++)
        cmax(B[i],B[i-1]);
    for(reg int i=1;i<=N;i++)
        for(reg int j=A[i];j<=M;j+=A[i])
            cmax(res,B[j+A[i]-1]%A[i]);
    printf("%d\n",res);
    return 0;
}

7. summary”

And then do some more difficult two points. Try some new routines.

Link of this Article: Two point exercise – 20180519

Leave a Reply

Your email address will not be published. Required fields are marked *