Difference between revisions of "2019 ICPC HongKong Onsite"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) (Created page with "== Problem A == Unsolved. == Problem B == Solved by Kilo_5723. 00:17 (+) == Problem C == Unsolved. == Problem D == Solved by Kilo_5723. 00:12 (+) == Problem E == Unso...") |
Xiejiadong (talk | contribs) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 25: | Line 25: | ||
== Problem G == | == Problem G == | ||
| − | Solved by Kilo_5723. 01:30 (+2) | + | Solved by Kilo_5723 && Weaver_zhu. 01:30 (+2) |
== Problem H == | == Problem H == | ||
| 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.