2019 Multi-University,Nowcoder Day 6

Problem A

Solved by Kilo_5723. 00:09:05 (+)

温暖的签到题。

Problem B

Solved by Xiejiadong. 01:01:25 (+1)

题意：IP v6 二进制转十进制，每一段的前缀 $0$ 可以省略，连续的大于等于两段 $0$ 可以用 :: 表示，求最短的表示方式，最短的情况下保证字典序最小。

题解：直接讨论有点麻烦还可能容易锅，把所有连续的大于等于两段 $0$ 可以用 :: 表示的可行方案都处理出来。

然后排序就好了。

Problem C

Upsolved by Xiejiadong. (-1)

题意：求有多少对回文子串满足其中一个是另一个的子串。

题解：

前情提要

有个区间的询问，我们可以发现，每次新增加一个字母，最多只会新增加一个本质不同的回文子串（利用对称性很好证明）。

这样一来，如果新增加一位以后新增加了回文子串，我们就针对这一个子串所在的区间做一次询问就好了。

最后答案就是所有询问的总和。

Problem D

Solved by Weaver_zhu && Kilo_5723. 01:56:52 (+2)

题意：给 $k$ 个包和 $n$ 个重量为 $w_i$ 的物品，不停的找最重的放到当前包内，满了就换下一个包装。问这种策略下至少要容量多少的包

题解：给出下界，然后暴力一个一个试。据后面队伍说直接输出下界就过了

Problem E

Solved by Xiejiadong. 04:17:25 (+)

题解：构造一个图，与它的补图同构。

题解：考虑对点的数量按照奇偶分类。

偶数个点，分成两类，其中一类变成团，然后团之间奇偶相同的点连边。

奇数个点，拿出其中一个点，剩下的点按照偶数的连边，多的一个点像其中的一类点，全部连边。

Problem F

Unsolved.

Problem G

Upsolved by Weaver_zhu. (-20)

题意：给出 $n$ 个字符串加密日期，每个都是周五，求出一个字典序最小的加密方案

题解：蔡勒公式+乱搞，场上思维jiang化没想到去重，实际上可能还需要随机判75%左右的日期才能过

Problem H

Unsolved.

Problem I

Unsolved.

Problem J

Solved by Kilo_5723. 00:51:40 (+)

题意：有 $n$ 个科技，初始都在 $0$ 层。把第 $i$ 个科技从 $j$ 提升到 $j+1$ 层能得到 $a_{i,j}$ 的价值，将所有科技提升到 $\ge i$ 层可以得到 $b_i$ 的价值，所有价值有正有负，求最多获得的价值。

题解：先递推出每个科技从 $i$ 层往上提升能独自获得的最大价值（可能为 $0$），再枚举所有科技提升到的最高层数，总价值就是层数之前所有价值的总和加上每个科技从这层开始提升获得的最大价值中较大的的 $n-1$ 个。