NFLSPC #1 E题 Hack it 题解

2019-06-30 22:25:49 By skyline

这是多校一个题(hdu6313)的加强版 我现场做的时候发现可以做得好不少 于是有了这个题

我们先考虑1的个数的最大上界

记二元组(x,y)对出现次数为:有多少个i使 i行x列 与 i行y列 都是1

发现每个二元组最多出现一次 不然就会出现四角为1的矩形

记$a_i$为第i行1的个数 有:$c(a_1,2)+c(a_2,2)+...+c(a_n,2) \le c(n,2)$

不妨在不影响数量级的情况下做一个近似,变为:$a_1^2+a_2^2+...+a_n^2 \le n^2$

取$k=sqrt(n)$ 由柯西不等式,有:

$(k\times a_1+k\times a_2+...+k\times a_n)^2 \le (k^2+k^2+...+k^2)\times (a_1^2+a_2^2+...+a_n^2) \le n^4$

于是$(a_1+a_2+..+a_k) \le n\times k$ 取等时$a_i=k$

这给了我们一个方向:在1较多时,每行大约sqrt(n)个1

在取$n=p^2$ (p代表质数)时 我们有了一个优美的构造:

请看int main里第一个for循环

但是,我们的n并不是一个质数的平方,我们有2种好的选择:

用若干个小正方形拼起来 用某个大正方形的一部分

因为$43^2 < 2018 < 47^2$ 而47的平方据2018更近(而且实测效果好不少) 所以采用“用某个大正方形的一部分”的方法

这样,就可以得到大约90分的高分了

我们注意到,截小正方形的位置很灵活,可以在任何位置截(事实上还可以不连续,但是实现起来较为麻烦) 我们可以在所以位置中找答案最大的截

但是上面那个构造过于优美导致过于平均,大的答案也并没有很大

我们给出一个类似但不太均匀的构造,再来找答案最大的小正方形输出即可

其中solve是构造,其它部分是找小正方形

另外这是一个吊打std的做法

这篇题解咕了8个月 因为我感觉构造题没什么好讲的 而且这个破方法还被最后一个做法吊打了 但是看那个题解合集一直缺一题难受 最后还是补上了

评论

回复

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。