2018 Multi-University Training Contest 2

Problem A

Unsolved.

Problem B

Unsolved.

Problem C

Xiejiadong：就靠着这一题，多校打到了人生巅峰，一个人碾压一队。

Solved.

题意：给一个无向图，求用最少的路径（可以非简单），覆盖无向图的所有边。

题解：每个人尽量的走欧拉回路，但是图中有奇数点怎么办

显然，一张图中的奇数点有偶数个，随便地两两连起来，形成一张存在欧拉回路的无向图，在图上跑出欧拉回路

我们所求的路径即是欧拉回路，但由于有一些边是我们自己添加上去的，所以我们需要在找出的环上把新添加的边断开，形成好几条路径，这里就需要好几个人分别来走

还有一个问题就是图本身可能是不联通的，我们需要对每一个联通图做一次欧拉回路

时间复杂度$O(m+n)$

Problem D

Solved.

题意：给$[n]$每次操作删除一个数和它所有的因数，求先手胜还是后手胜。

题解：先手必胜！

证明：考虑将游戏变成初始时只有$2$~$n$

如果先手必胜的话，那么先手第一步按这样取就获胜了；

如果后手必胜的话，那么先手第一步取走1就获胜了。

所以全输出Yes就行了。

Problem E

Solved.

题意：构造 2000×2000 的 01 矩阵，使得 1 的数量不少于 85000，且不存在 (x1, y1), (x1, y2), (x2, y1), (x2, y2) 同时为 1。

题解：取质数$m$使得$n=m*m$，考虑构造$n$个有比较多$1$的$01$序列使得没有任意两个有超过一个公共$1$。

对于每个$k,b\in [0,p)$取$i*p+(k*i+b)\%p(i\in [0,p))$为$1$即可。

Problem F

Unsolved.

Problem G

Solved.

题意：给出排列 $b_i$，对 $a_i$ 区间 $+1$，维护 $\lfloor \frac{a_i}{b_i} \rfloor$，区间求和。

题解：因为$b$是排列，考虑全部加都是$1$到$n$，答案最后也不过$n*log_{2}n$(调和级数)

用线段树来维护

记录一下线段树每个节点答案改变最小需要加几，查询的时候等于了就暴力下传修改

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Solved.

题意：任意交换相邻的两个数，或者逆序对都有花费的代价，求最小的花费代价。

题解：交换相邻的两个数，最多减少一个逆序对

也就是说，花费的代价一定是逆序对数量∗min(x,y) ∗min(x,y)

用归并求个逆序对就搞定了