AC. 梦想

frank_c1

2015多校联合训练9

发布于2016年05月25日 | 暂无评论 | 804阅读 | 算法框架

有点想做一些多校的题目练手。发现有一场是杜教出的?来体验一下被虐的快感~~

Expression

给定一个表达式,运算符包括加减乘。每次可以选择两个数执行运算。求所有运算顺序得到的结果之和。答案对10 ^ 9 + 7取模。

2 \le n \le 100, 0 \le a_i \le 10 ^ 9

比较明显的区间DP。设dp(i,j)为第ij个数所有运算顺序结果的和,则有

dp(i,j) = \sum_{k = i} ^ {j-1} {{j - i - 1 \choose k - i} f(i,j,k)}

其中f(i,j,k)是与k位置后的运算符有关的转移函数。

上述式子中组合数的意义是,我们将左区间和右区间并起来时,考虑到左右区间各选择一个结果p,q,产生新的结果方式有{j - i - 1 \choose k - i}种。

考虑加法运算,相当于在左右区间分别选择一个结果相加,即\sum_{p \in L} \sum_{q \in R} {p + q}。那么左区间的某一结果p对于答案的贡献是(k - i)!p,同理右区间的某一结果q对于答案的贡献是(j-k-1)!q,故此时

f(i,j,k) = (k-i)!dp(i,k) + (j-k-1)!dp(k+1,j)

减法运算类似。

再考虑乘法运算,相当于在左区间和右区间分别选择一个结果相乘,即\sum_{p \in L} \sum_{q \in R} {pq}。我们可以化简化一下式子,(\sum_{p \in L} {p})(\sum_{q \in R} {q}) = dp(i,k) dp(k+1,j)。故此时

f(i,j,k) = dp(i,k) dp(k+1,j)

时间复杂度O(n ^ 3)

Hack it!

定义字符串s的哈希函数f(s) = \sum_{i=0} ^ {n-1} {w(s_i) base ^ i} \mod r。构造两个等长的合法括号序列A,B,长度\le 10 ^ 4,满足f(A) = f(B)。其中w('(') = p,w(')') = q。保证数据随机。

1 \le p,q,r,base \le 10 ^ {18}

GCD Tree

有一个带权完全图,点编号为1n。边(u,v)的权值为\gcd(u,v)。求图的最大生成树。

测试数据约10 ^ 5组。1 \le n \le 10 ^ 5

本来以为这题有一些结论的,没想到是这么暴力的方法~

考虑按边权从大到小枚举边,设现在枚举到d,考虑边(u,v),且u,v \gt d,那么这条边可以用(d,u)(d,v)两条边等效替代。于是我们只要考虑dd的倍数连边的情况。换言之,我们只需考虑vu的倍数的边(u,v)

根据调和级数,有O(n\log n)条这样的边。用LCT动态维护最大生成树即可。维护时记录一下答案,即可O(1)回答询问。

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

Too Simple

m组函数f_1,f_2,...,f_m。定义域和值域均为[1,n]的整数。现给定部分函数,求有多少种合法的函数序列,满足对于1 \le i \le nf_1(f_2(...f_m(i))) = i。答案对10 ^ 9 + 7取模。

1 \le n,m \le 100

考虑这些函数,必定都是一对一的,而不会是多对一的。因为若有函数多对一,那么多个值就会映射到同一个值,最后不可能满足条件。所以这些函数实际上都是置换。

接下来我们分情况讨论。

如果所有函数都已经给定,我们只需将它们代入验证即可。

如果存在函数是未知的,我们只要确定m-1个函数,就能唯一地确定余下的一个函数。所以我们可以自由地决策cnt-1个函数,其中cnt是未知的函数数量。故答案为(n!)^{cnt-1}

Arithmetic Sequence

定义序列s(d_1,d_2)等差的,当且仅当存在i满足,对任意1 \le j \lt is_{j+1} = s_j + d_1,对任意i \le j \lt ns_{j+1} = s_j + d_2

现给定序列a,求有多少区间[l,r](d_1,d_2)等差的。

1 \le n \le 10 ^ 5, |a_i| \le 10 ^ 9, |d_1|,|d_2| \le 1000

不妨分成两种情况讨论。

d_1 = d_2时,我们就是要找序列中有多少个公差为d_1的等差数列。求出所有极长等差数列统计一下答案。

d_1 \neq d_2时,对于每个位置i,处理一下左边和右边分别可以延伸到的位置,乘法原理统计答案。

时间复杂度O(n)

Persistent Link/cut Tree

m+1棵树。T_0仅有一个点0T_i的构造方式如下:选择两棵树T_{a_i},T_{b_i},在T_{a_i}中的c_iT_{b_i}中的d_i连一条长度为l_i的边。若T_{a_i}k个点,将T_{b_i}中所有点的编号加上k

对于任意i,若T_in个点,求\sum_{i=0} ^ {n-1} \sum_{j=i+1} ^ {n-1} {dist(i,j)}。答案对10 ^ 9 + 7取模。

测试数据约100组。1 \le m \le 60,0 \le a_i,b_i \lt i,0 \le l_i \le 10 ^ 9

Travelling Salesman Problem

有一个n \times m的网格。每个格子里有一个非负整数。现要从(1,1)走到(n,m),每次可以从一个格子走到一个相邻的格子,同一个格子不能经过两次。最大化经过格子的权值之和。输出路径。

1 \le n,m \le 100, nm \ge 2, 0 \le a_{ij} \le 10 ^ 4

nm若有一个是奇数,我们就可以遍历整个棋盘。因为权值非负,直接遍历棋盘即可。

接着nm均为偶数的情况我就不会啦~~

[UPD] 杜教的题太神啦。我们考虑棋盘的黑白染色,不妨设(1,1)是黑色,故(n,m)也是黑色。考虑一条路径,因为路径上的颜色一定时交替的,所以黑色恰好比白色多一格。又因为棋盘上黑白格子数目相等,所以一定有一个白格没有经过。于是我们不经过权值最小的白格就好了。构造比较显然,但是考虑的情况较多,FST好题。

时间复杂度O(nm)

Goldbach's Conjecture

d(x)x所有约数的和。我们称x是一个好数,当且仅当[1,d(x)]中的所有整数均可以表示为x的某些约数之和。

询问一个偶数p是否可以表示成两个好数之和。输出方案。

测试数据约40000组。1 \le p \le 10 ^ {18}

Sometimes Naive

n个点的树。点i的权值为w_i。现要求支持两种操作:

1 u w: 将点u的权值修改为w

2 u v:求\sum_{i=1} ^ {n} \sum_{j=1} ^ {n} {f(i,j)}。若路径(u,v)与路径(i,j)有交点,f(i,j) = w_i w_j,否则f(i,j) = 0。答案对10 ^ 9 + 7取模。

1 \le n,m \le 10 ^ 5, 0 \le w_i \le 10 ^ 9, 0 \le w \le 10 ^ 9