今天在刷递归题的时候看到看到两道比较有意思的题

P1036 选数 和 P1010 幂次方

鉴于我搜索回溯都还没学，数据处理也比较菜，就想到尝试用位运算的方法来解决。

不说废话了来认识一下位运算的一些性质吧。

为什么使用位运算

  • 数字在计算机中以二进制形式储存，所以使用位运算符计算比使

    用算数运算符速度更快

  • 对于一类特定的问题，如子集问题，改写数字等，使用二进制&

    位运算是十分直观的方法。

位运算的基础运算符

先来看一段示例程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <cstdio>

int A = 85, B = 51;
int p, q, r, s, u, v;

int main()
{
    p = A & B;
    q = A | B;
    r = A ^ B;
    s = ~A;
    u = A << 2;
    v = A >> 3;

    printf("%d %d %d %d %d %d", p, q, r, s, u, v);

    return 0;
}

运行得到

1
17 119 102 -86 340 10

分析

首先将A B改写为二进制数

6 5 4 3 2 1 0
A 1 0 1 0 1 0 1
B 0 1 1 0 0 1 1

  • &：按位与运算符

    与 逻辑运算符&&类似，当参与运算的值均为1时才返回1

A 1 0 1 0 1 0 1
B 0 1 1 0 0 1 1
A&B 0 0 1 0 0 0 1

  • |: 按位或运算符

    与逻辑运算符 || 相似，当参与运算的值至少有一个为1就返回1

A 1 0 1 0 1 0 1
B 0 1 1 0 0 1 1
AorB 1 1 1 0 1 1 1

  • ^ : 按位异或运算符

    只有参与运算的值不完全相同才返回1，若均相同（不管同为1还

    是0）则输出0.

A 1 0 1 0 1 0 1
B 0 1 1 0 0 1 1
A^B 1 1 0 0 1 1 0

  • ~ ： 非运算符

    输出将输入数据每一位取反

A 1 0 1 0 1 0 1
~A 0 1 0 1 0 1 0

  • << : 左移运算符

    将输入的数据向左（向高位）移位，后面用0补齐

8 7 6 5 4 3 2 1 0
A 0 0 1 0 1 0 1 0 1
A<<2 1 0 1 0 1 0 1 0 0

将两数转换为十进制

A = 85
A<<2 = 340

