「CTSC 2011」排列

「CTSC 2011」排列

要求不存在公差为 A 或者公比为 B 的子列，那么实际上可以把该问题转化为求一个图的最优拓朴序。

任意差为 A 或者比为 B 的两个数连一条边。

求一个合法序列的答案可以用树状数组。

接下来如果直接用优先队列计算最小拓朴序就可以得到32分的好成绩。

如上方法复杂度为\(o(nlog(n))\)，远远小于给定时限。

尝试引入随机算法。

每个数都定义一个优先级\(rank\)。

用爬山求出局部最优解：

? 每次先随机生成\(rank\)数组，然后随机一个点，试图将该点$rank $和其它所有点交换。

多爬几次，这里爬\(130-n\)次，每次爬山跑150次。

另外测试点9，10已经给出，打表即可。

#include<bits/stdc++.h>
#define rep(q,a,b) for(int q=a,q##_end_=b;q<=q##_end_;++q)
#define dep(q,a,b) for(int q=a,q##_end_=b;q>=q##_end_;--q)
#define mem(a,b) memset(a,b,sizeof a )
#define debug(a) cerr<<#a<<' '<<a<<"___"<<endl
using namespace std;
void in(int &r) {
    static char c;
    r=0;
    while(c=getchar(),!isdigit(c));
    do r=(r<<1)+(r<<3)+(c^48);
    while(c=getchar(),isdigit(c));
}
int head[95],to[200],ne[200],cnt1;
#define link(a,b) to[++cnt1]=b,ne[cnt1]=head[a],head[a]=cnt1
#define travel(x) for(int q(head[x]);q;q=ne[q])
int ind[95],rk[95];
struct node{
    int v;
    bool operator <(const node &A)const{
        return rk[v]<rk[A.v];
    }
};
priority_queue<node> qw;
int ans[95],n,mid_ind[95],mid[95];
void toposort(){
    while(!qw.empty())qw.pop();
    rep(q,1,n)mid_ind[q]=ind[q];
    int ct=0;
    rep(q,1,n)if(!mid_ind[q])qw.push({q});
    while(!qw.empty()){
        mid[++ct]=qw.top().v;
        qw.pop();
        travel(mid[ct]){
            --mid_ind[to[q]];
            if(!mid_ind[to[q]])qw.push({to[q]});
        }
    }
}
int c[95],c1[95];
void add(int x,int v){
    while(x<=n)++c[x],c1[x]+=v,x+=x&-x;
}
int ask(int x,int v){
    int sm=0,ct=0;
    while(x)ct+=c[x],sm+=c1[x],x&=x-1;
    return v*ct-sm;
}
int end_v;
int solve(){
    rep(q,1,n)c[q]=0,c1[q]=0;
    toposort();
    int tot=0;
    rep(q,1,n){
        tot+=ask(mid[q],mid[q]);
        add(mid[q],mid[q]);
    }
    if(tot>end_v){
        end_v=tot;
        rep(q,1,n)ans[q]=mid[q];
    }
    return tot;
}
int sx[95];
int main(){
    freopen("pal.in","r",stdin);
    freopen("pal.out","w",stdout);
    srand(19890519);
    int a,b;
    in(n),in(a),in(b);
    if(n==60&&a==21&&b==3){
        puts("48 27 51 30 9 45 24 3 43 22 1 50 29 8 57 36 15 47 26 5 54 33 12 46 25 4 60 39 18 6 44 23 2 42 21 49 28 7 40 19 41 20 52 31 10 53 32 11 55 34 13 56 35 14 58 37 16 59 38 17");
        return 0;
    }
    if(n==90&&a==18&&b==2){
        puts("78 60 84 42 66 48 24 30 12 6 75 57 39 21 3 74 56 76 38 58 80 40 20 82 64 46 28 10 86 68 50 32 14 62 88 44 22 70 52 34 16 26 8 4 2 73 55 37 19 1 77 59 41 23 5 79 61 43 25 7 83 65 47 29 11 85 67 49 31 13 90 72 54 36 18 81 63 45 27 9 87 69 51 33 15 89 71 53 35 17");
        return 0;
    }
    rep(q,1,n){
        if(a&&a+q<=n)link(a+q,q),++ind[q];
        if(q*b<=n&&b!=1)link(b*q,q),++ind[q];
    }
    int tim=130-n;
    rep(q,1,n)rk[q]=q,sx[q]=q;
    while(tim--){
        random_shuffle(rk+1,rk+n+1);
        int ti=150;
        int now=solve();
        while(ti--){
            int to=rand()%n+1;
            rep(q,1,n)if(q!=to){
                swap(rk[q],rk[to]);
                int tmp=solve();
                if(tmp>now)now=tmp;
                else swap(rk[q],rk[to]);
            }
        }
    }
    rep(q,1,n)printf("%d ",ans[q]);
    return 0;
}

「CTSC 2011」排列

原文：https://www.cnblogs.com/klauralee/p/11283686.html