2019 ICPC China Nanchang Invitational Programming Contest
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 (+)
白送的签到。