【题解】第十六届浙江大学宁波理工学院程序设计大赛重现赛

The 2019 Ningbo Institute of Technology, ZJU Programming Contest

Super easy: A/K

Easy: B/C/I/J

Medium: D/E/H

Hard: F/G

D. 雷顿女士与分队(hard version)


动态规划

显然先将所有人按能力值大小排序。

dp_i表示从1分到第i个位置,矛盾因数的最小值

转移方程:



E. 雷顿女士与平衡树


首先题目显然可以将最大值和最小值分为两部分分别计算。
求最大值的方法:从小到大将每个点与相连的点用并查集合并,同时维护每个联通块的size,此时显然可以计算此点作为最大值的路径条数。
计算最小值的方法同理。

H. 雷顿女士与选书


我们对于计算合并两个分馆的方案,可以将两个分馆的方案进行卷积运算。
然后就显然可以用线段树来修改和维护区间。
std复杂度为,一些做法可能导致复杂度退化为如使用矩阵乘法运算或者退化为,如使用线段树时分治k导致重复运算,不过此方法可用记忆化搜索抢救。
除此之外,也可以用生成函数来理解,可以将每个位置储存的信息看成是(ax+1)的多项式,然后维护多项式乘法。本题也可以使用树状数组,有两种方法第一种是强行退化成mlog_n^2k^2,但是要卡常。另一种是用树状数组维护一个多项式前缀卷积以及多项式前缀逆卷积。然后ans=get_val(r)*get_inv[l-1],get_val是树状数组求前缀卷积get_inv是前缀逆卷积,复杂度为

F. Lady Layton with Math

















先推一波莫比乌斯反演。
显然能数论分块,后面的狄利克雷卷积部分用杜教筛来求。
将欧拉函数和莫比乌斯函数分别与常函数1卷积,分别可以得到标号函数和幺元函数。而常函数与常函数卷积则能得到一个除数函数,可以用数论分块来根号复杂度求得。

G. 雷顿女士与多米诺骨牌

数据范围比较小,不是网络流就是DP,然后min⁡(𝑛,𝑚)>20显然不能用插头DP,所以考虑费用流。
二分图取消流量优先建模。
首先拆点,构建一个双层网络,对第一层网络进行黑白染色,第二层网络进行白黑染色(两层网络对应节点的颜色相反),发现黑白色节点构成一张二分图。并且至少存在一种方案使得整张图满流(所有对应节点进行自我匹配,则流量为n*m达到满流)
此时流量已经不起作用,也就取消掉了费用流流量优先的性质。
对于强制参与匹配,则可删除掉对应节点之间的自我匹配边,然后如果不满流,则说明强制匹配失败,无解。
对于强制不能参与匹配,则可只保留对应节点之间的自我匹配边,删除其他边。
除此之外也可以使用带上下界费用流的建模。
关于二分图取消流量优先的建模,在这里进行说明:

下图是一个二分图,在求仅最大权匹配的时候如果直接建图跑费用流的话会得到如下的图

然后跑出来答案为4,因为费用流默认流量优先满足最大。费用流优先满足最大流,其次才满足最大费用这一点很烦。所以思考如何能够消除费用流费用优先。

为了达到这个效果,我们将整个二分图复制一份,放到它后面。并且将对应的节点连上一条“引流边”,引流边的流量限制为1,费用为0。

接下来请发挥一下空间想象能力,我们认为“引流边”是横向的,而二分图中原来的边是纵向的。对于一个节点,它在匹配的时候只有两种可能:

1、横向进行自我匹配。

2、纵向进行二分图匹配。

不可能会有点找不到匹配的对象,因为至少每个点都能够自我匹配。

我们重点看一下横向的自我匹配,如果某一个点进行了横向的自我匹配,那么将会从两张二分图中同时占用该点,这个点将不能够进行任意一张二分图匹配。这样做的结果相当于在两张二分图中同时删除这个节点。

这样就能强制保持满流,也就消除了费用流流量优先的性质。

为了保证每个点的流量只能够横向或者纵向匹配,而不是在网络中循环。两张图的源汇点要整好相反,即第一张图连接源点的集合在第二张图中连接汇点,第一张图连接汇点的点要在第二张图中连接源点。

接下来只要同时进行两张二分图的匹配,由于是两张图,所以最终答案要除以2。

该图为达到最大费用时网络中流的示意图。最终最大费用为20,所以输出20/2=10为正确答案。


此模型在进行强制匹配时只需删除“引流边”就可以达到效果。

update:

出题人:
A/B/C/D/F/H/I/J/K Megalovania
E/G winterzz1(四糸智乃)
D题是某人打CF读了假题写的假代码(能WA7)
G题因为校赛的时候本地oj不支持多组...只能合并数据,然后复杂度就不太对劲了,理论复杂度1e9~1e10,其实应该是单组5s比较合适。



全部评论
D雷顿女士与分队https://www.cnblogs.com/myrtle/p/12046001.html E雷顿女士与平衡树https://www.cnblogs.com/myrtle/p/12046384.html
点赞 回复
分享
发布于 2019-12-18 10:35

相关推荐

点赞 评论 收藏
转发
4 3 评论
分享
牛客网
牛客企业服务