2017年多校联训1 部分题解

1001. Add More Zero

参见附件。

1002. Balala Power!

每个字符对答案的贡献都可以看作一个26进制的数字，直接按26进制的从高到低位比较大小。由排序不等式，显然贡献越大的对应的数字越大时答案最大。

注意点：一个字符一旦做过最高位(位数大于1)就不能被赋值为0。

1003. Colorful Tree

单独考虑每一种颜色，答案就是对于每种颜色，至少经过一次这种颜色的路径条数之和。反过来思考只需要求有多少条路径没有经过这种颜色即可。

记 u 的颜色为col[u]。对于 v ，若在子树 v 中取 x ，在子树 v 外取 y ，则这些路径一定会经过col[v]。那么有两个推论：

• 不经过col[v]的路径的两端 x,y 一定同在子树 v ；
• 对于 v 的祖先 u ，若col[v]==col[u]，则在 u 上计算时整棵子树 v 都要被排除。

这样我们可以用合并线段树的方法解决，复杂度 O(nlogn) ，详见附件2。

又发现线段树实际上只维护了单点增加的操作，可以用sum[i]表示颜色i需要排除的节点数对于dfs序的前缀和，复杂度 O(n) 。

1006. Function

考虑置换 a 的一个循环节，长度为 l ，那么有 f(i)=bf(ai)=bbf(aai)=b⋯bf(i)l times b

那么 f(i) 的值在置换 b 中所在的循环节的长度必须为 l 的因数。

而如果 f(i) 的值确定下来了，这个循环节的另外 l−1 个数的函数值也都确定下来了。

答案就是 ∑ki=1∑j|lij⋅calj ，其中 k 是置换 a 中循环节的个数， li 表示置换 a 中第 i 个循环节的长度， calj ​​ 表示置换 b 中长度为 j 的循环节的个数。

1008. Hints of sd0061

参见附件。

1009. I Curse Myself

按题解写出来的那个方法过的，时间很险，3697ms。。。
参见附件。

1011. KazaQ’s Socks

参见附件。

1012. Limited Permutation

题目给的信息实际上就是 p[li...ri]≥p[i] 。

首先必须有一个位置 i 满足 li=1,ri=n ，否则方案数为 0 。考虑 i 左右的两段数，因为 p[i] 是最小的，所以左边数向右的界不会越过 i ，即 (rj<i) ；右边数向左的界不会越过 i ，即 (lk>i) 。可以发现：左边数和右边数不会再有任何联系，是完全相同的两个子问题。每次递归给答案累乘从 ri−li 个数中选出一部分作为左边数的方案数即可。思路来自附件3，代码为附件4中的1012_NlogN.cpp。

很显然，递归算法的瓶颈不在于递归本身而在于利用映射查询是否有位置对应 [L,R] 。某大佬：用一个栈搞一搞就行了。代码为附件4中的1012.cpp。

附件

1. solutions BY 北京航空航天大学
2. HDU6035 Colorful Tree
3. HDU6044 Limited Permutation
4. 我的实现代码