Acwing50+Acwing51周赛+Acwing3493.最大的和（未完结）

Acwing50:

                                                                        第一题：

每周一次打卡题，下面用了哈希的思想。

#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;
}

第二题：

 暴力枚举的话时间复杂度O（n*m）超出时间限制

思路：在n种选取一个固定区间后开始分情况讨论，假设第二个端点在区间右边，那么选取区间的左端点越靠右边越好（第一次选取区间左右端点固定）。同理假设第二个端点在区间左边，那么选取区间的右端点越靠左边越好。

可以看出，再找第二组区间时两个区间是相对固定的，也就是第二组选定的区间是不会再改变的，这样我们就可以枚举第一组区间

下面是代码：

#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表示第一组区间种最靠左的右端点，b表示最靠左的右端点
    while (n -- )
    {
        int l,r;
        scanf("%d%d", &l, &r);
        a=min(a,r);
        b=max(b,l);
    }
    //选取完两个区间
    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);
    }
    //判断上述的情况
    cout<<res;
    return 0;
}

第三题：需要用到dp，暂时不会；

Acwing51周赛

第一题：

 打卡题。

#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;
}

第二题：

 直接上代码了，这里用到并查集，后面要注意判重

#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};//偏移量
int get(int x,int y)//将每个方格对应一个唯一整数
{
    return x*m+y;
}
int find(int x)  // 并查集
{
    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]);//读入地图
    for(int i=0;i<n*m;i++) p[i]=i,s[i]=1;//初始化并查集
    
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)//枚举每个元素及其四个方向
            if(g[i][j]=='.')//判断是不是空地
                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(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(".");//判断周围四个元素，并判重
        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)//开始判重
            {
                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;
}

接下来是3493

先解释一下题目意思，在一个整型数列中选取长度为k的区间，把其中的数字不可选的换为可选的，再加上区间外可选的，之后求总和。这样题目就变成了，可选的+区间里改变的即为答案。

本题解法有两个，先来第一种，双指针

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//记得写ll，不然会爆
const int N=100010;

int a[N],b[N];//a用于存放数，b用于存放状态

int main(){
    int n,k;
    cin>>n>>k;
    ll sum=0,v=0,s=0;//sum为可选数的和，v为窗口内改变状态后最大的和，s为当前区间的和
    for(int i=0;i<n;i++) scanf("%d",&a[i]);//输入a
    for(int i=0;i<n;i++){
        scanf("%d",&b[i]);//输入b
        if(b[i]) sum+=a[i];//计算sum
    }
    for(int i=0;i<n;i++){
        if(b[i]==0) s+=a[i];//如果该数状态为0即不可选，则其状态改变并加上
        if(i>=k&&b[i-k]==0) s-=a[i-k];//当i大于等于k时，窗口开始向右滑动，每次滑动减去左边状态为0的数
        v=max(v,s);//窗口最大和
    }
    printf("%lld",sum+v);
    return 0;
}

接着是前缀和

#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;//前缀和操作，如果状态可选直接加上，并改为不可选
        if(state)
        {
            ans+=a[i];
            a[i] = 0;
        }
        s[i] = s[i-1]+a[i];
    }
    ll res = 0;
    // 枚举每一个滑动窗口左端点
    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;
}

此次的题解有些问题，写完一直觉得不满意，之后会再补。