ICPC 2019 Nanjing Online Contest

From EOJ Wiki
Jump to navigation Jump to search

Problem A

Solved by Xiejiadong. 02:41 (+)

题意:蛇形矩阵中有 $n$ 个位置是有价值的,价值是位置上的数位和,每次询问一个子矩阵中的价值总和。

题解:蛇形矩阵,给出坐标求位置上的数,可以直接 $O(1)$ 通过分类讨论出来。

只需要知道他是从内往里第几圈就能算出来。

得到了每一个位置的价值,就变成了一个二维数点问题,直接树状数组维护一下就好了。

Problem B

Solved by Weaver_zhu && Kilo_5723. 03:01 (+9)

Problem C

Solved by Weaver_zhu. 02:20 (+)

Problem D

Solved by Kilo_5723. 02:10 (+)

Problem E

Unsolved. (-5)

Problem F

Solved by Xiejiadong. 00:50 (+)

题意:给出一个全排列,第 $i$ 次操作,$a_1=i$ ,每次可以从 $a_i$ 所在全排列中的附近 $k$ 个位置选择一个 $<a_i$ 数作为 $a_j$ ,要求字典序最大的,求这样的数列非 $0$ 数有几个。

题解:产生这个数列的方式,显然是贪心,每次在全排列中的附近 $k$ 个位置选择一个 $<a_i$ 且最大的数。

于是就发现,当前的数列非 $0$ 个数就是当前数所在位置在全排列中的附近 $k$ 个位置选择一个 $<a_i$ 且最大的数的数列中非 $0$ 数量 $+1$ 。

直接用 set 维护一下窗口的数,二分查找就能得到每一个数周围满足要求的数,然后从小往大递推一下就好了。

Problem G

Unsolved.

Problem H

Solved by Kilo_5723 && Xiejiadong. 01:12 (+)

Problem I

Unsolved.