2020-team1-C004

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]
== 概述 ==
solved: 5/12  dirt: 62%
rank: 35
[[Image(Rank.png,800px)]]

== 流水账 ==

== 总结 ==
在路上了
== 题解 ==
A: 先随便匹配生成一些不相交的环，然后依次把环并起来，可以证明任何两个合法环存在一种并起来的方式使得并后仍然是合法的
B: 
C: 圆的左下角互不重合，依次询问后容斥
D: dp
E: 搞一组基出来，基外一定有用，基内被基外消过的一定有用，其余没用
F: 需求度数比当前最大度数大的时候无解，否则猜想一定有解
每轮设开始时最大度数为d，优先去掉d和d之间的边，然后跑一遍d和d-1之间的边的二分图匹配，根据hall定理可以证明完美匹配存在，
删掉完美匹配中的边可以转化为最大度数为d-1的情况，归纳一下发现猜想正确
G: 搞一个比300*100还大的权值系数，然后最小割
H: 根据排序不等式可以证明字符出现次数越小编码长度越大
dp，f[i][j][k]代表频率第i高的字符串长度为j，trie上深度为j的节点有k个，转移要么加一个当前深度节点要么深度-1、当前深度节点/2
I: 枚举所有mu!=0的因子容斥
J: 
K: 网络流，建一个额外节点，把所有节点的最小出边连向这个点，把这个点用（别的节点的）最小入边连向所有节点
L: 
M: 插头dp

[/wiki/2020-team1 返回]

概述

solved: 5/12 dirt: 62%

rank: 35

流水账

总结

在路上了

题解

A: 先随便匹配生成一些不相交的环，然后依次把环并起来，可以证明任何两个合法环存在一种并起来的方式使得并后仍然是合法的

B:

C: 圆的左下角互不重合，依次询问后容斥

D: dp

E: 搞一组基出来，基外一定有用，基内被基外消过的一定有用，其余没用

F: 需求度数比当前最大度数大的时候无解，否则猜想一定有解

每轮设开始时最大度数为d，优先去掉d和d之间的边，然后跑一遍d和d-1之间的边的二分图匹配，根据hall定理可以证明完美匹配存在，

删掉完美匹配中的边可以转化为最大度数为d-1的情况，归纳一下发现猜想正确

G: 搞一个比300*100还大的权值系数，然后最小割

H: 根据排序不等式可以证明字符出现次数越小编码长度越大

dp，f[i][j][k]代表频率第i高的字符串长度为j，trie上深度为j的节点有k个，转移要么加一个当前深度节点要么深度-1、当前深度节点/2

I: 枚举所有mu!=0的因子容斥

J:

K: 网络流，建一个额外节点，把所有节点的最小出边连向这个点，把这个点用（别的节点的）最小入边连向所有节点

L:

M: 插头dp

附加文件