HBUACM

没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录，请你统计一下他们抢红包的收获。 输入格式:输入第一行给出一个正整数N（≤104），即参与发红包和抢红包的总人数，则这些人从1到N编号。随后N行，第i行给出编号为i的人发红包的记录，格式如下： K N1 P1 ⋯ NK PK 其中K（0≤K≤20）是发出去的红包个数，N*i是抢到红包的人的编号，P*i（>0）是其抢到的红包金额（以分为单位）。注意：对于同一个人发出的红包，每人最多只能抢1次，不能重复抢。 输出格式:按照收入金额从高到低的递减顺序输出每个人的编号和收入金额（以元为单位，输出小数点后2位）。每个人的信息占一行，两数字间有1个空格。如果收入金额有并列，则按抢到红包的个数递减输出；如果还有并列，则按个人编号递增输出。 输入样例:1234567891011103 2 22 10 58 8 1255 1 345 3 211 5 233 7 13 8 1011 7 88002 1 1000 2 10002 4 250 10 3206 5 11 9 22 8 33 7 44 10 55 4 ...

对于在中国大学MOOC（http://www.icourse163.org/ ）学习“数据结构”课程的学生，想要获得一张合格证书，总评成绩必须达到 60 分及以上，并且有另加福利：总评分在 [G, 100] 区间内者，可以得到 50 元 PAT 代金券；在 [60, G) 区间内者，可以得到 20 元PAT代金券。全国考点通用，一年有效。同时任课老师还会把总评成绩前 K 名的学生列入课程“名人堂”。本题就请你编写程序，帮助老师列出名人堂的学生，并统计一共发出了面值多少元的 PAT 代金券。 输入格式:输入在第一行给出 3 个整数，分别是 N（不超过 10 000 的正整数，为学生总数）、G（在 (60,100) 区间内的整数，为题面中描述的代金券等级分界线）、K（不超过 100 且不超过 N 的正整数，为进入名人堂的最低名次）。接下来 N 行，每行给出一位学生的账号（长度不超过15位、不带空格的字符串）和总评成绩（区间 [0, 100] 内的整数），其间以空格分隔。题目保证没有重复的账号。 输出格式:首先在一行中输出发出的 PAT 代金券的总面值。然后按总评成绩非升序输出进入名人堂的学 ...

给定一个单链表 L1→L2→⋯→Ln−1→Ln，请编写程序将链表重新排列为 Ln→L1→Ln−1→L2→⋯。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。 输入格式:每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N (≤105)。结点的地址是5位非负整数，NULL地址用−1表示。 接下来有N行，每行格式为： 1Address Data Next 其中Address是结点地址；Data是该结点保存的数据，为不超过105的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。 输出格式:对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。 输入样例:123456700100 600000 4 9999900100 1 1230968237 6 -133218 3 0000099999 5 6823712309 2 33218 输出样例:12345668237 6 0010000100 1 9999999999 5 1230912309 2 0000000000 4 332183 ...

河北大学2022寒假萌新程序设计训练每日知识分享-day02 每日分享——0x3f3f3f3f在算法竞赛中，我们常常需要用到设置一个常量用来代表“无穷大”。比如对于int类型的数，有的人会采用INT_MAX，即0x7fffffff作为无穷大。但是以INT_MAX为无穷大常常面临一个问题，即加一个其他的数会溢出。而这种情况在动态规划，或者其他一些递推的算法中常常出现，很有可能导致算法出问题。所以在算法竞赛中，我们常采用0x3f3f3f3f来作为无穷大。0x3f3f3f3f主要有如下好处： 0x3f3f3f3f的十进制为1061109567，和INT_MAX一个数量级，即10^9^数量级，而一般场合下的数据都是小于10^9^的。 0x3f3f3f3f * 2 = 2122219134，无穷大相加依然不会溢出。 可以使用memset(array, 0x3f, sizeof(array))来为数组设初值为0x3f3f3f3f，因为这个数的每个字节都是0x3f memset这个函数是把array的每个字节都赋值成第二个参数（因为他的头文件是cstring嘛)，一个int数字,每个字节都是0 ...

河北大学2022寒假萌新程序设计训练每日知识分享-day01 每日分享——《C++Primer》写算法题常使用C++语言，因为它的运行效率相对来说较高，而且相比于C语言，也有很好用的STL库。这是一本很好的C++语言教程，适合学过一门编程语言，打算成为专业C++开发者人的阅读。此书是语言教材，不是语言规格书，它并没有面面俱到地谈到C++的每一个角落，而是重点讲解C++程序员日常生活中真正有用的、必须掌握的语言设施和标准库。这本书用语非常严谨，用词平和，讲解细致，读起来并不枯燥。当然写算法题也几乎使用不到C++中面向对象，模版等知识，但是如果有空闲时间，系统学习一下C++也非常不错。

