题解 P3739 【[HAOI2014]走出金字塔】
wuzhoupei
2018-03-03 20:48:43
这个题啊，真是流弊
我一开始是蒙圈的
然后就猜测一些性质，比如令(x,y)为当前的坐标
那我们会发现这样的性(gui)质(lv) :
**首先所有 y 为偶数的三角形是反着的(顶点向下)，同理 y 为奇数的三角是正着的 **
**然后，两个三角的相对位置不变，距离则不变**
**再然后，任何一个三角都可以通过对称移动到(x,1) **
**最后任何一个(x,1)形式的三角和(1,1)之间的距离是(x-1)<<1 **
根据上面的性质，我们就可以发现，把任何一个三角的横纵坐标做一些处理，使之成为(x,1)的形式，并且此时将起始坐标点转化为(1,1),这样就好求了许多
在此之前，由于可能三角是倒着的，那么我们就将他们正过来
还有可能是起始点的坐标在询问点的下面，我们要将他们交换
而且翻转时会对 ans 产生一定影响，而且要先交换再翻转
至于原因，请(wo)读(lan)者(de)自(qu)行(jie)考(shi)虑(le)(画个图就好了的)
-------------------
```cpp
#include <bits/stdc++.h>
#define II int
#define IL inline
#define R register
#define I 123546
using namespace std;
template < typename T > IL void of(R T &a) {
R char c=getchar (); R T w=1, p=0;
while (!isdigit(c)) { if(c=='-') w=-1; c=getchar (); }
while (isdigit(c)) { p=p*10+c-'0'; c=getchar (); }
a=w*p;
}
/* -------------------- Peipei -------------------- */
II n,m,k,s,nx,ny;
int main()
{
of(n); of(m); of(k); of(s); of(nx); of(ny);
R II ans=1e9, now=0;
for(R II i=1,x,y;i<=m;i++) {
R II xx=nx, yy=ny;
now=0;
of(x); of(y);
if(nx>x) swap(x,nx), swap(y,ny);
if(!(ny&1)) nx--, ny--, now--;
if(!(y&1)) x--, y--, now++;
x-=nx-1; y-=ny-1;
if(y>x*2-1) now+=y-(x*2-1);
if(y<1) now+=1-y;
y=1;
now+=(x-1)*2;
ans=min(ans,now);
nx=xx; ny=yy;
}
ans*=k; ans++;
if(ans>s) ans=-1;
else ans=s-ans;
printf("%d\n",ans);
exit(0);
}
```
---------------------------