#2509. 「AHOI / HNOI2018」排列

题目描述

给定 nnn 个整数 a1,a2,…,an(0≤ai≤n)，以及 nnn 个整数 w1,w2,…,wn。称 a1,a2,…,an 的一个排列 ap[1],ap[2],…,ap[n] 为 a1,a2,…,an 的一个合法排列，当且仅当该排列满足：对于任意的 kkk 和任意的 jjj，如果 j≤kj \le kj≤k，那么 ap[j]a_{p[j]}ap[j] 不等于 p[k]p[k]p[k]。（换句话说就是：对于任意的 kkk 和任意的 jjj，如果 p[k]p[k]p[k] 等于 ap[j]a_{p[j]}ap[j]，那么 k<jk<jk<j。）

定义这个合法排列的权值为 wp[1]+2wp[2]+…+nwp[n]。你需要求出在所有合法排列中的最大权值。如果不存在合法排列，输出 −1-1−1。

样例解释中给出了合法排列和非法排列的实例。

输入格式

第一行一个整数 nnn。

接下来一行 nnn 个整数，表示 a1,a2,…,an。

接下来一行 nnn 个整数，表示 w1,w2,…,wn。

输出格式

输出一个整数表示答案。

样例

样例输入 1

样例输出 1

样例解释 1

对于 a1=0,a2=1,a3=1a_1=0,a_2=1,a_3=1a1=0,a2=1,a3=1，其排列有

a1=0,a2=1,a3=1a_1=0,a_2=1,a_3=1a1=0,a2=1,a3=1，是合法排列，排列的权值是 1∗5+2∗7+3∗3=281*5+2*7+3*3=281∗5+2∗7+3∗3=28；
a2=1,a1=0,a3=1a_2=1,a_1=0,a_3=1a2=1,a1=0,a3=1，是非法排列，因为 ap[1]a_{p[1]}ap[1] 等于 p[2]p[2]p[2]；
a1=0,a3=1,a2=1a_1=0,a_3=1,a_2=1a1=0,a3=1,a2=1，是合法排列，排列的权值是 1∗5+2∗3+3∗7=321*5+2*3+3*7=321∗5+2∗3+3∗7=32；
a3=1,a1=0,a2=1a_3=1,a_1=0,a_2=1a3=1,a1=0,a2=1，是非法排列，因为 ap[1]a_{p[1]}ap[1] 等于 p[2]p[2]p[2]；
a2=1,a3=1,a1=0a_2=1,a_3=1,a_1=0a2=1,a3=1,a1=0，是非法排列，因为 ap[1]a_{p[1]}ap[1] 等于 p[3]p[3]p[3]；
a3=1,a2=1,a1=0a_3=1,a_2=1,a_1=0a3=1,a2=1,a1=0，是非法排列，因为 ap[1]a_{p[1]}ap[1] 等于 p[3]p[3]p[3]。

因此该题输出最大权值 323232。

样例输入 2

样例输出 2

-1

样例解释 2

对于 a1=2,a2=3,a3=1a_1=2,a_2=3,a_3=1a1=2,a2=3,a3=1，其排列有：

a1=2,a2=3,a3=1a_1=2,a_2=3,a_3=1a1=2,a2=3,a3=1，是非法排列，因为 ap[1]a_{p[1]}ap[1] 等于 p[2]p[2]p[2]；
a2=3,a1=2,a3=1a_2=3,a_1=2,a_3=1a2=3,a1=2,a3=1，是非法排列，因为 ap[1]a_{p[1]}ap[1] 等于 p[3]p[3]p[3]；
a1=2,a3=1,a2=3a_1=2,a_3=1,a_2=3a1=2,a3=1,a2=3，是非法排列，因为 ap[1]a_{p[1]}ap[1] 等于 p[3]p[3]p[3]；
a3=1,a1=2,a2=3a_3=1,a_1=2,a_2=3a3=1,a1=2,a2=3，是非法排列，因为 ap[2]a_{p[2]}ap[2] 等于 p[3]p[3]p[3]；
a2=3,a3=1,a1=2a_2=3,a_3=1,a_1=2a2=3,a3=1,a1=2，是非法排列，因为 ap[2]a_{p[2]}ap[2] 等于 p[3]p[3]p[3]；
a3=1,a2=3,a1=2a_3=1,a_2=3,a_1=2a3=1,a2=3,a1=2，是非法排列，因为 ap[1]a_{p[1]}ap[1] 等于 p[3]p[3]p[3]。

