2015-ACM多校训练第三场

题外话

尼玛颓废着颓废着就开学了= =无聊终于把第三场的题全补完了


hdu 5316(1001) Magician

Solution

线段树裸题,维护四个东西,以奇/偶开头奇/偶结尾的最大值,正常线段树合并即可。

Code


hdu 5317(1002) RGCDQ

Solution

水题,发现$2\times 3\times 5\times 7\times 9\times 11\times 13 \times17>1000000$,所以素因子种数最多为7个,前缀和统计一下即可

Code


hdu 5318(1003) The Goddess Of The Moon

Solution

水题,题目太长比赛没看= =,唯一的坑是要把数字去重,然后容易看出可以用矩阵乘法来递推

Code


hdu 5319(1004) Painter

Solution

简单模拟题,按题目要求一刷刷到底就可以了

Code


hdu 5320(1005) Fan Li

Solution

感觉这道题是个不错题,考虑以$i$为开头的序列,$gcd$如果发生变化一定至少除以$2$,所以不同的gcd区间最多也是log级的。可以预处理出所有的四元组$(g,i,l,r)$,表示以$i$为开头,结尾在$[l,r]$区间内$gcd$为$g$。
考虑$dp$,不妨考虑当前$gcd=x$的方案数以及区间数,假设该四元组开头为$i$,显然区间数是以结尾在$[1,i-1]$区间内的最大值$+1$,方案数也很好计算。容易发现用一个线段树就可以轻松维护了。

Code


hdu 5321(1006) Beautiful Set

Description

A的计算方法是:对于$n$个数的某个排列,此排列的美丽值为这个排列所有的区间最大公约数之和。然后这个集合的美丽值为$n$个数的所有排列的美丽值之和。
B的计算方法是:在$n$个数中选出$k(1 \le k \le n)$个数,对于某种选取方案,这种方案的美丽值为$k$个数的最大公约数乘上$k$。然后这个集合的美丽值为所有选数方案的美丽值之和。

Solution

很容易想到用$cnt[i]$表示集合中$i$的倍数个数

  • 考虑第一个人
    $F1[x]$表示$gcd$为$x$的倍数的区间的个数
    $f1[x]$表示$gcd$为$x$的区间的个数
    $F1[x]=\sum_{x|d}f1[d]$

且$F1[x]=\sum_{j=1}^{cnt[x]} \binom{cnt[x]}{j}\times j! \times (n-j+1)!$
从$cnt[x]$里选$j$个数,再把$n-j$个数和这$j$个数算做$n-j+1$的排列

  • 考虑第二个人
    $F2[x]$表示$gcd$为$x$的倍数的区间的个数
    $f2[x]$表示$gcd$为$x$的区间的个数
    易知$F2[x] = \sum_{x|d}f2[d]$

且$F2[x]= \sum_{j=1}^{cnt[x]} \binom{cnt[x]}{j}\times j = cnt[x]\times 2^{cnt[x]-1}$
这个稍微推推就能推出来

同样的$F2[x] = \sum_{x|d}f2[d]$

然后就是我们熟悉的莫比乌斯反演辣!

$F(n)=\sum_{n|d}f(d)$

可以得到

$f[n]=\sum_{n|d}\mu(d/n)\times F(d)$

于是可以计算出$f$,$\sum f[i]\times i$即是答案

Code


hdu 5322(1007) Hope

Solution

这题其实并不难,考虑$dp[i]$为长度为$i$的排列的答案,枚举这个排列最大值所在的位置,最大值左边和它都是联通的,于是我们可以得到转移方程
$dp[i]=\sum_{j=1}^i \binom{i-1}{j-1}\times (j-1)!\times dp[i-j]\times j^2$

稍加变换我们可以得到

$dp[i]=(i-1)!\times \sum_{j=1}^i \frac{j^2}{(i-j)!}\times dp[i-j]$

令$k=i-j$我们可以得到$dp[i]=(i-1)!\times \sum_{k=0}^{i-1}\frac{(i-k)^2}{k!}\times dp[k]$
展开得$dp[i]=(i-1)!\times (i^2-2ik+k^2)\times \frac{dp[k]}{k!}$
维护三个前缀和即可O(N)解决,当然你可以没思维难度得想到cdq分治+NTT得做法QAQ

Code


hdu 5323(1008) Solve this interesting problem

Solution

考虑$[l,r]$是做左儿子还是右儿子,具体有$4$种情况,暴力枚举即可,实际上的复杂度是$4^{11}$,完全可以接受

Code


hdu 5324(1009) Boring Class

Solution

三维最长不下降序列之类的题,很容易想到按$id$算答案,$r$这一维排序,$l$这一维用树状数组维护然后cdq分治的经典做法。
考虑$dp$由于要字典序最小,先cdq分治算右区间的答案,考虑对左区间的影响即可。
写了不到$80$行,轻松愉快,cdq分治真是个高大的姿势。。。爽

Code


hdu 5325(1010) Crazy Bobo

Solution

水题,按权值排序后,权值小的向大的连即可,dp一下就行了

Code


hdu 5326(1011) Work

Solution

水题,随便dfs就行了= =

Code

完结撒花!
继续补题!>_<