本文共 2509 字，大约阅读时间需要 8 分钟。
https://www.luogu.org/problemnew/show/P1228
我真傻，真的，我单知道这种题目可以用dfs剪枝过，没有想到还能构造分治，当我敲了一发dfs上去的时候，只看到一个42分的返回┭┮﹏┭┮
题意：构造用所给的四个图案拼凑一个缺制定位置的正方形，正方形的长度为2 ^ k (0 < k < 10)
一开始直接选择了dfs暴力填充，TLE却想不到有效的剪枝方法，一看题解这竟然是一道构造分治，原因除了愚蠢之外还有忽略了题目中正方形边长为2 ^ k这个条件
我们定义多出来的点为特殊点，我们可以用一个给定的图形把他构造为一个2 * 2的矩形，这时候如果要构造的是4 * 4的矩形，我们只需要在2 * 2的矩形下面拼接上一个图案，就多出了三个位置的特殊点，利用刚才的方法将他们补上，就变成了一个4 * 4的矩形，8 * 8同理。直接分治递归即可。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;int read(){ int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){ if (c == '-') f = -1;c = getchar();}while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}#define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--)#define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x)#define Sca2(x,y) scanf("%d%d",&x,&y)#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define Scl(x) scanf("%lld",&x); #define Pri(x) printf("%d\n", x)#define Prl(x) printf("%lld\n",x); #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();#define LL long long#define ULL unsigned long long #define mp make_pair#define PII pair #define PIL pair #define PLL pair #define pb push_back#define fi first#define se second typedef vector VI;const double eps = 1e-9;const int maxn = 110;const int INF = 0x3f3f3f3f;const int mod = 1e9 + 7; int N,M,K;void dfs(int a,int b,int x,int y,int l){ if(l == 1) return; l >>= 1; if(x - a + 1 <= l && y - b + 1 <= l){ //左上 printf("%d %d 1\n",a + l,b + l); dfs(a,b,x,y,l); dfs(a,b + l,a + l - 1,b + l,l); dfs(a + l,b,a + l,b + l - 1,l); dfs(a + l,b + l,a + l,b + l,l); } if(x - a + 1 <= l && y - b + 1 > l){ // 右上 printf("%d %d 2\n",a + l,b + l - 1); dfs(a,b,a + l - 1,b + l - 1,l); dfs(a,b + l,x,y,l); dfs(a + l,b,a + l,b + l - 1,l); dfs(a + l,b + l,a + l,b + l,l); } if(x - a + 1 > l && y - b + 1 <= l){ //左下 printf("%d %d 3\n",a + l - 1,b + l); dfs(a,b,a + l - 1,b + l - 1,l); dfs(a,b + l,a + l - 1,b + l,l); dfs(a + l,b,x,y,l); dfs(a + l,b + l,a + l,b + l,l); } if(x - a + 1 > l && y - b + 1 > l){ //右下 printf("%d %d 4\n",a + l - 1,b + l - 1); dfs(a,b,a + l - 1,b + l - 1,l); dfs(a,b + l,a + l - 1,b + l,l); dfs(a + l,b,a + l,b + l - 1,l); dfs(a + l,b + l,x,y,l); } }int main(){ Sca(K); int x = read(),y = read(); dfs(1,1,x,y,(1 << K)); return 0;}
转载于:https://www.cnblogs.com/Hugh-Locke/p/10301053.html