Homework Introduction

二进制

  • 逢 22 进 11

  • intint 32位32 位

  • 二进制：
第一位符号位
非负数
0： 0000
1： 0001
2： 0010
...
7:  0111

负数：
-1 
正数 ： 0001  
减1：   0000
取反：  1111
计算机中-1 的状态就是 1111

-2
正数：0010
减1： 0001
取反： 1110
计算机中 -2 的状态就是 1110

一个二进制数字怎么看他是负几呢
1001  最高位为1， 肯定是负数
取反： 0110
+1 ： 0111 
原数为：正 7 
所以 1001 是负7

所以如果一个二进制为4位
	那他的表示范围为： -8 ~ 0 ~ 7

  • int 类型 32 位
负数：  -2^31 ~ -1
正数：	 0 ~ 2^31-1

  • 0x 3f3f3f3f  是一个很有用的数值
    整数的两倍不超过 0x7fffffff, 即 int 能表示的最大正整数
    整数的每 8 位（每个字节）都是相同的
    
memset( a, val , sizeof(a))
该语句把数值 val (0x00 ~ 0xff) 填充到数组 a 的每个字节上
1 个 int 占据四个字节，所以 memset 只能赋值出 每8位相同的 int 

0x7f7f7f7f 是memset 能赋值出的最大数值
避免算出溢出或者繁琐的判断，一般通常用 memset(a, 0x3f , sizeof(a)) 来赋值数组

位运算

  • ~ : 按位取反 ： 0 变 1 ， 1 变 0
  • & : 位与 ： 两个位置都为 1 ， 结果才为 1
  • | ： 位或 ： 两个位置都为 0 ， 结果才为 0
  • ^ : 异或 ： 相同为 0 ， 不同为 1
  • << : 左移 ： 1 << n 等价于 2n 2^n ， 低位以 0 填充，高位越界后舍弃
    • n << 1 等价于 ， 2n
  • >> : 右移 ： n >> 1 等价于 n / 2.0 向下取整，
    • （-3）>>1 = -2
    • 3 >> 1 = 1
    • 整数 / 2 ， 是除以 2 向零取整 （-3） /2 = -1

P1226 【模板】快速幂

  • /*
  基于二进制拆分
  3^7
  7 在二进制下是 0111 = 2^2 + 2^1 +1 =7
  3^7 = 3^( 2^2 + 2^1 +1 )
  = 3^(2^2) * 3^(2^1) * 3^(2^0)
  所以只需要做三次 乘法算出 3 的 7 次方

  3^7  直接暴力算的话，时间复杂度是 O(n)

  如果是二进制拆分的话，相当于就是这个 幂次
  在二进制下有几位就做几次乘法
  7在二进制下有三位，所以做三次乘法，时间复杂度O(log(n))

  3^1 = 3 = 3^(2^0)
  3^1 * 3^1 = 3^(2^0) * 3^(2^0) = 3^(2^0 + 2^0) = 3^(2^1)
  3^(2^1) * 3^(2^1) = 3^(2^1 + 2^1) = 3^(2^2)

  然后需要计算的次数就是 幂 次在二进制下有几位就计算几次 O(logn)

 */
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

ull qmi(ull a, ull b, ull p) {
	ull res = 1 % p; // %p 是为了不进入循环的考虑
	while (b) {
		// 1014578 0 1  这个样例，不会进入循环里面
		// 如果个位是 1  ， 1ll：防止溢出,long long 类型的整数 1
		if (b & 1) res = res  * a % p;
		b >>= 1 ; // 去除个位
		a = a  * a % p; // 准备好下一个位的幂次
	}
	return res;
}

int main() {
	ull a, b, p;
	cin >> a >> b >> p;
	cout << a << "^" << b << " mod " << p << "=" << qmi(a, b, p);
	return 0;
}

P10446 64位整数乘法

  • /*
  a*b 等价于 a+a+a b个a相加

  a*1 = a
  a*2 = 2a
  a*4 = 4a
  a*8 = 8a
  ...
  a*(2^k) = 2^k*a
 */

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;