因此该题没有合法排列。

样例输入 3

10

6 6 10 1 7 0 0 1 7 7

16 3 10 20 5 14 17 17 16 13

样例输出 3

数据范围与提示

对于前 20%20\%20% 的数据，1≤n≤101 \le n \le 101≤n≤10；

对于前 40%40\%40% 的数据，1≤n≤151 \le n \le 151≤n≤15；

对于前 60%60\%60% 的数据，1≤n≤10001 \le n \le 10001≤n≤1000；

对于前 80%80\%80% 的数据，1≤n≤1000001 \le n \le 1000001≤n≤100000；

对于 100%100\%100% 的数据，1≤n≤5000001 \le n \le 5000001≤n≤500000，0≤ai≤n(1≤i≤n)0 \le a_i \le n (1 \le i \le n)0≤ai≤n(1≤i≤n)，1≤wi≤1091 \le w_i \le 10^91≤wi≤109 ，所有 wiw_iwi 的和不超过 1.5×10131.5 \times 10^{13}1.5×1013。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define maxn 500010

using namespace std;

int a[maxn],w[maxn],p[maxn],n;

long long ans=-;

bool check(){

    for(int i=;i<=n;i++)

        for(int j=i;j<=n;j++)

            if(a[p[i]]==p[j])return ;

    return ;

}

long long count(){

    long long res=;

    for(int i=;i<=n;i++)res+=1LL*i*w[p[i]];

    return res;

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&a[i]);

    for(int i=;i<=n;i++)scanf("%d",&w[i]);

    for(int i=;i<=n;i++)p[i]=i;

    do{

        long long ww=count();

        if(ans>=ww)continue;

        if(check())ans=max(ans,ww);

    }while(next_permutation(p+,p+n+));

    cout<<ans;

    return ;

}

20分枚举全排列

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#define maxn 500010

using namespace std;

int n,a[maxn],fa[maxn],sz[maxn];

long long sum[maxn],ans;

struct node{

    long long v;

    int s,x;

    bool operator < (const node &b)const{

        return v*b.s>b.v*s;

    }

};

priority_queue<node>q;

long long qread(){

    long long i=,j=;

    char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')j=-;ch=getchar();}

    while(ch<=''&&ch>=''){i=i*+ch-'';ch=getchar();}

    return i*j;

}

int find(int x){

    if(fa[x]==x)return x;

    return fa[x]=find(fa[x]);

}

int main(){

    n=qread();

    for(int i=;i<=n;i++)fa[i]=i;

    for(int i=;i<=n;i++){

        a[i]=qread();

        int f1=find(i),f2=find(a[i]);

        if(f1==f2){puts("-1");return ;}

        fa[f1]=f2;

    }

    for(int i=;i<=n;i++)sum[i]=qread();

    for(int i=;i<=n;i++)sz[i]=,fa[i]=i;

    for(int i=;i<=n;i++)q.push((node){sum[i],sz[i],i});

    while(!q.empty()){

        node tmp=q.top();q.pop();

        if(tmp.s!=sz[tmp.x])continue;

        int f1=find(a[tmp.x]);

        ans+=tmp.v*sz[f1];

        fa[tmp.x]=f1;

        sz[f1]+=tmp.s;

        sum[f1]+=tmp.v;

        if(f1)q.push((node){sum[f1],sz[f1],f1});

    }

    cout<<ans;

    return ;

}

100分并查集

巴特西

loj #2509. 「AHOI / HNOI2018」排列