P1228 地毯填补问题

离散上讲了这个问题，如下图

初看这个问题，似乎无从下手，于是我们可以先考虑最简单的情况，既n = 2时
0 0 0 1 这时，无论公主在哪个格子，我们都可以用一块毯子填满
继续考虑n = 4的情况
我们已经知道了解决2 * 2的格子中有一个障碍的情况如何解决，因此我们可以尝试构造这种情况
首先，显然可以将4 * 4的盘面划分成4个2 * 2的小盘面，其中一块已经存在一个障碍了
而我们只需在正中间的2 * 2方格中放入一块地毯，就可以使所有小盘面都有一个障碍
于是，n = 4的情况就解决了
我们可以将n = 4时的解法可以推广到一般情况，既当n = 2 k时，我们均可以将问题划分为4个n = 2 k – 1的子问题，然后分治解决即可。
来源

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define ls (p<<1)
#define rs (p<<1|1)
#define mid (l+r)/2
#define over(i,s,t) for(register int i=s;i<=t;++i)
#define lver(i,t,s) for(register int i=t;i>=s;--i)

#define ul solve(a+l-1,b+l-1,a,b,l)//左上角
#define ur solve(a+l-1,b+l,a,b+l,l)//右上角
#define dl solve(a+l,b+l-1,a+l,b,l)//左下角
#define dr solve(a+l,b+l,a+l,b+l,l)//右下角

using namespace std;
typedef long long ll;//全用ll可能会MLE，ll比int占的内存大

const ll N=1002;
const ll INF=1e9+9;
const ll mod=9999991;
const double EPS=1e-6;

inline void solve(ll x,ll y,ll a,ll b,ll l)//x,y是已覆盖点，a,b是除覆盖点剩下的图形的弯折角的点
{
    if(l==1)return;
    l>>=1;
    if(x<a+l&&y<b+l)//左上角
    {
        printf("%lld %lld 1\n",a+l,b+l);
        solve(x,y,a,b,l);//继续把有人的区块填满（现在只是填了1/4，左上角的整块的右下角填上了）
        ur;
        dl;
        dr;
    }
    if(x<a+l&&y>=b+l)//右上角
    {
        printf("%lld %lld 2\n",a+l,b+l-1);
        solve(x,y,a,b+l,l);//a不用动
        ul;

        dl;
        dr;
    }
    if(x>=a+l&&y<b+l)//左下角
    {
        printf("%lld %lld 3\n",a+l-1,b+l);
        solve(x,y,a+l,b,l);//b不用动
        ul;
        ur;

        dr;
    }
    if(x>=a+l&&y>=b+l)//右下角
    {
        printf("%lld %lld 4\n",a+l-1,b+l-1);
        solve(x,y,a+l,b+l,l);
        ul;
        ur;
        dl;

    }
}

ll x,y,k,n;

int main()
{
    scanf("%lld",&k);
    scanf("%lld%lld",&x,&y);
    solve(x,y,1,1,1<<k);
    return 0;
}

有任何疑问欢迎评论哦虽然我真的很菜