int main() {
	ull a, b, p;
	cin >> a >> b >> p;
	ull res = 0;
	while (b) {
		if (b & 1) res = (res + a) % p;
		b >>= 1;
		a = a * 2 % p;
	}
	cout << res;
	return 0;
}

二进制状态压缩

  • 二进制状态压缩，是值将一个长度为 mm 的 boolbool 数组 用一个 mm 位二进制整数表示并存储的方法

  • 利用位运算可以实现原 boolbool 数组中对应下标元素的存储

  • 操作(数第几位是从右往左数) 运算
    取出整数 nn 在二进制表示下的第 kk 位 (n>>k)&1(n >>k) \&1
    取出整数 nn 在二进制表示下的第 0至k−10 至 k-1 位（后 kk 位） n&((1<<k)−1)n \&((1<<k)-1)
    把整数 nn 在二进制表示下的第 kk 位取反 n xor (1<<k)n\ xor\ (1<<k)
    对整数 nn 在二进制表示下的第 kk 位赋值 11 $n
    对整数 nn 在二进制表示下的第 kk 位赋值 00 n&(n\&(~(1<<k))(1<<k))

B3622 枚举子集

  • #include <bits/stdc++.h>
using namespace std;
int n;
int main() {
	cin >> n;
	// 枚举所有可能
	for (int i = 0; i < (1 << n) ; i++) {
		for (int j = n - 1; j >= 0; j--)
			if (i >> j & 1)
				cout << "Y";
			else cout << "N";
		cout << endl;
	}
	return 0;
}

P10447 最短 Hamilton 路径

  • /*
  起点在 0 终点在 n-1，所有点都经过一次

  0 1 2 3
  0->1->2->3
  0->2->1->3

  1. 哪些点被用过  2^20
  2. 目前停在哪个点上  20
  2^20 *20 = 2*1e7

  state 表示哪些点被用过， j 表示当前停在哪个点上
  state_k  = state 除掉 j 之后的集合
  f[state][j] = f[state_k][k] + weight[k][j]
  就等于先到 k 然后又从 k 到 j

  用一个二进制的整数来表示 state , 二进制集合，状态压缩
 */
#include <bits/stdc++.h>
using namespace std;
const int N = 20, M = 1 << 20;
int n, f[M][N], weight[N][N];
int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> weight[i][j];
	memset(f, 0x3f, sizeof f);
	f[1][0] = 0;
	for (int i = 0; i < 1 << n ; i++)
		for (int j = 0; j < n; j++) { // 枚举所有的点
			// & 两个都为 1， 结果才为 1
			if (i >> j & 1) { // 判断 i 的第 j位是不是 j
				for (int k = 0; k < n; k++) {  // 枚举点
					// state_k = i - (1<<j) , 不包含 j 这个位置
					if (i - (1 << j) >> k & 1 ) { // 判断这个 k 是不是用过
						f[i][j] = min(f[i][j], f[i - (1 << j)][k] + weight[k][j]);
					}
				}
			}
		}
	// 用了所有的点，最后停留在 n-1 的位置上
	cout << f[(1 << n) - 1][ n - 1];
	return 0;
}

P10456 The Pilots Brothers' refrigerator

  • /*
  4*4 矩阵
  + 闭合状态
  - 打开状态
  把所有的全部处于打开状态，求最小次数
  操作一个，同行和同列的全部状态切换

  每个位置只会操作一次，16个位置，顶多 2^16 次方个操作
  然后再判断是否合法，
  2^16 * 16 = 2^20 = 1e6 ，时间完全够

  枚举方案：0 ~ 2^16 -1

  给位置进行编号
  0 1 2 3
  4 5 6 7
  8 9 10 11
  12 13 14 15

 */

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int > pii;
int change[4][4];

int get(int x, int y) {
	return x * 4 + y; // 快速计算出来x,y对应的位置
}

