NOIP-基础算法
2024-03-13 12:16:51 # OI # Note

尺取法

其实就是双指针法。

给一道例题找找感觉吧：

HDU2029判断回文串

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        string s;
        cin>>s;
        bool ans=true;
        int i=0,j=s.size()-1;
        while(i<j)
        {
            if(s[i]!=s[j])
            {
                ans=false;
                break;
            }
            i++,j--;
        }
        if(ans) cout<<"yes"<<endl;
        else cout<<"no"<<endl;
    }
    return 0;
}

尺取法可以解决滑动窗口问题，也可以进行数组去重。

指针不够的时候可以加；

二分法

这是一种非常考验边界处理细节的一种算法。

STL

在这里不多赘述，只可意会不可言传。

练习：

P1462通往奥格瑞玛的道路

二分+最短路

#include<bits/stdc++.h>
using namespace std;
const int N=50005,M=1000005;
int n,m,b;
int f[N],fir[N],cnt,dist[N],righ[N];
struct edge{
    int next,to,w;
}e[M];
const int MAX=1e9;
void add(int u,int v,int w)
{
    e[++cnt].next=fir[u];
    e[cnt].to=v;
    e[cnt].w=w;
    fir[u]=cnt;
}
struct node{
    int p,d;
    node(){}
    node(int a,int b){p=a;d=b;}
};
bool operator<(const node &a,const node &b)
{
    return a.d>b.d;
}
priority_queue<node>q;
int dijksta(int x)
{
    if(x<f[1]) return 0;
    for(int i=1;i<=n;i++)
        dist[i]=1e9;
    memset(righ,0,sizeof(righ));
    dist[1]=0;
    for(int i=1;i<=n;i++)
    {
        q.push(node(i,dist[i]));
    }
    for(int i=1;i<=n;i++)
    {
        while(righ[q.top().p]) q.pop();
        node now=q.top();
        int p=now.p;
        righ[p]=1;
        q.pop();
        for(int j=fir[p];j;j=e[j].next)
        {  
            int v=e[j].to;
            if(f[v]>x) continue;
            int d=e[j].w+dist[p];
            if(d<dist[v])
            {
                dist[v]=d;
                
                q.push(node(v,d));
            }
        }
    }
    if(dist[n]<=b) return 1;
    return 0;
}
int erfen()
{
    int l=1,r=MAX,mid=(l+r)>>1;
    int c;
    while(l<=r)
    {
        c=dijksta(mid);
        if(c!=0)
        {
            r=mid-1;
            mid=(l+r)>>1;
        }
        else
        {
            l=mid+1;
            mid=(l+r)>>1;
        }
    }
    return l;
}
int main()
{
    scanf("%d%d%d",&n,&m,&b);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&f[i]);
    }
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }
    if(dijksta(MAX)==0)
    {
        cout<<"AFK"<<endl;
        return 0;
    }
    cout<<erfen()<<endl;
}

P1824进击的奶牛

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e9;
int a[1000010],n,c;
bool P(int d)
{
    int k=0,last=-maxn;
    for(int i=1;i<=n;i++)
    {
        if(a[i]-last>=d)
        {
            last=a[i];
            k++;
        }
    }
    return k>=c;
}
int main()
{
    scanf("%d%d",&n,&c);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    int l=0,r=1e9,ans,mid;
    while(l<=r)
    {
        if(P(mid=l + r >> 1))
            ans=mid,l=mid+1;
        else
            r=mid-1;
    }
    printf("%d",ans);
}

P1419

