标签 位运算 下的文章

url: https://www.luogu.com.cn/problem/P4310

tag:
动态规划，位运算

思路：
如果用求最长上升子序列的方式来求会超时。这时我们可以观察到因为要满足bi & bi - 1 != 0，所以对于以ai 结尾的数来说，只要是某一个序列末尾的数的某一位和ai 都是1就可以想接。所以可以用一个数列bit来存某一位为1时的最长序列。之后更新时只需要枚举ai 的每一位为1的情况，更新f就行。最后求出最大值后，用这个最大值再来更新当前情况下的bit数组值。对于枚举每一位可以通过lowbit函数求出最低位的1（2k 的形式），之后再通过map log_2来映射每一个2k 的 k值即为位数。

代码：

#include <iostream>
#include <map>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int n;
int ans;
int f[N];
int bit[N];
map<int, int> log_2;
int lowbit(int x)
{
    return x & -x;
}
int main()
{
    cin >> n;
    for (int i = 0, j = 1; i <= 31; i ++, j <<= 1)
    {
        log_2[j] = i;
    }
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++)
    {
        for (int j = a[i], low = lowbit(j); j; j -= low, low = lowbit(j))
        {
            f[i] = max(f[i], bit[log_2[low]] + 1);
        }
        for (int j = a[i], low = lowbit(j); j; j -= low, low = lowbit(j))
        {
            bit[log_2[low]] = max(bit[log_2[low]], f[i]);
        }
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}

url: https://www.luogu.com.cn/problem/P1074

tag:
NOIP2009 提高组，搜索，剪枝，位运算，NOIP提高组，2009

思路：

  1. 核心变量解析
  • a[10][10]：存储数独棋盘，ai表示第i行第j格的数字（0表示空格）
  • r[10]：行约束，r[i]的二进制第k位表示第i行能否填数字k+1（1表示可用）
  • c[10]：列约束，c[j]的二进制第k位表示第j列能否填数字k+1
  • e[5][5]：九宫格约束，ex的二进制第k位表示第x行第y列九宫格能否填k+1
  • p[1<<11]：位掩码到数字的映射，p[1<<k]=k+1（快速获取候选数字）
  • o[1<<10]：预计算二进制中1的个数，o[mask]表示mask的候选数字个数
  • ans：存储最终的最大得分
  1. 关键函数解析
  • gs()：根据位置计算得分，边缘得分低，中心得分高（计算公式：值*(6+距边缘距离)）
  • init()：初始化约束为全可用状态，预处理o[]和p[]的映射关系
  • dfs()：采用最小候选数优先的回溯算法，通过位运算快速枚举候选值
  1. 算法流程
  • 预处理所有约束条件
  • 优先选择候选数最少的格子进行填充（剪枝优化）
  • 用位运算快速遍历所有候选数字
  • 递归搜索时动态更新约束条件
  • 达到填满状态时更新最大得分
  1. 位运算优化点
  • 用异或操作快速增删约束条件（r[i]^=mask）
  • 用lowbit技巧遍历候选数字（t&-t获取最低位的1）
  • 预计算o[]避免重复计算候选数个数

参考： https://www.luogu.com.cn/article/gerq24ll
ps: 好强大的位运算思路，爱了爱了。

代码：

#include <iostream>
using namespace std;
int a[10][10], r[10], c[10], e[5][5], p[1 << 11], ans = -1;
int o[1 << 10];
int gs(int i, int j)
{
    return a[i][j] * (6 + min(min(i, 8 - i), min(j, 8 - j)));
}
void init()
{
    for (int i = 0; i < 9; i ++) r[i] = c[i] = e[i / 3][i % 3] = (1 << 9) - 1;
    for (int i = 0; i < (1 << 9); i ++)
    {
        int t = i;
        while (t)
        {
            t &= t -1;
            o[i] ++;
        }
    }
    for (int i = 0; i < 9; i ++) p[1 << i] = i + 1;
}
void dfs(int cnt, int sum)
{
    if (cnt == 0)
    {
        ans = max(ans, sum);
    }
    int mi = 10, x, y;
    for (int i = 0;  i< 9; i++)
        for (int j = 0; j < 9; j ++)
        {
            if (!a[i][j])
            {
                int t = r[i] & c[j] & e[i / 3][j / 3];
                if (o[t] < mi)
                {
                    mi = o[t], x = i, y = j;
                }
            }
        }
    int t = r[x] & c[y] & e[x / 3][y / 3];
    while (t)
    {
        int l = (t & -t);
        t -= l;
        a[x][y] = p[l];
        r[x] -= l, c[y] -= l, e[x / 3][y / 3] -= l;
        dfs(cnt -1, sum + gs(x, y));
        a[x][y] = 0;
        r[x] += l, c[y] += l, e[x / 3][y / 3] += l;
    }
}
int main()
{
    init();
    int cnt = 0, sum = 0;
    for (int i = 0; i < 9;  i++)
        for (int j = 0; j < 9; j ++)
        {
            cin >> a[i][j];
            if (a[i][j])
            {
                r[i] -= 1 << a[i][j] - 1;
                c[j] -= 1 << a[i][j] - 1;
                e[i / 3][j / 3] -= 1 << a[i][j] -1;
                sum += gs(i, j);
            }else cnt ++;
        }
    dfs(cnt, sum);
    cout << ans << endl;
    return 0;
}