农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数L*i个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是L*i的总和。 但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。 请编写程序帮助农夫计算将木头锯成N块的最少花费。 输入格式：输入首先给出正整数N（≤104），表示要将木头锯成N块。第二行给出N个正整数（≤50），表示每段木块的长度。 输出格式：输出一个整数，即将木头锯成N块的最少花费。 输入样例：1284 5 1 2 1 3 1 1 输出样例：149 思路回忆下离散中或是人工智能数学基础中所学的最优二叉树，本题即为将给定的n个结点构建最优二叉树，输出非叶子结点值的和 根据最优二叉树（也叫赫夫曼树）的构建方法，我们每轮操作需要找到剩余结点中最 ...

给定一个单链表 L1→L2→⋯→L n−1 → L n，请编写程序将链表重新排列为 L n→L1→L n−1→L2→⋯。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。 输入格式：每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N (≤105)。结点的地址是5位非负整数，NULL地址用−1表示。 接下来有N行，每行格式为： 1Address Data Next 其中Address是结点地址；Data是该结点保存的数据，为不超过105的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。 输出格式：对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。 输入样例：123456700100 600000 4 9999900100 1 1230968237 6 -133218 3 0000099999 5 6823712309 2 33218 输出样例：12345668237 6 0010000100 1 9999999999 5 1230912309 2 0000000000 4 ...

知识点：前缀和 输入一个长度为 n 的整数序列，接下来再输入 m 个询问，1≤n,m≤100000。 每个询问输入一对 l,r，1≤l≤r≤n。 对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。 输入格式：第一行包含两个整数 n 和 m。 第二行包含 n 个整数，表示整数数列，−1000≤数列中元素的值≤1000。 接下来 m 行，每行包含两个整数 l 和 r，表示一个询问的区间范围。 输出格式：共 m 行，每行输出一个询问的结果。 输入样例：123455 32 1 3 6 41 21 32 4 输出样例：1233610 思路题目已经给了提示啦：前缀和 如果暴力计算，每次都遍历区间[l,r]，复杂度最坏是O(mn) 使用前缀和数组pre，记录pre[i]记录前i个数的和，复杂度最坏是O(m) 知识点：一维数组前缀和 上次CSP的第二题，可以使用二维数组前缀和优化，才能满分。邻域均值 代码如下是前缀和计算，最坏复杂度O(m) 12345678910111213141516171819202122232425#include <iostream>#include ...

将N个整数按从小到大排序的冒泡排序法是这样工作的：从头到尾比较相邻两个元素，如果前面的元素大于其紧随的后面元素，则交换它们。通过一遍扫描，则最后一个元素必定是最大的元素。然后用同样的方法对前N−1个元素进行第二遍扫描。依此类推，最后只需处理两个元素，就完成了对N个数的排序。 本题要求对任意给定的K（<N），输出扫描完第K遍后的中间结果数列。 输入格式：输入在第1行中给出N和K（1≤K<N≤100），在第2行中给出N个待排序的整数，数字间以空格分隔。 输出格式：在一行中输出冒泡排序法扫描完第K遍后的中间结果数列，数字间以空格分隔，但末尾不得有多余空格。 输入样例：126 22 3 5 1 6 4 输出样例：12 1 3 4 5 6 思路以下假设是进行升序排序： 冒泡排序：依次比较两相邻元素，如果后面的大于前面的，则交换，进行(n-1)轮，第k轮会确定第k大的数的最终位置 冒泡排序复杂度O(n2)，效率低，也是理解其余复杂排序方法的基础 知识点：冒泡排序 代码1234567891011121314151617181920212223242526272829303132#inc ...

众所周知，ln是一个dalao，lty是一个five，现在lty问ln，你能将n个数字进行选择法排序使其从小到大有序吗？ln觉得这个问题很简单，然后就反问lty，你能在这个的基础上，输出进行k轮选择法排序的结果吗？lty是个弱鸡，当然不会，于是向你请教这个问题，你能替lty解决这个问题吗？ 给你n个数字，输出将这n个数字经过k轮选择法排序后的结果。 选择法排序：遍历整个数组，第一轮遍历第1位到第n位，找到最小的与第1位交换，第二轮遍历第2位到第n位，找到最小的与第2位交换，以此类推。（每轮只交换一次） 输入格式：输入在第1行中给出N和K（1 ≤ K < N ≤ 100），在第2行中给出N个待排序的正整数，数字间以空格分隔。 输出格式：在一行中输出选择法排序扫描完第K遍后的中间结果数列，数字间以空格分隔，但末尾不得有多余空格。 输入样例：126 22 3 5 1 6 4 输出样例：11 2 5 3 6 4 思路以下假设是进行升序排序： 选择排序：依次从数组中选出最小、第2小、第3小。。。的数，放到数组的第1、第2、第3。。。个位置。选择(n-1)次排序完成 第k轮会确定第k小的数 ...