HBUACM

在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。 输入格式：输入在第一行给出一个正整数N（≤$10^4$），是已知小圈子的个数。随后N行，每行按下列格式给出一个小圈子里的人： K P[1] P[2] ? P[K] 其中K是小圈子里的人数，P[i]（i=1,?,K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过10^4。 之后一行给出一个非负整数Q（≤$10^4$），是查询次数。随后Q行，每行给出一对被查询的人的编号。 输出格式：首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。 输入样例：1234567843 10 1 22 3 44 1 5 7 83 9 6 4210 53 7 输出样例：12310 2YN 思路简单的并查集应用，在判断有多少个部落时，可以利用STL里的set来去重，在实现find函数时，记得路径 ...

将一系列给定数字插入一个初始为空的小顶堆H[]。随后对任意给定的下标i，打印从H[i]到根结点的路径。 输入格式：每组测试第1行包含2个正整数N和M(≤1000)，分别是插入元素的个数、以及需要打印的路径条数。下一行给出区间[-10000, 10000]内的N个要被插入一个初始为空的小顶堆的整数。最后一行给出M个下标。 输出格式：对输入中给出的每个下标i，在一行中输出从H[i]到根结点的路径上的数据。数字间以1个空格分隔，行末不得有多余空格。 输入样例：1235 346 23 26 24 105 4 3 输出样例：12324 23 1046 23 1026 10 思路这道题是不断插入，不断调整，最后形成一个小顶堆。左子树的节点下标为 2 * i , 右子树的节点下标为 2 * i + 1。父节点下标为 i /2; 堆顶下标为1. 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344#include<bits/stdc++.h>using namespace st ...

病毒容易发生变异。某种病毒可以通过突变产生若干变异的毒株，而这些变异的病毒又可能被诱发突变产生第二代变异，如此继续不断变化。 现给定一些病毒之间的变异关系，要求你找出其中最长的一条变异链。 在此假设给出的变异都是由突变引起的，不考虑复杂的基因重组变异问题 —— 即每一种病毒都是由唯一的一种病毒突变而来，并且不存在循环变异的情况。 输入格式：输入在第一行中给出一个正整数 N（≤$10^4$），即病毒种类的总数。于是我们将所有病毒从 0 到 N?1 进行编号。 随后 N 行，每行按以下格式描述一种病毒的变异情况： 1k 变异株1 …… 变异株k 其中 k 是该病毒产生的变异毒株的种类数，后面跟着每种变异株的编号。第 i 行对应编号为 i 的病毒（0≤i<N）。题目保证病毒源头有且仅有一个。 输出格式：首先输出从源头开始最长变异链的长度。在第二行中输出从源头开始最长的一条变异链，编号间以 1 个空格分隔，行首尾不得有多余空格。如果最长链不唯一，则输出最小序列。注：我们称序列{a1,…,an}比序列{b1,…,bn} “小”，如果存在 1≤k≤n 满足$a^i$=$b^i$对所有 i& ...

一门武功能否传承久远并被发扬光大，是要看缘分的。一般来说，师傅传授给徒弟的武功总要打个折扣，于是越往后传，弟子们的功夫就越弱…… 直到某一支的某一代突然出现一个天分特别高的弟子（或者是吃到了灵丹、挖到了特别的秘笈），会将功夫的威力一下子放大N倍 —— 我们称这种弟子为“得道者”。 这里我们来考察某一位祖师爷门下的徒子徒孙家谱：假设家谱中的每个人只有1位师傅（除了祖师爷没有师傅）；每位师傅可以带很多徒弟；并且假设辈分严格有序，即祖师爷这门武功的每个第i代传人只能在第i-1代传人中拜1个师傅。我们假设已知祖师爷的功力值为Z，每向下传承一代，就会减弱r%，除非某一代弟子得道。现给出师门谱系关系，要求你算出所有得道者的功力总值。 输出格式在一行中输出所有得道者的功力总值，只保留其整数部分。题目保证输入和正确的输出都不超过$x^10$。 输入样例123456789101110 18.0 1.003 2 3 51 91 41 70 72 6 11 80 90 40 3 输出样例1404 思路这道题与上一道题比较类似，注意判断得道的弟子，然后计算和就可以了。 代码1234567891011121 ...

