2018 ICPC 区域赛 青岛站 F题 Tournament ZOJ 4063（找规律）

题目

ZOJ 4063 Tournament

思路

手写答案或者打表，找规律

会发现是把左上角的块放到右下角，右上角的块放到左下角。
块的大小依次为2 4 8 16 ……

枚举块长度即可

显然，lowbit(n)决定了完整的行的数目，即它决定了k的值。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e4 + 10;
const int INF = 0x3f3f3f3f;int a[maxn][maxn];
int t, n, k;
void solve(int L){
    ///把左上角的块放到右下角for(int x = 1; x + 2 * L - 1 <= n; x += 2 * L){
    ///x y枚举当前块的坐标for(int y = 1; y + 2 * L - 1 <= n; y += 2 * L){
    for(int i = x; i <= x + L - 1; i++){
    ///枚举块内元素的坐标for(int j = y; j <= y + L - 1; j++){
    a[i + L][j + L] = a[i][j];}}}}///把右上角的块放到左下角for(int x = 1; x + L - 1 <= n; x += 2 * L){
    ///x y枚举当前块的坐标for(int y = L + 1; y + L - 1 <= n; y += 2 * L){
    for(int i = x; i <= x + L - 1; i++){
    ///枚举块内元素的坐标for(int j = y; j <= y + L - 1; j++){
    a[i + L][j - L] = a[i][j];}}}}
}
int lowbit(int x){
    return x & -x;
}
int main(){
    scanf("%d", &t);while(t--){
    scanf("%d %d", &n, &k);if((n & 1) || lowbit(n) - 1 < k){
    printf("Impossible\n");continue;}for(int i = 1; i <= n; i++){
    a[1][i] = i;}for(int i = 1; i <= n; i += 2){
    a[2][i] = i + 1;a[2][i + 1] = i;}///枚举块的长度 2 4 8 16for(int i = 2; 2 * i <= n; i <<= 1){
    solve(i);}for(int i = 2; i <= k + 1; i++){
    for(int j = 1; j <= n; j++){
    printf("%d%c", a[i][j], j == n ? '\n' : ' ');}}}return 0;
}