CF Round #538 (Div. 2)

昨晚十点多开始的比赛,肝到凌晨,然后一两点钟睡的觉。有点遗憾就是F题没来的及交(居然让我写线段树!欺负我没板子!),好在是没有掉rating.

A. Got Any Grapes?

A题我居然交了4发才过…

分析

首先我们要满足Andrew对于绿葡萄的要求,其次,还要满足另外两人吃的葡萄数量足够。

C. Trailing Loves (or L’oeufs?)

Keyword Number Theory

这题好像是原题,很多外国友人都做过…

分析

我们考虑一下转换进制的短除法,你就马上明白了B进制下n!结尾的0个数就是n!B的最高次,到这一步已经说得非常明白了。

D. Flood Fill

Keyword DP

分析

我们首先要选定一个出发点,然后向两边拓展。考虑到向不同方向拓展会影响答案,因此需要DP. 注意到每次将一个区间变成相同颜色后区间的颜色一定是原来左端点或者右端点的颜色,这样我们就可以区间DP了。

E. Arithmetic Progression

Keyword Number Theory, interactive

第一道交互题!

分析

首先用30次二分出a_n,然后随机取30个数,d就取他们排序后相邻两个差的gcd.

出锅总归是有可能的,不过概率非常小。我们可以这样去计算,设我们取到到等差数列为0,1,..,n-1(一般地),我们设不出锅(也就是d=1)的概率为P,那么出锅的概率就是1-P. 也就是说,如果我们选出子序列S,设计算得的dD(S),那么

P=\sum\limits _{S}[D(S)=1]=\sum\limits_{S}\sum\limits_{d\mid D(S)}\mu (d)=\sum\limits_{S}\sum\limits_{d=1}^n [d\mid D(S)]\mu(d)=\sum\limits_{d=1}^n\mu(d)\sum\limits_{S}[d\mid D(S)]

我们设f(x)x整除D(S)的概率,那么P=\sum\limits_{d=1}^n f(d)\mu(d).

接下来考虑如何计算f(x),我们转化一下,就是我们选出的子序列s_1,s_2,…s_k都满足\forall s_i\equiv r\text{, and }0\le r < x,设g(r)为选出子序列S满足上述条件的方案数。那么依据定义,f(x)就可以表示为:

f(x)=\frac {\sum\limits_{r=1}^{x-1} g(r)} {\binom {n} {k}}

现在考虑怎么算g(r). 要满足条件,S一定是r,x+r,2x+r,…的子序列,设q=\lfloor \frac {n} {x} \rfloor

  • If r< n\text{ mod }x,这样g(r)=\binom {q+1} {k}
  • If n \text{ mod } x\le r,这样g(r)=\binom {q} {k}

综合一下,我们就可以写个程序来计算P了。可以看这份代码

F. Please, another Queries on Array?

Keyword Segment Tree, Number Theory

分析

不得不说这个题目出得很没有新意,F题居然放小码农题…

我们知道\varphi是积性函数,有什么用呢?拆开它,利用\varphi的另外一种形式:\varphi(n)=n\prod\limits_{i=1}^k\frac {p_i-1} {p_i}

因此我们维护两棵线段树:一棵维护区间积,一颗维护这个区间出现的质数,注意到300以内的质数个数只有62个,因此全部压入一个long long即可。

总结

这场算是简单的吧。主要还是手速不够,而且打这种比赛一定要备足板子… 另外看到交互题很可能跟概率论有关,考试的时候是不可能有时间去证明的,瞎猜一波结论就好。

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注