1.1编程基础之输入输出
第三部分数据结构第一节 队列、栈知识点：1. 队列先进先出FIFO：First In First Out，元素在队尾追加，在队首删除。queue&T&q.emtpy();//如果队列为空返回true,否则false；q.size();//返回队列中元素个数q.front();//返回队首元素q.back(); //返回队尾元素q.push(item); //将内容入队尾 q.pop(); //删除队首元素 1. 优先队列同样满足先进先出的队列性质。priority_queue&T&按照权值从大到小排序的队列，权值大的在队首，权值小的在队尾。pq.empty(); //如果队列为空返回true，否则pq.size(); //返回队列中元素的个数pq.top(); //返回队列中具有优先级最高的元素，也即队首元素pq.push(item); //将内容基于优先级插入适当位置
pq.pop(); //删除队首元素自定义优先级：bool operator &(T a, T b){
return a&b;//T类型中小的优先级高}示例1：priority_queue&int& //普通优先队列，int类型，按照从大到小排序示例2：priority_queue&int, vector&int&, greater&int&&//按照int从小到大优先队列示例3：priority_queue&int, vector&int&, less&int&& //按照int从大到小队列示例4：struct Node{int x,y;bool operator &(Node a, Node b){
return a.x &b.x;}}priority_queu&Node&//按照结构体Node中的优先级，x值小的优先级大。2. 栈后进先出的结构：LIFO（Last In First Out）stack&T&s.emtpy(); //如果栈为空，返回true，否则false；s.size(); //返回栈中元素的个数s.top(); //返回栈顶元素s.push(item); //将元素压入栈顶s.pop(); //删除栈顶元素习题：1. 纸牌游戏【题目描述】桌上有一叠牌，从第一张牌（即位于顶面的牌）开始从上往下依次编号为1~n。当至少还剩下两张牌时，进行以下操作：把第一张牌扔掉，然后把新的第一张牌放到整叠牌的最后。输入n，输出每次扔掉的牌以及最后剩下的牌【样例输入】7【样例输出】1 3 5 7 4 2 62. 舞会假设在周末舞会上，男士们和女士们进入舞池时各自排成一队。跳舞开始时，依次从男队和女队的队首各自出一人配成舞伴。规定每个舞曲只有一对跳舞者。若两队初始时人数不同，则较长一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。输入：第1行两队的人数m和n，第2行舞曲的数目k。输出：k行，每行两个整数，表示该舞曲舞伴的编号。输入 输出3 45 1 12 23 31 42 13. 约瑟夫环设有n个人依次围成一圈，从第1个人开始报数，数到第m个人出列，然后从出列的人的下一个人开始报数，数到第m个人又出列，…，反复如此直到所有人全部出列为止。设n个人的编号分别为1,2,…,n,请输出出列的顺序。【样例输入输出】输入 输出7 3 3 6 2 7 5 1 41. 排队接水学校里有一个水房，水房里共装有m个龙头可以供学生接开水，每个龙头每秒钟的供水量相同，均为1.现在有n名同学准备接水，初始接水的顺序已经确定。将这些同学按照接水顺序从1到n编号，i号同学的接水量为wi。接水开始时，1到m号同学各占一个水龙头，并同时打开水龙头接水。当其中某位同学j完成其接水量wj时，下一名排队等候的同学k马上接替j同学的位置开始接水。换人过程瞬间完成，且没有任何水的浪费。即j同学在第x秒结束，k同学第x+1秒立即开始接水。若当前接水数n‘不足m，则只有n’个水龙头供水，其他水龙头关闭。现在给出n名同学接水量，按照上述规则，问所有同学都接完水需要多少秒。【输入】第1行2个整数n和m，用一个空格隔开，分别表示接水人数和龙头个数；第2行n个整数w1,w2,…wn，每两个数之间用空格隔开，wi表示i号同学的接水量。【输出】只有1行一个整数，表示接水所需总时间。2. 火车站【题目描述】每辆火车都从A方向驶入火车站，再从B方向驶出火车站，同时它的车厢可以进行某种方式的重新组合。假设从A方向驶来的火车有n节车厢(n&=1000)，分别按顺序编号为1,2,3，…n。假设进入车站之前每节车厢之间都是不连接的，并且它们可以自由移动，直到驶入B方向上的铁轨上。另外假设C站可以停放任意节车厢，但一旦进入C，只能去B，不能向A回退，一旦进入B，就不能回到C了。试判断从B方向驶出的a1，a2，…，an的顺序是否是合理的。 输入格式：第一行整数n，表示n辆车厢第二行n个元素，表示期待B出现的排列情况输出格式：YES或者NO表示这个序列是否可行【样例输入输出】输入 输出51 2 3 4 5 YES55 4 1 2 3 NO3. 括号配对【题目描述】假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，但需要成对出现。即([ ]( ))或 [([ ][ ])]等为正确的格式，[ ( ] )或 ( [ ( ) )或( ( ) ] )均为不正确的格式。给定一串括号输入（换行作为结束符），检测格式是否正确，若正确输出YES；错误输出NO。【样例输入】([]())【样例输出】YES4. 猜猜数据结构【题目描述】你有一个类似“包包”的数据结构，支持两种操作：1 x：把元素x放入包包中2：从包包中拿出一个元素。给出一系列操作以及返回值，你的任务是猜猜这个包包到底是什么。它可能是一个栈（后进先出），队列（先进先出），优先队列（数值大的整数先出）或者其他什么奇怪的东西。【输入格式】输入包含多组数据。每组数据第一行为一个整数n（1≤n≤1000）。以下n行每行要么是一条类型1的命令，要么是一条类型2的命令后面跟着一个整数x（1≤x≤100）。这个整数x表示执行完这条类型2的命令后，包包无错误的返回了x。输入结束标志为文件结束符（EOF）。输入文件不超过1MB【输出格式】对于每组数据，输出一行，一共5种可能的输出：输出 备注stack 一定是一个栈queue 一定是一个队列priority queue 一定是一个优先队列impossible 肯定不是栈、队列或者优先队列（甚至有可能不存在这样的包包）not sure 栈、队列、优先队列中至少有两种是可能的。【样例输入输出】输入 输出 输入 输出61 11 21 32 12 22 361 11 21 32 32 22 121 12 2 queuenot sureimpossible 41 21 12 12 271 21 51 11 32 51 42 4 stackpriority queue练习题：poj3614（奶牛晒太阳）poj2051（工作时间）poj2970（程序员）poj1442（黑盒子） 栈，队列第二节 堆堆可以视为一棵完全二叉树。完全二叉树：如果一个深度为k的二叉树，1至k-1层的结点都是满的，即满足2i-1，只有最下面的一层的结点数小于2i-1，并且最下面一层的结点都集中在该层最左边的若干位置。最大堆：堆中最大元素存放在根节点，且每个结点的子树中的结点值都小于该结点的值。最小堆：堆中最小元素存放在根节点，且每个结点的子树中的结点值都大于该结点的值。两个主要操作：put操作（往堆里加入元素） get操作（删除堆顶元素）并维护堆性质。利用库函数，头文件#include &algorithm& 实现put()以及get()函数：
典型例题：合并果子【问题描述】在一个果园里，多多已经将所有的果子打了下来，而且按照果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能的节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。【输入】输入包含两行，第一行一个整数n(1&=n&=30000)，表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai(1&=ai&=20000)是第i种果子的数目。【输出】输出包含一行，这一行只包含一个整数，即最小的体力耗费值。【样例输入输出】输入 输出31 2 9 15103 5 1 7 6 4 2 5 41 120【数据范围】30%的数据： n&=1000;50%的数据： n&=5000;100%的数据：n&=30000【题目解析】多种思路（1）利用最小堆，每输入一个维护最小堆性质；（2）priority_queue.堆排序：时间复杂度为O(nlogn)，模板：
第三节 线段树动态统计问题：有一个包含n个元素的整数数组A，可以进行以下两种操作：(1) 每次可以修改一个元素(2) 每次可以查询一个区间[l,r]内所有元素之和/最大值/最小值如何设计算法，使得修改和查询操作时间复杂度尽量低？解决方案：一、 朴素的数组模拟方法：对于操作(1)，修改元素，时间复杂度：O(1)对于操作(2)，区间查询，依次访问A[l,…,r]的每个元素并累加，时间复杂度：O(n)如何能够提高查询的效率？优化思想：区间加法例如：A[1…100]= A[1…50]+A[51…100]，如果已知A[1…50]和A[51…100]则只需要一次运算。二、 线段树的思想：通过对区间信息的维护，加速查询操作，使得修改以及区间求和的操作时间均为O(logN).线段树是一棵完全二叉树，树中的每个结点表示了一个区间[p,r]。每个叶子节点表示了一个单位区间。对于每个非叶子节点所表示的区间[p,r]，左子节点表示的区间为[p+1,m]，右子节点表示的区间为[m,r]，其中m=(p+r)/2; 线段树的根节点表示了所要处理的最大线段区间，而叶子节点则表示了形如[a,a]单位区间。一棵[1,10]的线段树的结构如图所示： 线段树的性质：1. 线段树是一个平衡树，树的高度为logN2. 线段树把区间上的任意一条长度L的线段都分成不超过2logL条线段的并3. 任意两个结点的关系，要么是包含关系，要么没有公共部分，不可能部分重叠。4. 对于给定一个叶子p，从根到p路径上所有结点（即p的所有直系祖先）代表的区间都包含点p，且其他结点代表的区间都不包含点p；线段树的基本存储结构和操作1. 线段树的基本存储结构线段树的一个节点的最基本存储结构如下：struct Node {int left,int sum,};其中left和right分表代表该节点所表示线段的左右端点，即当前节点所表示的线段为[left,right]。在实际解决问题中，需要根据题目要求，在节点中添加各种数据结构，例如添加sum保存[left,right]区间和，lazy表示当前区间的元素是否有累加值。2. 线段树的建立在对线段树进行操作前，我们需要建立起线段树的结构。使用结构体数组来保存线段树，对于非叶子节点，若它在数组中的编号为n，则其左右子节点编号分别为2*n以及2*n+1。由于线段树是满二叉树结构，可以用递归的方法从根节点建立一个树。 3. 线段树的修改操作为了在插入线段后能够知道哪些节点的线段是被插入（覆盖）过的，我们需要在节点中添加一个lazy变量，记录当前节点所表示的线段是否被覆盖。在建树过程中，lazy初始化为0.在线段的修改过程中，从根节点开始，采用递归的方法。如果待修改的线段完全覆盖当前节点所代表的区域，则将当前节点的lazy设为修改值并返回，否则将线段递归进入当前节点的左右子节点进行修改。4. 线段树的统计操作对应不同的问题，线段树会统计不同的数据，比如线段覆盖的长度，线段覆盖连续区间的个数等。现讲解统计线段覆盖长度的思路：从根节点开始搜索整棵线段树，如果当前节点所代表的线段已经覆盖，则将统计长度加上当前线段长度，否则，递归进入当前节点的左右子节点进行统计。 1. A Simple Problem with Integers(poj 3468)现有N个整数A1，A2,…,AN，要处理两种操作：一是需要将给定一段区间内所有数都加上特定的值，另一个操作位查询给定区间所有数的和。输入：第一行给出两个数N和Q(1&=N,Q&=100000)。第二行包含N个整数：A1,A2,…,AN, -109&=Ai&=109.接下来有Q行，每行表示一个操作：“C a b c”：区间[a,b]之间所有的值Aa, Aa+1, …, Ab都加c(-10000&=c&=10000)“Q a b”：查询区间[a,b]之间所有数的和。输出：对于每一个Q命令给出查询结果，每个结果占一行。(注意结果可能会超过32位整数)样例输入输出：输入 输出10 51 2 3 4 5 6 7 8 9 10Q 4 4Q 1 10Q 2 4C 3 6 3Q 2 4 4559152. Hotel(poj 3667)Hotel有N个房间(1&=N&=50000)，所有的房间都是连续排列在同一边，一个团队需要入住房间，要求一个团队的房间编号为连续的，也即从r,…r+Dj-1，并且r第最小的。游客随时可以退房，每次退房的编号为连续的Xi,…,Xi+Di-1（1&=Xi&=N-Di+1）。你的任务是协助Hotel管理M(1&=M&50000)组入住及退房的要求，在初始时，房间都为空。输入：第一行为两个用空格隔开的整数N和M，分别表示N个房间以及M组入住/退房请求；接下来M行，每行一个请求，有两种格式（a）用空格隔开的两个整数表示一个入住请求：1 Di （b）用空格隔开的三个整数表示退房:2 Xi Di输出：对于每一个入住要求，输入一个整数r，表示即将入住的连续的房间中的第一个房间编号，如果该请求无法满足请输出0.样例输入输出：样例输入 样例输出10 61 31 3 1 31 32 5 51 6 14705练习题：poj3264（区间最值查询），poj3277（City Horizon），poj2528，poj2828，poj2886， poj2777，poj2750，poj2482(star)， poj2823第四节 二叉索引树（树状数组）动态连续和查询问题，给定一个n个元素的数组A1,A2,…,An，任务是设计一个数据结构，支持以下两种操作：1. Add(x,d): 让Ax增加d2. Query(L,R): 计算A[L]+A[L+1]+…+A[R]数据结构一：线段树，效率O(nlogn)，程序实现复杂数据结构二：二叉索引树(Binary Indexed Tree, BIT)，又称树状数组引入lowbit，对于正整数x，lowbit(x)为x的二进制表达式中最右边的1所对应的值，比如38288的二进制是0000,所以lowbit(38288)=16(二进制是10000)。实际计算中lowbit(x)=x&(-x);c数组的具体含义如图所示： c[1] = a[1]c[2] = a[1]+a[2]c[3] = a[3];c[4] = a[1]+a[2]+a[3]+a[4]…c[2^n]=a[1]+a[2]+…+a[2^n]求和和add数值：
1. 乒乓比赛（LA 4329）一条大街上住着n个乒乓球爱好者，经常组织比赛切磋技术，每个人都有一个不同的技能值ai，每场比赛需要3个人：两名选手，一名裁判。他们有一个奇怪的规定，即裁判必须在两名选手的中间，并且技能也必须在两名选手之间。问一共能够组织多少种这样的比赛。输入格式：输入第一行为数据组数T(1&=T&=20).每组数据占一行，首先是整数n(3&=n&=20000)，然后是n个不同的整数，即a1,a2,…,an(1&=ai&=100000), 按照住所从左往右的顺序给出每个乒乓爱好者的技能值。输出格式：对于每组数据，输出比赛总数的值。2. star(poj2352)天文学家经常观察星象图，星象图用平面上的点来表示一颗星星，每一颗星星都有一个笛卡尔坐标，设定星星的等级为其左下角星星的总数，天文学家们想知道星星等级的分布情况。 如上图，5号星星的等级为3（左下角有编号为1,2,4的星星），2号星星和4号星星的等级为1，在上图中只有一颗星星等级为0，两颗星星等级为1，一颗星星等级为2，一颗星星等级为3.给定一个星象图，请写程序计算各个等级星星的数目。输入：输入的第一行包含星星的总数N(1&=N&=15000).接下来N行，描述星星的坐标(X,Y)（X和Y用空格分开，0&=X,Y&=32000）.星象图中每个点处最多只有一颗星星。所有星星按照Y坐标升序排列.Y坐标相等的星星按照X坐标升序排列。输出：输出包含N行，每行一个整数。第一行包含等级为0的星星数目，第二行包含等级为1的星星数目，以此类推，最后一行包含等级为N-1的星星的数目。样例输入输出输入 输出51 15 17 13 35 5 12110练习题：poj2481、poj3067、poj3468、poj2299第五节 RMQ问题范围最小值查询问题（Range Minimum Query）。用Sparse-Table表，简称ST表，预处理时间为O(nlogn)，查询时间O(1)，常数系数也不大。令d[i][k]表示：从第一个数开始，连续2k个元素中的最小值。 利用动规：d[i][k] = min{d[i][k-1], d[i+2k-1][k-1]}预处理所有的d[i][k]后，即可利用d[i][k]的值求区间最小值，预处理时间为O(nlogn)。询问区间[L,R]之间的最小值，k=floor(log(R-L+1))，则区间最小值为:min{d[L[k],d[R-2k+1][k]} 预处理： 查询： 典型例题：频繁出现的数值uva11235【问题描述】给出一个非降序排列的数组a1,a2,…,an，你的任务是对于一系列询问(i,j)，回答ai,ai+1,…,aj中出现次数最多的值所出现的次数。【输入格式】输入包含多组测试数据。每组数据第一行为两个整数n个q(1&=n,q&=100000)。第二行包含n个非降序排列的整数a1,a2,…,an,(-100000&=ai&=100000)。以下q行每行包含两个整数i和j(1&=i&=j&=n)，输入结束标志为n=0。【输出格式】对于每个查询，输出查询结果。【题目解析】非降序列中所有相等的元素都集聚在一起，所以可以编码，例如-1,2,2,2,3,3,4，可以编码成(-1,1),(2,3),(3,2),(4,1)，其中(a,b)表示有b个连续的a。用value[i]和count[i]分别表示第i段的数值和出现的个数。num[p],left[p],right[p]分别表示位置p所在的段的编号和左右端点的位置。每次查询[L,R]的结果，可以分成以下3个部分：从L到L所在字段的结束，共right[L]-L+1个元素从R所在字段的开始到R，共R-left[R]+1个元素中间第num[L]+1段到num[R]-1段的count的最大值，典型的RMQ问题。 练习题：poj3264，poj3368
想要评论吗？
，如果您已经注册，请先君，已阅读到文档的结尾了呢~~
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
GCC程序设计问题
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口每组数据第一行输入一个整数n（2&&n&&10）表示有n个字
14-10-21 &匿名提问您所在位置： &
&nbsp&&nbsp&nbsp&&nbsp
(C语言练习题数组.docx 14页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：60 &&
(C语言练习题数组
你可能关注的文档：
··········
··········
Problem C: 颠倒字符串Time Limit: 1 Sec??Memory Limit: 64 MBSubmit: 3015??Solved: 1665Description输入一个以回车结束的字符串(少于80个字符)，将字符串的内容颠倒过来再输出Input多组测试数据，每组输入一个以回车结束的字符串（少于80个字符）。Output将这个字符串颠倒过来输出Sample InputABC XYZMy godSample OutputZYX CBAdog yMHINTProblem D: 更改大小写Time Limit: 1 Sec??Memory Limit: 64 MBSubmit: 2848??Solved: 2110Description将输入一行字符串(小于80个字符)，将其中的所有小写字母改为大写，其他字符不变。Input输入一行字符串，以回车结束。Output将字符串中小写字母改大写后输出。Sample InputThere are 3 pens.Sample OutputTHERE ARE 3 PENS.HINTProblem E: 统计元音字母数 Time Limit: 1 Sec??Memory Limit: 64 MBSubmit: 1659??Solved: 1256Description输入一行字符串，统计字符串中所有英文字母中的各元音字母'a/A'、'e/E'、'i/I'、'o/O'、'u/U'的个数Input输入一行字符串(少于80个字符)，以回车结束。Output逐行输出字符串中各元音字母'a/A'、'e/E'、'i/I'、'o/O'、'u/U'的个数。 Sample InputThere are 10 ducks.Sample Output13001HINTProblem F: 加密程序2Time Limit: 1 Sec??Memory Limit: 64 MBSubmit: 1892??Solved: 1203Description有一行电文，请将电文中大写字母按A→Z，B→Y，C→X, D→W,……，X→C，Y→B，Z→A，的规律译成密文，其他字符保持不变。Input多组测试数据，每组输入一行以回车结束的字符串（少于80个字符）。Output输出加密后的字符串。Sample InputABCDEFabcdefg?123hello WORLD 890Sample OutputZYXWVUabcdefg?123hello DLIOW 890HINTProblem G: 判断回文字符串Time Limit: 1 Sec??Memory Limit: 64 MBSubmit: 2370??Solved: 1343Description输入一字符串（少于80个字符），所谓“回文：是指顺读和倒读都一样的字符串，如“XYZYX”。若是回文，以输出“Yes”，否则“No”。Input多则测试数据，每组输入一字符串（少于80个字符）。Output若是回文，以输出“Yes”，否则输出“No”。Sample InputXYZYXHOWAREYOUSample OutputYesNoHINTProblem H: 统计每个字母个数Time Limit: 1 Sec??Memory Limit: 64 MBSubmit: 603??Solved: 170Description输入一段英文（字数小于100），以回车结束，统计其中的每个字母出现次数,不区分大小字。Input多组测试数据，每组输入一段英文（字数小于100），以回车结束Output输出每个字母出现的次数(次数为零的不输出) 每组数据后面输出一个空行Sample InputWelcome to c world.Sample Outputc: 2d: 1e: 2l: 2m: 1o: 3r: 1t: 1w: 2HINTProblem I: 加密程序Time Limit: 1 Sec??Memory Limit: 64 MBSubmit: 491??Solved: 301Description有一行电文，请将电文中所有字母按A→F，B→G，……，U→Z，V→A，W→B，X→C，Y→D，Z→E，a→f，b→g，……，u→z，v→a，w→b，x→c，y→d，z→e的规律译成密文，其他字符保持不变。 Input多组测试数据，每组输入一行以回车结束的字符串（少于80个字符）。Output输出加密后的字符串。Sample InputThere are 5 ducks.Sample OutputYmjwj fwj 5 izhpx.HINTProblem J: 零起点学算法80——逆序输出（数组练习）Time Limit: 1 Sec??Memory Limit: 64 M
正在加载中，请稍后...