Acwing50+acwing51 weeks +acwing3493 Maximum sum (open)

Acwing50:

                                                                         The first question is ：

Punch in once a week , The following uses the idea of hashing .

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N],n;
int main()
{   
    int num;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>num;
        a[num]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(!a[i]) cout<<i<<endl;
    }
    return 0;
}

The second question is ：

  The time complexity of violent enumeration O（n*m） Time limit exceeded

Ideas ： stay n Select a fixed interval and start the discussion by case , Suppose the second endpoint is on the right side of the interval , Then the left end point of the selected interval is closer to the right, the better （ For the first time, the left and right endpoints of the interval are fixed ）. Similarly, suppose that the second endpoint is on the left of the interval , Then the right endpoint of the selected interval is closer to the left, the better .

It can be seen that , When looking for the second group of intervals, the two intervals are relatively fixed , That is, the selected interval of the second group will not be changed , So we can enumerate the first set of intervals

Here is the code ：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int INF=1e9;
int main()
{
    int n,m;
    cin>>n;
    int a=INF,b=-INF;//a Represents the leftmost right endpoint of the first group of interspecific species ,b Represents the leftmost right endpoint 
    while (n -- )
    {
        int l,r;
        scanf("%d%d", &l, &r);
        a=min(a,r);
        b=max(b,l);
    }
    // Select two intervals 
    int res=0;
    cin>>m;
    while (m -- )
    {
        int l,r;
        scanf("%d%d", &l, &r);
        if(b>r) res=max(res,b-r);
        if(a<l) res=max(res,l-a);
    }
    // Judge the above situation 
    cout<<res;
    return 0;
}

Third question ： Need to use dp, Not for the time being ;

Acwing51 Weekly game

The first question is ：

  Punch in question .

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
    int n;
    int p,q;
    int res=0;
    cin>>n;
    while(n--)
    {
        cin>>p>>q;
        if(q-p>=2) res++;
    }
    cout << res;
    return 0;
}

The second question is ：

  Go straight to the code , Here we use and look up sets , Pay attention to weight judgment later

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1010,M=N*N;
int n,m;
int p[M],s[M];
char g[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};// Offset 
int get(int x,int y)// Each square corresponds to a unique integer 
{
    return x*m+y;
}
int find(int x)  //  Union checking set 
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i=0;i<n;i++) scanf("%s",g[i]);// Read in map 
    for(int i=0;i<n*m;i++) p[i]=i,s[i]=1;// Initialize and query set 
    
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)// Enumerate each element and its four directions 
            if(g[i][j]=='.')// Judge whether it is an open space 
                for(int k=0;k<4;k++)
                {
                    int x=i+dx[k],y=j+dy[k];
                    if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]=='.')// Judge whether you crossed the line 
                    {
                        int a=get(i,j),b=get(x,y);
                        a=find(a),b=find(b);
                        if(a!=b)
                        {
                            s[b]+=s[a];
                            p[a]=b;
                        }
                    }
                }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        if(g[i][j]=='.') printf(".");// Judge the four surrounding elements , And sentenced to heavy 
        else
        {
            int father[4],cnt=0;
            for(int k=0;k<4;k++)
            {
                int x=i+dx[k],y=j+dy[k];
                if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]=='.')
                {
                    int a=get(x,y);
                    father[cnt++]=find(a);
                }
            }
            int sum=1;
            if(cnt)// Start weight judgment 
            {
                sort(father,father+cnt);
                cnt=unique(father,father+cnt)-father;
                for(int k=0;k<cnt;k++)
                sum+=s[father[k]];
            }
            printf("%d",sum%10);
        }
        puts("");
    }
    return 0;
}

Next is 3493

First explain the meaning of the topic , Select an integer sequence with a length of k The range of , Replace the non optional number with the optional number , Plus optional outside the interval , Then sum up . So the title becomes , Optional + What changes in the interval is the answer .

There are two solutions to this problem , Let's start with the first , Double pointer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Remember to write ll, Or it will explode 
const int N=100010;

int a[N],b[N];//a Used for storing numbers ,b For storage status 

int main(){
    int n,k;
    cin>>n>>k;
    ll sum=0,v=0,s=0;//sum Is the sum of optional numbers ,v Is the maximum sum after changing the state in the window ,s Is the sum of the current interval 
    for(int i=0;i<n;i++) scanf("%d",&a[i]);// Input a
    for(int i=0;i<n;i++){
        scanf("%d",&b[i]);// Input b
        if(b[i]) sum+=a[i];// Calculation sum
    }
    for(int i=0;i<n;i++){
        if(b[i]==0) s+=a[i];// If the number status is 0 That is, not optional , Then its state changes and 
        if(i>=k&&b[i-k]==0) s-=a[i-k];// When i Greater than or equal to k when , The window starts sliding to the right , Each slide minus the left state is 0 Number of numbers 
        v=max(v,s);// Window maximum and 
    }
    printf("%lld",sum+v);
    return 0;
}

Then the prefix and

#include<iostream>
#include<algorithm>
using namespace std;
const int N= 1000010;
typedef long long ll;
ll a[N],s[N],ans;
int n,k;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    cin>>a[i];

    int state=0;
    for(int i=1;i<=n;i++)
    {
        cin>>state;// Prefix and operation , If the status is optional, add , And change to not optional 
        if(state)
        {
            ans+=a[i];
            a[i] = 0;
        }
        s[i] = s[i-1]+a[i];
    }
    ll res = 0;
    //  Enumerate the left endpoint of each sliding window 
    for(int i=1;i<=n;i++)
    {
        int r = i+k-1;
        if(r>n) r=n;
        ll now = s[r]-s[i-1];
        if(now>res) res = now;
    }

    cout<<ans+res;

    return 0;
}

There are some problems in this solution , I'm not satisfied after writing , I'll make it up later .