2024下学期《C语言》- 位运算

本文主要是介绍2024下学期《C语言》- 位运算，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题单

点这里去刷题（仅校内用户）

---

• Problem A 1380 101
• Problem B 1325 K-Good Number
• Problem C 1243 Bob’s Password
• Problem D 1436 礼物
• Problem E 1270 Unique Digit Number
• Problem F 1307 Beautiful Number
• Problem G 1426 Dice

参考资料

• 位运算知识
• 状态压缩动态规划
• 从集合论到位运算，常见位运算技巧分类总结！

A 1380 101

枚举，位运算

---

• 按照题目描述模拟将所有 $101$ 改为 $111$ 即可
• 对于位数为 $m$ 的无符号整数，只需从第一位枚举至第 $(m-2)$ 位
• 获取第 $i$ 位的值： (n >> i) & 1
• 将第 $i$ 位（$0$）改为 $1$：n ^= (1 << i)

核心代码如下

static void solve () {// Java 不提供无符号类型，因此输入数据时要采用下面的方式，相应的按位左移使用 <<<, 右移使用  >>>// n = Long.parseUnsignedLong(in.nextLine());res = 0;for (int i = 63; i >= 2; --i) {if (((n >>> i & 1) == 1) && (((n >>> (i - 1)) & 1) == 0) && (((n >>> (i - 2)) & 1) == 1)) {// 1 后不加 L 会被默认当作 int 类型（32 位）n ^= 1L << (i - 2);++res;}}
}

B 1325 K-Good Number

枚举，位运算

---

• 枚举所有位，统计 $0$ 和 $1$ 的个数即可
• 获取第 $i$ 位的值： (n >> i) & 1

核心代码

static void solve () {zero = one = 0;for (int i = Integer.toBinaryString(n).length() - 1; i >= 0; --i) {if (((n >> i) & 1) == 0) ++zero;else ++one;}
}

C 1243 Bob’s Password

枚举，位运算优化

---

• 建立二维数组 jump, jump[i][j] 表示从点 $i$ 到点 $j$ 必须经过的点
  • 枚举密码序列 passwd，若点 jump[passwd[i]][passwd[i + 1]] 未被访问过，则说明密码无效
  • 判断某个点有没有被访问可以采用位运算，因为只有 $1$ ~ $9$ 共 $9$ 个点，所以考虑一个 9 位 $01$ 串 $a$，若 $a_i$ 为 $0$ 则表示点 $i$ 未被访问过，否则反之。最后令 $01$ 串等价于一个十进制数的二进制表示即可

核心代码

static boolean solve () {int visited = 1;int prev = 0;for (char ch : passwd.toCharArray()) {int cur = ch - '0';if (prev != 0 && (visited & (1 << jump[prev][cur])) == 0) return false;visited |= (1 << cur);prev = cur;}return true;
}

D 1436 礼物

动态规划，记忆化搜索

---

• 这是一个 $01$ 背包板子题，解法很多，我采用的是最简单直观的 记忆化搜索，即在 dfs 搜索的基础上使用一个缓存数组来剪枝，避免重复搜索
• 感觉本题和位运算关系不大，和位运算有所关联的是状态压缩动态规划

核心代码

static int solve (int i, int j) {if (i == 0) return 0;if (cache[i][j] != -1) return cache[i][j];if (P[i] > j) return solve_Jun0809(i - 1, j) - D[i];else {cache[i][j] = Math.max(solve_Jun0809(i - 1, j) - D[i], solve_Jun0809(i - 1, j - P[i]) + I[i]);return cache[i][j];}
}

E 1270 Unique Digit Number

组合数学，位运算优化

---

• 可能大部分人看到这道题第一时间想到的解法是 dfs 暴力搜索或者直接暴力枚举，其实我也是，但是用 Java 写出来结果超时了
• 于是我想了一个基于组合数学的解法，比直接暴搜要好得多
  • 首先我们可以很容易的求出 $m$ 位的 “数位不同的数” 有多少个， 可以从 $0$ ~ $9$ 中取数，若目标数不止一位则最高位不能为 $0$（只有一位的情况后面特判），因此有 $9$ 种取法，剩下的 $m-1$ 位从剩下的 $9$ 个数里取，有 $A_9^{m-1}$ 种取法，因此$m$ 位的 “数位不同的数” 有 $9\ast A_9^{m-1}$ 个
  • 将第一步的结果保存在 cnt 数组里，用输入的 $n$ 依次减去 cnt[1], cnt[2], … 直至遇到第一个比当前的 $n$ 大的 cnt[i]，由此可以知道我们要求的数有 $i$ 位。此时的 $n$ 表示目标数在 $i$ 位的 “数位不同的数” 中排第 $n$ 位
  • 接下来直接枚举每一位，不过这里的枚举是高效的，因为我们同样可以利用组合数学的思路。逐一枚举当前位所有可能的取值 $0$ ~ $9$，注意若目标数不止一位则最高位不能取 $0$ ，假若我们已经确定当前位（设为第 $j$ 位）为 $k$，那么所有以 $k$ 开头的数的个数为 $cn{t}_k$ = $k\ast A_{i-j}^{j-1}$（这里的 $cnt$ 不是前面的 cnt 数组），我们可以用 $n$ 依次减去 $cn{t}_1$，$cn{t}_2$… 直至遇到第一个比当前的 $n$ 大的 $cn{t}_k$，就可以确定当前位为 $k$ 啦，这里和确定目标数的位数时很像。已经使用过的数可以直接排除，因此可以像 C题 那样利用位运算来标记，终于出现位运算啦！
