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 ...

河北大学暑期程序设计训练每日知识分享-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 ...

河北大学暑期程序设计训练每日知识分享-day24 每日分享——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数字,每个字节都 ...

河北大学暑期程序设计训练每日知识分享-day23 每日分享——可保存多次复制内容-Ditto可以保存多次复制内容的软件，Ditto Ditto是剪贴板增强工具，免费开源且支持中文（开源就是说大概率能在github找到这个软件的源代码，可以下载下来自己魔改自己用）保存多次复制的内容，打开近期内容面板后选择一个用于粘贴，包括图片等非文字格式的复制也可，可以自己设置保存多少条近期复制的信息和一些快捷键避免在做题调试代码时重复的复制测试点、复制代码提交 软件安装包见群文件。 小彩蛋：STL中的next_permutation()函数可以计算全排列，示例如下。