头像

acmdyh




离线:23小时前


最近来访(84)
用户头像
蒟弱
用户头像
leimingze
用户头像
snkz5qing
用户头像
iChenwei
用户头像
15358022392
用户头像
WanderOvO
用户头像
从未看过满天繁星
用户头像
IEE__
用户头像
RyanMoriarty
用户头像
神明的救续
用户头像
填海难....填心更难
用户头像
余火
用户头像
苦行僧_7
用户头像
MartinHero
用户头像
acw-热河
用户头像
食物链生存法则
用户头像
acwing_4164
用户头像
放弃最轻松
用户头像
wayy
用户头像
Maxwell_20


acmdyh
3天前
/*无*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int main()
{
    int a[N],b[N];
    int n,m;cin>>n>>m;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<m;i++)cin>>b[i];

    int i=0,j=0;
    while(i<n&&j<m)
    {
        if(a[i]==b[j])i++;
        j++;
    }
    if(i==n)puts("Yes");
    else puts("No");
}



acmdyh
3天前

1.两个指针,要么同方向移动,要么相反方向,要看题目了

C++ 代码


#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N],b[N];
int main()
{
    int n,m,x;cin>>n>>m>>x;

    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=0;i<m;i++)cin>>b[i];

    for(int i=0,j=m-1;i<n;i++)//初始化这两个指针
    {
        //i从左向右
        //j从右向左
        while(j>=0&&a[i]+b[j]>x)//当什么情况时,j--,考虑清楚
        {
            j--;
        }
        if(a[i]+b[j]==x)
        {
            printf("%d %d",i,j);
            break;
        }
    }
    return 0;
}



acmdyh
3天前

题目思路:

1.本题的核心思想是双指针算法,i指针是快指针,j是慢指针,每当i指针i指针右移一位的时候,

其对应的元素的个数就需要++,

2.接下来介绍check函数,check函数的实现功能就是,当s[a[i]]>1的话,我们就持续j++,

且将s[a[j]]–,这一步绝对不能省。

3.第三步就是最后的操作了res = max(res, i - j + 1);

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N],s[N];
int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];

    int res=0;
    for(int i=1,j=1;i<=n;i++)
    {
        s[a[i]]++;
        while(s[a[i]]>1)
        {
            s[a[j]]--;
            j++;
        }
        res=max(res,i-j+1);
    }
    printf("%d\n",res);
}



acmdyh
3天前

题目思路:

1.在输入时直接insert()

2.q次操作insert()

3.利用b[][]本身进行前缀和运算,求得矩阵最后结果,b[i][j]=b[i][j]+b[i][j-1]+b[i-1][j]-b[i-1][j-1];

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000+10;
long long b[N][N],a[N][N];

void inster(int x1,int y1,int x2,int y2,int c)
{
    b[x1][y1]+=c;
    b[x2+1][y1]-=c;
    b[x1][y2+1]-=c;
    b[x2+1][y2+1]+=c;
}

int main()
{
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    scanf("%lld ",&a[i][j]);

    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    inster(i,j,i,j,a[i][j]);

    while(k--)
    {
        int x1,x2,y1,y2,c;
        scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&c);
        inster(x1,y1,x2,y2,c);
    }


    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    b[i][j]=b[i][j]+b[i][j-1]+b[i-1][j]-b[i-1][j-1];//b[i][j]是单个元素,b[i][j-1],b[i-1][j],b[i-1][j-1]是前缀和


    for(int i=1;i<=n;i++)
    {
    for(int j=1;j<=m;j++)
    {
    printf("%lld ",b[i][j]);
    }
    printf("\n");
    }
    return 0;
}
/*

            [x1,y1]+c          [x1,y2][x1,y2+1]-c



            [x2,y1]            [x2,y2]
            [x2+1,y1]-c               [x2+1,y2+1]+c

*/




acmdyh
3天前

题目思路:

目的:让一组数的某些区间加上c,重复多次,求后来的结果

差分数组d[i]=a[i]-a[i-1]

数组a[i]是前i个d[]的前缀和

关键:d[l]+=c;d[r+1]-=c;

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N],d[N];
void div(int l,int r,int c)
{
    d[l]=d[l]+c;
    d[r+1]=d[r+1]-c;
}
int main()
{
    int n,q;cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        d[i]=a[i]-a[i-1];//a[i]是d[i]的前缀和
    }
    while(q--)
    {
        int l,r,c;cin>>l>>r>>c;
        div(l,r,c);
    }
    for(int i=1;i<=n;i++)
    {
        a[i]=a[i-1]+d[i];
        printf("%d ",a[i]);
    }

}



