Difference between revisions of "ICPC 2019 Nanjing Online Contest"
| Line 29: | Line 29: | ||
== Problem E == | == Problem E == | ||
| − | Upsolved. | + | Upsolved by Weaver_zhu. |
题目：求 $\sum\sum...\sum(a_1,...a_k)^2$ | 题目：求 $\sum\sum...\sum(a_1,...a_k)^2$ | ||
| + | |||
题解：枚举gcd，莫比乌斯反演然后杜教筛。$ans=\sum\limits_{k}\sum\limits_{i=1}^{n}i^2\sum\limits_{j=1}^{n/i}\mu(j)\frac{n}{ij}^k$,把 $k$ 求和移到最后就是等比数列，交换 $i,j$ 得 $\sum\limits_{j=1}^{n}calc(j) \times \mu * I^2$，后部分杜教筛，前部分数论分块。 | 题解：枚举gcd，莫比乌斯反演然后杜教筛。$ans=\sum\limits_{k}\sum\limits_{i=1}^{n}i^2\sum\limits_{j=1}^{n/i}\mu(j)\frac{n}{ij}^k$,把 $k$ 求和移到最后就是等比数列，交换 $i,j$ 得 $\sum\limits_{j=1}^{n}calc(j) \times \mu * I^2$，后部分杜教筛，前部分数论分块。 | ||
Revision as of 01:15, 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
Upsolved by Weaver_zhu.
题目：求 $\sum\sum...\sum(a_1,...a_k)^2$
题解：枚举gcd，莫比乌斯反演然后杜教筛。$ans=\sum\limits_{k}\sum\limits_{i=1}^{n}i^2\sum\limits_{j=1}^{n/i}\mu(j)\frac{n}{ij}^k$,把 $k$ 求和移到最后就是等比数列，交换 $i,j$ 得 $\sum\limits_{j=1}^{n}calc(j) \times \mu * I^2$，后部分杜教筛，前部分数论分块。
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.