NOI2015 Day1

NOI2015 Day1

程序自动分析

题目描述：给出等式或不等式(n)条，问(n)条式子是否成立。

solution：
用并查集处理等式，在判断不等式是否成立。

时间复杂度：(O(n)) (hash)

软件包管理器

题目描述：维护一棵树，支持两种操作：
1、询问点到根的点权和，并将路径上的点的权值修改为1
2、询问点的子树的点权和，并将子树的点的权值修改为0

solution：
树链剖分可以很好的解决第一种操作，那第二种操作也可以用树链剖分吗？
可以，先求出重儿子，然后用(dfs)建线段树，(dfs)时先(dfs)重儿子，再(dfs)其他儿子，这样既能保证重链在线段树上是连续的，每棵子树在线段树上也是连续的。

时间复杂度：(O(nlogn))

寿司晚宴

题目描述：设正整数集合$A,B, A cap B = Ø (，使)forall x in A, forall y in B,(有)x in [2, n], y in [2, n], (x, y)=1(,给定)n(，求集合)A,B(对的方案数。)A,B(可以为)Ø$

solution：
(n leq 500， sqrt{n} < 23),小于(sqrt{n})的质数只有8个（暂且称为小质数，其它质数称为大质数），所以可以用二进制来表示每个数拥有的小质数因子集合。每个数最多只会有一个大质数因子(大质数 $ >sqrt{n} (),所以比较好处理。设状态)f[i][j][k](，表示做完第)i(个大质数，)A(拥有小质数集为)j(，)B(拥有小质数集为)k$$(j & k=0)$ 的方案数。(f[0])表示没有大质数，所以直接对没有大质数因子的数dp就好了。对于有大质数因子，枚举具有该因子的数(p),(p)拥有的小质数因子集为(z) 转移方程如下：

$ f[i][j][k]=d[j][k][0]+d[j][k][1]+f[i-1][j][k] $

$ d[j | z][k][0]=d[j][k][0]+f[i-1][j][k] $

$ d[j][k | z][1]=d[j][k][1]+f[i-1][j][k] $

先解释第二、三条方程，对于(d[j][k][q])，(A)拥有小质数集为(j)，(B)拥有小质数集为(k)的方案数，当(q=0)时表示将(p)放入(A)，当(q=1)时表示将(p)放入(B). 其实就是对拥有该大质数因子的数进行dp。然后将dp的结果用一个总的(f[i][j][k])进行dp（前i个大质数因子的dp）

时间复杂度：(O(2^{16}n))