Difference between revisions of "2019 ICPC HongKong Onsite"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) |
|||
Line 38: | Line 38: | ||
Solved by Xiejiadong. 04:13 (+3) | 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 == | == Problem K == | ||
Unsolved. | Unsolved. |
Latest revision as of 13:33, 14 December 2019
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.