AC. 梦想

frank_c1

2016多校联合训练5

发布于2016年08月02日 | 暂无评论 | 692阅读 | 比赛经历

只A了七题。不知所措。

1005本来差一点就可以A,1002、1004本来如果有人去打也是可以做出来的。然而没有如果了。

掉rating了好忧伤啊~~ 不过这次贡献了三题似乎比上次长进了一点,不过水平还是不够啊。

补题补题。

1001. ATM Mechine

有一个[0,k]的随机整数x。某人不知道x的值,他每次可以选择一个整数c,如果x-c \ge 0,则x = x - c,否则他会收到一次警告。当x = 0时游戏结束。他不能收到超过w次警告。同时他会采取最优策略使自己的询问次数最少。求他期望要询问多少次。

1 \le k,w \le 2000

1002. Cycle

给定两个等长字符串s,t。对于i \in [1,n],求出st长度为i的前缀是否循环同构。

1 \le n \le 10000

1003. Divide the Sequence

给定一个长度为n的数列a

求至多可以将a分为多少个连续子序列,满足每个子序列任意前缀和均不小于0

1 \le n \le 10 ^ 6, |a_i| \le 10 ^ 4

长的就像思博题,其实就是思博题。

考虑贪心,可以发现只有负数对答案有影响,且最优情况下长度\ge 2的子序列的最后一个数必定是负数。所以我们只需要对每一个负数向前扫,直到和大于零为止。于是只要从后向前扫一遍即可。

时间复杂度O(n)

1004. How Many Triangles

给定平面直角坐标系上的n个点,第i个点的坐标为(x_i,y_i)

求这些点可以构成多少个锐角三角形。

3 \le n \le 2000, 0 \le x_i,y_i \le 10 ^ 9

1005. Interesting

给定字符串ss仅含有小写英文字母。

求所有三元组(i,j,k)(1 \le i \le j \lt k \le n)ik值之和,i,j,k满足s[i:j]s[j+1:k]均是回文串,答案对10 ^ 9 + 7取模。

1 \le n \le 10 ^ 6

怎么这样呐,居然跪在模板上了。吸取教训以后还是用自己的板吧>_<

先Manacher跑一遍,处理出以每一个字符为中心的最长回文串半径(有些是虚字符)。

设以i结尾的回文串的起点下标和为f(i),以i开始的回文串结尾下标和为g(i)。答案就是\sum_{i=1} ^ {n-1} {f(i)g(i+1)}

考虑如何快速求f(i),g(i)。我们发现一个字符的贡献是在某一段区间上加一个等差数列,于是二维差分做一下即可。可能需要仔细考虑一些细节。

考场上莫名其妙超时来不及改,考后换了个Manacher模板就A了。真是浑身难受……

时间复杂度O(n)

1006. Interval

给定m个数列,第i个长度为s_i

我们可以将m个数列的顺序重新排列形成一个新的数列,设其长度为n,第i个元素是a_i,定义其权值为

value = \sum_{i=1} ^ {n} \sum_{j=i} ^ {n} {\gcd(a_i,a_{i+1},...,a_j)}

求全部m! 种排列方式形成的数列的权值之和,答案对10 ^ 9 + 7取模。

1 \le m \le 80000, 1 \le s_i \le 80000, \sum {s_i} \le 80000, 1 \le a_i \le 80000

1007. K-wolf Number

统计区间[L,R]中有多少个整数满足十进制表示中任意连续k个数字互不相同。

1 \le L \le R \le 10 ^ {18}, 2 \le k \le 5

考场上1A了十分资瓷。

预处理f(i,j)表示[1,10 ^ i]k = j时的答案。

预处理g(i,j,c)表示已经确定了j个数字,再确定i个数字且满足k = c的方案数。

对于一组询问,由于答案满足可减性,我们只需考虑[1,n]的情况。

如果整数有x位,则先加上f(x-1,k)。再从高位到低位逐位确定即可,顺便统计一下答案。

时间复杂度O(10 \cdot k \log n)

1008. Level Up

给定n个点的带权有根树,根为1,第i个的权值是a_i

定义p_ii子树中a_i的中位数。

现在你可以将一个a_i修改为100000,最大化所有p_i之和。

中位数定义为t个数中第\lceil \frac{t} {2} \rceil小的。

1 \le n \le 10 ^ 5, 1 \le a_i \le 10 ^ 5

1009. Permutation

给定n个点的有根树,根为root

若一个n元排列,满足对任意结点,它子树中的结点编号都在其编号前面,我们称其为一个好的排列。

求所有好的排列的逆序对数之和。答案对10 ^ 9 + 7取模。

1 \le n \le 50

1010. Prefix

给定n个字符串和q个询问,每次询问第l个到第r个字符串的所有前缀中有多少本质不同的字符串。

强制在线。

1 \le n,q \le 10 ^ 5, 1 \le |s| \le 10 ^ 5, \sum {|s|} \le 10 ^ 5, 1 \le l \le r \le n

抢了个一血真资瓷。

考虑哈希,设第i个串长度为x_i,则第i个串相当于一个有x_i个不同整数的集合。不妨先离散化。

于是问题转化为,询问第l个到第r个整数集合出现了多少个不同的整数。

由于所有集合的大小相加也只是O(n)级别,不妨将集合拆分。

问题转化为,有一个数列a,每次询问a_l, a_{l+1}, ...,a_r中出现了多少个不同的整数。

如果离线我会,在线就不会了呢QAQ

学姐说这是经典问题,在学姐的教导下涨了一些新姿势。膜膜膜学姐~~

我们设p_ia_i上一次出现的位置,对于一个询问(l,r),如果p_i \lt l,那么这是a_i在这个区间第一次出现,需要计入答案。于是问题就转化成,求区间[l,r]p_i \lt l的个数,这个问题显然可以用主席树完成。

时间复杂度O(n \log n)

1011. Two

给定长度分别为n,m的数列A,B

(A',B')的对数。其中A'A的子序列,B'B的子序列,且A' = B'。答案对10 ^ 9 + 7取模。

1 \le n,m \le 1000

1012. World is Exploding

给定长度为n的数列A

求四元组(a,b,c,d)的数目。其中1 \le a \lt b \le n, 1 \le c \lt d \le n, b \neq c, A_a \lt A_b, A_c \gt A_d

1 \le n \le 50000, 1 \le A_i \le 10 ^ 9