Difference between revisions of "ICPC 2019 Nanjing Online Contest"

From EOJ Wiki
Jump to navigation Jump to search
(Created page with "== Problem A == Solved by Xiejiadong. 02:41 (+) == Problem B == Solved by Weaver_zhu && Kilo_5723. 03:01 (+9) == Problem C == Solved by Weaver_zhu. 02:20 (+) == Problem...")
 
 
(9 intermediate revisions by 3 users not shown)
Line 2: Line 2:
  
 
Solved by Xiejiadong. 02:41 (+)
 
Solved by Xiejiadong. 02:41 (+)
 +
 +
题意:蛇形矩阵中有 $n$ 个位置是有价值的,价值是位置上的数位和,每次询问一个子矩阵中的价值总和。
 +
 +
题解:蛇形矩阵,给出坐标求位置上的数,可以直接 $O(1)$ 通过分类讨论出来。
 +
 +
只需要知道他是从内往里第几圈就能算出来。
 +
 +
得到了每一个位置的价值,就变成了一个二维数点问题,直接树状数组维护一下就好了。
  
 
== Problem B ==
 
== Problem B ==
  
Solved by Weaver_zhu && Kilo_5723. 03:01 (+9)
+
Solved by Weaver_zhu. 03:01 (+9)
 +
 
 +
数据范围改了没看到,被搞了
  
 
== Problem C ==
 
== Problem C ==
  
 
Solved by Weaver_zhu. 02:20 (+)
 
Solved by Weaver_zhu. 02:20 (+)
 +
 +
毫无营养的分块打表
  
 
== Problem D ==
 
== Problem D ==
  
 
Solved by Kilo_5723. 02:10 (+)
 
Solved by Kilo_5723. 02:10 (+)
 +
 +
题意:给定一个 DAG,每一次等概率从一个点走向其连向的每个点或者停在原地,第 $i$ 次操作会造成 $i$ 的伤害,求总伤害的期望值。
 +
 +
题解:如果每次操作都只会造成 $1$ 的伤害,令 $S(u)$ 代表节点 $u$ 相连的所有点(包括 $u$),到终点的期望伤害就是 $f(u)=1+\frac{1}{|S(u)|}\sum_{v\in S(u)}f(v)$,移项之后就可以算出值。
 +
 +
现在第 $i$ 次操作会造成 $i$ 的伤害,但我们可以将其拆成路径上每个点到终点的路径之和。这样,令 $g(u)$ 代表此时到终点的期望伤害,则 $g(u)=f(u)+\frac{1}{|S(u)|}\sum_{v\in S(u)}g(v)$。同样,移项后计算出答案。
  
 
== Problem E ==
 
== Problem E ==
  
Unsolved. (-5)
+
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 ==
 
== Problem F ==
  
 
Solved by Xiejiadong. 00:50 (+)
 
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 ==
 
== Problem G ==
Line 30: Line 60:
  
 
Solved by Kilo_5723 && Xiejiadong. 01:12 (+)
 
Solved by Kilo_5723 && Xiejiadong. 01:12 (+)
 +
 +
题意:在一个存在负权边的图中,依次加入六条给定起点终点的边,使得加入的边边权尽量小,且加入之后不存在负权环。
 +
 +
题解:每一次加入一条边,用 SPFA 算出两点之间的距离,取反作为边权加入图。
  
 
== Problem I ==
 
== Problem I ==
  
 
Unsolved.
 
Unsolved.

Latest revision as of 06:30, 10 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 (+)

题意:给定一个 DAG,每一次等概率从一个点走向其连向的每个点或者停在原地,第 $i$ 次操作会造成 $i$ 的伤害,求总伤害的期望值。

题解:如果每次操作都只会造成 $1$ 的伤害,令 $S(u)$ 代表节点 $u$ 相连的所有点(包括 $u$),到终点的期望伤害就是 $f(u)=1+\frac{1}{|S(u)|}\sum_{v\in S(u)}f(v)$,移项之后就可以算出值。

现在第 $i$ 次操作会造成 $i$ 的伤害,但我们可以将其拆成路径上每个点到终点的路径之和。这样,令 $g(u)$ 代表此时到终点的期望伤害,则 $g(u)=f(u)+\frac{1}{|S(u)|}\sum_{v\in S(u)}g(v)$。同样,移项后计算出答案。

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 (+)

题意:在一个存在负权边的图中,依次加入六条给定起点终点的边,使得加入的边边权尽量小,且加入之后不存在负权环。

题解:每一次加入一条边,用 SPFA 算出两点之间的距离,取反作为边权加入图。

Problem I

Unsolved.