【stack用法详解】 7-21 求前缀表达式的值（25 分） 算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指二元运算符位于两个运算数之前，例如2+3*(7-4)+8/4的前缀表达式是：+ + 2 * 3 - 7 4 / 8 4。请设计程序计算前缀表达式的结果值。 输入格式: 输入在一行内给出不超过30个字符的前缀表达式，只包含+、-、*、\以及运算数，不同对象（运算数、运算符号）之间以空格分隔。 输出格式: 输出前缀表达式的运算结果，保留小数点后1位，或错误信息ERROR。 输入样例: + + 2 * 3 - 7 4 / 8 4 输出样例: 13.0 ...

7-41 PAT排名汇总（25 分） 计算机程序设计能力考试（Programming Ability Test，简称PAT）旨在通过统一组织的在线考试及自动评测方法客观地评判考生的算法设计与程序设计实现能力，科学的评价计算机程序设计人才，为企业选拔人才提供参考标准。 每次考试会在若干个不同的考点同时举行，每个考点用局域网，产生本考点的成绩。考试结束后，各个考点的成绩将即刻汇总成一张总的排名表。现在就请你写一个程序自动归并各个考点的成绩并生成总排名表。 输入格式: 输入的第一行给出一个正整数N（≤100），代表考点总数。随后给出N个考点的成绩，格式为：首先一行给出正整数K（≤300），代...

【priority_queue用法详解】 7-29 修理牧场（25 分） 农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数Li个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是Li​​的总和。 但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。 请...

7-9 旅游规划（25 分） 有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。 输入格式: 输入说明：输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N−1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解...

7-14 电话聊天狂人（25 分） 给定大量手机用户通话记录，找出其中通话次数最多的聊天狂人。 输入格式: 输入首先给出正整数N（≤105​​ ），为通话记录条数。随后N行，每行给出一条通话记录。简单起见，这里只列出拨出方和接收方的11位数字构成的手机号码，其中以空格分隔。 输出格式: 在一行中给出聊天狂人的手机号码及其通话次数，其间以空格分隔。如果这样的人不唯一，则输出狂人中最小的号码及其通话次数，并且附加给出并列狂人的人数。 输入样例: 4 13005711862 13588625832 13505711862 13088625832 13588625832 18087...

7-22 堆栈模拟队列（25 分） 设已知有两个堆栈S1和S2，请用这两个堆栈模拟出一个队列Q。 所谓用堆栈模拟队列，实际上就是通过调用堆栈的下列操作函数: int IsFull(Stack S)：判断堆栈S是否已满，返回1或0； int IsEmpty (Stack S )：判断堆栈S是否为空，返回1或0； void Push(Stack S, ElementType item )：将元素item压入堆栈S； ElementType Pop(Stack S )：删除并返回S的栈顶元素。 实现队列的操作，即入队void AddQ(ElementType item)和出队Eleme...

7-25 朋友圈（25 分） 某学校有N个学生，形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好，形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论可以得出，如果A和B是朋友，且B和C是朋友，则A和C也是朋友。请编写程序计算最大朋友圈中有多少人。 输入格式: 输入的第一行包含两个正整数N（≤30000）和M（≤1000），分别代表学校的学生总数和俱乐部的个数。后面的M行每行按以下格式给出1个俱乐部的信息，其中学生从1~N编号： 第i个俱乐部的人数Mi（空格）学生1（空格）学生2 … 学生Mi 输出格式: 输出给出一个整数，表示...

【题目链接】 按照逆时针绕向给出一个凸多边形的 n 个顶点 P0,P1,··· ,Pn−1，再给出凸多边形内部（含边界） 一点 Q。现在要将这个凸多边形在地上无滑动地滚动一周，初始时 P0P1 边与地面接触，假设当前是 PiP(i+1) mod n 边与地面接触，那么滚动一下之后则是 P(i+1) mod nP(i+2) mod n 边与地面接触。不难发现， 从初始状态滚动 n 下之后 P0P1 边再一次与地面接触，这时认为凸多边形已经滚动了一周。现在你需要 求出凸多边形滚动一周之后点 Q 经过的轨迹长度。 输入格式 第一行包含一个整数 T，表示测试数据的组数。 接下来依次描述 T ...