int main() {
	// 用一个数字来表示整个状态
	int state = 0;
	for (int i = 0; i < 4; i++) {
		string line;
		cin >> line;
		for (int j = 0; j < 4; j++)
			if (line[j] == '+')
				state += 1 << get(i, j); // 这个位置上有1,记录一下
	}
	// 预处理得到 change 数组，
	// 计算当操作 i,j 这一个位置的时候，需要 异或的数字
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++) {
			for (int k = 0; k < 4; k++) {
				// 需要处理的行和列，减去重复处理的一个数
				change[i][j] += 1 << get(i, k);
				change[i][j] += 1 << get(k, j);
			}
			change[i][j] -= 1 << get(i, j);  // 减去重复计算的一个数字
		}
	// 枚举所有不同的方案
	vector<pii> res;
	for (int k = 0; k < 1 << 16 ; k++) {
		int now = state;
		vector<pii> path;
		for (int i = 0; i < 16 ; i++)
			if (k >> i & 1) { // 当前位置为1
				int x = i / 4, y = i % 4;
				now ^= change[x][y];
				path.push_back({x, y});
			}
		// ! now 当前 now 已经全部为0 了

		if (!now && (res.empty() || res.size() > path.size()))
			res = path;
	}
	cout << res.size() << endl;
	// 答案的下标是从 1开始，所以都增加1
	for (auto p : res)
		cout << p.first + 1 << " " << p.second + 1 << endl;
	return 0;
}

P2114 [NOI2014] 起床困难综合症

  • /*
  选择 0~m 之间的一个整数x,经过n次位运算
  使得结果 ans 最大
  位运算的主要特点之一是在二进制下不进位
  所以参与运算的各个位(bit)之间是独立无关的
  即：ans的第几位只与 x 的第几位有关

  所以可以从高到底，依次考虑 x 的每一位是 1 还是0
  x 的第 k 位可以填1，当且仅当同时满足
  1. 已经填好的更高位构成的数值加上 1<<k 以后不超过 m
  2. 用每个参数的第 k 位参与位运算，
	  若初值为1，则n次运算后结果为1
	  若初值为0，则n次运算后结果为0

  如果不满足上述条件，要么填1会超过 m的范围
  要么填1不如填0更优
 */
#include <bits/stdc++.h>
using namespace std;
pair<string, int> a[100005];
int n, m;
// 用参数的第 bit 位进行 n 次运算
int calc(int bit, int now) {
	for (int i = 1; i <= n; i++) {
		// 获取到 bit 位
		int x = a[i].second >> bit & 1;
		if (a[i].first == "AND") now &= x;
		else if (a[i].first == "OR") now |= x;
		else now ^= x;
	}
	return now;
}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> a[i].first >> a[i].second;
	int val = 0, ans = 0;
	for (int bit = 29 ; bit >= 0 ; bit--) {
		int res0 = calc(bit, 0);
		int res1 = calc(bit, 1);
		// 当前位置填 1 , 其实 res0 和 res1 要么是 0 要么是1
		if (val + (1 << bit) <= m && res0 < res1)
			val += 1 << bit, ans += res1 << bit;
		else ans += res0 << bit;
	}
	cout << ans;
	return 0;
}

成对变换

  • 对于非负整数
    • 当 nn 为偶数的时候， n xor 1n \ xor \ 1 等于 n+1n+1
    • 当 nn 为奇数的时候， n xor 1n \ xor \ 1 等于 n−1n-1
  • 因此，0 与 1 ，2 与 3 ， 4 与 5 ... 关于 xor 1xor \ 1 构成 成对交换
  • 常用于图论邻接表中边集的存储，在具有无向边（双向边）的图中把一对正反方向的边分别存储在邻接表数组的第 nn 与 n+1n+1 的位置（n为偶数）

lowbit 运算

  • lowbit(n)lowbit(n) 定义为非负整数 nn 在二进制表示下 最低位的 1 及其后边所有的 0 构成的数值

    • n=10n = 10 的二进制表示为 (1010)2(1010)_2 , 则 lowbit(n)=2=(10)2lowbit(n) = 2 =(10)_2

  • 推导

    • 设 n>0 , n 的第k位是1，第 0 ~ k-1 位都是0
