0X01 位运算笔记
位运算,经常可以用来处理一些数学或动归方面的问题,通常会在数据范围较小的情况下使用。
为方便起见,一个 (mathrm{n}) 位二进制数从右到左分别为第 (mathrm{0 sim n - 1}) 位。
快速幂 (( exttt{ACW89 a^b}))
求 (mathrm{a^b}) 对 (mathrm{p}) 取模的值。
(a, b leq 10 ^ 9, 1 leq p leq 10 ^ 9)。
考虑 (b) 的二进制。若可以表示为 (sum_{i}^{} 2^i) 的形式,那么 (a^b) 就可以表示成 (a ^ {sum_{i}^{} 2 ^ i})。
而 (a ^ {2 ^ i} = (a^{2^{i - 1}}) ^ 2),这样可以通过递推的方式求出 (a ^ {2 ^ i})。由于 (max{i}) 是 (log b) 级别的,所以总时间复杂度为 (O(log b))。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
using LL = long long;
int qpow(int a, int b, int p) {
int ans = 1 % p; // 这里是为了避免 p = 0 的情况出现
while (b) {
if (b & 1) ans = (LL)ans * a % p;
a = (LL)a * a % p;
b >>= 1;
}
return ans;
}
int main() {
int a, b, p;
scanf("%d%d%d", &a, &b, &p);
printf("%d
", qpow(a, b, p));
return 0;
}
六十四位整数乘法 (( exttt{ACW90}))
求 (a * b) 对 (p) 取模的值。
- 算法一:
我们可以用类似快速幂的思想,使用二进制优化算法。将 (b) 拆分成二进制来看。假设 (b) 拆分成二进制之后是 (sum 2^i),那么答案就是 (a ^ {sum 2 ^ i} = prod a ^ {2 ^ i})。由于 (max_i leq log_2 b) ,因此可以保证复杂度为 (O(log b))。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
using LL = long long;
LL mul(LL a, LL b, LL p) {
LL ans = 0;
while (b) {
if (b & 1) ans = (ans + a) % p;
a = (a << 1) % p;
b >>= 1;
}
return ans;
}
int main() {
LL a, b, p;
scanf("%lld%lld%lld", &a, &b, &p);
printf("%lld
", mul(a, b, p));
}
- 算法二:
(a imes b pmod p = a imes b - left lfloor a imes b / p ight floor) 。
因此可以使用 (operatorname{long double}) 存储 (left lfloor a imes b / p ight floor),(operatorname{long long}) 存储 (a imes b)。二者相减即可。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
using LL = long long;
LL mul(LL a, LL b, LL p) {
a %= p, b %= p;
LL c = (long double)a * b / p;
LL ans = a * b - c * p;
ans += (ans < 0) ? p : 0;
ans -= (ans >= p) ? p : 0;
return ans;
}
int main() {
LL a, b, p;
scanf("%lld%lld%lld", &a, &b, &p);
printf("%lld
", mul(a, b, p));
}
最短 ( ext{Hamilton}) 路径 (( exttt{ACW91}))
给定一张 (n) 个点的带权无向图,点从 (0∼n−1) 标号,求起点 (0) 到终点 (n−1) 的最短 ( ext{Hamilton}) 路径。
( ext{Hamilton}) 路径的定义是从 (0) 到 (n−1) 不重不漏地经过每个点恰好一次。 (n leq 20)。
考虑状态压缩 (dp)。由于 (n) 的规模很小,可以直接用二进制枚举每个点的状态,其中 (1) 表示经过一次,(0) 表示没有经过。
设置状态 (f_{i, j}) ,表示当前在第 (i) 个点,当前状态是 (j) 的最短路径。首先要枚举所有可行状态,刷表时枚举当前点和要走到的点,如果当前点没有被走到过或者要去的点已经走过一遍了,那么直接剪掉。最终答案即为 (f_{n - 1, 2^n - 1})。
由此来看,复杂度为 (O(2 ^ n n ^ 2)),但是剪枝强度很大,可以跑过。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 21;
int f[N][1 << N];
int n, w[N][N];
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i ++ )
for (int j = 0; j < n; j ++ )
scanf("%d", &w[i][j]);
memset(f, 0x3f, sizeof f);
f[0][1 << 0] = 0;
for (int i = 1; i < 1 << n; i ++ )
for (int j = 0; j < n; j ++ ) if (i & (1 << j)) {
for (int k = 0; k < n; k ++ ) {
if (i & (1 << k)) continue;
f[k][i | (1 << k)] = min(f[k][i | (1 << k)], f[j][i] + w[j][k]);
}
}
printf("%d
", f[n - 1][(1 << n) - 1]);
return 0;
}
起床困难综合征 (( exttt{ACW998}))
本题思路是按位贪心。可以参照 (01trie) 进行理解。
形象地看,假设我有一个 (n) 位的二进制数,每一位都是 (0),现在我可以把某一位变成一使得这个数最大,那么我肯定要变 (n - 1) 位,因为我只要把最高位设成 (1),就会比 (0 sim n - 2) 位都设成 (1) 要大 (1)。
本题也可以用这种思路,将答案从高位到低位按最优方案填充即可。
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 100010;
int n, m, w[N];
string str[N];
int calc(int bit, int now) {
for (int i = 1; i <= n; i ++ ) {
int x = w[i] >> bit & 1;
if (str[i] == "AND") now &= x;
else if (str[i] == "OR") now |= x;
else now ^= x;
}
return now;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i ++ )
cin >> str[i] >> w[i];
int val = 0, ans = 0;
for (int i = 29; ~i; i -- ) {
int res0 = calc(i, 0);
int res1 = calc(i, 1);
if (val + (1 << i) <= m && res0 < res1)
val += 1 << i, ans += res1 << i;
else ans += res0 << i;
}
cout << ans << endl;
return 0;
}
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击