【题目链接】 现在有 n 只怪兽，每只怪兽有一个体力值 HPi 和一个攻击值 ATKi。 英雄需要同时和这 n 只怪兽进行战斗。 在每一秒，首先英雄会被当前未被打倒的所有怪兽攻击，受到与这些怪兽的攻击值之和等量的伤害。 然后他要选择一只未被打倒的怪兽进行攻击。对同一只怪物进行的第 i 次攻击能对其造成 i 点伤害。 当怪兽的体力值 ≤ 0 的时候就会倒下，当所有怪兽都被打倒时战斗立即结束。 英雄需要合理地进行攻击以使战斗过程中受到的伤害之和最小，请你求出这个伤害总量。 输入格式 第一行包含一个整数 T，表示有 T 组测试数据。 接下来依次描述 T 组测试数据。对于每组测试数据：...

【题目链接】 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description Chiaki has an array of n positive integers. You are told some facts about the array: for every two elements ai and aj in the subarray al..r (l≤i Input There are multiple test cases. The ...

【题目链接】 Problem Description 糟糕的事情发生啦，现在大家都忙着逃命。但是逃命的通道很窄，大家只能排成一行。 现在有n个人，从1标号到n。同时有一些奇怪的约束条件，每个都形如：a必须在b之前。 同时，社会是不平等的，这些人有的穷有的富。1号最富，2号第二富，以此类推。有钱人就贿赂负责人，所以他们有一些好处。 负责人现在可以安排大家排队的顺序，由于收了好处，所以他要让1号尽量靠前，如果此时还有多种情况，就再让2号尽量靠前，如果还有多种情况，就让3号尽量靠前，以此类推。 那么你就要安排大家的顺序。我们保证一定有解。 Input 第一行一个整数T(1 <=...

【题目链接】 题目意思就是说要求一个边长为 n (1<=n<=2000) 的正方形，其中每一个点的值为0或1，要求1的数目不少于85000个，并且任意四个可以构成矩形的点不全为1，求满足条件的任意一个正方形，先输出一行边长，再输出正方形。 我们先考虑当n=25时，满足任意四个可以构成矩形的点不全为1的正方形之一如下图所示，找一下规律可以发现，（设 1 出现的位置为 s ）前五行， s = 0，1 的起始位置都在第0列，每输出5个数字，s = ( s + 行数 ) % n，这样就输出了前五行数字，通过观察前五行数字满足任意四个可以构成矩形的点不全为 1 ，由此推广到n=36 , ...

由于树状数组没有负数节点和0节点，(有些书上说有0节点，是为了方便理解树状数组而假设存在的虚拟节点，)，所以当排列中有负数或0的话，先将他们按照输入顺序标号，再将其从小到大排序，然后以标号为排列查找逆序数。 原理 假设数列为 5 4 3 2 1 5前面比它本身小的数有0个 4前面比它本身小的数有1个 3前面比它本身小的数有2个 2前面比它本身小的数有3个 1前面比它本身小的数有4个 所以他的逆序数为1+2+3+4=10 如果只是单纯的暴利的话，这是一种O(n2)的做法，但是我们有一种更为方便的数据结构—-树状数组，它查询和，修改单点值的复杂度为O(logn)，所以复杂度就降到...

【题目链接】 先给一个t表示案例个数，然后每一行给三个数字，表示立体的长宽高，输出立体。 比赛的时候没有想到开数组存然后遍历更新，接近两个小时的调试，修完所有bug，总算AC了。哇的一下就哭了。 一行一行纯暴力，一行一行直接输出，说多了都是泪啊。 下面是AC代码。 #include <iostream> using namespace std; int main() { int t, a, b, c, q, w, e, flag = 1; scanf("%d", &t); while (t--) { ...