2020-team1-048

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2020-team1 返回]
== 概述 ==
solved: 6/10  dirt: 50%
rank: 20
[[Image(Rank.png,800px)]]

== 流水账 ==

== 总结 ==
Grammy: 科技场？ 开场我又是做了两个结论题，然后给了一个C的建图，给了一个G的做法，就开始挂机了，G因为不好写，到最后也没有人愿意上机写。感觉这场不会的科技太多，后面真的是做不动题了，有几道题的进度看了题解后感觉已经是自己知识水平范围的极限了。
== 题解 ==
A: 每次取一个增量最小的点，一共有三种情况：x<=当前x且y最小，y<=当前y且x最小，x,y均>当前x,y且x+y最小，三种排序后拿两个堆维护一下贪心
B:
C: 上下界可行流。 左边建一排人，右边建一排歌，每首歌左边建上专属于他的语言，每个人右边建他的专属语言节点，中间建一排语言连上左右对应的专属语言节点，找一个上下界可行流。
D: 线性基+每个盒子至多选一个，这两个拟阵求交
E: 乱搞：重复若干次，第t次排序后以1/2^t^概率取一个1~n的排列，更新剩余需要的期望，把重复的排列合并，输出总概率最大的n个排列
题解看不懂
F: 
G:
H: 二分，变成01矩阵，能取到1当且仅当不是每一行都有0
I: 首先用0~3的数表示顺时针四个方向，发现是个同余类，而且不论你怎么转，整个图这个玩意的和都是不变的，并且只要和相同就可以构造解。于是得到判定最终图是否合法的条件：终图可以由初始图得到当且仅当这个东西的和一样。然后考虑鞋子的同向匹配和左右匹配： 横着的一定对这个值贡献0，竖着的一定贡献2. 然后对这个图的LR做二分图匹配，如果不存在完备匹配，一定可以调整没有用到的东西使得这个完备匹配合法；若存在完备匹配，似乎有个结论是不管你怎么调整匹配，得到的值一定是同一个，于是拿这个值和初始值比较一下，如果一样就合法，不一样就匹配数-1去调整。
J:左移1，右移c，左移 c^2^ ，依次类推，按题解的说法c=3.5附近比较优。我的是一个比较类似的写法，c取了5

[/wiki/2020-team1 返回]

概述

solved: 6/10 dirt: 50%

rank: 20

流水账

总结

Grammy: 科技场？ 开场我又是做了两个结论题，然后给了一个C的建图，给了一个G的做法，就开始挂机了，G因为不好写，到最后也没有人愿意上机写。感觉这场不会的科技太多，后面真的是做不动题了，有几道题的进度看了题解后感觉已经是自己知识水平范围的极限了。

题解

A: 每次取一个增量最小的点，一共有三种情况：x<=当前x且y最小，y<=当前y且x最小，x,y均>当前x,y且x+y最小，三种排序后拿两个堆维护一下贪心

B:

C: 上下界可行流。 左边建一排人，右边建一排歌，每首歌左边建上专属于他的语言，每个人右边建他的专属语言节点，中间建一排语言连上左右对应的专属语言节点，找一个上下界可行流。

D: 线性基+每个盒子至多选一个，这两个拟阵求交

E: 乱搞：重复若干次，第t次排序后以1/2t概率取一个1~n的排列，更新剩余需要的期望，把重复的排列合并，输出总概率最大的n个排列

题解看不懂

F:

G:

H: 二分，变成01矩阵，能取到1当且仅当不是每一行都有0

I: 首先用0~3的数表示顺时针四个方向，发现是个同余类，而且不论你怎么转，整个图这个玩意的和都是不变的，并且只要和相同就可以构造解。于是得到判定最终图是否合法的条件：终图可以由初始图得到当且仅当这个东西的和一样。然后考虑鞋子的同向匹配和左右匹配： 横着的一定对这个值贡献0，竖着的一定贡献2. 然后对这个图的LR做二分图匹配，如果不存在完备匹配，一定可以调整没有用到的东西使得这个完备匹配合法；若存在完备匹配，似乎有个结论是不管你怎么调整匹配，得到的值一定是同一个，于是拿这个值和初始值比较一下，如果一样就合法，不一样就匹配数-1去调整。

J:左移1，右移c，左移 c2 ，依次类推，按题解的说法c=3.5附近比较优。我的是一个比较类似的写法，c取了5

附加文件