Difference between revisions of "2018 Multi-University, HDU Day 6"

From EOJ Wiki
Jump to navigation Jump to search
 
(6 intermediate revisions by one other user not shown)
Line 28: Line 28:
  
 
== Problem D ==
 
== Problem D ==
 +
 +
Upsolved by ultmaster.
 +
 +
题意:有 $n$ 块横板带一定权重,每次操作用一定的代价将一些横板射穿,问消去所有横板的最小总代价。
 +
 +
题解:属于赛场上应该做但是没有做的题。坐标离散化 (注意离散化后是坐标而不是区间) 后 $f(l,r)$ 表示将完全包含在 $[l,r]$ 区间内的所有东西全部消掉的最小代价。考虑转移,区间内最大的那个东西肯定需要消去,设这个东西是 $w$,则 $f(l,r) = \min_{l \le k \le r} f(l,k-1)+f(k+1,r)$。
  
 
== Problem E ==
 
== Problem E ==
Line 35: Line 41:
 
== Problem G ==
 
== Problem G ==
  
Unsolved. (-6)
+
Upsolved by zerol. (-6)
 +
 
 +
题意:求最小方差生成树。
 +
 
 +
题解:按边权排序,一条一条加入,如果已经联通,那么剔除掉边权最小的那个(这部分你只需要一个 LCT,当然还得额外维护一个 边权最小 / 出现时间最小的边,所以每条边上都要额外放一个点)。设换入和换出的边权分别为 new.w, old.w,那么考虑对平均数的枚举,(new.w + old.w) / 2 是临界值。记录每一条边的出入临界值,最后按临界值排序,模拟这个边替换的过程。注意计算答案时会爆 long long。
 +
 
 +
zerol:到最后都对不会爆 LL 十分自信,直到我看了标程。
 +
 
 +
模拟的是平均值的移动,而真实的平均值可能并不是这样,但是这样为什么对呢?考虑我试图增加当前的平均值,肯定要拿一个大的替换掉一个小的,随着平均值的增加,优劣的双方也在发生转化,这时我挑那个临界点靠前的肯定是好的,即便是使答案更差了。
 +
 
 +
在计算临界值的时候为什么换入换出的恰好是一对呢?
  
 
== Problem H ==
 
== Problem H ==

Latest revision as of 09:11, 21 August 2018

ultmaster: 除了我签了个到,全是 kblack 做的。可能 kblack 1v3 结局也差不多吧。。。

Problem A

Solved by ultmaster. 00:39 (+4)

题意:小学积分题。

题解:不会积分,上了个 Wolfram Alpha。没想到漏除一个 $b$(纸上是有的,抄上去就没有了)。对着一个明显不对的答案调了好久,还仔细考虑有没有精度问题。答案是 $\pi a + 2b$。注意输出要去尾。根本不需要什么 long double...

Problem B

Solved by kblack. 02:12 (+2)

题意:$K$ 个书架放 $N$ 本书,总价值为 $score = gcd(beauty_1, beauty_2, ..., beauty_k)$,$beauty_i = 2^{fib(cnt_i)} - 1$,求期望。

题解:首先研究 gcd 的性质了解到 $scrore = 2^{fib(gcd(cnt_i))}-1$,枚举 gcd,用插板求出方案数,然后容斥一下(减去gcd是倍数的方案数)就好了,乘一下价值就好了。

Problem C

Solved by kblack. 04:12 (+5)

题意:环上 $N$ 对狗男女,权是环上距离,求最小权匹配的大小。

题解:环上必定有至少一处没有任何狗男女经过,记狗男为 $+1$ 狗女为 $-1$ 并求前缀和 $f_i$,从 $-n$ 到 $n$ 枚举 $x$ 即是,$\sum{|f_i-x|}$ 即是最小权和,突变点一共 $n$ 个,基数维护一下就好了。

kblack: 千万不要去离散化这个突变点,两个数组合并一定要归并,但凡有半个 $log$ 你就离 T 不远了。

Problem D

Upsolved by ultmaster.

题意:有 $n$ 块横板带一定权重,每次操作用一定的代价将一些横板射穿,问消去所有横板的最小总代价。

题解:属于赛场上应该做但是没有做的题。坐标离散化 (注意离散化后是坐标而不是区间) 后 $f(l,r)$ 表示将完全包含在 $[l,r]$ 区间内的所有东西全部消掉的最小代价。考虑转移,区间内最大的那个东西肯定需要消去,设这个东西是 $w$,则 $f(l,r) = \min_{l \le k \le r} f(l,k-1)+f(k+1,r)$。

Problem E

Problem F

Problem G

Upsolved by zerol. (-6)

题意:求最小方差生成树。

题解:按边权排序,一条一条加入,如果已经联通,那么剔除掉边权最小的那个(这部分你只需要一个 LCT,当然还得额外维护一个 边权最小 / 出现时间最小的边,所以每条边上都要额外放一个点)。设换入和换出的边权分别为 new.w, old.w,那么考虑对平均数的枚举,(new.w + old.w) / 2 是临界值。记录每一条边的出入临界值,最后按临界值排序,模拟这个边替换的过程。注意计算答案时会爆 long long。

zerol:到最后都对不会爆 LL 十分自信,直到我看了标程。

模拟的是平均值的移动,而真实的平均值可能并不是这样,但是这样为什么对呢?考虑我试图增加当前的平均值,肯定要拿一个大的替换掉一个小的,随着平均值的增加,优劣的双方也在发生转化,这时我挑那个临界点靠前的肯定是好的,即便是使答案更差了。

在计算临界值的时候为什么换入换出的恰好是一对呢?

Problem H

Problem I

Solved by kblack. 01:01 (+1)

题意:村民狼人互相指认,村民一定说实话,狼人可以胡说八道,求铁狼数量。

题解:显然,可能所有人都在胡说八道。如果指认组成一个圈,其中一项指控是狼人其他是村民,那么狼人指控的目标一定是铁狼,认为铁狼是村民的也是铁狼,也要计算在内。

Problem J

Problem K

Upsolved by ultmaster. (-5)

题意:$M_n(i,j) = 1 \text{ if} \binom{i}{j} \bmod p > 0 \text{ else } 0$. $F(n,k) = \sum_{i = 0}^{p^n-1}\sum_{j=0}^{p^n-1}M_n^k(i,j)$. 求 $(\sum_{n=1}^N\sum_{k=1}^K F(n,k)) \bmod (10^9 + 7)$.

题解:打表找规律,最后发现如果枚举 $k$ 的话,是一个首项为 $q=p(p+1)\cdots(p+k)/(k+1)!$,公比也为 $q$ 的等比数列。求前 $N$ 项和即可。

ultmaster: 小学生常犯错误:等比数列求和直接套公式,从来不考虑公比为 $1$ 的情况,到最后都没看出来。(差点就有贡献了啊。。。心痛。。。

Problem L

Solved by kblack. 00:23 (+)

温暖的签到。