#include<bits/stdc++.h>
const int N=100005;
using namespace std;
int n,s,t;
int a[100050];
double sum[N];
int q[N];
bool check(double k)
{
    int l=1,r=0;
    for(int i=1;i<=n;i++)//预处理前缀和（-k）
    {
        sum[i]=sum[i-1]+a[i]*1.0-k;
    }
    for(int i=s,p=0;i<=n;i++,p++)//单调队列
    {
        while(r>=l&&sum[q[r]]>sum[p]) r--;
        q[++r]=p;
        while(i-q[l]>t)++l;
        if(sum[i]-sum[q[l]]>=0) return 1;
    }
    return 0;
}
int main()
{
    cin>>n;
    cin>>s>>t;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    double l=-1e4,r=1e4,mid;
    while(r-l>1e-5)//实数二分
    {
        mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%.3f\n",l);
    return 0;
}

POJ3122

#include<stdio.h>
#include<math.h>
#include<iostream>
using namespace std;
double PI=acos(-1.0);
double a[100000];
int n,m;
bool check(double mid)
{
    int sum=0;//能切的PIE总数
    for(int i=1;i<=n;i++)
    {
        sum+=(int)(a[i]/mid);
    }
    if(sum>=m) return true;
    else return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        m++;
        double maxp=0;
        for(int i=1;i<=n;i++)
        {
            int r;
            scanf("%d",&r);
            a[i]=PI*r*r;
            if(maxp<a[i]) maxp=a[i];
        }
        double l=0,r=maxp;
        for(int i=1;i<=100;i++)
        {
            double mid=l+(r-l)/2;
            if(check(mid)) l=mid;
            else r=mid;
        }
        printf("%.4f\n",l);
    }
    return 0;
}

P1083

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+117;
int r[N],d[N],s[N],t[N],pre[N],ne[N];
int n,m;
bool check(int mid)
{
    memset(pre,0,sizeof(pre));
    for(int i=1;i<=mid;i++)
    {
        pre[s[i]]+=d[i];
        pre[t[i]+1]-=d[i];
    }
    for(int i=1;i<=n;i++)
    {
        ne[i]=ne[i-1]+pre[i];//利用差分数组求当天要租的教室
        if(ne[i]>r[i]) return false;
    }
    return true;
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%lld",&r[i]);
    for(int i=1;i<=m;i++)
        scanf("%lld%lld%lld",&d[i],&s[i],&t[i]);
    if(check(m))
    {
        cout<<"0";
        return 0;
    }
    int l=1,r=m;
    while(l<r)//等于后不用判断
    {
        int mid=(l+r)>>1;
        if(check(mid)) l=mid+1;
        else r=mid;//注意细节
    }
    printf("-1\n%lld",l);
    return 0;
}

P2678

#include<bits/stdc++.h>

using namespace std;

int L,N,M;
int ans;
int stone[500005];
int s[100000005]={0};

int f(int x)
{
	
	int size=0,take=0;
	s[0]=0;
	for(int i=1;i<=N;++i)
	{
		if(stone[i]-s[size]<x)
		{
			take++;
			continue;//去掉 
		}
		s[++size]=stone[i];	
	}
	if(L-s[size]<x)
	{
		size--;
		take++;        
	}
	return take<=M;
}
int main ()
{
	scanf("%d%d%d",&L,&N,&M);
	for(int i=1;i<=N;++i)
		scanf("%d",&stone[i]);
	int left=0,right=L+1;
	while(left+1<right)
	{
		int mid=(left+right)/2;
		if(f(mid)==1)
			left=mid;
		else
			right=mid;
	}
	ans=left;//***
	cout<<ans;
	return 0;
}

P1314

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+7;
long long ans=1e12+7;
int n,m,s,maxn=-1,sum;
int w[N],v[N],l[N],r[N];
int ren[N],rev[N],y;//数量前缀和，价值前缀和，y
bool check(int mid)
{
    y=0,sum=0;
    memset(ren,0,sizeof(ren));
    memset(rev,0,sizeof(rev));
    for(int i=1;i<=n;i++)
    {
        if(w[i]>=mid) ren[i]=ren[i-1]+1,rev[i]=rev[i-1]+v[i];
        else ren[i]=ren[i-1],rev[i]=rev[i-1];
    }
    for(int i=1;i<=m;i++)
        y+=(ren[r[i]]-ren[l[i]-1])*(rev[r[i]]-rev[l[i]-1]);
    sum=llabs(y-s);
    if(y>s) return true;
    else return false;
}
signed main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&w[i],&v[i]);
        maxn=max(maxn,w[i]);
    }
    for(int i=1;i<=m;i++)
        scanf("%lld%lld",&l[i],&r[i]);
    int l=0,r=maxn;
    while(l<=r)
    {
        int m=l+(r-l)/2;
        if(check(m)) l=m+1;
        else r=m-1;
        if(sum<ans) ans=sum;
    }
    printf("%lld",ans);
    return 0;
}

