Noi...

update:16.07.07

XJOI NOI2016模拟训练题5

小 H 的卡片

给 n 个数，选取每个数有代价，求代价最小且满足 $gdb=1$ 的集合，$n \le 300$

状压，枚举一个一定要取的数，最多 9 个不同的质因子，其他数要满足某一质因数的次数为 0，接着状压即可，$O(n^22^9)$

小 Z 的积木

给立体积木的摆放和光线角度，问多少积木被照到

对于矩形我们可以映射到一条线段上，变成 $n^2$ 条线段，接着就可以离散化端点，变成线段树和区间max操作区间min询问

小 W 的数字

给一个数 n，每次可以减去 $1-9$，只要其现在在数位中出现过，问最少次数，$n<=10^{18}$

记忆化搜索，存下前面最高位和后面尚未处理的数位，然后一位一位推进（状态数玄学）

计蒜客2016复赛

微软项目经理的挑选方案

给一堆线段，选取一些线段，使得和被选取的线段的交集为空的线段的集合为空……求方案数

先按右端点-左端点排序

设 $F(i,j)$ 表示最大标号为 j 且最小不能被触及的线段为 i 的集合的总和，设 $A(i,j)=|F(i,j)|$，$S(i,j)=\sum A(i,j)$

离散化后可以预处理出一条线段所不能触及的右边最小、左边最大线段，设为 $L,R$

转移如下：

$A(i,j)=S(i,j-1),~(i<=L[j])$

$A(i,j)=\sum_{i'}^{L[i]<i'<=R[i]}S(i',j-1),~(i=R[j])$

其他的 A 都为0

（上面特么的都是原来题解的扯蛋。。。

排序完设 $S_i$ 表示最小标号没被覆盖的线段的方案数，同样处理出 $L,R$，考虑线段 i 的放置，$L_i+1..R_i-1$ 的方案经过放置会统一变成 $R_i$，其他的原地不变；我们要求前缀和，也就是将 $L_i+1..R_i-1$ 的方案数 Copy 一份加到 $R_i$，其余的直接 *2

最后弄个线段树维护区间加和区间乘即可

（类似思路：考虑最小没被选中的东西

百度地图的实时路况

设 $D(a,b,c)$ 表示 b 点不可经过时 a 到 c 的最短路长度，求总和

分治 Flody

Flody 进行 k=[mid+1..r] 然后求上半部分，进行 k=[l..mid] 然后求下半部分