HBUACM

新浪微博上有个“悄悄关注”，一个用户悄悄关注的人，不出现在这个用户的关注列表上，但系统会推送其悄悄关注的人发表的微博给该用户。现在我们来做一回网络侦探，根据某人的关注列表和其对其他用户的点赞情况，扒出有可能被其悄悄关注的人。 输入格式:输入首先在第一行给出某用户的关注列表，格式如下： 1人数N 用户1 用户2 …… 用户N 其中N是不超过5000的正整数，每个用户i（i=1, …, N）是被其关注的用户的ID，是长度为4位的由数字和英文字母组成的字符串，各项间以空格分隔。 之后给出该用户点赞的信息：首先给出一个不超过10000的正整数M，随后M行，每行给出一个被其点赞的用户ID和对该用户的点赞次数（不超过1000），以空格分隔。注意：用户ID是一个用户的唯一身份标识。题目保证在关注列表中没有重复用户，在点赞信息中也没有重复用户。 输出格式:我们认为被该用户点赞次数大于其点赞平均数、且不在其关注列表上的人，很可能是其悄悄关注的人。根据这个假设，请你按用户ID字母序的升序输出可能是其悄悄关注的人，每行1个ID。如果其实并没有这样的人，则输出“Bing Mei You”。 输入样例:123 ...

给定一个单链表 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 ...

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。 输入格式:输入在一行中给出长度不超过1000的非空字符串。 输出格式:在一行中输出最长对称子串的长度。 输入样例:在这里给出一组输入。例如： 1Is PAT&TAP symmetric? 输出样例:在这里给出相应的输出。例如： 111 思路利用双指针的思想，分别从字符串的前后进行比较，每次发现相同的就截取子串，做对称比较并更新最大长度。 代码12345678910111213141516171819202122232425#include <iostream>using namespace std;int main() { string s; getline(cin, s); int mlen = 0, clen = 0; for (int i = 0; s[i] != '\0'; i++) { for (int j = s.length() - 1; ...

河北大学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小的数 ...