2018 Multi-University Training Contest 2

From EOJ Wiki
Jump to navigation Jump to search

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)

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