题解 P3739 【[HAOI2014]走出金字塔】

· · 题解

作为一个蒟蒻我找了两个小时的规律才调出来emmmm

好像我的做法不是很一样

如果知道两个点，可以直接求出其距离

设A(x_1,y_1),B(x_2,y_2)且x_1\leq x_2

先把B平移到A所在层，这一步用了2(x_2-x_1)

接下来考虑平移后B在水平方向延伸的最大距离

可以看出这个距离是x_2-x_1

如果A和B'的距离不在这个范围内，我们就要给答案加上这个差

注意水平距离计算时要补成正方形来算

也就是ans+=max(|y_1-y_2+x_2-x_1|-x_2+x_1,0)

否则的话，还要考虑奇偶性

容易打表看出答案需要加上y_2\ mod\ 2\ -\ y_1\ mod\ 2

这样子就可以得到最终答案了

但是距离明明应该是对称的算出来的这个式子却不对称好气啊我也不知道为什么

代码还是挺简单的

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,k,s,x,y,ans=1e9+7;
int abs1(int x){return x>0?x:-x;}
int dis(int x1,int y1,int x2,int y2)
{
    if(x1>x2)swap(x1,x2),swap(y1,y2);
    int ans=(x2-x1)<<1,t=abs1(y1-y2+x2-x1)+x1-x2;
    ans+=t>0?t:(y2&1)-(y1&1);
    return k*ans;
}
int getin()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
    return x;
}
int main()
{
    n=getin(),m=getin(),k=getin(),s=getin(),x=getin(),y=getin();
    for(int i=1;i<=m;i++)
    {
        int xx=getin(),yy=getin();
        ans=min(ans,dis(x,y,xx,yy)+1);
    }
    if(ans<=s)cout<<s-ans<<endl;
    else cout<<-1<<endl;
}

找规律是不可能的，这辈子都不可能找规律的