昨天晚上被教练暗中怼了一波，然后让我们认真想题。
也觉得是这样的，所以决定以后每天都写日志。
然后今天是想思维题。
\(\text{Sports Festival}\)
有 \(n\) 个人和 \(m\) 个活动，每个人对所有活动有一个喜爱顺序。
你可以*决定每个活动是否开展，随后每个人会选择开展的最喜爱的活动参加。
最小化参加人数最多的活动的参加人数。
\(1<=n,m<=5000\)
首先，因为你的每个人都有一个喜爱的顺序，然后让你最小化参加人数最多的活动的参加人数。
考虑到可以先假设每个活动都开展，那么可以知道当前参加人数最多的活动。
要最小化，就不开展他。
由于不能全部不开展，于是执行到只剩一个的时候，就是最优的了。
复杂度为 \(\text{ O( nm ) }\) 。
\(\Large{\textcolor{green}{\text{Accept}}}\)
\(\text{Regular Bridge }\)
构造一张无向图，每个点的度都是 \(k\) ，且至少存在一条边是桥。
无解输出 \(\text{NO}\) 。
\(k<=1000\) 。
构造题目。
从桥的定义下手，一条边被称为桥只有在没了这条边之后会多出一个连通分量。
也就是说，这条边是唯一的连接了两个强连通分量。
去掉桥之后，是左边与右边都有一个连通块中有一个度数为 \(k-1\)，其余度数为 \(k\) 。
因为是无向图，所以一个节点的度既是出度又是入度，也就是说无向图的度数一定是偶数。
那么考虑当 \(k\) 为偶数的时候，其中一个连通块的度数变为了 \(nk-1\) 。
这样度数就是奇数，所以只有在 \(k\) 为奇数时有解。
那么我们假设左边有 \(l\) 个点，右边有 \(r\) 个点。
我们相当于是要设立左边的 \(l-1\) 与右边的 \(r-1\) 个度为 \(k\) 的点，然后再设立两个度为 \(k-1\) 的点，再将两点相连。
这就是我们的构造方案。
一个比较简单的构造就是取 \(l = k + 2\) ，然后先取出一个节点度数为 \(k-1\) 个。
然后我们取 \(k-1\) 个点，让这些点向他连边。
然后还剩 \(2\) 个点，两个点先连一条边，再让 \(k-1\) 个点向他们都连边。
然后就构造完了，右边也是一样的。
然后将两个确定的度数为 \(k-1\) 的点之间进行连上边。
然后其实就是先构造完全图，然后再删去一部分边，就好了。
时间复杂度为 \(\text{O(k^2)}\) 。
\(\Large{\color{green}{\text{Accept}}}\)
\(\text{Rearranging}\)
给定 \(n\) 个整数 \(a_1…a_n\)，开始时，A 将它们任意排列。
接着，B 每次可以选择两个相邻且互质的数，交换它们的位置。
A 会最小化字典序， B 会最大化字典序，求最终序列。
\(1<=n<=2000\)
容易想到一对不互质的数的相对位置是不会改变的。
根据这个来建图，然后求出的最大的拓扑序就是 B 答案。
考虑 A 怎么做。
容易发现 A 就是对于图上所有的点进行一个定向的过程。
那么为了让最终答案小，我们尽量小的在前面，然后大的在后面，然后满足相对位置不变。
于是贪心建图，从小到大就完了。
因为这题太神仙了，我并没有自己想出来是看的题解，所以其他相关证明见我博客中专门关于这道题的随笔。
\(\Large{ \color{green}{ \text{Accept} } }\)
\(\text{Wash}\)
你现在要洗 \(L\) 件衣服。你有 \(n\) 台洗衣机和 \(m\) 台烘干机。由于你的机器非常的小，因此每台机器在一个时刻只能洗涤(烘干)一件衣服 。
第i台洗衣机洗一件衣服需要 \(w_i\) 分钟，第 \(i\) 台烘干机烘干一件衣服需要 \(d_i\) 分钟。请问把所有衣服洗干净并烘干，最少需要多少时间？
假设衣服在机器间转移不需要时间，并且洗完的衣服可以过一会再烘干。
\(L,n,m<=10^6\)
首先将洗衣机的速度于烘干机的速度从小到大排序。
一台洗衣机会在 \(w_i, 2w_i , 3 w_i\) 的时候洗完衣服。
然后考虑配对出在洗衣机做 \(L\) 个的最快时间。
然后烘干也是一样，然后与洗衣服时间倒过来配对取最值即可。
\(\Large{\color{green}{\text{Accept}}}\)
今日已 \(\Large{\text{vp:}}\)
\(\Large{\text{ABC156 DE}}\)