P4222 [CQOI2012] 编号

· · 题解

这道题让我深刻地体会到了打史山代码的快乐。

一共 7 位，需要有 3 位不同。为了尽量优化状态空间，考虑先选出 2 个不同位，那么有 \binom{7}{2}=21 种选法。然后剩下的五位中有一位可以不同。

设 f_{k,a,b,c,d,e} 为选出 2 位时采用第 k 种方案（1 \le k \le 21），且其他位的值分别为 a,b,c,d,e 的状态是否被占用过。

于是可以枚举所有位上的值，如果当前状态的一种表示被占用了就不能更新，否则将所有状态表示方法标记为占用。注意这里的全部 21 种状态是手敲的，当然也可以用枚举全排列的方法。

当达到 k 个时就退出，注意写为十六进制。时间复杂度 \Theta(k)。

#include <bits/stdc++.h>
using namespace std;
#define int long long

int k, r[22][16][16][16][16][16];

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin >> k;
    for(int a = 0; a < 16; ++ a)
    for(int b = 0; b < 16; ++ b)
    for(int c = 0; c < 16; ++ c)
    for(int d = 0; d < 16; ++ d)
    for(int e = 0; e < 16; ++ e)
    for(int f = 0; f < 16; ++ f)
    for(int g = 0; g < 16; ++ g){
        if(!(r[1][a][b][c][d][e] || r[2][a][b][c][d][f] || r[3][a][b][c][d][g] || r[4][a][b][c][e][f] || r[5][a][b][c][e][g]
        || r[6][a][b][c][f][g] || r[7][a][b][d][e][f] || r[8][a][b][d][e][g] || r[9][a][b][d][f][g] || r[10][a][b][e][f][g]
        || r[11][a][c][d][e][f] || r[12][a][c][d][e][g] || r[13][a][c][d][f][g] || r[14][a][c][e][f][g] || r[15][a][d][e][f][g]
        || r[16][b][c][d][e][f] || r[17][b][c][d][e][g] || r[18][b][c][d][f][g] || r[19][b][c][e][f][g] || r[20][b][d][e][f][g]
        || r[21][c][d][e][f][g])){
            if(! -- k){
                int res[8] = {a, b, c, d, e, f, g};
                for(int i = 0; i < 7; ++ i)
                    cout << char(res[i] < 10 ? res[i] + '0' : 'a' + res[i] - 10);
                return 0;
            }
            r[1][a][b][c][d][e] = r[2][a][b][c][d][f] = r[3][a][b][c][d][g] = r[4][a][b][c][e][f] = r[5][a][b][c][e][g]
            = r[6][a][b][c][f][g] = r[7][a][b][d][e][f] = r[8][a][b][d][e][g] = r[9][a][b][d][f][g] = r[10][a][b][e][f][g]
            = r[11][a][c][d][e][f] = r[12][a][c][d][e][g] = r[13][a][c][d][f][g] = r[14][a][c][e][f][g] = r[15][a][d][e][f][g]
            = r[16][b][c][d][e][f] = r[17][b][c][d][e][g] = r[18][b][c][d][f][g] = r[19][b][c][e][f][g] = r[20][b][d][e][f][g]
            = r[21][c][d][e][f][g] = 1;
        }
    }

    return 0;
}