Difference between revisions of "2016-2017 CT S03E07: HackerEarth Problems Compilation"

From EOJ Wiki
Jump to navigation Jump to search
 
(9 intermediate revisions by 3 users not shown)
Line 12: Line 12:
  
 
Solved by zerol. 00:13 (+)
 
Solved by zerol. 00:13 (+)
 +
 +
温暖的签到。
  
 
== Problem C ==
 
== Problem C ==
  
 
Solved by ultmaster. 01:13 (+)
 
Solved by ultmaster. 01:13 (+)
 +
 +
题意:找一个无向图里的小人。
 +
 +
题解:显然枚举中间那条边,但是两边用到的点不能重复。考虑求出和两边的点分别相邻的点 $l,r$ 和公共相邻的点 $s$,那么答案就增加 $\sum_{i=0}^3 \sum_{j=0}^2 \binom{l}{i} \binom{r}{j} \binom{s}{3-i,2-j}$。
  
 
== Problem D ==
 
== Problem D ==
  
 
Solved by zerol & kblack. 02:30 (+5)
 
Solved by zerol & kblack. 02:30 (+5)
 +
 +
题意:给一个数列,每次询问两个区间内相同的数的对数。
 +
 +
题解:容斥拆成 4 个询问后莫队。
 +
 +
 +
zerol:再问自杀。(死于复杂度写错,算错,平衡点找错,头铁,莫队排序写错)
  
 
== Problem E ==
 
== Problem E ==
Line 30: Line 43:
  
 
Solved by ultmaster. 03:31 (+1)
 
Solved by ultmaster. 03:31 (+1)
 +
 +
题意:$f_i = f_{i-1} + a_{i \bmod n}$, $f_0 = 0$; $g_n = h - \frac{n(n+1)}{2}$。求第一个 $n$ 满足 $f_n \ge g_n$。
 +
 +
题解:枚举剩余系下的每一个数,是一条单调减的直线。要么第一个点就大了,要么总有一天会大。后面一种情况二分一下就好了。
  
 
== Problem G ==
 
== Problem G ==
  
 
Solved by zerol. 04:01 (+)
 
Solved by zerol. 04:01 (+)
 +
 +
题意:求范围在 a 和 b 之间的一个单调增数列数量,使得 LCM 是 d 的倍数。
 +
 +
题解:把 d 分解成若干个素数幂之积,然后容斥(有那几个素数幂炸了),再容斥(a 到 b 之间有多少个数被炸了),再用插板法计算一下方案数。
  
 
== Problem I ==
 
== Problem I ==
  
 
Solved by kblack. 01:36 (+1)
 
Solved by kblack. 01:36 (+1)
 +
 +
题意:a 转化到 b,转化方式是加减质数,要求过程量全部都是质数。
 +
 +
题解:要么直接 +2 过去,要么从 2 中转,瞎几把判判。
  
 
== Problem J ==
 
== Problem J ==
  
 
Solved by kblack. 03:49 (+4)
 
Solved by kblack. 03:49 (+4)
 +
 +
题意:给一个带点权的树,询问一条链,求点权和最大的子链。
 +
 +
题解:按是否跨过 LCA 分类,树上前缀和转化为最大差后,用倍增处理最大值最小值最大差,瞎几把合并,特判直接连接 LCA 的情况,合并两边。
  
 
== Problem K ==
 
== Problem K ==
  
 
Solved by ultmaster. 02:12 (+)
 
Solved by ultmaster. 02:12 (+)
 +
 +
题意:有 $n$ 个车厢的火车,每节车厢可以染成 $k$ 种颜色,要求能选择 $d$ 端连续车厢的方案数刚好是 $t$,求染色方案数。
 +
 +
题解:首先把火车切成若干段,要求相邻两段染不同颜色。我们枚举有 $a$ 段长度大于等于 $d$,$b$ 段长度小于 $d$。那么这 $a$ 段长度的和就是 $t + a(d-1)$,我们记为 $x$,记 $y=n-x$(这 $y$ 节车厢要分给那 $b$ 段),那么最终的方案数就是 $f(x,a)g(y,b) \binom{a+b}{a} k (k-1)^{a+b-1}$。其中 $f(x,a)$ 是把 $x$ 切成 $a$ 段每段长度都不小于 $d$ 的方案数,用插板法可求;$g(y,b)$ 是把 $y$ 切成 $b$ 段,每段长度都在 $1$ 到 $d-1$ 之间的方案数。显然有 $g(y,b)=g(y-1,b-1)+\cdots+g(y-d+1,b-1)$,用 DP 预处理一下就好了。