为了实现lowbit运算，先把 n 取反，此时第 k 位变为0， 第 0 ~ k-1 位都是1
再令 n = n +1, 因为进位，第 k 位变为1，第 0 ~ k-1 位置都是0
在上面的取反加1操作后， n 的第 k+1 位到最高位恰好与原来相反
所以 n&(~n+1) 仅有第 k 位为 1，其余为都是0
在补码表示下， ~n+1 = -n

找出整数二进制下所有是1的位

  • #include <bits/stdc++.h>
using namespace std;
const int N = 1 << 20;
int h[N + 1], n;

int lowbit(int x) {
	return x & -x;
}

int main() {
	// 预处理 代替 logn
	// h[2^k] = k
	for (int i = 0; i <= 20; i++)
		h[1 << i] = i;
	while (cin >> n) {
		while (n > 0) {
			cout << h[lowbit(n)] << " ";
			n -= lowbit(n);
		}
		cout << endl;
	}
	return 0;
}

题目练习

P10482 Sudoku 2

  • /*
每一行出现1-9
每一列出现1-9
3*3的九宫格出现1-9
暴搜：搜索的顺序
	  1.每次随意挑选一个空白格子
	  2.枚举这个该格子选哪个数
	  3. DFS
TLE

看 (x,y) 位置可以用哪些数
每一个位置不是 0 就是 1 如果是 1 代表这个数字可以用
row[i] : 存储一个二进制数 0 到 2^9-1
col[j] : 存储一个二进制数 0 到 2^9-1
cell[i][j] : 存储一个二进制数 0 到 2^9-1
可以选用的数字就是他们的交集
给 九宫格进行标号 (0,0) (0,1)(0,2)
				    (1,0)
row[x] & col[y] &cell[x/3][y/3]
最后 & 完的数字就是我们可以用的数字

lowbit(x) 返回数字 x 的最后一个 1
lowbit(10010) = 10
*/

#include <bits/stdc++.h>
using namespace std;
const int N = 9;
// 优化，ones 记录这个里面有几个 1
// mp 数组记录这个1 是第几个位置
int ones[1 << N], mp[1 << N];
int row[N], col[N], cell[3][3];

char str[100];

inline int lowbit(int x) {
	return x & -x;
}

void init() {
	for (int i = 0; i < N; i++)
		row[i] = col[i] = (1 << N) - 1;
	for (int i = 0; i < 3; i++)
		for (int j = 0; j < 3; j++)
			cell[i][j] = (1 << N) - 1;
}

inline int  get(int x, int y) {
	return row[x] & col[y] & cell[x / 3][y / 3];
}

bool dfs(int cnt) {
	if (!cnt) return 1;
	// 找出可选方案数最小的
	int minn = 10;
	int x, y;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			if (str[i * 9 + j] == '.') {
				int t = ones[get(i, j)];
				if (t < minn) {
					minn = t;
					x = i, y = j;
				}
			}

	for (int i = get(x, y) ; i ; i -= lowbit(i)) {
		// 当前位置要填充的数字是 t
		int t = mp[lowbit(i)];
		// 修改状态
		row[x] -= 1 << t;
		col[y] -= 1 << t;
		cell[x / 3][y / 3] -= 1 << t;
		str[x * 9 + y] = '1' + t;

		if (dfs(cnt - 1)) return 1;

		//  回溯
		row[x] += 1 << t;
		col[y] += 1 << t;
		cell[x / 3][y / 3] += 1 << t;
		str[x * 9 + y] = '.';
	}
	return 0;
}

int main() {
	for (int i = 0; i < N; i++)
		mp[1 << i] = i;
	for (int i = 0; i < 1 << N ; i++) {
		int s = 0;
		for (int j = i ; j ; j -= lowbit(j)) s++;
		ones[i] = s; // i 的二进制表示中有 s 个1
	}

	while (cin >> str, str[0] != 'e') {
		init();

		int cnt = 0;
		for (int i = 0, k = 0; i < N ; i++)
			for (int j = 0; j < N; j++, k++) {
				if (str[k] != '.') {
					// 1 - 9 映射到下标 0 - 8
					int t = str[k] - '1';
					row[i] -= 1 << t;
					col[j] -= 1 << t;
					cell[i / 3][j / 3] -= 1 << t;
				} else cnt++;
			}
		dfs(cnt);
		cout << str << endl;
	}
	return 0;
}

