2019 ICPC China Nanchang Invitational Programming Contest

From EOJ Wiki
Jump to navigation Jump to search

Replay

Xiejiadong:

  • 怎么会有中文题面这种操作。
  • 怎么会有签到题是 “hello world” 这种操作。
  • Weaver_zhu 被巨大套房砸中。于是我又变成了一人间。(准确的说,是三个人都是三人间。
  • 被模板砸中。甚至一摸一样。
  • 靠一手模板,抢了第一个 Onsite 一血。
  • 热身赛当天,大雨磅礴,校园积水。鞋袜湿透。
  • 我们那排送气球的 XJJ 好可爱。

Kilo_5723:

Weaver_zhu:

Problem A

Solved by Xiejiadong. 00:45 (+)

题意:求最小边权使得四对点联通。

题解:斯坦纳树模板题。抄就完事了。

Problem B

Unsolved.

Problem C

Solved by Weaver_zhu. 04:51 (+6)

Problem D

Unsolved.

Problem E

Unsolved.

Problem F

Solved by Xiejiadong. 01:14 (+)

题意:支持两个操作:单点修改;求 $\oplus_{i=l}^{r} \oplus _{j=i}^{r} f(i,r)$ , 其中 $f(l,r)=\oplus _{i=l}^r a_i$ 。

题解:考虑对于一个区间,每一位的贡献。

因为全部都是异或,所有只需要考虑每一位贡献的奇偶性。

  • 如果区间的长度为奇数,所有的奇数位有贡献。
  • 如果区间的长度为偶数,答案为 $0$ 。

Problem G

Solved by Kilo_5723. 01:39 (+)

Problem H

Solved by Xiejiadong && Kilo_5723. 04:16 (+3)

题意: $c_{i,j}=c_i \oplus c_j$ ,将 $c_i$ 排序以后进行两种操作:将一个区间全部开方,询问单点值。

题解:求 $c_i$ 的过程是裸的 Fwt ,操作为异或即可。

对于第二部分操作,显然开方的次数不会太多, 对于每一位操作次数都是 $log(c_i)$ ,所以对于每一位只需要暴力开方,到 $1$ 了不再操作即可。

所以我们只需要标记每一位进行的开方次数即可。

线段树维护区间和,区间修改,单点查询,暴力开方即可。

Problem I

Unsolved.

Problem J

Solved by Kilo_5723. 00:57. (+)

Problem K

Solved by Xiejiadong. 00:10 (+)

题意:给出区间,求 $\sum _{i=1}^k ( k\times \sum_{j=l_i}^{r_i} a_j )$ ,可以任意调整 $\sum_{i=l_i}^{r_i} a_i$ ,使得值最大。

题解:贪心。价值大的在后即可。

Problem L

Solved by Xiejiadong. 00:02 (+)

白送的签到。