网站升级通知广西建设工程信息网官网

网站升级通知,广西建设工程信息网官网,安化网站建设,湖州 网站建设文章目录位运算简介与、或、异或左移和右移关于优先级常见应用内置函数状压DP简介核心练习题位运算 简介 位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据#xff0c;位运算是相当快的。 比赛题目中出现的位运算基本有 5 种#xff0c;分…文章目录位运算简介与、或、异或左移和右移关于优先级常见应用内置函数状压DP简介核心练习题位运算简介位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据位运算是相当快的。比赛题目中出现的位运算基本有 5 种分别为按位与、按位或、按位异或、左移和右移。与、或、异或这三者都是两数间的运算。它们都是将两个整数作为二进制数对二进制表示中的每一位逐一运算。运算代码运算符数学符号解释与、and只有当两个对应位都为 1 时结果才为 1否则为 0。或|、or异或^⊕ \oplus⊕, xor当两个对应位不同时结果为 1相同时结果为 0 (也称为不进位加法)。举例10 ( 1010 ) 2 12 ( 1100 ) 2 10 12 ( 1000 ) 2 8 10 ∣ 12 ( 1110 ) 2 14 10 ⊕ 12 ( 0110 ) 2 6 \begin{aligned} 10 (1010)_2 \\ 12 (1100)_2 \\ 10 \ \ \ 12 (1000)_2 8 \\ 10 \ | \ 12 (1110)_2 14 \\ 10 \oplus 12 (0110)_2 6 \\ \end{aligned}1012101210∣1210⊕12​(1010)2​(1100)2​(1000)2​8(1110)2​14(0110)2​6​对应的 C 代码验证#includeiostreamusingnamespacestd;intmain(){inta10;// 二进制 1010intb12;// 二进制 1100cout10 12 (ab)endl;// 输出 8cout10 | 12 (a|b)endl;// 输出 14cout10 ^ 12 (a^b)endl;// 输出 6return0;}左移和右移num i表示将 的二进制表示向左移动 位所得的值。num i表示将 的二进制表示向右移动 位所得的值。举例9 ( 00001001 ) 2 9 ≪ 2 ( 00100100 ) 2 36 9 ≫ 2 ( 00000010 ) 2 2 \begin{aligned} 9 (00001001)_2 \\ 9 \ll 2 (00100100)_2 36 \\ 9 \gg 2 (00000010)_2 2 \end{aligned}99≪29≫2​(00001001)2​(00100100)2​36(00000010)2​2​移位运算中如果出现如下情况则其行为未定义右操作数即移位数为负值右操作数大于等于左操作数的位数例如对于int类型的变量aa-1和a32都是未定义的。对于左移操作需要确保移位后的结果能被原数的类型容纳否则行为也是未定义的。对一个负数执行左移操作也未定义。对于右移操作右侧多余的位将会被舍弃而左侧较为复杂对于无符号数会在左侧补 0而对于有符号数则会用最高位的数其实就是符号位非负数为 0负数为 1补齐。关于优先级位运算的优先级低于算术运算符除了取反而按位与、按位或及异或低于比较运算符所以使用时需多加注意在必要时添加括号。常见应用位运算一般有三种作用高效地进行某些运算代替其它低效的方式。表示集合常用于状压DP。题目本来就要求进行位运算。需要注意的是用位运算代替其它运算方式即第一种应用在很多时候并不能带来太大的优化反而会使代码变得复杂使用时需要斟酌。但像「乘 2 的非负整数次幂」和「除以 2 的非负整数次幂」就最好使用位运算因为此时使用位运算可以优化复杂度。内置函数GCC 中还有一些用于位运算的内建函数int __builtin_ffs(int x)返回 的二进制末尾最后一个 1 的位置位置的编号从 1 开始最低位编号为 1 。当 为 0 时返回 0 。int __builtin_clz(unsigned int x)返回 的二进制的前导 0 的个数。当 为 0 时结果未定义。int __builtin_ctz(unsigned int x)返回 的二进制末尾连续 0 的个数。当 为 0 时结果未定义。int __builtin_clrsb(int x)当 的符号位为 0 时返回 的二进制的前导 0 的个数减一否则返回 的二进制的前导 1 的个数减一。int __builtin_popcount(unsigned int x)返回 的二进制中 1 的个数。int __builtin_parity(unsigned int x)判断 的二进制中 1 的个数的奇偶性。由于这些函数是内建函数经过了编译器的高度优化运行速度十分快有些甚至只需要一条指令。状压DP简介状压 DP 是动态规划的一种通过将状态集合转化为整数记录在 DP 状态中来实现状态转移的目的。为了达到更低的时间复杂度通常需要寻找更低状态数的状态。大部分题目中会利用二元状态用 位二进制数表示 个独立二元状态的情况。核心用一个N位的二进制数每一位表示一个物品0/1表示不同的状态。因此可以用0 → 2^(N − 1)(N二 进 制 对 应 的 十 进 制 数 中的所有数来枚举全部的状态。练习题[蓝桥杯 2019 省 A] 糖果不难看出此题不是爆搜就是动态规划而爆搜需要考虑每一种搭配情况复杂度O ( 2 n ) O(2^n)O(2n)肯定超时。考虑动态规划可以发现数据范围很小并且是搭配类型的想到状压。首先设计状态一共可以设计出两种d p [ i ] dp[i]dp[i]表示取状态为i ii的几包糖最多可以凑出的口味数量。这种状态比较麻烦且结果不是很容易得出。d p [ i ] dp[i]dp[i]表示凑出状态为i ii的口味最少需要几包糖。很显然第二种很合理那么我们来推一下方程。思考发现如果直接枚举i ii再找合理的上一种状态不是很好找。但我们可以通过已经求出来的一种状态配合另一种状态来更新新的状态。设v [ i ] v[i]v[i]表示第i ii包糖的口味状态则有d p [ i ∣ v [ j ] ] min ⁡ ( d p [ i ∣ v [ j ] ] , d p [ i ] 1 ) dp[i|v[j]] \min(dp[i|v[j]], dp[i] 1)dp[i∣v[j]]min(dp[i∣v[j]],dp[i]1)d p [ i ∣ v [ i ] ] dp[i|v[i]]dp[i∣v[i]]为更新的新状态i ii为已知的状态 1再找一包糖j jj更新出d p [ i ∣ v [ i ] ] dp[i|v[i]]dp[i∣v[i]]。考虑正确性因为i ii状态从 0 开始枚举因此枚举到i ∣ v [ i ] i|v[i]i∣v[i]时肯定已经求出d p [ i ] dp[i]dp[i]的值并且是最优的。还有一个问题是否可能重复选了某包糖如果是那么肯定这个值不是最优的因为你买两包同样的糖和只买一包口味不会有新的。#includebits/stdc.husingnamespacestd;constintN110,M22;intn,m,k,v[N],dp[1M];voidsolve(){cinnmk;for(inti0;i(1m);i){dp[i]1e9;}for(inti1;in;i){intstate0;for(intj1;jk;j){intx;cinx;x--;state|(1x);}v[i]state;dp[state]1;}for(inti0;i(1m);i){for(intj1;jn;j){dp[i|v[j]]min(dp[i|v[j]],dp[i]1);}}cout(dp[(1m)-1]1e9?-1:dp[(1m)-1])\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);intT1;// cinT;while(T--)solve();return0;}