Difference between revisions of "2019 Multi-University,Nowcoder Day 5"
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
Line 21: | Line 21: | ||
== Problem F == | == Problem F == | ||
− | + | Upsolved. (-15) | |
+ | |||
+ | 题意:给出 $n$ 个数,求最大的数集,使得两两的二进制表示不同位数至少为 $2$ 。 | ||
+ | |||
+ | 题解:因为保证了每个数都是不同的,所以考虑将恰好有一位不同的数之间连边。 | ||
+ | |||
+ | 于是就相当于是求这个图的最大独立集。 | ||
+ | |||
+ | 可以很容易的发现这是一个二分图,如果 $x$ 和 $y,z$ 都恰好有一位不同,而因为 $y\neq z$ ,所以 $y,z$ 至少有两位不同。 | ||
+ | |||
+ | 二分图的最大独立集 = 点数 - 二分图匹配。 | ||
+ | |||
+ | 可行的方案,是通过再跑未匹配的交叉路标记来得到。 | ||
== Problem G == | == Problem G == |
Revision as of 14:50, 1 August 2019
Problem A
Solved by Kilo_5723. 00:17:42 (+)
Problem B
Solved by Kilo_5723. 01:27:34 (+)
Problem C
Unsolved. (-8)
Problem D
Unsolved.
Problem E
Unsolved.
Problem F
Upsolved. (-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)