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

From EOJ Wiki
Jump to navigation Jump to search
 
(22 intermediate revisions by 3 users not shown)
Line 2: Line 2:
  
 
Solved by Xiejiadong. 00:32:38 (+)
 
Solved by Xiejiadong. 00:32:38 (+)
 +
 +
题意:将字符串尽可能少的断开,使得断开的每部分都是其循环串种字典序最小的。
 +
 +
题解:考虑最多的断开情况,一定是 $1111\; 0111\; 0011\; 0001\; 0000$ 如此的。
 +
 +
也就是断开的一定是 $\sqrt{n}$ 级别的。
 +
 +
于是考虑贪心的做,从后往前枚举断点,用最小表示法判断合法性即可。
  
 
== Problem B ==
 
== Problem B ==
  
Solved by Weaver_zhu && Kilo_5723. 01:09:39 (+)
+
Solved by 柴俊,丁大公,陈咸平等. 01:09:39 (+)
 +
 
 +
题意:对于一个整系数 $n$ 次多项式,判断它是否能分解成两个多项式的乘积。
 +
 
 +
题解:《高等数学(上册)》 P149 5.4.6 有理函数的积分:
 +
 
 +
……,由代数学可知,$Q(x)$ 在实数范围内总可以分解为一些因式(一次二项式或有虚根的二次三项式)的乘积,……
  
 
== Problem C ==
 
== Problem C ==
  
 
Solved by Xiejiadong. 03:49:18 (+5)
 
Solved by Xiejiadong. 03:49:18 (+5)
 +
 +
题意:有 $n$ 种树,每种树砍掉一棵都需要 $p_i$ ,每种树有 $c_i$ 棵,现在要求高度最高的树数量超过一半,求最小的砍法代价。
 +
 +
题解:把高度相同的树都放在一起。枚举当前最高的树是高度是多少,高度比当前高的肯定全部砍掉。高度比当前低的选择中选择代价最小的来砍掉就好了。
 +
 +
题目中 $c_i$ 和 $p_i$ 看反了,还过样例了。自闭了两个小时。
  
 
== Problem D ==
 
== Problem D ==
  
 
Solved by Weaver_zhu. 00:03:13 (+)
 
Solved by Weaver_zhu. 00:03:13 (+)
 +
 +
温暖的签到,二血心态崩了
  
 
== Problem E ==
 
== Problem E ==
  
 
Solved by Kilo_5723. 04:48:49 (+)
 
Solved by Kilo_5723. 04:48:49 (+)
 +
 +
题意:每次将 $[l_i,r_i]$ 里的 $r_i-l_i+1$ 个数加入数列,求数列的中位数。
 +
 +
题解:离散化线段树,需要支持区间加,求第 $k$ 大的值。
  
 
== Problem F ==
 
== Problem F ==
  
Unsolved.
+
Upsolved by Xiejiadong.
 +
 
 +
题意:有 $n$ 个石头,每个石头有一个初始能量 $e_i$ ,石头每秒增加能量 $l_i$ ,每个石头有拥有的能量上限 $c_i$ 。在某些时间点,会获取一个区间的石头能量,这个区间会集体置 $0$ ,求能获得的能量总和。
 +
 
 +
题解:因为只要求获得能量的总和,所以可以对考虑石头对总答案的贡献。
 +
 
 +
如果我们知道当前这个石头每次获取的时间,显然,答案只和第一次获取的时间,以及之后每一次的差值有关。
 +
 
 +
每个石头获取的差值有一个上限,大于这个上限的时间,只能获得能量上限,其余的获得的就是时间差 * 每秒上升的能量。
 +
 
 +
于是我们用 set 维护当前石头的获取,用两个树状数组分别维护前缀时间差的数量和时间差的和(用线段树会 MLE)。
  
 
== Problem G ==
 
== Problem G ==
Line 29: Line 65:
 
== Problem H ==
 
== Problem H ==
  
Unsolved.
+
Upsolved by Weaver_zhu. (-4)
 +
 
 +
题意:求 $x\;{\rm xor}\;y < C$ 或 $x\;{\rm and}\;y > C$ 且 $1 \le x \le A, 1 \le y \le B$ 的二元组 $(x,y)$ 数量。
 +
 
 +
题解:数位 dp,容斥搞出来。显然前缀只有可能和 $C$ 相同才不是平凡情况,否则可以直接特判掉。场上被卡内存难受的很,实际上的确有更好的做法
  
 
== Problem I ==
 
== Problem I ==
  
Unsolved.
+
Solved by Kilo_5723. 03:13:21 (+)
 +
 
 +
题意:给定 $n,m$,要在任意大小的正方形棋盘上每格放至少 $m$ 个棋子,使得任意 $k$ 个不同行同列的格子上棋子数量之和都相等且 $\le n$,求有多少种摆放方式。
 +
 
 +
