「zig-zag pattern」笔记

· · 算法·理论

zig-zag，意为『之字形』。zig-zag pattern主要解决在完全图上找到一条经过所有节点的简单路径的问题。其具体算法如下：

现有一个节点数 |V|=n 的完全图 G，要在找到一条节点数为 n 的简单路径 P，则

P=i\rightarrow i-1 \rightarrow i+1 \rightarrow i-2\rightarrow i+2\rightarrow\cdots\rightarrow i-\frac{n}{2} \rightarrow i+\frac{n}{2}

（n 为偶数）

或

P=i\rightarrow i-1 \rightarrow i+1 \rightarrow i-2\rightarrow i+2\rightarrow\cdots\rightarrow i-\frac{n}{2}

（n 为奇数）

将所有节点看作是一个环，当遇到节点编号越界的情况，使其变为在环上对应的点即可。

如图：

应用

P9837 汪了个汪

在本题中，将：

  1. 所有由任意一行内相邻两个数组成的无序二元组互不相同
  2. 一行内的所有数必须互不相同

转换为将一个节点数为n的完全图的边划分为长度分别为 1,2,3,\cdots,n 的 n 条简单路径。

考虑 n 为偶数的情况：

根据高斯算法可知这 n 条简单路径可以转换为 \frac{n}{2} 条长度为 n 的简单路径，（因为一条路径的终点是另一条路径的起点。）此时使用 zig-zag pattern 找出起点为 1,2,3,\cdots,\frac{n}{2} 的路径，将每条路径拆分为长度为 i 和 n-i 的两条路径，即为棋盘第 i 行和第 n-i 行的填数情况。代码如下：

#define re register
#define rep(i, s, t) for(re int i=s; i<=t; ++i)

int lim(int x) {
    if(x==0) return n;
    else if(x>0&&x<=n) return x;
    else if(x>n) return x%n;
    else if(x==-n) return n;
    else return x+n;
}

rep(i, 1, n>>1) {
    mem[i][1] = i;
    rep(j, 1, n>>1) {
        mem[i][2*j] = lim(i-j);
        mem[i][2*j+1] = lim(i+j);
    }
    rep(j, 1, n+1-i) {
        mem[n+1-i][j] = mem[i][n+1-j];
    }
}
rep(i, 1, n) {
    rep(j, 1, i) {
        std::cout << mem[i][j] << ' ';
    }
    std::cout << '\n';
}

当 n 为奇数时，只需要添加 0 作为虚点，按照 n 为偶数的算法进行，最后以 0 为断点将路径拆分即可。代码如下：

int lim_(int x) {
    if(x==n+1) return 0;
    else if(x>=0&&x<=n) return x;
    else if(x>n) return x%(n+1);
    else if(x==-n) return 1;
    else return x+n+1;
}
rep(i, 0, ((n+1)>>1)-1) {
    int k;
    if(i%2) k = lim_((i+1)>>1);
    else k = lim_(-((i+1)>>1));
    mem[i][1] = k;
    rep(j, 1, (n+1)>>1) {
        mem[i][2*j] = lim_(k-j);
        mem[i][2*j+1] = lim_(k+j);
    }
    rep(j, 1, n-i) {
        mem[n-i][j] = mem[i][n+2-j];
    }

}
rep(i, 1, n) {
    rep(j, 1, i) {
        std::cout << mem[i][j] << ' ';
    }
    std::cout << '\n';
}

CF1290D Coffee Varieties (hard version)

在得出本题 easy version 的算法后，考虑用 zig-zag pattern 进行优化。将所有分块之间的两两比对转换为完全图中的边，使用 zig-zag pattern 将整个图划分为边不相交的链，再进行操作。

代码：

void better() {
    if(k==1) {
        rep(i, 1, n) {
            rep(j, i+1, n) {
                ask(i);
                if(ask(j)=='Y') death[j] = 1;
                std::cout << "R\n";
            }
        }
        std::cout << "! " << n-death.count() << '\n';
        return;
    }
    rep(i, 1, n/k) {
        int d=0;
        rep(j, 1, n/k) {
            x = i+d;
            rep(s, 1, k) {
                if(!death[(lim(x)-1)*k+s])
                if(ask((lim(x)-1)*k+s)=='Y') {
                    death[(lim(x)-1)*k+s] = 1;
                }
            }
            if(d>=0) {
                d = -d-1;
            }
            else {
                d = -d;
            }
        }
        std::cout << "R\n";
    }
    std::cout << "! " << n-(death.count()) << '\n';
    return;
}