noone___'s blog
0%

13801202-AGC023

发表于 更新于 分类于
AGC023

D

一条数轴上有 $n$ 个公寓，第 $i$ 个位于 $x_i$ ，共有 $P_i$ 个人居住。 现在这 $\sum P_i$ 个人聚集在点 $S$ 处。只有一辆公交车，每次只能向前或向后，每个人会投票沿正/负方向，票数多的胜，相同时向负方向开。每个人用自私的投票方向，而有长期利益时也会做，到家必须下车。在这种策略下，求让所有人都到家的时间

原问题与绝对坐标无关，仅与相对位置有关，不妨设 $S=0$

若所有 $X_i$ 同号，则顺着开过去显然对所有人有利

考虑不同号：若 $P_1\leq P_N$ 有结论：此时对于 $1,N$ 号公寓，车一定先到达 $1$ ，这不难证明

由此，将 $P_1$ 视作 $P_1+P_N$ ，然后删去 $N$ 点，对结果的策略显然不产生影响

由此往复，直至所有人的公寓都位于 $S$ 同侧

对于计算总时间，考虑倒着记录公交车的轨迹，即，删去 $N$ 后将轨迹最后一个点设为 $X_N$ ，最后让公交车沿轨迹行驶+同侧的最远距离即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N=1e5+100;
int n,cnt,x[N],a[N];
ll p[N],ans;

int main(){
    rei i,j,s=0,v=0;
    scanf("%d%d",&n,&x[0]);
    for(i=1;i<=n;++i) scanf("%d%lld",&x[i],&p[i]),(x[i]-=*x)<0 && (s=i);
    *x=0;
    for(i=1,j=n;i<=s && j>s;a[cnt++]=p[i]>=p[j] ? (p[i]+=p[j],j--) : (p[j]+=p[i],i++));
    for(a[cnt++]=(i<=s ? i : j);cnt;ans+=abs(x[ a[--cnt] ]-x[v]),v=a[cnt]);
    printf("%lld\n",ans);
    getchar(),getchar();
    return 0;
}

E

给定一个长度为 $N$ 的序列 $A$ ，求 $\forall i, P_i\leq A_i$ 的 $1\sim n$ 的排列的逆序数的和

将 $A$ 升序后的数组为 $a$ ，则总方案数为 $f(n)=\prod_{i=1}^n (a_i-i+1)$

设 $A_i$ 排名为 $rnk_i$ ，有 $a_i=A_{rnk_i}$

对于位置 $i,j$ 考虑其对逆序对的贡献：

即，$p_j>p_i$ 的方案数为 $a_i,a_j$ 相同时的总方案数 $\div 2$

而对于 $a_i>a_j$ 的部分，求出顺序对，并用总合减去

对于相同的部分：

后半部分用线段树维护即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
const int N=2e5+5;
const int mod=1e9+7;
int n,res,tot=1;
struct Data{ int data,pos;}a[N];
inline bool cmp(const Data a,const Data b){ return a.data<b.data;}

inline void fix(int &x){ x>=mod ? x%=mod : 0;}
inline int qpow(int x,int k){ int res=1; for(;k;k>>=1,x=x*x%mod) if(k&1) res=res*x%mod; return res;}

struct Seg_Tree{
    struct Node{ int data,tag;}tr[N<<2];
    inline void up(int u){ tr[u].data=(tr[u<<1].data+tr[u<<1|1].data)%mod;}
    inline void updata(int u,int z){
        tr[u].data*=z,tr[u].data%=mod,tr[u].tag*=z,tr[u].tag%=mod;
    }
    inline void down(int u){
        updata(u<<1,tr[u].tag),updata(u<<1|1,tr[u].tag);
        tr[u].tag=1;
    }
    void build(int u,int l,int r){
        tr[u].tag=1; if(l==r) return ;
        rei mid=l+r>>1; build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        return ;
    }
    int query(int u,int l,int r,int x,int y){
        if(x>y) return 0;
        if(x<=l && r<=y) return tr[u].data;
        rei mid=l+r>>1,res=0; down(u);
        if(x<=mid) res+=query(u<<1,l,mid,x,y);
        if(y>mid) res+=query(u<<1|1,mid+1,r,x,y);
        return res%mod;
    }
    void change(int u,int l,int r,int x,int z){
        if(l==r) return tr[u].data=z,void();
        rei mid=l+r>>1; down(u);
        x<=mid ? change(u<<1,l,mid,x,z) : change(u<<1|1,mid+1,r,x,z);
        return up(u);
    }
}seg;