三分法

练习

P3382

#include<bits/stdc++.h>
using namespace std;
const double eps=1e-6;
int n;
double a[20];
double f(double x)
{
    double s=0;
    for(int i=n;i>=0;i--)
        s=s*x+a[i];
    return s;
}
int main()
{
    double l,r;
    scanf("%d%lf%lf",&n,&l,&r);
    for(int i=n;i>=0;i--) scanf("%lf",&a[i]);
    while(r-l>eps)
    {
        double k=(r-l)/3.0;
        double m1=l+k;
        double m2=r-k;
        if(f(m1)>f(m2)) r=m2;
        else l=m1;
    }
    printf("%.5f\n",l);
    return 0;
}

P3745

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+7;
int n,m,t[N],b[N];
ll A,B,C,ans;
ll calc1(int p)//将最晚公布成绩的时间调整到p所产生的不愉快度
{
    ll x=0,y=0;//x代表能提前改完卷子的[总提前天数和]但是由于不愉快度只由最后改完卷子的那一天决定，所以可以将提前改完的天数延后而使推迟改完的天数提前
    //y代表推迟改完卷子的[总推迟天数和]，意味着可以选择用x来填补y，使整体平均，使最晚那一天尽可能靠前
    for(int i=1;i<=m;i++)
    {
        if(b[i]<p) x+=p-b[i];
        else y+=b[i]-p;
    }
    if(A<B)//如果操作A（交换互补）的代价更低，那就能交换即交换，不能交换再新添人手
        return min(x,y)*A+(y-min(x,y))*B;
    else return y*B;//不如直接添人手代价更低
}
ll calc2(int p)//所有同学的在最后一天产生的不愉快总和
{
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        if(t[i]<p) sum+=(p-t[i])*C;//推迟的天数*C
    }
    return sum;
}
int main()
{
    cin>>A>>B>>C>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&t[i]);
    for(int i=1;i<=m;i++) scanf("%d",&b[i]);
    sort(b+1,b+m+1);
    sort(t+1,t+n+1);
    if(C>=1e16)//全部补充老师也比让学生不满意更优，那就调老师让学生满意
    {
        printf("%lld\n",calc1(t[1]));
        return 0;
    }
    ans=1e16;
    int l=1,r=N;
    while(r-l>2)//三分得到最小值所在的天的序号的区间
    {
        int m1=l+(r-l)/3;
        int m2=r-(r-l)/3;
        ll c1=calc1(m1)+calc2(m1);
        ll c2=calc1(m2)+calc2(m2);
        if(c1<=c2) r=m2;
        else l=m1;
    }
    for(int i=l;i<=r;i++)//枚举
    {
        ll x=calc1(i)+calc2(i);
        ans=min(ans,x);
    }
    printf("%lld",ans);
}

P1883

咕咕咕

倍增与ST

超级快的速度：O(log2n)O(log_2n)

原理与二分法相对，不多赘述。

倍增

利用二进制的“特性”，可以将一个数展开得到我们想要的“倍增形式”。

习题

P4155

这道题有道思路相仿的题目可以先做一下：P1803

对于本题：

  1. 断环为链。
  2. 贪心：选择一个区间，下一个区间的左端点必须小于等于这个区间的右端点，其中满足条件的下一个区间的右端点最大为最优。
  3. 倍增：快速查询走2i2^i步所能到达的最优的区间，避免暴力枚举。

