> 首先注意到所有的数都在整数格点上，而且半径只有两且都很小。 我们可以发现，
> 一个0.58半径的圆只会影响到周围4格，一个1.31半径的圆只会影响到周围12格（见图）
> 
> 半径1.31的影响范围            半径0.58的影响范围
>       .XX.                       ....
>       XXXX                       .XX.
>       XXXX                       .XX.
>       .XX.                       ....
> 
> 于是发现，一个格子的状态（被覆盖的面积），仅仅取决于它周围的12个格子！ 而这个状
> 态的数目，只有3^4*2^8=20736种！
> 
> 于是写一个simpson暴力，把20736个状态预处理出来。但这一步要花大约2秒，会tle，
> 因此必须打表。
> 但直接打表会超代码长度限制。 我们观察这个表，发现连续的重复的段很多，于是用一个
> 简单的压缩，把一段相同的数（精确到5位小数就绰绰有余了）用二元组[a,b]表示出来
> ，a出现了b次。
> 然后进一步压缩，因为只出现了0～9，其他的字符都被浪费了，于是转成64进制（0～9,
> A~Z,a~z和两个其他字符），这样一个二元组用5个字符就能表示了。
> 这时候表只有不到20K了，就可以装下了。
> 
> 然后任务就简单了，一个圆只会影响到周围的格子，用hash表记录某个格子被影响的状态，
> 然后统计一下即可，整个过程是线性的。
狂赞XHR大神圣诞节不陪女朋友，在这里刷神题

• Re:orz (5) peargobble 2011-12-25 20:05:51
  • Re:orz (9) dut200901102 2011-12-25 21:24:18