Difference between revisions of "2019 ICPC HongKong Onsite"

From EOJ Wiki
Jump to navigation Jump to search
(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...")
 
 
(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.