当前位置：首页 > news >正文

Codeforces Round #637 (Div. 2) D. Nastya and Scoreboard（位运算dfs/记忆化搜索）

news 来源：原创 2024/5/20 21:16:48

传送门

在这里插入图片描述
1.题意：给出如图所示的 $7$ 位二进制代表的火柴棒， $1$ 代表亮，而且对于组成的 $0 - 9$ 数字的二进制已经给出：“1110111”, “0010010”, “1011101”, “1011011”, “0111010”, “1101011”, “1101111”, “1010010”, “1111111”, “1111011”。现在给出 $7$ 位可能残缺的火柴棒，问点亮 $k$ 位后 $n$ 个棒从前往后能否构成最大的十进制数（允许前导零），如果能就输出能构成的最大值；否则输出 $- 1$

2.比赛时朋友跟我说这是 $d p$ ，我有一点点搜索的想法的，但是我以为每个棒那样去枚举，最多要枚举 $10^n$ 次？那太逆天了吧！但是补题的时候发现了可以搜索写的，原来，如果能构成的话实际上搜索的次数可以降到最少，最坏的情况下 $O(k*n^2)$ 再剪枝也能过的。位运算的 $d f s$ 之前只写过一次，还是不太熟练，以后一定多多练习！

3.正解：

主体：首先将 $0 - 9$ 的二进制表示转化为十进制数，接下来也要把输入的 $n$ 个数都转化为十进制数。那么我们每次尝试将第 $i$ 为数转换为 $9 - 0$ ，如果能转换得到当前的消耗的次数——取二者异或的二进制数的’ $1$ '的个数，因为我们每次优先搜索的是较大的数字，因此能得到解时得到的第一个解一定是最大的
剪枝：设置 $v i s [i] [j]$ 数组表示当前的第 $i$ 个棒时已经累积点亮了 $j$ 次，可能从多个方向达到，因此记录一下重复的直接 $r e t u r n$
亮点：① $_\_builtin\_popcount()$ 函数，统计十进制数的对应二进制中 $1$ 的个数；②在 $d f s$ 函数中直接输出并 $e x i t ()$ 结束程序。第一次见到上述操作，学到了很多！

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e3+10;
int tab[]={119,18,93,91,58,107,111,82,127,123};
int n,k,a[maxn],ans[maxn];
bool vis[maxn][maxn];
string s;

void dfs(int i,int x) {   //第i个数前已经消耗了x次
    if(x>k || vis[i][x]) return;  //剪枝
    vis[i][x]=1;
    if(i==n){
        if(x==k) {
            for(int j=0;j<n;j++) printf("%d",ans[j]);
            exit(0);
        }
        return;
    }
    for(int j=9;j>=0;j--){
        ans[i]=j;
        if((tab[j] & a[i])==a[i]) dfs(i+1,x+__builtin_popcount(tab[j]^a[i])); //只有相与之后还是a[i]才能转换
    }
}

int main(){
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>s;
        for(int j=0;j<s.size();j++)  //转化为十进制
            a[i]=(a[i]<<1)+(s[j]-'0');
    }
    dfs(0,0);
    puts("-1");
    return 0;
}