Skip to content

离散优化

应用

解决有已知的固定输入(即没有在线插入，离线插入所有数据，计算过程不产生数据)，且范围较大的情况，通常需要的是排名而不是具体数值，因此直接按大小重新赋予每个数一个新值。

模板 

    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);//排序
    int tot=unique(b+1,b+n+1)-b-1;//去重
    for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+tot+1,a[i])-b;//重定义位置

哈希优化

应用

解决有查询且范围比较大的情况，会需要具体数值。

当解决动态在线问题时(可能是计算过程中产生数据)需要建立可插入的hash链表，离线问题可以直接用数组存储，从头到尾扫一遍判重。

本质就是将特别大的数通过h(k)的方式映射为新的小数值，并存储到链表或数组中。(若是链表则范围是链头数组大小的范围；若是数组则范围是int(long long)的范围。)

不是普通数的也可以进行hash优化，例如数字字符串就可以用hash优化存储。（尤其是字符串中数字特别大的情况，ASCII码存不下）

~~在动态查询上因为码量而完胜平衡树~~

P2852

通过p和P解决问题。

定义p=1000017(10007也行，就是1e6不需要进位，更直观),P=1000000007,取了两个质数防止冲突。

因此将问题转化为：将字符串以p进制数的方式存储为小于P的数。(这个过程就是hash的核心：将特别大的数通过h(k)的方式映射为新的小数值，并存储。)

注意存储的是p进制数在10进制表示下 mod P的结果。

判断是排个序就行。

然后二分,没了。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long 
using namespace std;
const int N=3e4+10,p=10007,P=1000000007;
int a[N],b[N],c[N],d[N];
int n,k;
void init(){
    b[0]=0;
    c[0]=1;
    for(int i=1;i<=n;++i){
        b[i]=(b[i-1]*p+a[i])%P;
    }
    for(int i=1;i<=n;++i){
        c[i]=(c[i-1]*p)%P; 
    }
    return;
}
bool cmp(int a,int b){
    return a<b;//:)
}
bool check(int x){
    memset(d,0,sizeof d);
    int top=0;
    for(int i=x;i<=n;++i){
        d[++top]=(b[i]-b[i-x]*c[x])%P;
        if(d[top]<0)d[top]+=P;
    }
    sort(d+1,d+top+1,cmp);
    int cnt=0,ans=0;
    for(int i=1;i<=top;++i){
        cnt++;
        if(d[i+1]!=d[i] || i==top){
            ans=max(ans,cnt);
            cnt=0;
        }
    }
    return ans>=k;
}
int solve(){
    int l=0,r=n+1,ans=0;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)){
            ans=max(ans,mid);
            l=mid+1;
        }else r=mid;
    }
    return ans;
}
signed main(){
    scanf("%lld%lld",&n,&k);
    for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
    init();
    int ans=solve();
    printf("%lld",ans);
    return 0;
}

康托展开

本质也是一种hash优化，这次的映射函数为cantor(k)。对于一个全排列,其康托展开为 $$ cantor(k)=\sum_{k=n}^1 f(a[k])* (k-1)!$$ f(a[k])指比a[k]小的，未出现的数的个数。 例如34512值为61,所以是第62个。

P1379

因为总共的状态一共9!=362880种，且后进队的重复状态一定没有之前的界更优，所以直接剪枝bfs即可，用cantor(k)判断是否入队。 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define int long long 
using namespace std;
const int N=4e5+10;
int tmp[3][3],d[3][3]={1,2,3,8,0,4,7,6,5};
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int vis[9],vist[N];
int l[10];
int n,goal;
struct node{
    int v;
    int step;
    int d[3][3];
    node(int vv,int s,int dd[3][3]){
        v=vv;
        step=s;
        for(int i=0;i<3;++i){
            for(int j=0;j<3;++j)d[i][j]=dd[i][j];
        }
    }
};
int cantor(int d[3][3]){//3x3->cantor
    memset(vis,0,sizeof vis);
    int ans=0;
    for(int i=0;i<3;++i){
        for(int j=0;j<3;++j){
            int cnt=0;
            for(int k=0;k<d[i][j];++k)if(vis[k])cnt++;
            ans+=(d[i][j]-cnt)*l[9-i*3-j-1];
            vis[d[i][j]]=1;
        }
    }
    return ans;
}
void get1(int n){//int->3x3
    for(int i=2;i>=0;--i){
        for(int j=2;j>=0;--j){
            d[i][j]=n%10;
            n/=10;
        }
    }
    return;
}
void init(){
    l[0]=l[1]=1;
    for(int i=2;i<=9;++i)l[i]=l[i-1]*i;
    goal=cantor(d);
    return;
}
int bfs(){
    memset(vist,0,sizeof vist);
    queue<node> q;
    get1(n);
    while(!q.empty())q.pop();
    int a=cantor(d);
    q.push(node(a,0,d));
    vist[a]=1;
    while(!q.empty()){
        memcpy(d,q.front().d,sizeof q.front().d);
        int step=q.front().step;
        int a=cantor(d);
        if(a==goal)return step;
        int x=0,y=0;
        for(int i=0;i<3;++i){
            for(int j=0;j<3;++j){
                if(d[i][j]==0){
                    x=i,y=j;
                    break;  
                }
            }
        }
        q.pop();
        for(int i=0;i<4;++i){
            int xx=dx[i]+x,yy=y+dy[i];
            if(xx>=0 && xx<3 && yy>=0 && yy<3){
                memcpy(tmp,d,sizeof d);
                swap(tmp[x][y],tmp[xx][yy]);
                int a=cantor(tmp);
                if(a==goal)return step+1;
                if(!vist[a]){
                    vist[a]=1;
                    q.push(node(a,step+1,tmp));
                }
            }
        }
    }
    return -1;
}
signed main(){
    init();
    if(goal!=46685)goal=46685;
    scanf("%lld",&n);
    printf("%lld",bfs());
    return 0;
}