2019 Multi-University,Nowcoder Day 5

Problem A

Solved by Kilo_5723. 00:17:42 (+)

Problem B

Solved by Kilo_5723. 01:27:34 (+)

Problem C

Upsolved Weaver_zhu. (-8)

Problem D

Upsolved by Kilo_5723.

Problem E

Upsolved by Xiejiadong.

题意：求所有子图的最大独立集之和。

题解：$n$ 只有 $26$ 考虑状态压缩。

$f[x]$ 表示子图为 $x$ 的时候，最大独立集。

我们只考虑从最低位的转移，显然这个图的最大独立集变大了，只能是最低位加入的时候，他的相邻顶点都不在集合中，也就是状态 $x\&\~(e[lowbit(x)])$ ， $lowbit$ 表示最低位。

所以 $f[x]=max\{f[x-lowbit(x)],f[x\&\~(e[lowbit(x)])]+1\}$ 。

Problem F

Upsolved by Xiejiadong. (-15)

题意：给出 $n$ 个数，求最大的数集，使得两两的二进制表示不同位数至少为 $2$ 。

题解：因为保证了每个数都是不同的，所以考虑将恰好有一位不同的数之间连边。

于是就相当于是求这个图的最大独立集。

可以很容易的发现这是一个二分图，如果 $x$ 和 $y,z$ 都恰好有一位不同，而因为 $y\neq z$ ，所以 $y,z$ 至少有两位不同。

二分图的最大独立集 = 点数 - 二分图匹配。

可行的方案，是通过再跑未匹配的交叉路标记来得到。

Problem G

Solved by Xiejiadong && Weaver_zhu. 03:42:19 (+)

题意：求字符串 $s$ 中有多少子序列（不能有前导 $0$ ）满足按照数字比较比字符串 $t$ 大 。

题解：字符串 $s$ 中长度比 $t$ 大的很好处理，只要去掉 $0$ 开头的就好了。

长度相等的考虑用 dp 来做。 $f[i][j][k]$ 表示处理到第 $i$ 位，比较到了字符串 $t$ 的第 $j$ 位，前 $j$ 位是否相等 $k=0/1$ 。

暴力转移一下就好了。

读错题了。以为 $t$ 也是子序列。

数位 dp 这部分也是不需要的。

我又负输出了。

Problem H

Solved by Xiejiadong. 03:00:20 (+2)

题意：每次给出两个字母的相对关系，还原原字符串。

题解：每次给出的字母一定是包含了所有出现位置的，否则就是无解的情况。

于是我们先对所有的字母编号，然后在每次给出的顺序相邻之间连边（所有边都连的话，可能会 TLE ）。

在连出的图中跑一个拓扑排序就好了。

Problem I

Solved by Kilo_5723. 03:13:09 (+1)

Problem J

Unsolved. (-12)