HBUACM

7-10 深入虎穴著名的王牌间谍 007 需要执行一次任务，获取敌方的机密情报。已知情报藏在一个地下迷宫里，迷宫只有一个入口，里面有很多条通路，每条路通向一扇门。每一扇门背后或者是一个房间，或者又有很多条路，同样是每条路通向一扇门…… 他的手里有一张表格，是其他间谍帮他收集到的情报，他们记下了每扇门的编号，以及这扇门背后的每一条通路所到达的门的编号。007 发现不存在两条路通向同一扇门。 内线告诉他，情报就藏在迷宫的最深处。但是这个迷宫太大了，他需要你的帮助 —— 请编程帮他找出距离入口最远的那扇门。 输入格式：输入首先在一行中给出正整数 N（<10​5​​），是门的数量。最后 N 行，第 i 行（1≤i≤N）按以下格式描述编号为 i 的那扇门背后能通向的门： 12K D[1] D[2] ... D[K]​ 其中 K 是通道的数量，其后是每扇门的编号。 输出格式：在一行中输出距离入口最远的那扇门的编号。题目保证这样的结果是唯一的。 输入样例：1234567891011121314133 2 3 42 5 61 71 81 902 11 101 13001 1200 输出样例： ...

河北大学程序设计训练营每日分享-day03 算法书籍推荐今天是每日分享的第三天， 今天给大家推荐 适合初学者学习 数据结构与算法的书籍 算法笔记 【 算法笔记 PAT在线练习】 不仅可以作为考研机试和PAT的学习教材，对其他的一些算法考试（例如CCF的CSP考试）或者考研初试的数据结构科目的学习和理解也很有帮助 因为这本书的作者与其他大学的官方教材不同。作者出版这本书的时候也是一个大学生，所以整本书的语言风格更容易让人接受，简单易懂，而且整本书的配套的例题全部来自 PAT甲级乙级和天梯赛真题，对于小白或者有一定基础的人来说，读这本书的效率非常高，很快就能掌握基本算法的书写，这与晴神贴出的大量参考代码是分不开的。有点后悔没有早点看到这本书。 推荐大家能够完整阅读 第六章 C++ 标准模板库 咱们学校可能大部分同学都没有学习C++ ，即使学习了C++ 可能对于 STL 模板库的理解和使用也是一知半解，通过这本书可以 把之前懵懂的部分融会贯通，即使C++零基础 只要学过C语言，学习这个章节也是没有问题的。 扩展阅读除了算法笔记之外，我再推荐几本 适合训练营不同人群的算法书籍进行阅读 大话 ...

