Wanaalfy Summer Camp Round 3 A Knight 【大规模贪心，小规模暴力】

题目分析：这个题和bzoj 1193 很类似，唯一的区别就是这个n,m特别大，所以要求我们在处理大数据的时候，尽可能的把答案缩减到一个合适的范围内，如果数据很大的话，一开始肯定是走 1*2往前走更合适，我们首先假设 x>=y>0，另外三个象限所在的点走法相同，所以在这种情况下，我们只要判断x,y的大小关系，如果x>y 我们就往x方向走两步，y方向走1步，走到当x=y的时候，交换x,y，那么什么情况下会相等呢

我们可以设相等的情况 y方向走了a步
列出等式 x- 2*a =y-a;
此时 a= x-y;
前提 a<x/2 $a<x/2$ 且 a<y $a<y$
然后，我们就不断的循环，最后我们控制 x,y在20的范围内，暴力搜就可以了
一开始暴力的时候选了50 T了，然后我们控制了20就过了
Q老师说这个题是打表找规律， 我打了一个表，盯着他看了一个小时，还是归纳不清楚到底是什么规律，我实在是太菜了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,n,m;
ll ans=0;
ll f[200][200];
int dx[]={-1,-1,1,1,-2,-2,2,2};
int dy[]={2,-2,2,-2,1,-1,1,-1};
bool vis[200][200];
struct node
{
    int x,y;
    ll l;
};
ll bfs(int i,int j)
{
    if(i==0&&j==0)return 0;
    ll len=0;
    queue<node>q;
    memset(vis,false,sizeof(vis));
    node t;
    t.x=i;
    t.y=j;
    t.l=0;
    q.push(t);
    while(!q.empty())
    {
        node tmp = q.front();
        q.pop();
        if(tmp.x==100&&tmp.y==100)return tmp.l;
        for(int i=0;i<8;i++)
        {
            node ne;
            ne.x = tmp.x +dx[i];
            ne.y = tmp.y +dy[i];
            if(ne.x<90||ne.x>120||ne.y <90||ne.y >120) continue;
            if(!vis[ne.x ][ne.y ])
            {
                vis[ne.x][ne.y] = true;
                ne.l = tmp.l+1;
                q.push(ne);
            }
        }
    }
}
void init()
{
    for(int i=100;i<120;i++)
        for(int j=100;j<120;j++)
    {
        f[i-100][j-100] = bfs(i,j);
    }
}
int main()
{
     memset(f,0,sizeof(f));
    init();
    /*for(int i=0;i<50;i++) { for(int j=0;j<50;j++) { printf("%2lld ",f[i][j]); } printf("\n"); } */
    scanf("%d",&T);
    while(T--)
    {
        ans =0;
        scanf("%d%d",&n,&m);
        n = abs(n);
        m = abs(m);
        if(n<m) swap(n,m);

        while(n>20||m>20)
        {
            if(n == m) {int a = (n-10)/3; n -= a*3; m -= a*3; ans += 2*a;continue;}
            if(n<m) swap(n,m);
            if (m == 0)
            {
                int a = max(0,(n-10)/4);
                n-=a*4;
                ans+=a*2;
            }
            else
            {

                int t=max(0,min(min(n-m,(n-10)/2),m));
                n -= t*2;
                m -= t;
                ans += t;
            }
        }
        printf("%lld\n",ans+f[n][m]);
    }
    return 0;
}