题解:根据题意,合法的摆放一定可以拆解成肯每一列都放上一枚棋子,或每一行都放上一枚棋子两种操作,对于不同的棋盘大小分别计数。但是有一个可能导致重复计数的问题:给每行都放上一枚棋子和给每列都放上一枚棋子是完全等效的。所以,我们要对每种大小的棋盘,先枚举棋子数量最少的格子有的棋子个数,再求得给任意行任意列放上棋子,但有至少一行一列没有放上棋子的方案数。这样的方案数可以通过容斥原理预处理得到。
  
 
== Problem J ==
 
== Problem J ==
  
Unsolved.
+
Solved by Xiejiadong. 00:06:51 (+)
 +
 
 +
温暖的签到。
  
 
== Problem K ==
 
== Problem K ==
  
Unsolved.
+
Upsolved by Weaver_zhu.

Latest revision as of 10:31, 16 August 2019

Problem A

Solved by Xiejiadong. 00:32:38 (+)

题意:将字符串尽可能少的断开,使得断开的每部分都是其循环串种字典序最小的。

题解:考虑最多的断开情况,一定是 $1111\; 0111\; 0011\; 0001\; 0000$ 如此的。

也就是断开的一定是 $\sqrt{n}$ 级别的。

于是考虑贪心的做,从后往前枚举断点,用最小表示法判断合法性即可。

Problem B

Solved by 柴俊,丁大公,陈咸平等. 01:09:39 (+)

题意:对于一个整系数 $n$ 次多项式,判断它是否能分解成两个多项式的乘积。

题解:《高等数学(上册)》 P149 5.4.6 有理函数的积分:

……,由代数学可知,$Q(x)$ 在实数范围内总可以分解为一些因式(一次二项式或有虚根的二次三项式)的乘积,……

Problem C

Solved by Xiejiadong. 03:49:18 (+5)

题意:有 $n$ 种树,每种树砍掉一棵都需要 $p_i$ ,每种树有 $c_i$ 棵,现在要求高度最高的树数量超过一半,求最小的砍法代价。

题解:把高度相同的树都放在一起。枚举当前最高的树是高度是多少,高度比当前高的肯定全部砍掉。高度比当前低的选择中选择代价最小的来砍掉就好了。

题目中 $c_i$ 和 $p_i$ 看反了,还过样例了。自闭了两个小时。

Problem D

Solved by Weaver_zhu. 00:03:13 (+)

温暖的签到,二血心态崩了

Problem E

Solved by Kilo_5723. 04:48:49 (+)

题意:每次将 $[l_i,r_i]$ 里的 $r_i-l_i+1$ 个数加入数列,求数列的中位数。

题解:离散化线段树,需要支持区间加,求第 $k$ 大的值。

Problem F

Upsolved by Xiejiadong.

题意:有 $n$ 个石头,每个石头有一个初始能量 $e_i$ ,石头每秒增加能量 $l_i$ ,每个石头有拥有的能量上限 $c_i$ 。在某些时间点,会获取一个区间的石头能量,这个区间会集体置 $0$ ,求能获得的能量总和。

题解:因为只要求获得能量的总和,所以可以对考虑石头对总答案的贡献。

如果我们知道当前这个石头每次获取的时间,显然,答案只和第一次获取的时间,以及之后每一次的差值有关。

每个石头获取的差值有一个上限,大于这个上限的时间,只能获得能量上限,其余的获得的就是时间差 * 每秒上升的能量。

于是我们用 set 维护当前石头的获取,用两个树状数组分别维护前缀时间差的数量和时间差的和(用线段树会 MLE)。

Problem G

Unsolved.

Problem H

Upsolved by Weaver_zhu. (-4)

题意:求 $x\;{\rm xor}\;y < C$ 或 $x\;{\rm and}\;y > C$ 且 $1 \le x \le A, 1 \le y \le B$ 的二元组 $(x,y)$ 数量。

题解:数位 dp,容斥搞出来。显然前缀只有可能和 $C$ 相同才不是平凡情况,否则可以直接特判掉。场上被卡内存难受的很,实际上的确有更好的做法

Problem I

Solved by Kilo_5723. 03:13:21 (+)

题意:给定 $n,m$,要在任意大小的正方形棋盘上每格放至少 $m$ 个棋子,使得任意 $k$ 个不同行同列的格子上棋子数量之和都相等且 $\le n$,求有多少种摆放方式。

题解:根据题意,合法的摆放一定可以拆解成肯每一列都放上一枚棋子,或每一行都放上一枚棋子两种操作,对于不同的棋盘大小分别计数。但是有一个可能导致重复计数的问题:给每行都放上一枚棋子和给每列都放上一枚棋子是完全等效的。所以,我们要对每种大小的棋盘,先枚举棋子数量最少的格子有的棋子个数,再求得给任意行任意列放上棋子,但有至少一行一列没有放上棋子的方案数。这样的方案数可以通过容斥原理预处理得到。

Problem J

Solved by Xiejiadong. 00:06:51 (+)

温暖的签到。

Problem K

Upsolved by Weaver_zhu.