Difference between revisions of "2019 Multi-University,Nowcoder Day 6"

From EOJ Wiki
Jump to navigation Jump to search
Line 18: Line 18:
  
 
Unsolved. (-1)
 
Unsolved. (-1)
 +
 +
[http://xiejiadong.com/?p=1884 前情提要]
  
 
== Problem D ==
 
== Problem D ==

Revision as of 09:48, 6 August 2019

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

Unsolved. (-1)

前情提要

Problem D

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

Problem E

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

题解:构造一个图,与它的补图同构。

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

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

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

Problem F

Unsolved.

Problem G

Upsolved by Weaver_zhu. (-20)

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$ 个。