当前位置:网站首页>Algorithm template arrangement (1)

Algorithm template arrangement (1)

2020-11-09 22:37:54 Wind and snow

1. Merge sort board ( It includes finding the number of pairs in reverse order ):

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int a[maxn],tmp[maxn];
int ans=0;

void merge_sort(int l,int r)
{
    if(l>=r)
        return;
    int mid=l+r>>1;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    int i=l,j=mid+1,k=0;
    while(i<=mid&&j<=r)
    {
        if(a[i]<=a[j])
            tmp[k++]=a[i++];
        else
        {
          ans+=mid-i+1;
          tmp[k++]=a[j++];
        }
    }
    while(i<=mid)
        tmp[k++]=a[i++];
    while(j<=r)
        tmp[k++]=a[j++];
    for(i=l,j=0;i<=r;i++,j++)
        a[i]=tmp[j];
}


int main()
{
    int i,j,n;
    cin>>n;
    for(i=0;i<n;i++)
        cin>>a[i];
    merge_sort(0,n-1);
    cout<<ans<<endl;
    return 0;
}

2. Prefix and array board

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int n,m,q;
int a[maxn][maxn],sum[maxn][maxn];

int main()
{
    int i,j;
    int x,y,x2,y2;
    cin>>n>>m>>q;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            cin>>a[i][j];
            sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
        }
    }
    while(q--)
    {
        cin>>x>>y>>x2>>y2;
        cout<<sum[x2][y2]-sum[x-1][y2]-sum[x2][y-1]+sum[x-1][y-1]<<endl;
    }
    return 0;
}

3. Differential array board

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,m;
int a[maxn],b[maxn];

void insert(int l,int r,int c)
{
    b[l]+=c;
    b[r+1]-=c;
}

int main()
{
    int i,j,n,m;
    cin>>n>>m;
    for(i=1;i<=n;i++)
        cin>>a[i];
    for(i=1;i<=n;i++)
        insert(i,i,a[i]);
    while(m--)
    {
        int l,r,c;
        cin>>l>>r>>c;
        insert(l,r,c);
    }
    for(i=1;i<=n;i++)
    {
        b[i]+=b[i-1];
        cout<<b[i]<<" ";
    }
    cout<<endl;
    return 0;
}

4. Difference matrix board

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
int n,m,q;
int a[maxn][maxn],b[maxn][maxn];

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

int main()
{
    int i,j;
    cin>>n>>m>>q;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            cin>>a[i][j];
            insert(i,j,i,j,a[i][j]);
        }
    }
    while(q--)
    {
        int x1,y1,x2,y2,c;
        cin>>x1>>y1>>x2>>y2>>c;
        insert(x1,y1,x2,y2,c);
    }
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
            cout<<b[i][j]<<" ";
        }
    }
    cout<<endl;
    return 0;
}

 5. The board is divided into two parts ( When there is a l=mid, Need to put mid=(l+r+1)/2, Do plus 1 Handle , Otherwise, it will fall into a dead cycle )

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n,q,k;
int a[maxn];


int main()
{
    int i,j;
    cin>>n>>q;
    for(i=0;i<n;i++)
        cin>>a[i];
    while(q--)
    {
        cin>>k;
        int l=0,r=n-1,mid;
        while(l<r)
        {
            mid=(l+r)/2;
            if(a[mid]>=k)
                r=mid;
            else
                l=mid+1;
        }
        if(a[r]==k)
        {
            cout<<r<<" ";
            l=r;r=n-1;
            while(l<r)
            {
                mid=(l+r+1)/2;
                if(a[mid]<=k)
                    l=mid;
                else
                    r=mid-1;
            }
            cout<<l<<endl;
        }
        else
        {
            cout<<"-1 -1"<<endl;
        }
    }

    return 0;
}

6. Double pointer board (i It's a quick pointer ,j It's a slow pointer ,j<i)

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
int n;
int a[maxn];

int main()
{
    int i,j;
    cin>>n;
    map<int,int>s;
    for(i=0;i<n;i++)
        cin>>a[i];
    int ans=0;
    for(i=0,j=0;i<n;i++)
    {
        s[a[i]]++;
        while(j<i&&s[a[i]]>1)
        {
            s[a[j]]--;
            j++;
        }
        ans=max(ans,i-j+1);
    }
    cout<<ans;
    return 0;
}

Little knowledge Tip

Add a little Tip:STL You can use this function to arrange all arrays in :std::next_permutation() To show all the permutations in the array

The other one is small Tip: The operation of Joseph Ring :s=(s+M)%i, This can quickly find the number of the last person left , Attach code

#include <bits/stdc++.h>
using namespace std;
 int M;
int main()
{
    int n,i, s = 0;
    scanf("%d%d", &n,&M);
    for ( i = 2; i <= n; ++i)
    {
        s = (s+M)%i;
        cout<<s<<endl;
    }
    printf("%d\n", s+1);
    return 0;
}

 

版权声明
本文为[Wind and snow]所创,转载请带上原文链接,感谢