题解 P4222 【[CQOI2012]编号】

meyi · 2020-10-19 23:39:25 · 题解

解题算法：记忆化搜索

优点：码量较小。缺点：跑的很慢，最慢的一个点844ms，差点T了。

思路：与另一篇使用DP的题解类似，7位数中选出任意5位数判断是否被占用过，因为如果5位数一样，则最多只有两位数不同，这里使用二进制预处理组合数以避免DP冗长的转移。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ri register int
inline int popcount(int k){
    int s=0;
    while(k)s+=k&1,k>>=1;
    return s;
}   //计算二进制下k中1的数量
int a[7],c[21][5],f[21][16][16][16][16][16],l,n;
inline void init(int k){
    for(int i=0,j=0;i<7;++i,k>>=1)
        if(!(k&1))
            c[l][j++]=i;
}   //预处理组合数
void dfs(int k){
    if(k==7){
        for(ri i=0;i<21;++i)if(f[i][a[c[i][0]]][a[c[i][1]]][a[c[i][2]]][a[c[i][3]]][a[c[i][4]]])return;
        for(ri i=0;i<21;++i)f[i][a[c[i][0]]][a[c[i][1]]][a[c[i][2]]][a[c[i][3]]][a[c[i][4]]]=true;
        if(!--n){
            for(ri i=0;i<7;++i)putchar(a[i]<10?a[i]|48:a[i]-10+'a');
            exit(0);
        }
    }
    else for(ri i=0;i<16;++i)a[k]=i,dfs(k+1);
}   //记忆化搜索
int main(){
    scanf("%d",&n);
    for(ri i=0;i<128;++i)
        if(popcount(i)==2)
            init(i),++l;
    dfs(0);
    return 0;
}