• 这种做法需要求排列数，可以利用递推公式 $A_n^m=m\ast A_{n-1}^{m-1}+A_{n-1}^m$ 产生

核心代码

/* 求组合数 */
static void get_permutation () {for (int i = 0; i < MAX_SIZE; ++i) {A[i][0] = 1;A[i][1] = i;}for (int i = 1; i < MAX_SIZE; ++i) {for (int j = 2; j <= i; ++j) {A[i][j] = j * A[i - 1][j - 1] + A[i - 1][j];}}
}

/* 确定结果 */
static String solve (int n) {String res = "";int flag = 0;for (int i = 1; i <= MAX_SIZE; ++i) {if (n > cnt[i]) n -= cnt[i];else {for (int j = i, rest = MAX_SIZE; j >= 1; --j) {for (int k = 0, t = 0; k < MAX_SIZE; ++k, ++t) {if (((flag >> k) & 1) == 1) --t;// 处理最高位和目标数不止一位（此时最高位不能取 0）的情况else if (i > 1 && j == i && n <= k * A[rest - 1][j - 1]) {n -= (k - 1) * A[rest-- - 1][j - 1];res += Integer.toString(k);flag |= (1 << k);break;}// 处理其他位和目标数仅有一位（此时最高位可以取 0）的情况else if ((i == 1 || j != i) && n <= (t + 1) * A[rest - 1][j - 1]) {n -= t * A[rest-- - 1][j - 1];res += Integer.toString(k);flag |= (1 << k);break;}}}break;}}return res;
}

F 1307 Beautiful Number

枚举，位运算

---

• 区间的最大边界为 $10^{18}$，易知它有 $60$ 位，最高的四位为 $1101$，因此 $60$ 位的符合要求的美丽数仅有一个
• 易知 $i$ $(i<60)$ 位美丽数共有 $(i-1)$ 个
• 因此可以先确定 $a$ 和 $b$ 的位数 $la$ 和 $lb$，对 $la$ 和 $lb$ 之前的所有美丽数个数可以很方便的第二步的公式求得，然后再分别讨论 $la$ 位和 $lb$ 位的情况

核心代码

static int solve (long a, long b) {int res = 0;int l_a = Long.toBinaryString(a).length();int l_b = Long.toBinaryString(b).length();for (int i = l_a + 1; i < l_b; ++i) res += (i - 1);if (l_a != l_b) {res += (l_a == MAX_SIZE) ? 1 : l_a - 1;for (int i = l_a - 2; i >= 0; --i) {if (a > (((1L << l_a) - 1) ^ (1L << i))) --res;else break;}}for (int i = l_b - 2; i >= 0; --i) {if (b < (((1L << l_b) - 1) ^ (1L << i))) break;else if (a <= (((1L << l_b) - 1) ^ (1L << i))) ++res;}return res;
}

G 1426 Dice

枚举，位运算优化

---

• 枚举的思路很简单，不过要注意去下重，因为数据范围很小，所以可以直接用数组代替哈希表去重
• 标记骰子的某面有没有用过时可以用位运算优化
• 我一直在想怎么用组合数学来解这个题，可是要讨论的情况太多了，一直没想出来，数学好的大佬带带 ε(┬┬﹏┬┬)3

核心代码

/* 用数组保存所有可能的骰子顺序 */
static int[][] p = new int[][]{ {0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0} };static void solve_Jun0903 () {for (int t = 0; t < p.length; ++t) {for (int i = 0; i <= size[p[t][0]]; ++i) {if (((dice[p[t][0]] >> i) & 1) != 0) {flag[i] = 1;for (int j = 0; j <= size[p[t][1]]; ++j) {if (((dice[p[t][1]] >> j) & 1) != 0) {flag[i * 10 + j] = 1;for (int k = 0; k <= size[p[t][2]]; ++k) {if (((dice[p[t][2]] >> k) & 1) != 0) flag[i * 100 + j * 10 + k] = 1;}}}}}}
}

这篇关于2024下学期《C语言》- 位运算的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---