Problem′s Website
(因权限问题查看不了题目的同学不要打我)
根据题意直接进行模拟肯定会超时。。。
于是我们来优化,我们可以对x坐标进行普通的枚举,对y坐标进行差分。
因为等腰直角三角形的直角顶点有四种情况,所以要分类讨论
因为作者太懒了,所以请读者自行画图,我只在下文给出结论。。。
写在前面:num,每次循环前为0,然后不断递增。
opt=1
for i x ~ (x+l)
a[i][y] += c
a[i][y+l−num+1]−=c
-
opt=2
$for$ $i$ $x$ ~ $(x + l)$
$a[i][y - l + num] += c$
$a[i][y + 1] -= c$
opt=3
for i x ~ (x−l)
a[i][y]+=c
a[i][y+l−num+1]−=c
-
opt=4
$for$ $i$ $x$ $(x - l)$
$a[i][y - l + num] += c$
$a[i][y + 1] -= c$
最后直接枚举,计算最大值即可。
Code
1 | //Coded by dy. |
rp++
Related Issues not found
Please contact @dyrisingsunlight to initialize the comment