定义go[s][i] 表示从第s个区间出发，走2i2^i个最优区间所到达的区间（战士的范围）。

所以首先需要预处理出go[][]。

复杂度：nlog2nnlog_2n

递推式：go[s][i]=go[go[s][i-1]][i-1]

总复杂度：2nlog2n2nlog_2n

code：

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=4e5+1;
struct yum{
    int id,l,r;
    bool operator<(const yum x) const{
        return l<x.l;//以左端点最小的为第一个
    }
}w[N*2];
int n2;//断环为链后的链长
int go[N][20],res[N];
void init()
{
    int nxt=1;
    for(int i=1;i<=n2;i++)//贪心求每个区间的下一个区间
    {
        while(nxt<=n2&&w[nxt].l<=w[i].r)
            nxt++;
        go[i][0]=nxt-1;//因为结束循环时多加了1
    }
    for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j<=n2;j++)
            go[j][i]=go[go[j][i-1]][i-1];
}
void get(int x)//从x出发
{
    int len=w[x].l+m,cur=x,ans=1;//len为以x为起点最远能走到的位置，ans为初始的起点战士
    for(int i=log2(N);i>=0;i--)
    {
        int pos=go[cur][i];
        if(pos&&w[pos].r<len)
        {
            ans+=1<<i;//区间数（即战士数）
            cur=pos;//跳到这个区间
        }
        res[w[x].id]=ans+1;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        w[i].id=i;
        scanf("%d%d",&w[i].l,&w[i].r);
        if(w[i].r<w[i].l) w[i].r+=m;//若右端点比左端点小，则说明这段区间包含需要断环的点，那就断，使得这段区间在链上可以正常表示
    }
    sort(w+1,w+1+n);
    n2=n;
    for(int i=1;i<=n;i++)
    {
        n2++;
        w[n2]=w[i];
        w[n2].l=w[i].l+m;//复制一份
        w[n2].r=w[i].r+m;//复制是为了对于8~2-->8~12的这种超出区间的递推的正确性
    }
    init();
    for(int i=1;i<=n;i++)
        get(i);//计算以每名战士为起点的最少人数
    for(int i=1;i<=n;i++)
        printf("%d ",res[i]);
    return 0;
}

ST

ST算法基于倍增原理，适用于求解静态空间的区间最值查询（RMQ）。

RMQ问题：给定长度为n的静态数列，做m次查询，每次给定一段区间[L,R]，求这段区间中的最值。

以最小值为例：

若一个大区间能被两个小区间覆盖，那么大区间的最值等于两个小区间的最值的最值（重合不影响）。

于是得到基本思路：

  1. 将序列拆分为若干个小区间，并预处理小区间的最值。
  2. 对任意区间进行最值查询，只需要找到覆盖它的两个小区间，由两个小区间的最值得出。

定义dp[s][k]=min(dp[s][k-1],dp[s+(1<<(k-1))][k-1])，

代表从ss开始的2k2^k的区间最值为从s开始的2k−12^{k-1}区间和从s+2k−1s+2^{k-1}开始的2k−12^{k-1}区间的最值。

递推关系实际是一个DP的过程，复杂度nlognnlogn。

区间[L,R]的长度为len=R-l+1，两个小区间的长度都为x，使得x≤lenx\le{len}并且2x≥len2x\ge{len}，这样可以保证覆盖。

于是令x=2kx=2^k，k=log2(x)k=log_2(x)，由于k是向下取整的，于是能满足x≤lenx\le{len}并且2x≥len2x\ge{len}的条件。

当然也可以写作k=(int)(log(double(R−L+1))/log(2.0))k=(int)(log(double(R-L+1))/log(2.0))（利用换底公式）。

如果嫌库函数慢的话也可以自己写log函数。

ST:

nlogn−(∑i=1logn2i)nlogn-(\sum^{logn}_{i=1}2^i)

P2251

