Contest Info

date: 2018.08.02 12:00-17:00

practice link

Solutions

A. gpa

题目大意：带权平均，可以删除 \(k\) 个，使得答案最大。

题解：分数规划，二分答案，然后用 nth_element 实现，一个 log。

B. div

题目大意：定义 \(n\) 为好的，当且仅当存在 \(x\in[n^{2}+1,n^{2}+2n]\) 使得 \(x\mid n^{4}\)。求超过 \(m\) 的最小的好数。

题解：设 \(t=x-n^{2}\)，则原条件等价于 \(n^{2}+t|t^{2}\)。注意到在题目所给范围下只能有 \(t^{2}=2(n^{2}+t)\) 或 \(t^{2}=3(n^{2}+t)\)，解这两个佩尔方程即可。

C. grf

题目大意：给出一个 \(n(n\le19)\) 个点的无向图，设图 \(G\) 的连通块数量为 \(x\)，定义 \(k(G)=x^{x-1}\)，求给出的图的所有生成子图的 \(k\) 之和。

题解：

解法一：设 \(S=\{1,2,\cdots,n\}\)，\(P\) 为 \(S\) 的一个划分，设 \(f(P)\) 表示 \(P\) 中每个集合内部连通，集合间不连通的方案数，\(g(P)\) 表示集合内部随意，集合间不连通的方案数。则答案为 \[ \begin{aligned}&\sum_{P}f(P)|P|^{|P|-1}\\ =&\sum_{i=1}^{n}i^{i-1}\sum_{|P|=i}f(P) \end{aligned} \] 考虑通过 \(g\) 求 \(f\)，定义 \(P'\) 是 \(P\) 的子划分，当且仅当 \(P'\) 的任意一个元素都是 \(P\) 的某个元素的子集，为了方便记为 \(P'\subset P\)，那么有 \[ f(P)=g(P)-\sum_{P'\subset P,P'\neq P}f(P') \] 记 \(u(i)=\sum_{|P|=i}f(P),v(i)=\sum_{|P|=i}g(P)\)，则有 \[ \begin{aligned}u(i)=&\sum_{|P|=i}(g(P)-\sum_{P'\subset P,P'\neq P}f(P'))\\ =&v(i)-\sum_{|P|=i}\sum_{P'\subset P,P'\neq P}f(P')\\ =&v(i)-\sum_{j=i+1}^{n}\sum_{|P'|=j}\left( f(P')\sum_{P'\subset P,P'\neq P,|P|=i}1 \right) \end{aligned} \] 注意到 \(\sum_{P'\subset P,P'\neq P,|P|=i}1\) 相当于将一个大小为 \(j\) 的集合划分为 \(i\) 个集合的方案数，即第二类斯特林数 \(\begin{Bmatrix}j\\i\end{Bmatrix}\)，故上式等于 \[ v(i)-\sum_{j=i+1}^{n}\begin{Bmatrix}j\\i\end{Bmatrix}u(j) \] 接下来我们考虑求 \(v\)，定义集合幂级数 \(h=\sum_{T}2^{T内部的边数}x^{T}y^{|T|}\)。容易发现，\(\displaystyle v(i)=[x^{S}y^{|S|}]\frac{h^{i}}{i!}\)。

时间复杂度 \(\mathcal{O(n^{3}2^{n})}\)。

D. inv

题目大意：给出一个 \(1\) 到 \(n\) 的全部偶数的排列，现在要将它和一个由 \(1\) 到 \(n\) 所有奇数组成的单调数列归并起来，最小化归并后数列的逆序对数。

题解：偶数内部的逆序对数是一定的，考虑将奇数依次插入到偶数的 \(\frac{n}{2} + 1\) 个空中去。

用线段树维护每个空位会产生的逆序对数，当做完一个奇数之后会对一个前缀 \(+1\) ，对一个后缀 \(-1\) ，因此一定存在一个最优的放法使得插的空位是单调不减的。

因此直接每个奇数贪心取产生逆序对数最小的位置即可。

comment: 就算题目给出的奇数数列没有规定顺序，奇数数列单调递增的时候也能取到最优解。

E. room

题目大意：\(n\) 个四人间，\(4n\) 个人，一开始的居住状态为 \((x_{i0},x_{i1},x_{i2},x_{i3})(1\leq i\leq n)\)。要将居住状态调整为 \((y_{i0},y_{i1},y_{i2},y_{i3})\) ，问最少有几个人被调整。

题解：费用流。先将起止状态都在一个房间的人捆绑在一起，那么起始每个房间向对应的若干捆人连边 \((1,0)\)，这些捆人向终态每个房间连 \((1,4-w)\) 的边，表示最终房间中有 \(w\) 个人没有移动，而另外 \(4-w\) 个人被调整过来。

然后，源点连起始每个房间 \((1,0)\)，终态每个房间连汇点 \((1,0)\)，注意源点还要连终态每个房间 \((1,4)\)，表示最终房间可能每个人都是被调整过来的。

std solution: 起始第 \(i\) 间宿舍向终止第 \(j\) 间宿舍连边，费用为它们的交，二分图带权匹配。

F. take

树状数组简单维护即可。

G. max

签到题

H. subseq

题目大意：给定一个长度为 \(n\) 的整数数列 \(a_n\) ，求字典序第 \(k\) 小的下标序列 \(b\)，使得 \(a_{b_1},\dots,a_{b_m}\) 是严格单调上升序列。

题解：从后往前 dp 求出以位置 \(i\) 开头的单调上升序列数量，然后从前往后确定每一位，注意不能枚举到不单调上升的，以及数量爆 long long 可以与 inf 取 min 避免。

I. vcd

题目大意：定义一个点集 \(S\) 是好的，当且仅当对于 \(S\) 的任意子集 \(T\)，都存在 \(x,y_{1},y_{2}\in R,y_{1}\le y_{2}\)，使得 \([x,\infty)\times[y_{1},y_{2}]\cap S=T\)。给出 \(n\) 个点，求出它的好的非空子集的数量。

题解：首先容易知道一行最多只有一个点，并且对于 \(y_{i}<y_{j}<y_{k}\) 的任意三个点，必须要满足 \(x_{i}>x_{j}<x_{k}\)。运用这个条件可以知道，点数大于等于 \(4\) 时一定不是好的。因此只需要对小于等于 \(3\) 个点的情况讨论一下即可。

J. plan

签到题

Dirt Replay

G：-1 Z 和 D 在讨论 corner case 的时候，W 就着急上去写，结果写错了一个地方（应该慢慢写，写完给队友看）

F：-1 Z 的 Fenwick Tree 单点修改没用上传入的值（没有造数据测试，没有 code review）

E：-1 一开始建图的算法有问题，没有限制起始一个宿舍的人的总流量，也没有一个人都不留在原宿舍的边（造数据）

I：-2 第一次结论有问题，第二次 ans 没用 ll（code review，极限数据测试）

H：-2 第一次没看到数据范围更新的 clarification，第二次算法有问题，没有判断答案递增（造数据）