题解：UVA11205 The broken pedometer

· · 题解

事先声明：思路参考

分析概括题意

给出 n 行长度为 p 的序列，求出最少 k 位可以为 1，其他位得为 1 的序列能表示出的数字没有误导性（即不重复）。

解法:状压搜索

Step1：状态保存

状压的常规操作就是转二进制，题目里给我们的是序列，用 a_i 表示存储到序列中第 i 个值的状态， v_i 为序列中第 i 个值，显而易见，a_i=a_{i-1}\times2+v_i。

代码实现如下：

for(int i=1;i<=n;i++)
{
    a[i]=0;
    for(int j=1;j<=p;j++)
    read(k),a[i]=a[i]*2+k;
}

Step2：搜索

熟悉状压的同学应该都知道状压搜索的上界是状态位全为1的情况，在这道题中上界就是 2^p-1 ，下界就是 0。

我们只需要枚举 0 到 2^p-1 之间的所有状态，将枚举到的状态和 a 数组存储的相与得到新状态，再进行判重即可。

对于该操作可行的证明：

对于三个状态的相同状态位 m,n,q

可以得出结论按位与得出的新状态就是我们要的新状态。

如果新状态通过了判重，就记录新状态二进制下为 1 的个数，最少的 1 的个数就是答案。

Step3：剪枝

搜索是离不开剪枝的。

在第二步中，我们每次枚举状态都要记录该状态二进制下一的个数，再判断是否小于等于使用的上界 2^p-1 再进入循环。

但这里可以有一个非常大的优化，将每次记录到的通过判重的新状态二进制中 1 的个数作为新的上界！

AC 代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
namespace IO {
    template<class I>
    inline void read(I &x) {
        x = 0;
        I f = 1;
        char c = getchar();
        while(c < '0' || c > '9') {
            if(c == '-') f = -1;
            c = getchar();
        }
        while(c >= '0' && c <= '9') {
            x = x * 10 + c - '0';
            c = getchar();
        }
        x *= f;
    }
    template <typename T,typename ...Args>
    inline void read(T &tmp,Args &...tmps) {
        read(tmp);
        read(tmps...);
    }
    template<class T>
    inline void write(T x) {
        if(x<0) {
            putchar('-');
            x=-x;
        }
        if(x>=10) {
            write(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace IO;
#define int long long
#define lowbit(x) (x&(-x)) 
int a[200],b[40000];
signed main() {
    int T;
    read(T);
    while(T--)
    {
        int p,n,k;
        read(p,n);
        for(int i=1;i<=n;i++)
        {
            a[i]=0;
            for(int j=1;j<=p;j++)
            {
                read(k);
                a[i]=a[i]*2+k;//转换为二进制 等会用状压 
            }
        }
        int ztmx=(1<<p)-1,mx=p+1;//！！！ztmx是状态上限 mx是当前使用LED的数量最大值(最开始自然是p) 
        for(int i=0;i<=ztmx;i++)
        {
            int bt=0,j=i;//记录这一状态下开了多少LED
            while(j) {
                bt+=j&1;//这个学过位运算的应该都懂 就是取j的二进制里1的个数 不介意的话你或许可以用lowbit（ 
                j>>=1; 
            }
            if(bt>=mx) continue;//超过了要用的量 直接continue
            memset(b,0,sizeof(b));
            for(j=1;j<=n;j++) 
            {
                int k=a[j]&i;//k的二进制就是a[j]在当前状态下的表示 
                if(!b[k]) b[k]=1;//标记状态 出现过了就为1 
                else break;//重复出现 没法作为解决方案就break 
            }
            if(j==n+1) mx=bt;//剪枝 每次都只有bt<mx的数据进来 再mx=bt 不断缩小上界 
        }
        cout<<mx<<endl; 
    }
    return 0;
}