/*Set*/
/*
#include<bits/stdc++.h>
using namespace std;
set<pair<int,int> > S;
int n ,m,a[100005]; 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		S.insert(make_pair(a[i],i));
		if(i>=m) 
		{
			if(i>m)
				S.erase(make_pair(a[i-m],i-m));
			printf("%d\n",(*S.begin()).first);
		}
 	}
 	return 0;
}
*/
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[100005];
int st[100005][23];
int LOG2[100005];
void init()
{
    LOG2[0]=-1;
    for(int i=1;i<=n;i++) LOG2[i]=LOG2[i>>1]+1;
    for(int i=1;i<=n;i++)
        st[i][0]=a[i];
    for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)
            st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);
}
int qe(int l,int r)
{
    int k=LOG2[r-l+1];
    return min(st[l][k],st[r-(1<<k)+1][k]);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    init();
    for(int i=1;i<=n-m+1;i++)
    {
        printf("%d\n",qe(i,i+m-1));
    }
    return 0;
}

上面注释的做法是用set维护了一个长度为m的序列，利用set自动排序的机制和定值删除的功能实现，pair是为了防止重复。

然后删头去尾，每次输出第一个就是最小的。

st做法没啥好说的。

P1816

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int a[N],st[N][23];
int n,m;
void init()
{
    for(int i=1;i<=m;i++)
        st[i][0]=a[i];
    for(int i=1;(1<<i)<=m;i++)
        for(int j=1;j+(1<<i)-1<=m;j++)
            st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);

}
int qe(int l,int r)
{
    int k=(int)log2(r-l+1);
    return min(st[l][k],st[r-(1<<k)+1][k]);
}
int main()
{
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
        scanf("%d",&a[i]);
    init();
    for(int i=1;i<=n;i++)
    {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d ",qe(l,r));
    }
    return 0;
}

板子题，没啥好说的。

关于ST的一些理解：

st[i][j]代表以ii为起点，长度为2j2^j的区间中的最值大小（包含ii这个端点）

st[j][i]=min(st[j][i-1],st[j+(1<<(i-1))][i-1]);

所以预处理的时候这个是直接加上区间长度。

min(st[l][k],st[r-(1<<k)+1][k]);

而访问的时候要减去长度再加一。

前缀和

sum[i]=sum[i-1]+a[i]

sum[i]即元素a在[0,i][0,i]的区间和，这样就可以快速进行区间求和了。

sum[l~r]=sum[r]-sum[l-1]

差分

差分是前缀和的逆运算，它将区间修改转化为端点修改。

一维差分

定义差分数组D[]，D[i]=a[i]-a[i-1]。

查询：

a[k]=∑i=1kD[i]a[k]=\sum^{k}_{i=1}D[i]

也就是对差分数组求前缀和。

区间修改：

将区间[l,r][l,r]的每个元素都加dd，

只需要：

D[l]+=d,D[r+1]-=d

这样就可以保证：

  1. 1≤x<l1\le{x}<l，a[x]a[x]不变。
  2. l≤x≤rl\le{x}\le{r}，a[x]a[x]增加dd。
  3. r<x≤nr<x\le{n}，a[x]a[x]不变。

nn个数mm次区间修改+一次查询复杂度：O(mn)→O(m+n)O(mn)\to{O(m+n)}

差分对于单点查询不是很高效，这时候就需要线段树或者树状数组了。

习题：

HDU1556

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int D[N];
int n;
int main()
{
    while(~scanf("%d",&n))
    {
        memset(D,0,sizeof(D));
        for(int i=1;i<=n;i++)
        {
            int l,r;
            scanf("%d%d",&l,&r);
            D[l]++,D[r+1]--;
        }
        for(int i=1;i<=n;i++)
        {
            D[i]=D[i-1]+D[i];
            if(i!=n) printf("%d ",D[i]);
            else printf("%d\n",D[i]);
        }
    }
    return 0;
}

二维差分

点扩展为面

差分数组的前缀和：

