DQS DQS

分类 算法 下的文章

CCPC2017 Final hdu6243~hdu6253

in 算法,模拟赛 read (165)
谷歌的题真好!! 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 (154)
http://uoj.ac/problem/14 只是想来写一发带撤销的并查集,然而今天这题竟然不会做了… 只有前两个,显然每条边至多被加入和删除一次。直接用并查集做就行。注意按秩合并。 (然而删除时维护作为秩的高度很麻烦,所以用size当秩,正确性不知道,网上好多代码这...

[hdu2746]String painter 区间DP

in 简单DP,算法,DP read (162)
Problem Description There are two strings A and B with equal length. Both strings are made up of lower case letters. Now you have a power...

[BZOJ1854][Scoi2010]游戏 并查集||匈牙利

Description lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。 游戏进行到最后,lxhgww遇到了终极b...

[BZOJ1045] [HAOI2008] 糖果传递 中位数

in 算法,其他 read (150)
Description 有n个小朋友坐成一圈,每人有ai个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为1。 Input 第一行一个正整数nn<=1'000'000,表示小朋友的个数. 接下来n行,每行一个整数ai,表示第i个小朋友得到的糖果的颗数. O...
雷姆
拉姆