CF255D Mr. Bender and Square 题解
本文最后更新于 33 天前,其中的信息可能已经有所发展或是发生改变。

在洛谷查看题目 | 在CF查看题目

翻译

给出一个 $n\times n$ 的正方形和一个点的坐标($x,y$),从这个点每秒可以向外扩散四个点,即 $(x+1,y),(x-1,y),(x,y+1),(x,y-1)$ ,求需要多少秒才能大于或等于面积 $c$

思路

如果将这个点看作是在无限大的正方形上扩散,那么我们可以得出:

扩散时间 0 1 2
点的数量 1 5 13

于是,为了得出扩散时间和点的数量的关系,设一个二次函数为 $y=ax^2+bx+c$ 。( $x$ 为扩散时间, $y$ 为点的数量)
将上表的数据带入二次函数就得到了一个三元一次方程(由于在本站数学公式无法达到效果,所以只能在本地写好截屏),图片如下:


$\therefore$ 这个二次函数为: $y=2x^2+2x+1$

现在我们开始考虑边缘阻挡了的点的数量。
不难发现,在边缘以外需要减去的点组成了一个像金字塔一样的三角形(第一层有 $1$ 个,第二层有 $3$ 个 ……),图片如下(手画很丑,请见谅):

这个图片的扩散时间为 $3$ ,蓝色区域代表点,红色边框在 $3\times 3$ 的正方形边缘外,绿色圆圈圈出的三角形即为突出部分。
提供一下小学奥数的知识:
$1+3+5+…+2n-1=n^2$
因此,就可以得出突出部分的点数,其他几个边也一样。

然后,你会发现突出部分有重叠,如下图绿圈部分:


多次画图后,发现:重叠部分是个每层点数相差1的三角形,于是就可以用高斯求和 $(1+2+3+…+n=\frac{(1+n)n}{2})$ 算出重叠部分点数。
所以总的点数=忽略边缘时的点数-四边突出的点数+重叠部分的点数
注:上面得出的式子由容斥原理所得。

有了公式,就可以二分查找答案了!

代码

注:二分查找注意边界!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1e9+10;
ll n,x,y,c; 
int main() {
    cin>>n>>x>>y>>c;
    x--;y--;
    ll l=0,r=2*n+1,ans=INF;
    while(l<=r) {
        ll mid=(l+r)/2;
        ll s=2*mid*mid+2*mid+1; //忽略边界的点数
        if(mid-x>0) s-=(mid-x)*(mid-x); //上边突出部分
        if(mid-(n-1-x)>0) s-=(mid-(n-1-x))*(mid-(n-1-x)); //下边突出部分
        if(mid-y>0) s-=(mid-y)*(mid-y); //左边突出部分
        if(mid-(n-1-y)>0) s-=(mid-(n-1-y))*(mid-(n-1-y)); //右边突出部分

        if(mid-x-(n-y-1)-1>0) s+=(1+mid-x-(n-y-1)-1)*(mid-x-(n-y-1)-1)/2; //右上重叠部分
        if(mid-(n-1-x)-(n-1-y)>0) s+=(1+mid-(n-1-x)-(n-1-y)-1)*(mid-(n-1-x)-(n-1-y)-1)/2; //右下重叠部分
        if(mid-(n-1-x)-y-1>0) s+=(1+mid-(n-1-x)-y-1)*(mid-(n-1-x)-y-1)/2; //左下重叠部分
        if(mid-y-x-1>0) s+=(1+mid-y-x-1)*(mid-y-x-1)/2; //左上重叠部分

        if(s>=c) {
            r=mid-1;
            ans=min(mid,ans);
        }
        else {
            l=mid+1;
        }
    }
    cout<<ans<<endl;
    return 0;
}

本文作者:Ryan
本文链接:https://ryanblog.ga/index.php/archives/88
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可,转载请注明出处
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