Difference between revisions of "2019 Multi-University,HDU Day 4"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
| Line 38: | Line 38: | ||
Solved by Xiejiadong. 01:23:54 (+) | Solved by Xiejiadong. 01:23:54 (+) | ||
| + | |||
| + | 题意：询问一段区间 $a_l,a_{l+1},\cdots a_r$ 中元素 ${|a_1-p|,|a_{l+1}-p|,\cdots ,|a_r-p|}$ 中的 $k$ 大数。 | ||
| + | |||
| + | 题解：利用主席树可以维护一个区间里面一段值域里面元素的个数。 | ||
| + | |||
| + | 对于每个询问二分答案，假设当前答案为 $mid$ ，那么我们需要查询区间里面值域为 $[p-mid,p+mid]$ 的元素个数，元素个数恰好为 $k$ 的就是答案。 | ||
== Problem I == | == Problem I == | ||
Revision as of 10:40, 31 July 2019
Problem A
Solved by Kilo_5723. 00:12:16 (+1)
Problem B
Unsolved.
Problem C
Unsolved. (-3)
Problem D
Unsolved.
Problem E
Unsolved.
Problem F
Unsolved.
Problem G
Solved by Xiejiadong && Weaver_zhu. 02:45:41 (+1)
题意：判断十五数码问题是否无解。
题解：在 Xiejiadong 的强行误导下， Weaver_zhu 写了两个小时 A* 。
直接大力猜结论，大概模拟一下 $0$ 位置的变动。
根据 $0$ 所在位置的行列奇偶性和分行和列的逆序对数量奇偶行相同即可。
Problem H
Solved by Xiejiadong. 01:23:54 (+)
题意：询问一段区间 $a_l,a_{l+1},\cdots a_r$ 中元素 ${|a_1-p|,|a_{l+1}-p|,\cdots ,|a_r-p|}$ 中的 $k$ 大数。
题解：利用主席树可以维护一个区间里面一段值域里面元素的个数。
对于每个询问二分答案，假设当前答案为 $mid$ ，那么我们需要查询区间里面值域为 $[p-mid,p+mid]$ 的元素个数，元素个数恰好为 $k$ 的就是答案。
Problem I
Unsolved.
Problem J
Solved by Kilo_5723 && Xiejiadong. 04:09:28 (+1)