败犬#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尽可能大 所以对每份尽可能均分
更多推荐
败犬#1
发布评论