【Fortuna OJ】10/27 Contest / 题解

冒泡排序

题目描述

给出以下定义


算法 1 冒泡排序


输入:一个⻓度为 n 的排列 P。


输出: 排序后的结果。


function Sort(n, F)
while P 无序 do
x ← Rand(1, n)
y ← Rand(1, n)
Swap(P[x], P[y])
end while
return P
end function

小 S 开始专注于研究⻓度为 $n$ 的排列,他想知道,在你运气足够好的情况下(即每次冒泡排序的交换次数都是可能的最少交换次数,仿佛有上帝之手在操控),对于一个等概率随机的⻓度为 $n$ 的排列,进行这样的冒泡排序的期望交换次数是多少?

思路

令 $f_i$ 表示排列有 $i$ 个数时的期望交换次数。

我们考虑一个排列 $p$,设它的第 $n$ 位为 $k$,第 $k$ 位为 $x$。现在我们将 $x$ 看作 $n$,对前 $n-1$ 个数进行上述排序,期望操作次数为 $f_{n-1}$。如果 $k\neq n$,那么我们再交换 $n, k$,排序结束;如果 $k=n$,此时的 $p$ 已经有序。$k$ 的值共有 $n$ 种情况,其中 $n-1$ 种情况需要再交换一次,得出:

$$f_i=f_{i-1}+\dfrac{i-1}{i}$$

预处理逆元后,$\Theta (n)$预处理出所有可能的答案,$\Theta (1)$ 回答每个询问。

然后我们考虑怎么预处理逆元。

首先,已知 $1^{-1} \equiv 1 \pmod p$。

我们设 $p = k\cdot i + r,~r < i,~1 < i < p$.

在模意义下就是 $k\cdot i + r \equiv 0 \pmod p$。

两边同时乘上 $i^{-1}\cdot r^{-1}$,得到:

就可以线性处理逆元了。

代码

#include <bits/stdc++.h>
#define ll long long
#define maxn 10001000
#define md 998244353
using namespace std;
int inv[maxn],ans[maxn];
void init(){
    inv[1]=1;
    for (int i=2;i<maxn;i++)
    inv[i]=(ll)(md-md/i)*inv[md%i]%md;
    for (int i=1;i<maxn;i++)
    ans[i]=(ll)(i-1)*inv[i]%md;
    for (int i=1;i<maxn;i++)
    (ans[i]+=ans[i-1])%=md;
}
int main(){
    init();int T,x;
    scanf("%d",&T);
    while(T--)
        scanf("%d",&x),
        printf("%d\n",ans[x]);
}

情报中心

题目描述

最近,C 国成功地渗透进入了 D 国的一个城市。这个城市可以抽象成一张有 n 个节点,节点之间有 m 条双向道路连接的无向图,每条道路的⻓度都为 1 。

经过侦查,C 国情报部部⻓ GGB 惊讶地发现,这座看起来不起眼的城市竟然是 D 国的军事中心。因此 GGB 决定在这个城市内设立情报机构。情报专家 TAC 在侦查后,安排了 $q$ 种设立情报机构的方案。这些方案中,第 $i$ 种方案将计划建立 $k_i$ 个情报机构,第 $j$ 个情报机构可以安排人员到距离其不超过 $d_{i,j}$ 的节点上收集情报。

但是,由于人手不足,GGB 只能安排上述 $q$ 种方案中的一种进行实施。为了评估一种方案的性能,我们把能够收集到情报的节点数量视为这种情报的价值。现在,你被 GGB 和 TAC 派来侦查,请你统计每一种方案的价值。

思路

代码

百鸽笼

题目描述

原题矫揉造作,优化题面如下:

给定一个数列,有三种操作:

  1. 删去左端点;
  2. 左端点前插入一个数 $v$;
  3. 询问从左到右数,$[l, r]$ 中第 $k$ 大的数字。

思路

将数列翻转,用主席树维护每个数字的前缀出现次数,每次修改新增一个版本。

本题空间限制为 $\text{262144 KB}$,数组要精简,离散化不要使用 $map$。

代码

#include <bits/stdc++.h>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
#define maxn 301000
using namespace std;
int w[maxn],len;
struct Opera{
    int op,l,r,k,v,id;
}que[maxn];
int alnum[maxn<<1],tot,n,m,cnt;
int root[maxn<<1],L[maxn<<6],R[maxn<<6],tree[maxn<<6];
int build(int l,int r){
    int rt=++cnt;
    tree[rt]=0;
    if (l<r){
        L[rt]=build(l,mid);
        R[rt]=build(mid+1,r);
    }
    return rt;
}
int update(int &p,int pre,int l,int r,int t,int k){
    p=++cnt;
    L[p]=L[pre];R[p]=R[pre];tree[p]=tree[pre]+t;
    if (l<r){
        if (k<=mid) update(L[p],L[pre],l,mid,t,k);
        else update(R[p],R[pre],mid+1,r,t,k);
    }
}
int query(int Al,int Ar,int l,int r,int k){
    if (l>=r) return l;
    int x=tree[L[Ar]]-tree[L[Al]];
    if (x>=k) return query(L[Al],L[Ar],l,mid,k);
    else return query(R[Al],R[Ar],mid+1,r,k-x);
}
int main(){
    freopen("pigeon.in","r",stdin);
    freopen("pigeon.out","w",stdout);
    scanf("%d%d",&len,&m);
    for (int i=len;i;--i){
        scanf("%d",w+i);
        alnum[++tot]=w[i];
    }
    for (int i=1;i<=m;i++){
        scanf("%d",&que[i].op);
        if (que[i].op==1) continue;
        if (que[i].op==2) scanf("%d",&que[i].v),alnum[++tot]=que[i].v;
        else scanf("%d%d%d",&que[i].l,&que[i].r,&que[i].k);
    }
    sort(alnum+1,alnum+1+tot);
    int n=unique(alnum+1,alnum+1+tot)-alnum-1;
    for (int i=1;i<=len;i++){
        w[i]=lower_bound(alnum+1,alnum+1+n,w[i])-alnum;
        update(root[i],root[i-1],1,n,1,w[i]);
    }
    for (int i=1;i<=m;i++){
        if (que[i].op==1){
            update(root[len],root[len],1,n,-1,w[len]);
            w[len]=0;len--;
        }
        if (que[i].op==2){
            w[++len]=lower_bound(alnum+1,alnum+1+n,que[i].v)-alnum;
            update(root[len],root[len-1],1,n,1,w[len]);
        }
        if (que[i].op==3){
            int cl=len-que[i].r+1;
            int cr=len-que[i].l+1;
            printf("%d\n",alnum[query(root[cl-1],root[cr],1,n,que[i].k)]);
        }
    }
    return 0;
}