NanoApe's Blog

既是咸鱼又是辣鸡

2016 Contests July

NanoApe posted @ 2016年7月06日 21:22 in 蒟蒻不比赛何来学费 , 418 阅读

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] 然后求下半部分


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter