《《信息奥赛课课通》课件第10单元》由会员分享，可在线阅读，更多相关《《信息奥赛课课通》课件第10单元（120页珍藏版）》请在金锄头文库上搜索。
1、第 10 单元 位运算及标准模板库,作者：林厚从,信息学奥赛课课通（C+）,第 1 课 位运算,学习目标 1. 理解与掌握 C+ 中的位运算。 2. 灵活应用位运算优化程序。,任何信息在计算机中都是采用二进制表示的，数据在计算机中是以补码形式存储的，位运算就是直接对整数在内存中的二进制位进行运算。由于位运算直接对内存数据进行操作，不需要转换成十进制，因此处理速度非常快，在信息学竞赛中往往可以优化理论时间复杂度的系数。同时，一个整数的各个二进制位互不影响，利用位运算的一些技巧可以帮助我们简化程序代码。,1. 位运算符,C+ 提供了按位与（ int main() int x = 3,y = 8,z
2、; x = y; y = x; x = y; cout 1); cout z endl; return 0; ,例2、整数幂,判断一个数 n 是不是 2 的整数幂，比如 64=2 6 ，所以输出“yes”，而 65 无法表示成 2 的整数幂形式，所以输出“no”。n 在 int 范围以内。,【问题分析】 我们考虑一个数如果是2的整数幂会有什么特殊性。观察发现64转换成二进制为01000000，只有一个位是1。将这个数减去1，就变成00111111的形式，我们将这2个数做按位与运算，发现结果为0。分析发现，如果一个数不能表示成2的整数幂形式，则以上过程的运算结果一定不为0。所以，可以利用位运算将
3、算法的时间复杂度优化成O(1)。,/p10-1-2b #include using namespace std; int main() int n; cin n; if(n ,例3、找数,【问题描述】 给出 n 个整数，n 为奇数，其中有且仅有一个数出现了奇数次，其余的数都出现了偶数次。用线性时间复杂度、常数空间复杂度找出出现了奇数次的那个数。 【输入格式】 第一行一个整数n，1n5106 。接下来n 行，每行一个数。 【输出格式】 输出一行一个整数，表示出现了奇数次的那一个数。 【输入样例】 9 3 3 1 2 4 2 5 5 4 【输出样例】 1,【问题分析】 从头到尾“异或”一遍，最后得
4、到的那个数就是出现了奇数次的数。这是因为异或有一个神奇的性质：两次异或同一个数，结果不变。再考虑“异或”运算满足交换律，先异或、后异或都是一样的，因此这个算法显然正确。 参考程序见教材510-511页。,实践巩固,第 2 课 vector,学习目标 1. 了解 C+ 的标准模板库。 2. 掌握 vector 容器的使用方法。,标准模板库（Standard Template Library，STL）,C+功能强大，为开发者提供了标准模板库，其中封装了很多实用的容器。容器可以理解成能够实现很多功能的系统函数，或者说用来存放数据的对象，开发者可以根据接口规范（调用格式）直接调用，而不用关心其内部实现
5、的原理和具体代码，十分方便快捷。 常见的容器有vector、stack、queue、map、set等。,vector,vector直接翻译为“向量”，一般说成“变长数组”，也即“长度根据需要而自动改变的数组。 在信息学竞赛中，有些题目需要定义很大的数组，这样会出现“超出内存限制”的错误。比如，如果一个图的顶点太多，使用邻接矩阵就会超出内存限制，使用指针实现邻接表又很容易出错，而使用vector实现简洁方便，还可以节省存储空间。 使用vector，首先需要添加vector头文件，即#include ，同时，必须要有“using namespace std”。,1. vector 的定义,定义一个
6、 vector 的方法如下： vector name;,以上定义相当于定义了一个一维数组namesize，只是 size不确定，其长度可以根据需要而变化。其中typename可以是任何基本类型，例如int、double、char、结构体等，也可以是STL标准容器，例如vector、queue等。,访问 vector 中的元素一般有两种方式。 第一种是通过“下标”访问。 例如，对于容器 vector v，可以使用 vindex来访问它的第 index 个元素。其中，0indexv.size()-1，v.size()表示 vector 中元素的个数。 第二种方式是通过“迭代器”访问。 可以将迭代器
7、（iterator）理解为一种类似指针的变量。其定义为：vector:iterator it;,2. vector 的访问,例如： vector:iterator it= v.begin(); for(int i = 0; i = 5; i+) printf(%d ,*(it + i);,3. vector 的常用函数,（1）push_back() push_back(x)用来在 vector 后面添加一个元素 x，时间复杂度为 0(1)。 （2）size() 如果是一维数组，size()用来获得 vector 中元素的个数；如果是二维数组，size()用来获得vector 中第二维的元素个数
8、，时间复杂度为 0 (1)。 （3）pop_back() pop_back()用来删除 vector 的尾元素，时间复杂度为 0(1)。,3. vector 的常用函数,（4）clear() clear()用来清空 vector 中的所有元素，时间复杂度为 0(n)，其中 n 为 vector 中元素的个数。 （5）insert () insert(it，x)用来向 vector 任意迭代器 it 处插入一个元素 x，时间复杂度为 0(n)。 （6）erase() erase()用来删除 vector 中的元素，有两种用法。一种是 erase(it)，删除迭代器 it 处的元素；另一种是 er
9、ase(first，last)，删除左闭右开区间first，last)内的所有元素。,4. vector 的应用举例,例1、中间数 【问题描述】 依次读入若干正整数，如果是奇数个就输出最中间的那个数；否则，输出中间两个数的和。以 0 作为结束标志，但 0 不计数。,【问题分析】 参考程序见教材516-517页。,例2、上网统计,【问题描述】 在一个网络系统中有 N 个用户、M 次上网记录。每个用户可以自己注册一个用户名，每个用户名是一个只含小写字母且长度小于 1000 的字符串。每个上网的账号每次上网都会浏览网页，网页名是以一个只含小写字母且长度小于 1000 的字符串，每次上网日志里都会有记
10、录，现在请统计每个用户每次浏览了多少个网页。 【输入格式】 第 1 行包含两个用 1 个空格隔开的正整数 N（1N1000）和 M（1M5000）。 第 2M+1 行，每行包含 2 个用 1 个空格隔开的字符串，分别表示用户名和浏览的网页名。 【输出格式】 共 N 行，每行的第一个字符串是用户名，接下来的若干字符串是这个用户依次浏览的网页名（之间用一个空格隔开）。按照用户名出现的次序排序输出。,【输入样例】 5 7 goodstudyer bookshopa likespacea spaceweb goodstudyer bookshopb likespaceb spaceweb likesp
11、acec spaceweb likespacea juiceshop gameplayer gameweb 【输出样例】 goodstudyer bookshopa bookshopb likespacea spaceweb juiceshop likespaceb spaceweb likespacec spaceweb gameplayer gameweb,【问题分析】 由于用户名和浏览的网页名长度不固定，用 vector 解决比较方便，可以分别通过“下标”访问和“迭代器”访问。 参考程序见教材517-519页。,例3、蛇形方阵,【问题描述】 输入 n，n100，输出 n 阶蛇形方阵。例如
12、 n=5 时，输出如下： 1 2 6 7 15 3 5 8 14 16 4 9 13 17 22 10 12 18 21 23 11 19 20 24 25,【问题分析】 定义一个二维数组，模拟蛇形方阵填数的过程。具体程序参见教材520页。,实践巩固,第 3 课 stack,学习目标 掌握 stack 容器的使用方法。,stack的定义,stack翻译为栈，是STL中实现的一个“后进先出”的容器，其只能通过top()和pop()来访问栈顶元素。在第七单元中，我们已经介绍过手工栈的定义和操作，它一般用来解决因为系统栈空间较小而导致的“函数递归层数过深”出现程序运行崩溃的问题。 使用stack前，
13、要先添加stack头文件，即#include ，同时，必须要有“using namespace std”。 定义一个 stack 的方法如下： stack name; 其中，typename 可以是任何基本类型或者容器，name 是栈的名字。,1. stack 的常用函数,（1）push() push(x)用来将 x 压栈，时间复杂度为 0(1)。 （2）top() top()用来获得栈顶元素，时间复杂度为 0(1)。 （3）pop() pop()用来弹出栈顶元素，时间复杂度为 0(1)。 （4）empty() empty()用来检测 stack 是否为空，空返回 true，否则返回 fals
14、e，时间复杂度为 0(1)。 （5）size() size()用来返回 stack 内元素的个数，时间复杂度为 0(1)。,2. stack 的应用举例,例1、括号的匹配 【问题描述】 栈在计算机科学领域有着广泛的应用。比如在编译和运行计算机程序的过程中，就需要用栈进行语法检查，如检查 begin 和 end、 和 、（和）等是否匹配。 假设一个表达式只由小写英文字母、运算符（+，-，*，/）和左、右小括号构成，以“”作为表达式的结束符。 请编程检查表达式中的左、右小括号是否匹配，若匹配，则返回“YES”；否则返回“NO”，不必关心表达式中的其他错误。,【问题分析】 用一个栈存放表达式中从左往
15、右的左小括号。从左往右按顺序扫描表达式的每个字符，若是“（”，则将它压栈；若是“）”，则执行一次出栈操作。当栈发生下溢（右括号多）或当表达式处理完毕而栈非空（左括号多）时，意味着表达式中的括号不匹配，则输出“NO”；否则，表示小括号完全匹配，就输出“YES”。 参考程序见教材524页。,例2、溶液模拟器,【问题分析】 小 Y 虽有很多溶液，但还是没有办法配成想要的溶液，因为万一倒错了就没有办法挽回了。他从网上下载了一个溶液配置模拟器：模拟器在计算机中构造一种虚拟溶液，然后可以虚拟地向当前虚拟溶液中加入一定浓度、一定质量的这种溶液，模拟器会快速地算出倒入后虚拟溶液的浓度和质量。 模拟器的使用步骤
16、如下： （1）为模拟器设置一个初始质量和浓度 V0 、C0 % （0C0 100）。 （2）进行一系列操作，模拟器支持两种操作：一种是 P（v，c）操作，表示向当前的虚拟溶液中加入质量为 v、浓度为 c 的溶液；另一种是 Z 操作，即撤销上一步 P 操作。,【输入格式】 第 1 行两个整数 V0 、C0 。 第 2 行 1 个整数 n，n10000，表示操作数。 接下来的 n 行，每行一条操作，格式为：P_v_c 或 Z。其中“_”代表一个空格，当只剩初始溶液的时候，再撤销就没有用了。 任意时刻质量都不会超过 231 -1。 【输出格式】 输出 n 行，每行两个数 Vi 、Ci ，之间用一个空格隔开，其中 Vi 为整数，Ci 为实数（保留 5 位小数）。其中，第 i 行表示第 i 次操作以后的溶液质量和浓度。,【输入样例】 100 100 2 P 100 0 Z 【输出样例】 200 50.000 00 100 100.000 00,【问题分析】 使用栈来模拟实现。读入撤销时，栈顶元素出栈；读入溶液时，把新的溶液的质量和浓度压栈。每
