5
26
2015
2

Codeforces Round #305 (Div. 1)

B.我们可以强行把数字按照从大到小加入,当当第一次形成了一个>=k的长度的连续的已经被选出来的数的时候,那么ans[k]一定就是刚加进去的这个数。

C.注意到询问实际上是求$$[gcd(a[i],a[j])==1]$$

  用莫比乌斯反演转化成求$$\sum_{d|a[i]且d|a[j]}μ[d]$$

  然后这个公因数的话就可以记录一个$s[x]$表示有x这个因子的数的个数,然后对因子分开算贡献。

E.给出n个字符串,每次询问s[l,r]中字符串s[k]出现了多少次。

  这个问题有很多做法。

  我考场上想的是转化成前缀差,然后就可以一个一个字符串加入广义SAM,然后查询一个字符串出现了多少次。

  然而这需要动态维护right集合。我以为和BZOJ2555一样大力出奇迹就直接暴力更新了。

  然后发现WA了。原来是因为广义SAM插入的时候有可能在树的中间,这样就不能暴力更新了。除非每次dfs一遍子树?

  考完试后想了想如果我们事先把整个SAM建出来,然后每个字符串跑一遍,那么子树中编号∈[l,r]的个数就是我们的ans。

  这一步可以主席树或者离线之后树状数组搞定。

  然后AC自动机可以在fail树上进行同样的操作。

  后缀数组的做法也很直观。不过最近SAM做多了根本没往SA想。

  我们对所有串连在一起建立SA,那么s[k]出现的时候一定作为某个后缀的前缀。我们可以二分出s[k]向左向右拓展的最远点然后就成了和上面一样的问题。

还是太naive了。在A上花费了太多时间。然后还被hack了一次。最后还fst了。

不过上了黄还是蛮开心的

A.首先我们可以找出上下各第一次到达a1,a2的时间,然后找一下下一次到达a1,a2的时间。

中间特判掉无解和有部分解的情况。

那么剩下的可以exgcd。

也可以枚举上面那个走的循环节的个数,然后下面每一次就是一个新的函数,不超过m次肯定出现循环。所以答案可以在$O(m)$内找到。

我考场上直接让上下两个指针一个循环节一个跳着走。然后这样复杂度是不确定的。

然而走10*m次也能AC

Category: codeforces | Tags: | Read Count: 587
Avatar_small
tangjz 说:
2015年5月28日 21:32

T T 第一题手推的CRT被卡了。。。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com