P1074 靶形数独

  • /*
  每个位置上有一个分数，计算最大得分

  直接按照数独的方式来计算，暴力算出所有的解
  然后算出所有的解里面的得分，记录最大值

  优化，位运算优化
  和 10482 一样的逻辑

  位运算
  int row[9] , col[9] cell[3][3]
  搜索顺序：每次选择一个空格（可选择的数量少的一个空格）来填

  int state = row[x] & col[y] & cell[x/3][y/3]
  lowbit(state) 求出能用到的所有位置
  for(int i=state ; i!=0 ;i -= lowbit(i))

  计算分数，当前位置到上下左右四条边的最短距离 + 6 就是对应的分值
 */

#include <bits/stdc++.h>
using namespace std;
const int N = 9, M = 1 << N;
int row[N], col[N], cell[3][3];
int g[N][N], ans = -1;

// 需要快速计算某个数字的二进制有几个  1
// 打表 ones
// log 快速计算某个数是 2 的几次方
int ones[M], lg[M];

int lowbit(int x) {
	return x & -x;
}

void init() {
	for (int i = 0 ; i < N; i++)
		lg[1 << i] = i;
	for (int i = 0; i < M; i++) {
		for (int j = i; j ; j -= lowbit(j))
			ones[i]++; // 没减少一位证明有一个 1
	}
	// 初始每一行、列、九宫格的状态
	for (int i = 0; i < N; i++)
		row[i] = col[i] = cell[i / 3][i % 3] = M - 1;
}

int get_score(int x, int y) { // 计算分数的函数
	return min(min(x, 8 - x), min(y, 8 - y)) + 6;
}

// 在 x 位置上写上 t
void draw(int x, int y, int t) {
	int s = 1;
	if (t > 0)  g[x][y] = t; // 当前值要画上去
	else { // 把当前值抹掉
		s = -1;    // 所以需要给他加回去，s变成 -1
		t = -t;  // 取相反数
		g[x][y] = 0;
	}
	t--;   // 映射到 0 - 8 ， 所以需要 --
	row[x] -= s << t;
	col[y] -= s << t;
	cell[x / 3][y / 3] -= s << t;
}

int get(int x, int y) { // 计算可以选择的可选交集
	return row[x] & col[y] & cell[x / 3][y / 3];
}

void dfs(int cnt, int score) {
	if (!cnt) {
		ans = max(ans, score);
		return ;
	}
	int x, y, mins = 10; // 存出可选数字最少的位置
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++) {
			if (!g[i][j]) {
				int state = get(i, j);
				if (ones[state] < mins) {
					mins = ones[state];
					x = i, y = j;
				}
			}
		}
	for (int i = get(x, y) ; i ; i -= lowbit(i)) {
		int t = lg[lowbit(i)] + 1;
		draw(x, y, t);
		dfs(cnt - 1, score + t * get_score(x, y));
		draw(x, y, -t);  // 回溯
	}
}

int main() {
	init();
	// cnt 0 的个数
	int cnt = 0, score = 0;
	for (int i = 0; i < N ; i++)
		for (int j = 0; j < N; j++) {
			int x;
			cin >> x;
			if (x) {
				draw(i, j, x);
				score += x * get_score(i, j);
			} else cnt++; // 计算 0 的个数
		}
	dfs(cnt, score);
	cout << ans;
	return 0;
}

P10484 送礼物

  • #include <bits/stdc++.h>
