2015 Multi-University Training Contest 1 Solutions

官方题解:2015 Multi-University Training Contest 1 题解 BY FZU

 


 

1001 OO’s Sequence

HDU 5288:http://acm.hdu.edu.cn/showproblem.php?pid=5288

题意:给出一个数组 \(a[n]\) ,定义函数 \(f(l,r)\) 表示在区间 \([l,r]\) 内没有 \(a_i\) 的因子的 \(i\) 的数量,因子的下标不能为 \(i\) ,求

\[\sum_{i=1}^{n}\sum_{j=i}^{n}f(i,j)\mod(10^9+1)\]

 

题目可以转换成每个 \(a_i\) 可以贡献的区间个数为 \(K_i\) ,求出所有 \(K_i\) 之和

要求 \(K_i\) 就是找左右离 \(a_i\) 最近的2个因子,求出左右不包含因子的区间长度 \(l,r\)

\[K_i=(l+1)\times (r+1)\]

\[ans=\sum_{i=1}^{n}K_i\]

要求出最近的因子可以预处理10000内所有数的因数,在输入的时候记录每个数出现的位置,因为记录是有序的,所以可以找出离 \(a_i\) 最近的两个因子

 

 


 

1002 Assignment

 

HDU 5289:http://acm.hdu.edu.cn/showproblem.php?pid=5289

题意:求区间内的数两两之间差小于K的区间个数

 

RMQ+二分

先预处理出区间最大值和最小值

对于每个 \(a_i\) 可以用二分找出最大的r值满足区间 \([i,r]\)\( max-min

 

 


 

 

1012 Circles Game

题意:给出n个不想交的圆,两人轮流删圆,每次可以删去一个圆以及它包含的所有圆,不能删时为输

树上SG

如果做出圆的包含关系树,就是一个明显的树上SG。

对于树上SG附上一篇相关文章:树上删边游戏

 

这里直接说结论

树的删边游戏
从某一棵树上删除一条边,同时删去所有在删除边后不再与根相连的部分。双方轮流进行,无法再进行删除者判定为失败。

定理:

  • 叶子节点的 SG 值为 0;
  • 中间节点的 SG 值为它的所有子节点的 SG 值加 1 后的异或和。

对于建立圆的包含关系树,可以按半径从小到大排序,对于第一个大于并包含它的圆建边,然后break;

PS:交G++

 

 


 

(待续。。。)

Categories: ACM