2019 ICPC HongKong Onsite

From EOJ Wiki
Revision as of 13:33, 14 December 2019 by Xiejiadong (talk | contribs) (→‎Problem J)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Problem A

Unsolved.

Problem B

Solved by Kilo_5723. 00:17 (+)

Problem C

Unsolved.

Problem D

Solved by Kilo_5723. 00:12 (+)

Problem E

Unsolved.

Problem F

Unsolved.

Problem G

Solved by Kilo_5723 && Weaver_zhu. 01:30 (+2)

Problem H

Unsolved. (-8)

Problem I

Unsolved.

Problem J

Solved by Xiejiadong. 04:13 (+3)

题意:定义 $f(x)=\sum_{i=1}^{k-1}\sum_{j=i+1}^{k} d(x,i) \cdot d(x,j)$ 其中 $d(x,i)$ 表示数 $x$ 的第 $i$ 位,求 $[L,R]$ 中有多少满足 $x\equiv f(x)(mod\;m)$ 。

题解:显然 $f(x)$ 代表的是两两数位的乘积和。

考虑数位 dp ,令 $f[i][j][k]$ 表示处理到第 $i$ 位,$(x-f(x))\; mod\; m=j$ ,目前 $x$ 的数位和为 $k$ ,$p=0/1$ 代表前缀是否相同。

数位和用于计算 $f(x)$ ,$x$ 每次增加对应位置上的数字,减去 $f(x)$ 的增量即可。

用差分分别统计 $\le L$ 和 $\le R$ 的数量,特判 $L$ 是否成立即可。

Problem K

Unsolved.