输出格式：在一行中按规定顺序输出叶节点的编号。编号间以 1 个空格分隔，行首尾不得有多余空格。 输入样例：12345678981 -- -0 -2 7- -- -5 -4 6 输出样例14 1 5 思路首先，按照题目给的数据进行建树；然后，由于题目要求从上到下、从左到右地输出所有叶节点，所以只需要层序遍历就可以了，遍历到每个节点的时候判断是否为叶节点，叶节点就是左右子树都为空。另外需要注意的是，题目没有给出根节点是哪个点，所以需要自己找根节点，只需要判断谁没做过儿子就可以了。 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include<bits/stdc++.h>using namespace std;const int maxn = 110;typedef struct node{ int l,r;}Node;Node T[maxn];int n;unordered_map<int,int> ...

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。 输入格式：输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。 输出格式：在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。 输入样例12372 3 1 5 7 6 41 2 3 4 5 6 7 输出样例14 1 6 3 5 7 2 思路这道题就是经典的根据遍历序列恢复二叉树，采用递归的方式，一步一步来即可。 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include<bits/stdc++.h>using namespace std;const int maxn = 35;typedef struct node{ int data; struct node *left; ...

河北大学暑期程序设计训练每日知识分享-day28 每日分享—— 《C++ Primer Plus》《C++ Primer Plus》这本书针对C++初学者，从C语言基础知识开始介绍，然后在此基础上详细阐述C++新增的特性，因此不要求读者有C语言方面的背景知识。 它是根据2003年的ISO/ANSI C++标准编写的，通过大量短小精悍的程序详细而全面地阐述了 C++的基本概念和技术，并专辟一章介绍了C++11新增的功能。其分为18章，分别介绍了C++程序的运行方式、基本数据类型、复合数据类型、循环和关系表达式、分支语句和逻辑运算符、函数重载和函数模板、内存模型和名称空间、类的设计和使用、多态、虚函数、动态内存分配、继承、代码重用、友元、异常处理技术、string类和标准模板库、输入/输出、C++11新增功能等内容。

河北大学暑期程序设计训练每日知识分享-day27 每日分享——单调栈&单调队列1.核心思想利用栈和队列的单调性质，优化枚举区间内极值O(n)的时间复杂度到O(1) 2. 问题特征(1)区间内的极值(最大值，最小值)(2)找当前数左(右)边第一个比当前数大(小)的数 3. 分析流程step1: 先利用普通栈(队列)给出解法step2: 删除冗余的元素，得到具有单调性的栈和队列step3: 优化枚举元素的O(n)的时间复杂度到O(1) 4. 代码模板1234567891011121314151617181920212223242526272829303132单调栈：for(int i = 0, j = x; i < n; i++){ //栈不空&&冗余元素性质 while(!is_empty() && check(a[front()], a[i])) pop(); //找到目标元素 if(!is_empty()){ xx } else { //空栈 ...

河北大学暑期程序设计训练每日知识分享-day26 每日分享——《代码整洁之道》《代码整洁之道》讲述了一系列行之有效的整洁代码操作实践。软件质量，不但依赖于架构及项目管理，而且与代码质量紧密相关。这一点，无论是敏捷开发流派还是传统开发流派，都不得不承认。《代码整洁之道》提出一种观念：代码质量与其整洁度成正比。干净的代码，既在质量上较为可靠，也为后期维护、升级奠定了良好基础。作为编程领域的佼佼者，这些实践在《代码整洁之道》中体现为一条条规则(或称“启示”)，并辅以来自现实项目的正、反两面的范例。只要遵循这些规则，就能编写出干净的代码，从而有效提升代码质量。

河北大学暑期程序设计训练每日知识分享-day25 每日分享——高精度运算高精度就是说参与运算的数据和运算结果的范围，超出标准数据类型能表示的数据大小范围的运算。这个时候，如果要得到正确的计算结果，显然不能依靠普通方法实现了。而要在普通运算原理的基础上，加以辅助算法来实现超大数据的计算。例如：求两个100位的数据的和，或者计算两个100位的数字乘积。这时就要用到高精度算法了 高精度加法C从0到C .size( )为低位到高位 12345678910111213vector<int> add( vector<int> &A, vector<int> &B ) { if ( A.size() < B.size()) return add(B,A); int t = 0; vector<int> C; for ( int i=0; i<A.size(); i++) { t += A[i]; if ( i < B.size()) t += B ...