{"problem":{"name":"[信息与未来 2019] 方格覆盖","description":{"content":"给定一个 $n\\times n$ 的矩形，其中从左上角开始，对角线上连续的 $k$ 个格子中有障碍物。你可以把若干 $1\\times2$ 的小矩形放置到该大矩形中，要求是放置的两个小矩形不能占据相同的格子，且不能碰到障碍物。例如下图是 $n=4,k=2$ 的例子，我们放置了 $6$ 个 $1\\times2$ 的小矩形。 ![](https://cdn.luogu.com.cn/upload/im","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB3755"},"statements":[{"statement_type":"Markdown","content":"给定一个 $n\\times n$ 的矩形，其中从左上角开始，对角线上连续的 $k$ 个格子中有障碍物。你可以把若干 $1\\times2$ 的小矩形放置到该大矩形中，要求是放置的两个小矩形不能占据相同的格子，且不能碰到障碍物。例如下图是 $n=4,k=2$ 的例子，我们放置了 $6$ 个 $1\\times2$ 的小矩形。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/ifmknyb8.png)\n\n给定 $n,k$，请你输出一个方案，使得放置的 $1\\times2$ 小矩形尽可能多。可以证明，$n=4,k=2$ 时，至多只能放置 $6$ 个小矩形。\n\n## Input\n\n输入一行两个用空格分隔的正整数 $n,k$，表示矩形的大小和障碍物的数量。\n\n## Output\n\n输出 $n$ 行，每行 $n$ 个整数（用任意数量的空格分隔）。放置的小矩形分别用 $1,2,\\cdots$ 编号。不放置小矩形的格子输出 $0$。如有多种最优方案（放置最多数量的小矩形），输出任意一种即可。\n\n[samples]\n\n## Note\n\n对于 $50\\%$ 的测试数据，有 $1\\le k\\le n\\le10$。\n\n对于 $100\\%$ 的测试数据，有 $1\\le k\\le n\\le50$。\n> 本题原始满分为 $20\\text{pts}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3755","tags":["模拟","贪心","2019","江苏","Special Judge","构造","信息与未来"],"sample_group":[["4 2","0 0 1 2\n3 0 1 2\n3 4 4 0\n5 5 6 6"],["5 3","0 8 8 9 10\n1 0 0 9 10\n1 3 0 0 7\n2 3 5 5 7\n2 4 4 6 6"]],"created_at":"2026-03-03 11:09:25"}}