using namespace std;
const int N = 50;
#define int long long
int w, n, ans;
int a[N], weight[1 << 24], cnt;
signed main() {
	cin >> w >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	// 优化搜索顺序
	sort(a, a + n, greater<int>());
	int k = n >> 1;
	// 二进制枚举，枚举前半部分
	for (int i = 0; i < (1 << k) ; i++) {
		int sum = 0;
		for (int j = 0 ; j < k; j++) {
			// 取到每一位
			if (i >> j & 1)
				sum += a[j];
		}
		if (sum <= w)
			weight[++cnt]  = sum;
	}
	// 排序，去重
	sort(weight + 1, weight + 1 + cnt);
	cnt = unique(weight + 1, weight + 1 + cnt) - weight - 1;

	k = n - k;
	// 后半部分
	for (int i = 0; i < (1 << k) ; i++) {
		int sum = 0;
		for (int j = 0 ; j < k; j++) {
			// 取到每一位
			if (i >> j & 1)
				sum += a[j + (n >> 1)];
		}
		if (sum <= w) {
			int l = 1, r = cnt;
			while (l < r) {
				int mid = l + r + 1 >> 1;
				if (weight[mid] + sum <= w) l = mid;
				else r = mid - 1;
			}
			ans = max(ans, weight[l] + sum);
		}
	}
	cout << ans;
	return 0;
}

P10449 费解的开关

  • /*
  修改一个灯的状态
  上下左右相邻的也会改变
 */
// 固定第一行不能动
// 那就只能动 第二行
// 枚举第一行的状态
#include <bits/stdc++.h>
using namespace std;
const int INF = 1000000;
char g[10][10];
int dx[] = {0, -1, 0, 1, 0};
int dy[] = {0, 0, 1, 0, - 1};

void turn(int x, int y) {
	for (int i = 0; i < 5; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5)
			// 0 变成1，1 变成 0
			g[nx][ny] = '0' + ('1' - g[nx][ny]);
	}
}

int work() {
	int ans = INF;  // 定义一个全局最大值
	// 枚举 0- 32 这 32 个 5 位二进制数
	for (int k = 0; k < 1 << 5 ; k++) {
		int res = 0 ;
		char backup[10][10];
		// 弄一个备份
		memcpy(backup, g, sizeof(g));
		// 遍历每一位
		// 操作第一行，给第一行每个设置一个可能
		// 这里的 k 代表的是第一行如何操作，枚举第一行操作的可能性
		for (int j = 0; j < 5; j++) {
			if (k >> j & 1) {
				res++;  // 当前操作了一次
				turn(0, j);
			}
		}
		// 接下来处理剩下的四行
		for (int i = 0; i < 4; i++)
			for (int j = 0; j < 5; j++)
				// 当前行这个数字为 0 ，那么通过下一行来调整为1
				if (g[i][j] == '0') {
					res++;
					turn(i + 1, j ); //操作下一行
				}
		// 判断最后一行是否数字全部为 1
		bool flg = 1;
		for (int j = 0; j < 5; j++)
			if (g[4][j] == '0') {
				flg = 0;
				break;
			}
		if (flg) ans = min(ans, res);
		// g 数组恢复原状
		memcpy(g, backup, sizeof(g));
	}
	if (ans > 6) return -1;
	return ans;
}

int main() {
	int T;
	cin >> T;
	while (T--) {
		for (int i = 0; i < 5; i++)
			cin >> g[i];
		cout << work() << endl;
	}
	return 0;
}

Problem

Problem
P1226   【模板】快速幂
P10446   64位整数乘法
B3622   枚举子集（递归实现指数型枚举）
P10447   最短 Hamilton 路径
P10456   The Pilots Brothers' refrigerator
P2114   [NOI2014] 起床困难综合症
P10482   Sudoku 2
P1074   [NOIP 2009 提高组] 靶形数独
P10484   送礼物
P10449   费解的开关
Status
Done
Problem
10
Open Since
2025-12-22 0:00
Deadline
2026-1-10 23:59
Extension
24 hour(s)
  1. Judging Queue
  2. Service Status
  3. Legacy mode
  4. Theme
  2. 蜀ICP备2022005482号-4
  3. Worker 0, 17ms
  4. Powered by Hydro v5.0.0-beta.15 Community