acmdyh
3天前

题目思路:

二维前缀和:先计算左上方向的元素,即sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];

目的:求出[x1,y1]到[x2,y2]的和,即sum[x2][y2]+sum[x1-1][y1-1]-sum[x1-1][y2]-sum[x2][y1-1];

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int a[N][N],sum[N][N];
int main()
{
    int n,m;cin>>n>>m;
    int tt;cin>>tt;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        cin>>a[i][j];

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];

    while(tt--)
    {
        int x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        printf("%d\n",sum[x2][y2]+sum[x1-1][y1-1]-sum[x1-1][y2]-sum[x2][y1-1]);
    }
}



acmdyh
3天前

题目思路:

前缀和思想:求出前i个元素的和,即sum[i];

目的:求某一段区间的和,即sum[r]-sum[l-1];

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N];
int sum[N];
int main()
{
    int n;cin>>n;
    int tt;cin>>tt;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    while(tt--)
    {
        int l,r;cin>>l>>r;
        printf("%d\n",sum[r]-sum[l-1]);
    }
}



acmdyh
3天前

题目思路:

1.写题之前首先确定查找的是什么

2.数x的起始地址和终止地址

----------------------------------------------------------------------

理解:求x的两个边界,通过mid判断边界在那边,最后求出边界

A.求左端点(注意,逻辑上的):

if(a[mid]<=x)如果Mid满足左侧性质,那么说明边界x在区间[mid,r]

else如果Mid不满足左侧性质,那么说明边界x在区间[l,mid-1];

B.求右端点(注意,逻辑上的):

if(a[mid]>=x)如果Mid满足右侧性质,那么说明边界x在区间[l,mid]

else如果Mid不满足右侧性质,那么说明边界x在区间[mid+1,r];

----------------------------------------------------------------------

3.关于二分模板需要注意的是:

---------------------------------------------------------------------

l=mid----> mid=l+r+1>>1----->写在while内;

r=mid----> mid=l+r>>1----->写在while内;

--------------------------------------------------------------------

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int a[N];
int main()
{

    int n,tt;cin>>n>>tt;
    for(int i=0;i<n;i++)cin>>a[i];
    while(tt--)
    {
        int x;cin>>x;
        int l=0,r=n-1;
         while(l<r)
         {
            int mid=(l+r)>>1;
            if(a[mid]>=x)r=mid;
            else l=mid+1;
         }

        if(a[l]!=x)printf("-1 -1\n");
        else 
            {
            printf("%d ",l);
            int l=0,r=n-1;
             while(l<r)
                {
                 int mid=(l+r+1)>>1;
                 if(a[mid]<=x) l=mid;
                 else r=mid-1;
                }
                printf("%d\n",l);
            }
    }

}



/*
while(l<r)
{
    int mid=l+r>>1;
    if(check(mid))r=mid;
    else l=mid-1;
}




while(l<r)
{
    int mid=l+r+1>>1;
    if(check(mid)) l=mid;
    else r=mid-1;
}


*/



acmdyh
5天前

题目思路:

1.确定一段区间[l,r]

2.确定一个精度eps=-1e8

3.进行二分

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
int main()
{
    double n;cin>>n;
    double l=-1000,r=1000,mid;
    while(r-l>eps)
    {
        mid=(l+r)/2;
        if(mid*mid*mid<n)l=mid;
        else r=mid;
    }
    printf("%.6f\n",r);
}



acmdyh
5天前

题目思路:

1.将逆序对分成三类:

两个元素都在左边;

两个元素都在右边;

两个元素一个在左一个在右;

2.这个时候我们注意到一个很重要的性质,左右半边的元素在各自任意调换顺序,

是不影响第三步计数的,因此我们可以数完就给它排序。

这么做的好处在于,如果序列是有序的,会让第三步计数很容易。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int a[N];
long long mgs(int a[],int l,int r)
{
    if(l>=r)return 0;

    int mid=(l+r)>>1;
    long long res= mgs(a,l,mid)+mgs(a,mid+1,r);


    int temp[N],k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j])temp[k++]=a[i++];
        else 
        {
            temp[k++]=a[j++];
            res+=mid-i+1;
        }
    }
    while(i<=mid)temp[k++]=a[i++];

    while(j<=r)temp[k++]=a[j++];

    for(i=l,k=0;i<=r;i++,k++)
    a[i]=temp[k];


    return res;

}

int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int m=mgs(a,1,n);
    printf("%lld\n",m);
}