2023科协第二次MINI内训

发表于 阅读次数： Disqus：

写在前面

2023年3月26日，软件学院科协赛事部在EL大赛策划会议后举行了第二次内训。本次内训如愿线下举行，内容轻松愉快，讲述了如何将二进制运用到程序设计之中。算是一次成功的MINI内训。

回顾位运算

符号 描述 运算规则
& 与 两个位都为1时，结果才为1
或 两个位都为0时，结果才为0
^ 异或 两个位相同为0，相异为1
~ 取反 0变1，1变0
<< 左移 各二进位全部左移若干位，高位丢弃，低位补0
>> 右移 各二进位全部右移若干位

一些简单的例子

  1. 用位运算判断一个数是否是奇数

    1
    2
    3
    if (x & 1) {
        printf("x is odd.");
    }

  2. 取出二进制数的倒数第$k$位

    1
    (x >> (k - 1)) & 1

  3. 将一个整数乘以$2^k$

    1
    x <<= k;

这仍然是一个easy的问题

二进制以字符串的形式描述

（1）将一个二进制数转化为十进制数

1
2
3
4
int num = 0; 
for(int i = 0; i < len; i++) {
     num = (num << 1) | (s[i] - '0')
}

（2）将一个十进制数转化为二进制数

重要思想： 其实数在计算机内本来就是二进制的，所以十进制数转化为二进制数就是依次取出二进制数的倒数第$k$位

快速幂算法

问题：如何快速求解$x^p$ 或$x^p$ mod r的值

  • 在$O(n)$的时间内求解这个问题应该不是什么难事

  • 能否在$O(log n)$的时间内求解这个问题

分治思想

  • 当p 为偶数时， $n^p = (n^{p/2})^2$

  • 当p 为奇数时呢？ $p -1$ 是偶数

我们可以写递归函数解决

二进制分解

能否不用递归？

以求$x^{21}$ 为例：$(21)_{10}=(10101)_2$

$x^{16}$ $x^{8}$ $x^{4}$ $x^{2}$ $x^{1}$
每一位 1 0 1 0 1

ppgA6kn.png

Python参考代码

1
2
3
4
5
6
7
8
9
10
11
def fast_pow(x, p):
    ans = 1
    while p > 0:
        if p & 1 == 1:
            ans = ans * x
        x = x * x
        p >>= 1
    return ans

x, p = [int(t) for t in input().split()]
print(fast_pow(x, p))

状态压缩

P2040 打开所有的灯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

这个灯很奇怪，点一下就会将这个灯和其周围四盏灯的开关状态全部改变。现在你的任务就是就是求要打开全部这些灯最少需要点几下。

例如

1
2
3
0  1  1
1  0  0
1  0  1

点一下最中间的灯【2,2】就变成了

1
2
3
0  0  1
0  1  1
1  1  1

再点一下左上角的灯【1,1】就变成了

1
2
3
1  1  1
1  1  1
1  1  1

达成目标。最少需要2步。

分析

像极了洛克王国打幽系徽章玩的小游戏

  • 一个灯点1次和点3的效果是一样的
  • 那么我们是不是可以枚举每个灯的状态
  • 每个灯就是一个0或者1
  • 可以用9位的二进制数（0~511）描述所有操作组合

C语言参考代码

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 <stdio.h>
#include <stdbool.h>
#include <string.h>

int a[5][5], b[5][5];
int ans = 10;

bool check() { // 检查灯是否已经全部打开
    int sum=0;
    for(int i = 1 ;i <= 3; i++) {
        for(int j = 1; j <= 3; j++) {
            sum += b[i][j];
        }  
    }
    return (sum == 9);
}

int main()
{
  for(int i = 1;i <= 3;i++)
      for(int j = 1;j <= 3;j++)
          scanf("%d", &a[i][j]);
  for(int i = 0; i < (1 << 9); i++) {      // 从0 ~ 2 ^ 9 - 1枚举
  	  int j = i;  
      int count = 0;   
	  int t = 0;  
      memcpy(b, a, sizeof(a));             // 复制一份数组
	  while(j) {  
    	  t++;  
    	  if(j & 1) {  
    	      count++;  
    	      int x = (t - 1) / 3 + 1; 		   // 行
	    	  int y = (t - 1) % 3 + 1; 		   // 列
	    	  b[x][y] = b[x][y] ^ 1;       // 改变自己和周围灯的状态
	    	  b[x + 1][y] = b[x + 1][y] ^ 1;
	    	  b[x - 1][y] = b[x - 1][y] ^ 1;
	    	  b[x][y - 1] = b[x][y - 1] ^ 1;
	    	  b[x][y + 1] = b[x][y + 1] ^ 1;
	      }
	      j >>= 1;
	  }
	  if(check()) { ans= count < ans? count: ans;}  // 更新答案
    }
  printf("%d\n",ans);
  return 0;
}

注：这段代码在3*3的棋盘外面加上了“一层壳”，有效避免了边界的特别处理

改进

使用了Web CodeServer现场演示，PPT和内容存在网页中，可以在教室电脑上直接运行，无需投影/配环境