Difference between revisions of "2018 Multi-University, HDU Day 2"

From EOJ Wiki
Jump to navigation Jump to search
Line 22: Line 22:
  
 
Solved by zerol. 00:14 (+1)
 
Solved by zerol. 00:14 (+1)
 +
 +
题意:给一列数,可以花 y 交换相邻两个元素,最后要为每个逆序对付出 x。
 +
 +
题解:显然交换两个相邻元素一定能减少一个逆序对且至多减少一个,所以答案就是 逆序对数量 × min{x,y}。逆序对数量用树状数组或者归并可以求出。

Revision as of 12:53, 25 July 2018

Problem D

Solved by ultmaster. 00:16 (+)

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

题解:好像只有 Yes。证明不详。

Problem E

Solved by zerol. 02:06 (+1)

Problem G

Solved by kblack. 00:39 (+1)

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

题解:注意到 $b_i$ 是一个排列,每个位置总计最多 $+q$,值会总共最多变化次数是对数级的,故只要线段树记录 $ a_i - (a_i \bmod b_i) $,对于要突变的值暴力维护即可。

Problem J

Solved by zerol. 00:14 (+1)

题意:给一列数,可以花 y 交换相邻两个元素,最后要为每个逆序对付出 x。

题解:显然交换两个相邻元素一定能减少一个逆序对且至多减少一个,所以答案就是 逆序对数量 × min{x,y}。逆序对数量用树状数组或者归并可以求出。