Latest revision as of 11:42, 9 December 2018

Problem A

Solved by ultmaster. 04:51 (+4)

题意:给 $n$ 个串,有两种操作,一种是给某个串加一个字符,另一种是求存不存在一个串是查询串的子串。强制在线。

题解:由于限制了总长,所以不同的长度不会太多(根号级别)。枚举长度匹配一下哈希就行。把素数改成 unsigned long long 就能 AC 了。

所以为什么大家都是用自动机过的啊?

Problem B

Solved by zerol. 00:13 (+)

温暖的签到。

Problem C

Solved by ultmaster. 01:13 (+)

题意:找一个无向图里的小人。

题解:显然枚举中间那条边,但是两边用到的点不能重复。考虑求出和两边的点分别相邻的点 $l,r$ 和公共相邻的点 $s$,那么答案就增加 $\sum_{i=0}^3 \sum_{j=0}^2 \binom{l}{i} \binom{r}{j} \binom{s}{3-i,2-j}$。

Problem D

Solved by zerol & kblack. 02:30 (+5)

题意:给一个数列,每次询问两个区间内相同的数的对数。

题解:容斥拆成 4 个询问后莫队。


zerol:再问自杀。(死于复杂度写错,算错,平衡点找错,头铁,莫队排序写错)

Problem E

Solved by ultmaster. 00:16 (+)

排序签到。

Problem F

Solved by ultmaster. 03:31 (+1)

题意:$f_i = f_{i-1} + a_{i \bmod n}$, $f_0 = 0$; $g_n = h - \frac{n(n+1)}{2}$。求第一个 $n$ 满足 $f_n \ge g_n$。

题解:枚举剩余系下的每一个数,是一条单调减的直线。要么第一个点就大了,要么总有一天会大。后面一种情况二分一下就好了。

Problem G

Solved by zerol. 04:01 (+)

题意:求范围在 a 和 b 之间的一个单调增数列数量,使得 LCM 是 d 的倍数。

题解:把 d 分解成若干个素数幂之积,然后容斥(有那几个素数幂炸了),再容斥(a 到 b 之间有多少个数被炸了),再用插板法计算一下方案数。

Problem I

Solved by kblack. 01:36 (+1)

题意:a 转化到 b,转化方式是加减质数,要求过程量全部都是质数。

题解:要么直接 +2 过去,要么从 2 中转,瞎几把判判。

Problem J

Solved by kblack. 03:49 (+4)

题意:给一个带点权的树,询问一条链,求点权和最大的子链。

题解:按是否跨过 LCA 分类,树上前缀和转化为最大差后,用倍增处理最大值最小值最大差,瞎几把合并,特判直接连接 LCA 的情况,合并两边。

Problem K

Solved by ultmaster. 02:12 (+)

题意:有 $n$ 个车厢的火车,每节车厢可以染成 $k$ 种颜色,要求能选择 $d$ 端连续车厢的方案数刚好是 $t$,求染色方案数。

题解:首先把火车切成若干段,要求相邻两段染不同颜色。我们枚举有 $a$ 段长度大于等于 $d$,$b$ 段长度小于 $d$。那么这 $a$ 段长度的和就是 $t + a(d-1)$,我们记为 $x$,记 $y=n-x$(这 $y$ 节车厢要分给那 $b$ 段),那么最终的方案数就是 $f(x,a)g(y,b) \binom{a+b}{a} k (k-1)^{a+b-1}$。其中 $f(x,a)$ 是把 $x$ 切成 $a$ 段每段长度都不小于 $d$ 的方案数,用插板法可求;$g(y,b)$ 是把 $y$ 切成 $b$ 段,每段长度都在 $1$ 到 $d-1$ 之间的方案数。显然有 $g(y,b)=g(y-1,b-1)+\cdots+g(y-d+1,b-1)$,用 DP 预处理一下就好了。