冲刺600道AC

(눈_눈)

图（关系结构）

由点和边构成的集合

• 无向图
• 有向图

带权图

度

出度：从一个点出去的边的数量

入度：进入一个点的边的数量

连通图

概念：一个图中所有点之间至少存在一条路径（路径：一个点有一条路到达另一个点）的图

无向图：连通图

有向图

• 弱连通图：将此图转换为无向图后，是连通状态，即为若连通

• 强连通图：有向图中任意一点都存在一条到达其余所有点的路径

完全图

一张图中，任意两点之间均有着一条直接连接的边

树

概念：只有n-1(n:点的数量)条边的连通图

点和点之间的关系

• 父子
• 兄弟
• 祖孙

度：一个点的儿子数量

节点类型

• 根结点
• 分支节点
• 叶子节点

完全二叉树

概念：按照每一层节点依次填充的顺序的二叉树，是完全二叉树

特性：

• n层的二叉树，最多共有** 2n−12n−1个节点**
• 二叉树第n层，最多有个2n−12n**−1节点**

满二叉树

概念：n层的二叉树中所有分支节点的度数都为2

位运算符

左移运算：<<

用法：** **x<<y

作用：将表示** x 的二进制数的每一位左移 **y 位，移出去的数就丢掉，空余地方用 0 补位。

例如：一个二进制数 10101011 将其左移 3 位，得到 01011000。

右移运算：>>

用法：x>>y

作用：将表示** x 的二进制数的每一位右移 **y 位，移出去的数就丢掉，空余地方用 0 补位。

例如：一个二进制数 10101011 将其右移 3 位，得到 00010101。

按位与运算：&

用法：x&y

作用：按位进行与运算。

例如：1101 和 0011 进行与运算就为：0001。

按位或运算: |

用法：x|y

作用：按位进行或运算。

例如：1101 和 0011 进行或运算就为：1111。

按位异或运算：^

用法：x^y

作用：按位进行异或运算。

例如：1101 和 0011 进行异或运算就为：0001。

按位非运算：~

用法：~x

作用：按位进行非运算。

例如：1101进行非运算就为：0010。

状态压缩常用位运算符技巧

1.取出x的第k位:

y = x&(1<<(k-1));//i<<(k-1)能够做成一个第k为1，其余位为0，如:10000 的二进制数，再结合位与运算就能提取到变量x的二进制中第k位数为1还是0了，常用于判断

Copy

2.将x第k位取反:

x ^= (1<<(k-1));//通过左移制作一个10000般的二进制数，然后结合异或运算的特点，将变量x的二进制中第k位数取反

Copy

3.将x第k位变为1：

x |= (1<<(k-1));//通过左移制作一个10000般的二进制数，然后结合异或运算的特点，将变量x的二进制中第k位数修改为1

Copy

4.将x第k位变为0：

x &= (~(1<<(k-1))); //通过左移制作一个0001 0000般的二进制数，然后位非运算将其修改为1110 0000般的二进制数，最后结合位与运算的特点，将变量x的二进制中第k位数修改为0

Copy

5.将x最靠右的1去掉：

x = x&(x-1); //减去1会将数字二进制中末尾的1去掉，然后需要借位的地方全变为1，如原1010 0000，减去1后变成1001 1111，再进位与运算得1000 0000，相当于去掉末尾1

Copy

6.取出x最靠右的1:

y = x&(-x); //结合负数的二进制的特点，如数字20的二进制为0001 0100，-20的二进制为1110 1100，再进行位与运算能够获取到二进制数100也就是4，及提前数字x中包含的最大2的指数值

Copy

7.判断是否有两个连续的一：

if(x&(x<<1)) cout<<"YES"; //左移后的数字会进行偏移，如13的二进制0000 1101，左移后未0001 1010，再进行位与运算，连续的1会在偏移后有至少一个1重叠，让结果不为0，如果结果为0，说明不存在连续的1

Copy

8.枚举子集：

for( int x = sta ; x ;  x = ( ( x - 1 )&sta) )  
	cout<<x;//通过技巧6的方式，如二进制:1011 0101,此循环能够枚举1011 0101、1011 0100、1011 0000、1010 0000、1000 0000这几个数据，即十进制：181、180、176、160、128这几个数字。