2015达卡区域赛总结

期末了,在考期结束后,我们队重新开始了日常的Regional训练赛。今天的题目比较简单,赛场上有思路的有8道题,不过最终只过了6题。J题由于细节问题被卡了,C题虽然有思路但是已经没时间写了。F题很早就想出了O(n^3logn)的做法,但是由于数据组数较多,感觉要达到O(n^2logn)才能过,所以不太敢写,而且原来的思路最快也要O(n^3),也没有顺着思路继续想。赛后被告知O(n^3)完全能过这题……

A. Automatic Cheater Detection && B. Counting Weekend Days

签到题,读懂题意就行。

C. Toll Management IV

树链剖分

题目大意:给出n个点m条边的带权无向图。其中前n-1条边构成了一棵树,为该图的最小生成树。现在要对每一条边i求出Ai和Bi,满足第i条边的权值在[Wi-Bi,Wi+Ai]区间内变动时,仍然满足原树为最小生成树。输出的答案为:

S = $\sum\limits_1^m(iA_i + i^2B_i)$.
如果Ai或Bi为正无穷或负无穷,则用-1来代替它

题目的关键就是对每条边求出它的Ai和Bi。

对于非树边,显然它可以增加到无穷大。那么它可以减小多少呢?很容易发现应该是ui到vi的路径上的最大值。

对于树边,显然她可以减小到无穷小,那么它可以增大到多少呢?通过画图我们可以发现,应该为跨过它的非树边的Bi的最小值。

这两种操作都可以使用树链剖分来维护。

D. Owllen

贪心

题目大意:给出长为n的仅由小写字母组成的字符串,问对长度和它相同的仅由小写字母组成的字符串中,和它的最长公共子序列的长度最小为多少?

简单的分析一下就可以发现,构造只由原序列中出现次数最少的字母组成的字符串,则此时新字符串与原串的LCS最小,长度为原串中该字母出现的次数。

E. Sum of MSLCM

数学题+分块优化

题目大意:有200组数据,每组数据给出数字n(1 < n <= 2e7),对每个数字i(2 <= i <= n),找出一个集合使得该集合的lcm等于i且该集合中数字之和最大,记其和为MSLCM(i)。输出$\sum\limits_2^n(MSLCM(i))$。

我们很容易发现要求的集合即为由n的约数组成的集合。所以要求的公式应该为$\sum\limits_2^n$

$\sum\limits_{d\mid i} d$

但是面对这个公式我们发现并不能在时限内解决这个问题。

我们换一种思路来考虑,即每个数i对答案的贡献。第i个数被加了k次,k为$1\dots n$中是i的倍数的数的个数,即$\lfloor\frac{n}{i}\rfloor$。,因此,可以将上式化为:$\sum\limits_1^n(i\lfloor\frac{n}{i}\rfloor) - 1$。之所以要减1,是因为我们在使用$\lfloor\frac{n}{i}\rfloor$时将$1$的$MSLCM$也算入了前面的算式中。

由于n的范围很大,直接计算该公式仍不能在时限内解决该问题,这就用到了之前常用的一个技巧,根据$\lfloor\frac{n}{i}\rfloor$的分段性进行分段优化,这样可将单组数据的时间复杂度优化到$O(\sqrt{n})$

F. Unique Party

算法尚不明确

G. Honey King

算法尚不明确

H. Design New Capital

FFT

题目大意:在坐标平面上有n个点,这些点均不在坐标轴上。现在要从中选出一些点,使得$(0,0)$点到这些店的曼哈顿距离之和小于等于坐标平面上的其他任意点。问在选取个数为$1$到$n$个时,分别有几种选取方法。

由于是曼哈顿距离,所以可以将x、y分开考虑。可以发现,为了达到题目要求,必须使选出的点的横坐标的中位数等于0(如果有两个则0位于这两个数之间)且纵坐标也满足同样条件。

又由于坐标轴上没有点,因此在选择的点的个数为奇数时,其中位数必然不为0,因此此时没有任何选取方案。

在选择的点的个数为偶数时,则可发现,若在第一象限中选择一个点,则必然在第三象限中选择一个点与其对应。二四象限也同理。

设选择的总点数为$2k$,再设第一象限中有$A$个点,第二象限中有$B$个点,第三象限中有$C$个点,第四象限中有$D$个点。则方案数为:$\sum\limits_{i = 0}^k C_A^i C_C^i C_B^{k - i} C_D^{k - i}$

我们发现这是一个卷积的形式,因此可以使用FFT来加速,从而在$O(n\log n)$的时间复杂度内得出所有总点数为偶数的方案数。

由于需要取模,因此使用的应该是NTT。

I. Numbered Cards

状压 + 数位dp

题目大意:有$n$个数,值为$1$~$n$,要从中选出一个子集,使得该集合中任何两个数的十进制表示中都不含相同的数字。问有多少种选取方法。($n \leq 10^9$)

首先想到dp来表示之前已经用了几个数, 然后转移的时候用到了偏序(因为是集合的原因),我们强制让最后一个数包括最小的那个. 然后转移的g[2^i]是用3(4)进制状压的数位dp做.

重点:

  1. dp的想法来做,状压
  2. 集合无序性,我们用偏序做.
  3. 二进制都是恰好一定要用掉这么多,不能采用用不超过这个范围(但没必要全用完)这样的思维,因为会有很多重复情况. ——这是赛场上差点犯的错误QAQ
  4. 用3进制状压:不能用,要用还没用,要用已经用过了至少一次

J. The Hypnotic Spirals

计算几何+积分

题目大意:极坐标系中有一个螺旋线$r = a\theta$,还有n条射线$\theta = b_i$,以及m个点$(r_j, \theta_j)$,螺旋线和射线将坐标平面切割成了多个区域,所有的点均不在射线和螺旋线上,现在要把所有点所在的区域涂黑,输出$\frac{要涂黑的总面积}{10}$。若要涂黑的总面积为无穷,则输出-1

大致思路一下就有, 就是算出来第i个点属于的上一圈螺线和下一圈螺线,然后再看弧度在哪两个射线之间. 但是有细节要注意:

  1. 看弧度在哪两个之间,涉及到转一圈的问题,我们设置一个-角度(代码中没设但是特判了)和一个大于$2\pi$的角度,这样好找,然后$k(设角度为b_i + 2k\pi)$就能统一找了.
  2. 我们需要用map来判重复,但是记着一个负角度和一个大于$2\pi$的是一样的,需要特殊处理
  3. 本题中的特殊情况:
    • 在第一圈并且有负角的时候,负角度没用,我们应该从0开始积分
    • 在最内一圈,不用减去里面的圈,因为没有.
    • 在最内一圈和外面一圈的交界处,有的用减去里面的圈,有的不用,分段计算. 总结起来就是,最内圈先是从0开始,并且本身不是环状,影响了这三个
文章目录
  1. 1. A. Automatic Cheater Detection && B. Counting Weekend Days
  2. 2. C. Toll Management IV
  3. 3. D. Owllen
  4. 4. E. Sum of MSLCM
  5. 5. F. Unique Party
  6. 6. G. Honey King
  7. 7. H. Design New Capital
  8. 8. I. Numbered Cards
    1. 8.1. 重点:
  9. 9. J. The Hypnotic Spirals