a[i][j]a[i][j]代表点(1,1)(1,1)到点(i,j)(i,j)的矩形的面积（所有元素之和）；

差分：

D[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1]

a就是大矩形，D就是大矩形中的小矩形。

区间修改

将点(x1,y1),(x2,y2)(x_1,y_1),(x_2,y_2)围成的一段区间中每个元素都加上dd，需要：

  • D[x1][y1]+=d
  • D[x1][y2+1]-=d
  • D[x2+1][y1]-=d
  • D[x2+1][y2+1]+=d//被减了两次的地方需要加回来一次

处理的时候可以直接把DD数组当成aa来更新，以此节省空间，因为是从前往后更新，后面的值需要前面的值，前面的值不需要后面的值，所以互不影响。

习题：

P3397

#include<bits/stdc++.h>
using namespace std;
int n,m;
int D[5005][5005];
int main()
{
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        D[x1][y1]+=1;
        D[x1][y2+1]-=1;
        D[x2+1][y1]-=1;
        D[x2+1][y2+1]+=1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            D[i][j]+=D[i-1][j]+D[i][j-1]-D[i-1][j-1];
            printf("%d ",D[i][j]);
        }
        puts("");
    }
    return 0;
}

其中，计算前缀和可以这样替换：

for(int i=1;i<=n;i++)
    for(int j=1;j<n;j++)
        D[i][j+1]+=D[i][j];
for(int i=1;i<n;i++)
    for(int j=1;j<=n;j++)
        D[i+1][j]+=D[i][j];

即横向纵向分别处理前缀和。

也可以这样写：

for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        D[i][j]+=D[i][j-1];
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        D[i][j]+=D[i-1][j];

二维前缀和的应用：

P2280

#include<bits/stdc++.h>
using namespace std;
const int N=5001;//坐标范围：1~5001
int n,m,ans=-1;
int sum[5007][5007];//防越界
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x,y,v;
        scanf("%d%d%d",&x,&y,&v);
        sum[++x][++y]+=v;//将坐标范围由0~5000改为1~5001
    }
    for(int i=1;i<=N;i++)//二位前缀和，坐标范围内都需要处理
        for(int j=1;j<N;j++)
            sum[i][j+1]+=sum[i][j];
    for(int j=1;j<=N;j++)
        for(int i=1;i<N;i++)
            sum[i+1][j]+=sum[i][j];
    for(int i=m;i<=N;i++)//对于坐标范围内地毯式搜索
        for(int j=m;j<=N;j++)
        {
            int p=sum[i][j]-sum[i-m][j]-sum[i][j-m]+sum[i-m][j-m];
            ans=max(ans,p);
        }
    printf("%d",ans);
    return 0;
}

二次差分

这是一个链接

离散化

很多时候我们并不关心元素的绝对大小，我们关心它们的相对大小，那么就可以对它们进行离散化处理。

离散化的具体步骤：

  1. 排序
  2. 编号
  3. 归位

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=500;
struct data{
    int val,id;
}olda[N];
int newa[N];
bool cmp(data x,data y)
{
    return x.val<y.val;
}
int n;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&olda[i].val);
        olda[i].id=i;
    }
    sort(olda+1,olda+1+n,cmp);
    for(int i=1;i<=n;i++)
    {
        newa[olda[i].id]=i;
        if(olda[i].val==olda[i-1].val)
            newa[olda[i].id]=newa[olda[i-1].id];
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d ",newa[i]);
    }
    return 0;
}

排序

常见排序算法：

  • 选择
  • 插入
  • 冒泡
  • 归并
  • 快排
  • 堆排
  • 计数
  • 基数
  • 桶排
  • sort()

排列

STL

nextpermutation()next_permutation()函数，该函数内前两个参数为左开右闭的一个排列区间的指针（如s.begin(),s.end()s.begin(),s.end()），返回值为bool类型，表示有无下一个排列，排列后的结果会返回原序列中并覆盖。

上一页
2024-03-13 12:16:51 # OI # Note
下一页