2021牛客暑期多校第九场¶
排名 | 当场过题数 | 至今过题数 | 总题数 |
---|---|---|---|
58/1238 | 3 | 10 | 10 |
A¶
solved by 板子
题意¶
类欧几里得板子
题解¶
板子按道理大概不能过(?,但是过了,std解法待学习
B¶
upsolved by JJLeo
题意¶
给定一个
每个点的度数至少是 。 是连通的。 是极大的,也就是说 不是任何一个其它 度子图的子图。
一个
求权值最大的
题解¶
看到
将每个点以权值从大到小排序,相同随意给一个顺序,则每个点有一个唯一排名。从大到小遍历
考虑每个连通块的权值,点数很好维护,正好启发式合并就记录了;对于
这两个值也可以用并查集维护,记得合并的时候只和排名比自己靠前的点进行合并,否则就把不该合并的点合并进来了。
C¶
upsolved by 2sozx
题意¶
题解¶
根据 LGV 引理可以知道我们要求的不相交路径数即为
进行简单的化简可得到所求即为
后面的行列式是范德蒙德行列式,即为
D¶
upsolved by JJLeo
题意¶
本题中,给定了一种按子树大小的边分治算法,称其为
构造一个二叉树,点数不超过
最后一个点那一层也算一层,例如
题解¶
一条链分治起来递归层数是最少的,
我们考虑诱导
类似斐波那契数列的构造方法,好多链串在一根棍上(x
我们的分治方案是,拆掉
对于
为了让
F¶
upsolved by JJLeo
题意¶
买卖股票,各需要买 / 卖
题解¶
单调队列优化多重背包裸题。
比赛的时候不写公式就写代码,浪费大量时间没调出来,我是脑瘫。
G¶
upsolved by JJLeo
题意¶
一棵树
题解¶
赛时解法是纯概率 dp:
MJX是nt,一堆
显然每个点不管是不是回收站,至多有一个儿子不是回收站,否则上来俩就在这撞了。
处理出每个节点子树中不算自己这个点不出现碰撞的概率
设当前节点为
想清楚了就好写,有一个
正解是考虑其组合意义,相当于把树划分成数个不相交的向上的链,每个链链长为
I¶
upsolved by JJLeo
题意¶
题面又臭又长,区块链都出来了,本质就是问这个问题:
从装有
个红球、 个黑球的袋子中随机取出一球,记下颜色后放回袋中,并加进 个同色球。如此共取 次,则第 次取得红球的概率是多少?
题解¶
概统原题。答案是
J¶
upsolved by JJLeo
题意¶
四个方向过马路,每个方向都有三种去其它三个方向的车,每次可以很多辆车一起走,但是不能撞车,问最少要走几次。
题解¶
可以发现右转一定行,最后和右转的最大值取
剩下一定是每次最多走两个,将能一起走的点连边,得到下图,发现不是二分图,但是删掉两条边就是二分图了,因此枚举这两条边的匹配量,之后无视这两条边跑网络流,每个点与源点 / 汇点相连边的流量就是其剩余车数,总车数减去最大流加上之前的匹配量即为答案。
记录¶
0h:H是个看起来巨水的题,但是一时半会没想到,ZYF裂了冲向厕所,MJX开始乱写,写到ZYF回来还写寄了,ZYF重构过了。MJX看E是个巨水题直接写了,ZYF又裂了继续冲刺,MJX和CSK确认了一下直接写了。ZYF回来和ZYF确认个代码就交了。WA了,然后MJX sb了,主席树没新建节点。MJX想了想A推了一下发现是个大模板,直接开抄。
1h:快乐抄模板,期间CSK和ZYF讨论F,想了个完全正确的做法,准备写完A开始写。MJX抄完发现不对,然后仨人开始de,de半天发现MJX又没 init() ,拉出去击毙。交了一发WA了,发现插值的模板有 corner case 需要特判,改了就过了。
2h:ZYF开始写F,MJX开始和CSK想IG,I看半天不咋会,扔了,MJX推了个G的式子,MJX感觉老对了。CSK给ZYF做F数据,写半天一直没对,看没人过先过来搞G了。
3h:半天没调出来,发现MJX纯nt,没考虑条件概率之类的,就硬跑,完全不对,然后一顿改,终于过样例了,但是还是WA。开始双开de F和G
4h:感觉写的很对,但是不完全对,想看看clarification有没有啥东西,然后没看到I改了题意(淦),挂机到最后(x)