2020-team1-023

从 Trac 迁移的文章

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

原文章内容如下：

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

== 流水账 ==

== 总结 ==
好消息 又打爆leg了
坏消息 罚时全是oscar的
I题思维过程
显然结论1:如果两边点数不一样去掉少的那边是一个可行解
显然结论2:如果最终有个奇数大小连通块大小>1就可以额外操作几次使得变成1
显然结论3:一定存在一种剩余所有点大小都是1的方案
显然构造:去掉最小覆盖集
显然结论4:没有完美匹配时一定有解
猜想：有完美匹配时一定无解
== 题解 ==
A: 轮数充足，把所有得分分散到不同轮
B: dp,将排列中每个位置的值抽象成一个从这个位置指出去的箭头，f[i][j][mask]表示前i个数，在i的3个位置前有j个右箭头未指定目标，i的前3个位置的状态为mask，0代表左箭头，1代表右箭头，的方案数
C: 边数不对/度数不对->no
n=1->yes 0 1
先随便选一个作为0号点，随便分配popcount为1的点，从小到大枚举popcount，再枚举popcount对应点，分别去掉最后一个1和倒数第二个1，拿两个点出边的交确定当前点编号，最后验证一遍
D: 平均数，特判0，暴力模拟也可
E: 
F: 三维偏序
G: STL
H: 求出二次函数所有交点，暴力Kruskal
I: 有完美匹配->no
否则yes，方案取最小覆盖集
J: python
K: python 维护一次函数
L: 斜线dp

[/wiki/2020-team1 返回]

概述

solved: 11/12 dirt: 27%

rank: 4

流水账

总结

好消息 又打爆leg了

坏消息 罚时全是oscar的

I题思维过程

显然结论1:如果两边点数不一样去掉少的那边是一个可行解

显然结论2:如果最终有个奇数大小连通块大小>1就可以额外操作几次使得变成1

显然结论3:一定存在一种剩余所有点大小都是1的方案

显然构造:去掉最小覆盖集

显然结论4:没有完美匹配时一定有解

猜想：有完美匹配时一定无解

题解

A: 轮数充足，把所有得分分散到不同轮

B: dp,将排列中每个位置的值抽象成一个从这个位置指出去的箭头，f[i][j][mask]表示前i个数，在i的3个位置前有j个右箭头未指定目标，i的前3个位置的状态为mask，0代表左箭头，1代表右箭头，的方案数

C: 边数不对/度数不对->no

n=1->yes 0 1

先随便选一个作为0号点，随便分配popcount为1的点，从小到大枚举popcount，再枚举popcount对应点，分别去掉最后一个1和倒数第二个1，拿两个点出边的交确定当前点编号，最后验证一遍

D: 平均数，特判0，暴力模拟也可

E:

F: 三维偏序

G: STL

H: 求出二次函数所有交点，暴力Kruskal

I: 有完美匹配->no

否则yes，方案取最小覆盖集

J: python

K: python 维护一次函数

L: 斜线dp

附加文件