LOJ 6003 – 魔术球

题面链接:LOJ 6003

如果$x$个球放在$n$个柱子上,$x+1$个球放在$m$个柱子上,那么$m \geq n$。很好理解,第$x+1$个球可以和当前的任何一个柱子顶上的球组成平方和的话$m=n$,否则$m=n+1$。

基于这一点,我们考虑已知$x$求$n$。我们把小于等于$x$的所有点拿出来建图,$i+j(i \neq j)$为完全平方数的时候建边,那么$n$就是这张图的最小路径覆盖数。

我们已知$n$关于$x$单调不减,那么只要顺序枚举$x$,求$n$,知道$n$大于给定的输入即可。

坑点:

  • 按照我的写法汇点的编号应该是maxn / 2 – 1
  • maxn的规模为$10^5$,$10^6$会TLE(依然不知道如何估计这里的maxn)

 

说点什么

avatar
50
  Subscribe  
提醒