冒泡排序
题目描述
给出以下定义
算法 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 派来侦查,请你统计每一种方案的价值。
思路
代码
百鸽笼
题目描述
原题矫揉造作,优化题面如下:
给定一个数列,有三种操作:
- 删去左端点;
- 左端点前插入一个数 $v$;
- 询问从左到右数,$[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;
}