struct TA{
    int tr[N];
    inline int lowbit(int x){ return x&(-x);}
    inline void add(int k,int x){ for(;k<=n;k+=lowbit(k))tr[k]+=x;}
    inline int query(int k){ rei res=0; for(;k;k-=lowbit(k))res+=tr[k]; return res;}
}ta;

signed main(){
    scanf("%d",&n);
    for(rei i=1;i<=n;++i) scanf("%lld",&a[i].data),a[i].pos=i;
    sort(a+1,a+1+n,cmp);
    for(rei i=1;i<=n;++i) fix(tot*=a[i].data-i+1);
    for(rei i=1;i<=n;++i){
        rei tmp=0;
        fix(tmp+=seg.query(1,1,n,1,a[i].pos-1));
        fix(tmp+=mod-seg.query(1,1,n,a[i].pos+1,n));
        fix(tmp*=tot*qpow(2*(a[i].data-i+1),mod-2)%mod);
        fix(tmp+=(ta.query(n)-ta.query(a[i].pos))*tot%mod);
        fix(res+=tmp);
        seg.updata(1,(a[i].data-i)*qpow(a[i].data-i+1,mod-2)%mod);
        seg.change(1,1,n,a[i].pos,a[i].data-i),ta.add(a[i].pos,1);
    }
    printf("%lld\n",res);
    getchar(),getchar();
    return 0;
}

F

一颗 $n$ 节点的数和一个空序列，每个节点上有 $0/1$ ，每次选择一个没有父节点的点删除并将点上面的数字放到当前数列末尾，求这个数列能得到的最小逆序对数

有一个很好的贪心：将每个节点视作一个连通块，每次选择一个节点将其与其父节点的连通块合并，且排在父节点的后面

如此，根据子节点在连通块内的顺序不同，可以构成所有可能的序列

考虑如何安排顺序使跨越子树的逆序对最少

设 $cnt_{x,0/1}$ 表示连通块 $x$ 内的 $0/1$ 数量，对于连通块 $xy$ 的顺序，$x$ 在 $y$ 前当且仅当 $cnt_{x,1}\times cnt_{y,0} \leq cnt_{y,1}\times cnt_{x,0}$

那么按照 $\frac{cnt_{x,1}}{cnt_{x,0}}$ 从小到大选即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const int N=2e5+100;
int n,f[N],fa[N],cnt[N][2];
ll ans;

struct node{
    int x,cnt_0,cnt_1;
    node(int xx=0){x=xx;cnt_0=cnt[xx][0];cnt_1=cnt[xx][1];return;}
    friend bool operator <(const node &x,const node &y){ return (ll) x.cnt_1*y.cnt_0>(ll) x.cnt_0*y.cnt_1;}
};
priority_queue<node> q;

int get_fa(int x){ return fa[x]==x ? x : fa[x]=get_fa(fa[x]);}

int main(){
    scanf("%d",&n);
    for(rei i=2;i<=n;++i) scanf("%d",&f[i]);
    for(rei i=1;i<=n;++i){
        rei x; scanf("%d",&x);
        ++cnt[i][x]; fa[i]=i; if(i>1)q.push(node(i));
    }
    while(q.size()){
        node w=q.top(); q.pop();
        rei x=get_fa(w.x);
        if(fa[x]!=x || cnt[x][1]!=w.cnt_1 || cnt[x][0]!=w.cnt_0) continue;
        rei y=get_fa(f[x]); fa[x]=y;
        ans+=(ll) cnt[y][1]*cnt[x][0];
        cnt[y][0]+=cnt[x][0],cnt[y][1]+=cnt[x][1];
        if(y) q.push(node(y));
    }
    printf("%lld\n",ans);
    getchar(),getchar();
    return 0;
}