2020-team1-C018

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team1 返回]
== 概述 ==
solved: 6/12  dirt: 50%
rank: 18
[[Image(Rank.png,800px)]]
== 总结 ==
osc发现前8题他都不会，于是他就去写K了，还没抢到一血/fad
写完看了I发现是sb题，又写了一个I，然后就吃瓜看比赛了
Grammy： 没有看完所有题。C题不会做不应该。E题从dp的角度是个好题，从科技的角度模拟费用流是知识漏洞。 G题这个套路似乎又是见过但是又不会做，wqs二分写的时候忘记处理斜率相等了，本来是有机会过的。
lwn_16：
今天的F不知道在干什么，果然印证了昨天说的第一念头是对的，然后就把它推翻掉了。
我的第一念头是1e9的数据范围，然后模数是1e9+7，不可能是阶乘形式。
明明推出了一个N^2^的式子却不去打表看一下，还找了个特殊情况（r,0,b,1）推出来的式子认为怎么都不可能化简，分母肯定是阶乘形式，然后就不肯去打表
没救了
== 题解 ==
A: 三分，凸包，旋转卡壳
B: 推式子
C: 枚举X使得前K个人>=x，后N-K个人<=x
可行解画出来是个双阶梯的形状，先中间切一刀使得左上右下全可行
用dp算出左下或右上i行覆盖了j行的方案数
枚举左下覆盖了X行，右上覆盖了Y行，剩下就是两个阶乘
枚举前K个人>=X会算重复，所以需要用（前K个人>=X）减去（前K个人>X）来算
D: dp
E: 模拟费用流/推性质dp
F: 推式子
考虑分别算红色、蓝色、绿色的期望，绿色是(g+b)/b*K。
然后考虑一个红色和K个蓝色，其余的都不考虑（因为是期望）
如果有M个蓝色在这个红色前面，则对应的比例系数是1/(b+1)*[b/(b+1)]^M^
（如果红色在最后一个蓝色前面就算1，否则算0）sum一下就是1-[b/(b+1)]^K^，所以期望是r*(1-[b/(b+1)]^K^)
最终答案即为(g+b)/b*K+r*(1-[b/(b+1)]^K^)
G: 建笛卡尔树，wqs二分+dp
H: 若只有一个医院，两部分做法是显然的，标解就是在2个医院中间枚举，然后暴力，n^2log，自己写的T飞了，jls说可以三分（虽然他看起来就是错的），然后在区间比较小的时候暴力，就降到了nlog^2
I: 枚举O后其余可以按轮廓线唯一确定，最后再check一下是否合法
J: x看作2^(-x+1)^，扫一遍找一个前缀和一个后缀和<1
K: 建圆方树，枚举每条边和每个环，推式子算贡献更新答案，可以通过按dfn sort方点的邻居把环抠出来
L: 把0标号成n，从小点往大点建凸包，特判0~1

[/wiki/2020-team1 返回]

概述

solved: 6/12 dirt: 50%

rank: 18

总结

osc发现前8题他都不会，于是他就去写K了，还没抢到一血/fad

写完看了I发现是sb题，又写了一个I，然后就吃瓜看比赛了

Grammy： 没有看完所有题。C题不会做不应该。E题从dp的角度是个好题，从科技的角度模拟费用流是知识漏洞。 G题这个套路似乎又是见过但是又不会做，wqs二分写的时候忘记处理斜率相等了，本来是有机会过的。

lwn_16：

今天的F不知道在干什么，果然印证了昨天说的第一念头是对的，然后就把它推翻掉了。

我的第一念头是1e9的数据范围，然后模数是1e9+7，不可能是阶乘形式。

明明推出了一个N2的式子却不去打表看一下，还找了个特殊情况（r,0,b,1）推出来的式子认为怎么都不可能化简，分母肯定是阶乘形式，然后就不肯去打表

没救了

题解

A: 三分，凸包，旋转卡壳

B: 推式子

C: 枚举X使得前K个人>=x，后N-K个人<=x

可行解画出来是个双阶梯的形状，先中间切一刀使得左上右下全可行

用dp算出左下或右上i行覆盖了j行的方案数

枚举左下覆盖了X行，右上覆盖了Y行，剩下就是两个阶乘

枚举前K个人>=X会算重复，所以需要用（前K个人>=X）减去（前K个人>X）来算

D: dp

E: 模拟费用流/推性质dp

F: 推式子

考虑分别算红色、蓝色、绿色的期望，绿色是(g+b)/b*K。

然后考虑一个红色和K个蓝色，其余的都不考虑（因为是期望）

如果有M个蓝色在这个红色前面，则对应的比例系数是1/(b+1)*[b/(b+1)]M

（如果红色在最后一个蓝色前面就算1，否则算0）sum一下就是1-[b/(b+1)]K，所以期望是r*(1-[b/(b+1)]K)

最终答案即为(g+b)/b*K+r*(1-[b/(b+1)]K)

G: 建笛卡尔树，wqs二分+dp

H: 若只有一个医院，两部分做法是显然的，标解就是在2个医院中间枚举，然后暴力，n2log，自己写的T飞了，jls说可以三分（虽然他看起来就是错的），然后在区间比较小的时候暴力，就降到了nlog2

I: 枚举O后其余可以按轮廓线唯一确定，最后再check一下是否合法

J: x看作2(-x+1)，扫一遍找一个前缀和一个后缀和<1

K: 建圆方树，枚举每条边和每个环，推式子算贡献更新答案，可以通过按dfn sort方点的邻居把环抠出来

L: 把0标号成n，从小点往大点建凸包，特判0~1

附加文件