题意:给定一个长度 LLL,构造一个图,满足编号小的向编号大的连边,权值自己设,允许重边,使得一共有 LLL条路,且每条路权值为 [0L−1][0L-1][0L−1] 中的一种且不重复,点数不超过 202020,边数不超过 606060.
思路:用一个数系去完整的表示 [0L−1][0L-1][0L−1] 中每一个数,很容易想到用 222 进制,那我们先找一个最大的 nnn,满足 2n−1<=L−12^n-1<=L-12n−1<=L−1,然后连边就很容易了,i−>i+1i->i+1i−>i+1 连两条边权分别为 000 和 2i−12^{i-1}2i−1 的边,代表选或不选,这样我们就可以表示出 [02n−1][02^{n-1}][02n−1] 里所有的数,然后考虑不满的部分,意识流一下应该能调出来.大概就是考虑 101010010101001010100 这么一个数,那么 10100XX10100XX10100XX,即把那一位 111 翻转,则 XXXXXX 的部分就是选或不选都可以,所以我们把 333 向 nnn 连一条权值为 101000010100001010000 的边即可,以此类推,最后 111 向 nnn 连一条 L−1L-1L−1 的边即可.
tmp^=(1<<i);