Difference between revisions of "ICPC 2019 Nanjing Online Contest"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) |
|||
Line 13: | Line 13: | ||
== Problem B == | == Problem B == | ||
− | Solved by Weaver_zhu | + | Solved by Weaver_zhu. 03:01 (+9) |
+ | |||
+ | 数据范围改了没看到,被搞了 | ||
== Problem C == | == Problem C == |
Revision as of 00:53, 3 September 2019
Problem A
Solved by Xiejiadong. 02:41 (+)
题意:蛇形矩阵中有 $n$ 个位置是有价值的,价值是位置上的数位和,每次询问一个子矩阵中的价值总和。
题解:蛇形矩阵,给出坐标求位置上的数,可以直接 $O(1)$ 通过分类讨论出来。
只需要知道他是从内往里第几圈就能算出来。
得到了每一个位置的价值,就变成了一个二维数点问题,直接树状数组维护一下就好了。
Problem B
Solved by Weaver_zhu. 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.