一门武功能否传承久远并被发扬光大，是要看缘分的。一般来说，师傅传授给徒弟的武功总要打个折扣，于是越往后传，弟子们的功夫就越弱…… 直到某一支的某一代突然出现一个天分特别高的弟子（或者是吃到了灵丹、挖到了特别的秘笈），会将功夫的威力一下子放大N倍 —— 我们称这种弟子为“得道者”。 这里我们来考察某一位祖师爷门下的徒子徒孙家谱：假设家谱中的每个人只有1位师傅（除了祖师爷没有师傅）；每位师傅可以带很多徒弟；并且假设辈分严格有序，即祖师爷这门武功的每个第i代传人只能在第i-1代传人中拜1个师傅。我们假设已知祖师爷的功力值为Z，每向下传承一代，就会减弱r%，除非某一代弟子得道。现给出师门谱系关系，要求你算出所有得道者的功力总值。 输入格式：输入在第一行给出3个正整数，分别是：N（≤105）——整个师门的总人数（于是每个人从0到N−1编号，祖师爷的编号为0）；Z——祖师爷的功力值（不一定是整数，但起码是正数）；r ——每传一代功夫所打的折扣百分比值（不超过100的正数）。接下来有N行，第i行（i=0,⋯,N−1）描述编号为i的人所传的徒弟，格式为： K**i ID[1] ID[2] ⋯ ID[K ...

河北大学程序设计训练营每日分享-day01 每日分享 计算机的整个体系很庞大，程序设计也不仅仅是局限在算法题目这一件事情上，在我个人看来，普通的计算机从业学者，除了基础知识，还有特定领域涨知识和使用框架开发技能。 基础知识是指不管从事任何方向的软件工程师都应该掌握的，比如数据结构、算法、操作系统。 特定领域知识就是你从事某个细分方向时需要掌握的知识，比如做游戏引擎的需要掌握图形学；做前端的需要掌握浏览器渲染原理、前端三大件；算法工程师需要更多的数学知识。（如何成为一个计算机知识体系完整的毕业生？ - 编程指北的回答 - 知乎 https://www.zhihu.com/question/68571487/answer/1575982946） 知识很多又盘根错节，碎片化学习也需要学习系统知识，才能够构建知识结构。 所以每天两三分钟的分享，不会专门介绍某一个具体的知识点，而是尽量以体系化的顺序，分享一些实用的干货经验，推荐的这些东西是我个人认为需要学习和了解的不具有普遍性，希望同学们能够跟及时分享 感受和体会。 这个分享活动是和罗老师沟通过后起草的一个全新的尝试，我们会根据大家的反馈及时做 ...

学校有N个学生，许多同学在学习中与生活中成为了朋友，据说朋友关系有自反性（自己和自己是朋友），有对称性（你和我是朋友，我和你一定也是朋友），还有传递性，即如果A和B是朋友，且B和C是朋友，则A和C也是朋友，于是就形成了许多的朋友圈。下列矩阵表示的四个人的朋友圈：i行 j列为1表示是直接的朋友关系，为0表示并非直接的朋友关系，是否是间接的朋友不清楚。输入样例中，0,1,2是一个朋友圈，3号自己是一个朋友圈。故共有2个朋友圈。请编写程序，根据给定的关系矩阵，计算学校的朋友圈数量。 注意：因为关系矩阵是对称的，故只录入了下三角的数据，也就是只描述了i号学生与其前边的学生的朋友关系，后边的关系未再复述（包括对角线上的自己：N个学生，仅输入了N*(N+1)/2个数据）。 输入样例：12345411 11 0 10 0 0 1 输出样例：输出全校学生中的朋友圈的数量（指没有交集的朋友圈）： 12 思路： 并查集应用，朋友的朋友也是朋友，1说明肯定为朋友，0不确定，对为1的情况进行合并即可 代码：1234567891011121314151617181920212223242526272829 ...

战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的k个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。 输入格式：输入在第一行给出两个整数N（0 < N ≤ 500）和M（≤ 5000），分别为城市个数（于是默认城市从0到N-1编号）和连接两城市的通路条数。随后M行，每行给出一条通路所连接的两个城市的编号，其间以1个空格分隔。在城市信息之后给出被攻占的信息，即一个正整数K和随后的K个被攻占的城市的编号。 注意：输入保证给出的被攻占的城市编号都是合法的且无重复，但并不保证给出的通路没有重复。 输出格式：对每个被攻占的城市，如果它会改变整个国家的连通性，则输出Red Alert: City k is lost!，其中k是该城市的编号；否则只输出City k is lost.即可。如果该国失去了最后一个城市，则增加一行输出Game Over.。 输入样例：12345675 40 11 33 00 451 2 0 4 3 输出样例：123456Ci ...

古人云：秀恩爱，分得快。 互联网上每天都有大量人发布大量照片，我们通过分析这些照片，可以分析人与人之间的亲密度。如果一张照片上出现了 K 个人，这些人两两间的亲密度就被定义为 1/K。任意两个人如果同时出现在若干张照片里，他们之间的亲密度就是所有这些同框照片对应的亲密度之和。下面给定一批照片，请你分析一对给定的情侣，看看他们分别有没有亲密度更高的异性朋友？ 输入格式：输入在第一行给出 2 个正整数：N（不超过1000，为总人数——简单起见，我们把所有人从 0 到 N-1 编号。为了区分性别，我们用编号前的负号表示女性）和 M（不超过1000，为照片总数）。随后 M 行，每行给出一张照片的信息，格式如下： 1K P[1] ... P[K] 其中 K（≤ 500）是该照片中出现的人数，P[1] ~ P[K] 就是这些人的编号。最后一行给出一对异性情侣的编号 A 和 B。同行数字以空格分隔。题目保证每个人只有一个性别，并且不会在同一张照片里出现多次。 输出格式：首先输出 A PA，其中 PA 是与 A 最亲密的异性。如果 PA 不唯一，则按他们编号的绝对值递增输出；然后类似地输出 B PB ...

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

布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。 输入格式：输入第一行给出3个正整数：N（≤100），即前来参宴的宾客总人数，则这些人从1到N编号；M为已知两两宾客之间的关系数；K为查询的条数。随后M行，每行给出一对宾客之间的关系，格式为：宾客1 宾客2 关系，其中关系为1表示是朋友，-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后K行，每行给出一对需要查询的宾客编号。 这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友，朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。 输出格式：对每个查询输出一行结果：如果两位宾客之间是朋友，且没有敌对关系，则输出No problem；如果他们之间并不是朋友，但也不敌对，则输出OK；如果他们之间有敌对，然而也有共同的朋友，则输出OK but...；如果他们之间只有敌对关系，则输出No way。 输入样例：123456789101112137 8 45 6 12 7 -11 3 1 ...

给定两个整数集合，它们的相似度定义为：N**c/N*t×100%。其中Nc是两个集合都有的不相等整数的个数，Nt*是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。 输入格式：输入第一行给出一个正整数N（≤50），是集合的个数。随后N行，每行对应一个集合。每个集合首先给出一个正整数M（≤104），是集合中元素的个数；然后跟M个[0,109]区间内的整数。 之后一行给出一个正整数K（≤2000），随后K行，每行对应一对需要计算相似度的集合的编号（集合从1到N编号）。数字间以空格分隔。 输出格式：对每一对需要计算的集合，在一行中输出它们的相似度，为保留小数点后2位的百分比数字。 输入样例：123456733 99 87 1014 87 101 5 877 99 101 18 5 135 18 9921 21 3 输出样例：1250.00%33.33% 思路： 看数据范围：集合中的数据最大为10^9^，大致算一下，因为2^27^ < 10^9^ < 2^36^ ，有可能超int范围，所以用long long存储比较保险 采用set数组，在存入每 ...