2019 ICPC China Nanchang Invitational Programming Contest

Replay

Xiejiadong:

• 怎么会有中文题面这种操作。

• 怎么会有签到题是 “hello world” 这种操作。

• Weaver_zhu 被巨大套房砸中。于是我又变成了一人间。（准确的说，是三个人都是单人间。

• 被模板砸中。甚至一摸一样。

• 靠一手模板，抢了第一个 Onsite 一血。

• 热身赛当天，大雨磅礴，校园积水。鞋袜湿透。

• 我们那排送气球的 XJJ 好可爱。

Kilo_5723:

• 中文题面看呆了，然后 喜提新题一堆 果然读错了题。

• 志愿者服务全程好评。

• 我也是摸到过一血气球的人了。

• 队友开始坐在上机位，45 min 下来之后已经 3T 了？

• 在大雨里不撑伞从酒店走到学校，这种骚操作以后还是不搞了。

• 赛场降温用的冰块摸起来真舒服。

• 一血气球还是没保住（物理）。

• 队友的房间是我这辈子见过最大的酒店房间（后来才知道叫套房）。然后果断抛弃了我室友去享受富裕的气息了。

• 赛后甩锅大会，找规律硬搞 B 题的锅还是没甩掉。深刻意识到自己需要拓宽知识面。

Weaver_zhu:

Problem A

Solved by Xiejiadong. 00:45 (+)

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

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

Problem B

Unsolved.

Problem C

Solved by Weaver_zhu. 04:51 (+6)

题意：求a的b的b的。。。（c个b）次方

题解：欧拉定理有个扩展，底数和模数不互素的时候如果指数大于欧拉函数，则取模后再加一个模数。注意要用真实值，如果超过模数就改成-1。现场的时候不知道为什么，故意不用这个定理就过了

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 (+)

题意：有 $n$ 个玩家，每个人有三个游戏下的能力值，你可以任选两个人进行任何一种游戏并且淘汰败方，直到最后只剩一个玩家并成为冠军，问哪些玩家有可能成为冠军。

题解：可能成为冠军的玩家只有两种可能：

1）某个能力值是所有人中最高的

2）在任何一种模式下可以打败可能成为冠军的玩家

因此，先将三种能力值中最高的几个玩家加入队列，并不停把三种能力值任意一种比队列首的人高的人加入队列，队列为空时，加入过队列的人就是所有可能成为冠军的玩家。

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. (+)

题意：给定 $n$ 个字符串，将每个字符串的每个前缀加入序列，定义一个字符串的权值为字符串每一位的权值之积 $\mod m$，对这 $n$ 个字符串中的每一个询问序列中有多少字符串是其前缀且权值高于它。

题解：将 $n$ 个字符串加入 Trie 树，每个节点计数并计算权值，从每一个字符串的结束位置向上遍历 Trie 树，并对权值更高的节点的计数求和。

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 (+)

白送的签到。