DQS DQS

2017年12月

CCPC2017 Final hdu6243~hdu6253

in 算法,模拟赛 read (40)
谷歌的题真好!! A.Dogs and Cages 题意:求n的排列中a[i]!=i的期望。 概率没学好,于是错排硬推… 即错排数为k时的概率之和,式子为 $$\sum_{k=0}^n\frac{kf_kC_n^k}{n!}=\sum_{k=0}^n\frac{k*f_k...

【UER #1】DZY Loves Graph 带撤销并查集

in 算法,并查集,数据结构 read (40)
http://uoj.ac/problem/14 只是想来写一发带撤销的并查集,然而今天这题竟然不会做了… 只有前两个,显然每条边至多被加入和删除一次。直接用并查集做就行。注意按秩合并。 (然而删除时维护作为秩的高度很麻烦,所以用size当秩,正确性不知道,网上好多代码这...
雷姆
拉姆