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)
用归并求个逆序对就搞定了