可以发现将A左移2位相当于乘以4(2的二次方）

所以得出：A<<n=A*2^n

  • : 右移运算符

    将输入的数据向右（向低位）移位，前面用0补齐

6 5 4 3 2 1 0
A 1 0 1 0 1 0 1
A>>2 0 0 1 0 1 0 1

A = 85

A>>2 = 21

可以发现，与左移相反，右移n位可以将数除以2的n次方

喜闻乐见的例题讲解

  1. P1036 选数

这道题其实就是让我们从n个元素中选k个相加，判断和是否为质数

让我们先来看一个简单的例子

假设我们有一个5个元素的数组(下标从1开始）

i 1 2 3 4 5
a[ i ] 1 2 3 4 5

对于全集 U={ 1，2 ，3 ，4 ，5 } ,每个子集都包含其中任意个元素。

有没有什么办法可以给这些不同的子集编号呢？

我们可以以元素的存在情况作为依据：

令每个子集的编号为一个5位二进制数，如果其中一位对应的数在子

集中存在，那么那一位为1，否则为0。

以其中一个子集 S = { 1 , 3 , 5 } 为例，得到以下表格

a[i] 5 4 3 2 1
U 1 1 1 1 1
S 1 0 1 0 1
  • 注意：对于二进制数来说，数位由高到低递减。

则U的编号为11111，S的编号为10101，

转换成十进制后，U=31，S=21

我们惊喜的发现，U的大小就等于2^n-1(其中n为元素个数)

通过这种方法，每一个子集都有一个唯一的二进制编号与其一一对应。

接下来该做什么呢？

对于这道题来说，要求其中k个数的和，

就是求含k个元素的子集每个元素的和。

而我们编号之后会发现，如果一个子集有k个元素，
那么它的编号中也必有k个‘1’

（如S = { 1 , 3 , 5 }的编号10101中有3个1）

到此为止，这道题的思路就很清晰了，

先计算U的大小，从1到U枚举S，判断S中’1‘的个数

如果等于k，就把S中的元素相加，判断是否为素数，记录答案即可。

AC程序如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <cmath>        //*判断质数时需使用sqrt()
#include <algorithm>    //*使用__builtin_popcount()需包含该头文件

int n, k;
int ans;
int a[21];

bool is_prime(int n){   //*判断是否为质数
	if(n<2) return false;
	if(n==2||n==3) return true;
	for(int i=2;i<=sqrt(n);i++)
		if(n%i==0)
            return false;
    return true;
}

int cnt_1(int n) {      //*计算二进制数字中1的个数
    int cnt=0;          //*也可以用STL中内置的__builtin_popcount()函数代替
    while(n){
        if(n&1)
            cnt++;
        n >>= 1;
    }
    return cnt;
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n;i++)
        scanf("%d", &a[i]);
    int U = (1 << n) - 1;               //*U为全集，易知 U=2^n-1
    for (int S = 1; S <= U;S++){        //*枚举每一个子集
        if(cnt_1(S)==k){                //*判断子集中是否有k个元素
            int sum = 0;
            for (int i = 1; i <= n;i++)
                if(S & (1 << (i - 1)))      //*判断第i个元素是否在S中
                    sum += a[i];
            if(is_prime(sum))
                ans++;
        }
    }
    printf("%d", ans);
    return 0;
}
  1. P1010 幂次方

这道题其实就是让我们把一个十进制数改写成二的整数次幂之和

所以自然想到采用二进制的做法

我们以题目中的例子进行说明，先将137转换成二进制数观察

7 6 5 4 3 2 1 0
137 1 0 0 0 1 0 0 1

很明显我们可以发现：

需要改写的那一位已经以‘1’的形式存在了

只需要记录数中每一个‘1’在第几位，再对位数递归分解

直到所有的‘1’都在第0~2位上结束。

像这样：

1
2
3
4
5
6
7
8
9
//todo 位运算部分
    int d[100];                 //*储存n的二进制数各位为1的情况
    int k = n, u=0, i = 0;      //*k暂存n，u作为下标，i记录为第几位
    while(k){
        if(k&1)
            d[++u] = i;         //*d[u]=i表示第u个1在第i位
        k >>= 1;                //*k右移1位
        i++;                    //*位数+1
    }

继续来看，我们注意到137的二进制第7位为1，只需要再将7改写为二进制数如下表：

2 1 0
7 1 1 1

此时所有的‘1’都已经在0~2位上，达到了递归的边界，判断输出即可。

附上AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <cstdio>
#include <iostream>
using namespace std;
int n;

void rec(int n) {

    //todo 位运算部分
    int d[100];                 //*储存n的二进制数各位为1的情况
    int k = n, u=0, i = 0;      //*k暂存n，u作为下标，i记录为第几位
    while(k){
        if(k&1)
            d[++u] = i;         //*d[u]=i表示第u个1在第i位
        k >>= 1;                //*k右移1位
        i++;                    //*位数+1
    }

    //todo 处理部分
    while(u){                   //*从低到高储存后，从高到低处理

        if(d[u]>=3){                        //*由于题目要求只能用0，2表示，所以如果这个1在第3或更高位要递归继续分解
            printf("2(");                   //*后面还要递归，先把前面的括号输出

            rec(d[u--]);

            if(u)                           //*如果u不为零，说明后面还有数，要输出‘+’
                printf(")+");
            else                            //*如果u为零，说明已经是最后一个，只输出‘）’
                printf(")");
        }

        else{                   //*如果1在<=2位上

            if(d[u]==1&&u!=1)               //*如果‘1’在第一位上，且不是整个数中的第一个‘1’
                printf("2+");               //*后面还有其它‘1’，要输出‘+’

            else if(d[u]==1)                //*如果是第一个‘1’
                printf("2");                //*后面没有其它‘1’了，不输出‘+’

            if((d[u]==0||d[u]==2)&&u!=1)    //*如果1在第二位或第零位上，且不是整个数中的第一个‘1’
                printf("2(%d)+", d[u]);     //*输出位权和‘+’

            else if(d[u]==0||d[u]==2)       //*如果是第一个‘1’
                printf("2(%d)", d[u]);      //*只输出位权

            u--;
        }
    }
}
int main()
{
    scanf("%d", &n);
    rec(n);
    return 0;
}