败犬#1

败犬#1

A FZU 2257 .php?pid=2257
对每个点(x,y)计算它被选在矩形中的概率
选择的点是(x1,y1),(x2,y2)
先看x1和x2可能的选择（借用一下大哥给我讲解画的图）

对应的范围有2种情况 再将x1和x2倒一下就变成了2倍
同理再枚举y1 y2可以得到选中的概率p的公式
(1-p)^k就是k次都没选中的概率
1-(1-p)^k就是k次中选中了的概率
每个点选中的概率相加即为答案

B CF617E

莫队算法 利用前缀和来维护区间的答案

/

C
规律：2^n层中每层的个数分别为1,2,3……n
化简求和公式用快速幂求答案

D
签到题
每个位置记录4个方向是否合法
对每个人往4个方向更新若更新过则停止

E

构造最小生成树 利用倍增LCA求解

/

F .php?id=1822

待补

G

DAG上的dp
dp[i][j]记录到达i时经过j个城市的时间

/

H

暴力+贪心

因为尽量让min/max尽可能大 所以对每份尽可能均分