25-8-26日记
Table of Contents[*]今日概述：
[*]第一题：P1551 亲戚
[*]题目：
[*]WriteUp：
[*]第二题：让我又爱又恨的 P1455 搭配购买
[*]题目描述
[*]WriteUp：
[*]第三题： P2078 朋友
[*]题目背景
[*]WriteUp：
[*]第四题： P2835 刻录光盘
[*]题目背景
[*]WriteUp：
[*]第五题：P2256 一中校运会之百米跑
[*]题目背景
[*]WriteUp：
[*]总结经验：
[*]第六题：P2814 家谱
[*]题目：
[*]WriteUp：
[*]总结一下：
[*]今日总结：
P.S.:今天是挑战三个月冲击省一的第15天，目前阶段：动态规划+数据结构补充（并查集）
距离csp-j2开赛还有67天
今日概述：
1.给kali安装了中文输入法
2.将kali中火狐的语言调为中文
3.刷了6道题目；
4.学了简单的nmap；
第一题：P1551 亲戚
难度：提高-，并查集基础题
题目：
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
## 题目描述
规定：\(x\) 和 \(y\) 是亲戚，\(y\) 和 \(z\) 是亲戚，那么 \(x\) 和 \(z\) 也是亲戚。如果 \(x\)，\(y\) 是亲戚，那么 \(x\) 的亲戚都是 \(y\) 的亲戚，\(y\) 的亲戚也都是 \(x\) 的亲戚。
## 输入格式
第一行：三个整数 \(n,m,p\)，（\(n,m,p \le 5000\)），分别表示有 \(n\) 个人，\(m\) 个亲戚关系，询问 \(p\) 对亲戚关系。
以下 \(m\) 行：每行两个数 \(M_i\)，\(M_j\)，\(1 \le M_i,~M_j\le n\)，表示 \(M_i\) 和 \(M_j\) 具有亲戚关系。
接下来 \(p\) 行：每行两个数 \(P_i,P_j\)，询问 \(P_i\) 和 \(P_j\) 是否具有亲戚关系。
## 输出格式
\(p\) 行，每行一个 `Yes` 或 `No`。表示第 \(i\) 个询问的答案为“具有”或“不具有”亲戚关系。
WriteUp：
由于 \(n,m,p \le 5000\) 所以我们可以放心的使用路径压缩的并查集来做；
R 简化一下题目：给定m对元素，每次合并两个元素所在集合，之后维护p次询问，每次询问两个元素是否同集；
T 就是基础的并查集操作，使用路径压缩后均摊常数级，完全没问题；
E 开写；
M 就A了两个点；
E 找到问题了，unionset 函数写错了，我直接将x的父节点设为了y；
E 13min结束，AC；
第二题：让我又爱又恨的 P1455 搭配购买
难度：提高-，并查集01背包，或者叫捆绑的01背包；
TODO 题目描述
明天就是母亲节了，电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢？听说在某个网站上有卖云朵的，小朋友们决定一同前往去看看这种神奇的商品，这个店里有 \(n\) 朵云，云朵已经被老板编号为 \(1,2,3,...,n\)，并且每朵云都有一个价值，但是商店的老板是个很奇怪的人，他会告诉你一些云朵要搭配起来买才卖，也就是说买一朵云则与这朵云有搭配的云都要买，电脑组的你觉得这礼物实在是太新奇了，但是你的钱是有限的，所以你肯定是想用现有的钱买到尽量多价值的云。
## 输入格式
第一行输入三个整数，\(n,m,w\)，表示有 \(n\) 朵云，\(m\) 个搭配和你现有的钱的数目。
第二行至 \(n+1\) 行，每行有两个整数， \(c_i,d_i\)，表示第 \(i\) 朵云的价钱和价值。
第 \(n+2\) 至 \(n+1+m\) 行 ，每行有两个整数 \(u_i,v_i\)。表示买第 \(u_i\) 朵云就必须买第 \(v_i\) 朵云,同理，如果买第 \(v_i\) 朵就必须买第 \(u_i\) 朵。
## 输出格式
一行，表示可以获得的最大价值。
## 说明/提示
[*]对于 \(100\%\) 的数据，满足 \(1 \le n, w \le 10^4\)，\(0 \le m \le 5 \times 10^3\)。
WriteUp：
之前我们已经做过了这道题，当时本来想用并查集，奈何两天前的我太菜了，压根不会写并查集，遂用了dfs代替；
不过，在“菜就多练”方针的指引下，本蒟蒻已经通过2小时的攻关克难拿下了并查集，所以今天可以使用并查集解我心头一念了；
R 简化一下题目：给定n个物品和一个容量为W的背包，物品共有m对关系，具有关系的物品必须一起购买，输出最大价值；
T 我们要做的其实就是将有关系物品捆绑销售，价值和重量都为子物品的和；
T 这个操作使用并查集维护即可，每次将有关系的物品所在集进行并集，最后遍历一遍所有物品，执行findx，这样让所有的路径都压缩一遍，随后对所有的代表元所在集合的普通元素累加，累加到代表元即可；
E 我们开始编写；
M 好吧，第一次写炸了，我想想怎么改；
E 原来，我忘了都执行一遍findx了
E 样例过了，准备提交；
E 总计23min，AC，我简直太NB了；
第三题： P2078 朋友
难度：提高-，并查集模版题；
题目背景
小明在 A 公司工作，小红在 B 公司工作。
## 题目描述
这两个公司的员工有一个特点：一个公司的员工都是同性。
A 公司有 \(N\) 名员工，其中有 \(P\) 对朋友关系。B 公司有 \(M\) 名员工，其中有 \(Q\) 对朋友关系。朋友的朋友一定还是朋友。
每对朋友关系用两个整数 \((X_i,Y_i)\) 组成，表示朋友的编号分别为 \(X_i,Y_i\)。男人的编号是正数，女人的编号是负数。小明的编号是 \(1\)，小红的编号是 \(-1\)。
大家都知道，小明和小红是朋友，那么，请你写一个程序求出两公司之间，通过小明和小红认识的人最多一共能配成多少对情侣（包括他们自己）。
## 输入格式
输入的第一行，包含 \(4\) 个空格隔开的正整数 \(N,M,P,Q\)。
之后 \(P\) 行，每行两个正整数 \(X_i,Y_i\)。
之后 \(Q\) 行，每行两个负整数 \(X_i,Y_i\)。
## 输出格式
输出一行一个正整数，表示通过小明和小红认识的人最多一共能配成多少对情侣（包括他们自己）。
对于 \(100 \%\) 的数据，\(N,M \le 10^4\)，\(P,Q \le 2 \times 10^4\)。
WriteUp：
一开始我疑惑的点是：情侣数量是不是要按排列数计算，但是我发现它问的是对数，所以答案应该是男、女数量的最小值；
R 简化一下题目：小明小红是情侣，所有跟他们认识的人都会组成情侣（当然不能同性），问最终情侣数量；
T 这道题仍然使用并查集维护，先各自维护小明、小红的集合，最后都执行一遍findx，将所有的叶节点直接连到根上，统计各自的数量，最后输出父为小明和父为小红的最小值（包括他们自己）
T 还有个问题：对于负下标应该怎么处理；这个我相信应该都会，特判即可，使用两个fa数组记录；
M 就A了一个点，20pts，我看看哪里错了；
E 合并时，不一定1号节点是根，所以最后需要判断父节点是否为1的父节点而不是为1；
E AC，总计37min，不过使用了AI查错（虽然AI哔哩吧啦一堆，只有一条有用）；
第四题： P2835 刻录光盘
难度：提高（第一个提高，终于不是提高-了），并查集基础；
题目背景
在 JSOI2005 夏令营快要结束的时候，很多营员提出来要把整个夏令营期间的资料刻录成一张光盘给大家，以便大家回去后继续学习。组委会觉得这个主意不错！可是组委会一时没有足够的空光盘，没法保证每个人都能拿到刻录上资料的光盘，又来不及去买了，怎么办呢？
## 题目描述
组委会把这个难题交给了 LHC，LHC 分析了一下所有营员的地域关系，发现有些营员是一个城市的，其实他们只需要一张就可以了，因为一个人拿到光盘后，其他人可以带着 U 盘之类的东西去拷贝啊！
可是，LHC 调查后发现，由于种种原因，有些营员并不是那么的合作，他们愿意某一些人到他那儿拷贝资料，也不愿意让另外一些人到他那儿拷贝资料，这与我们 JSOI 宣扬的团队合作精神格格不入！！！
现在假设总共有 \(N\) 个营员 \((2 \le N \le 200)\)，每个营员的编号为 \(1 \sim N\)。LHC 给每个人发了一张调查表，让每个营员填上自己愿意让哪些人到他那儿拷贝资料。当然，如果 A 愿意把资料拷贝给 B，而 B 又愿意把资料拷贝给 C，则一旦 A 获得了资料，则 B 和 C 都会获得资料。
现在，请你编写一个程序，根据回收上来的调查表，帮助 LHC 计算出组委会至少要刻录多少张光盘，才能保证所有营员回去后都能得到夏令营资料？
## 输入格式
先是一个数 \(N\) 代表有 \(N\) 个营员。接下来的 \(N\) 行，分别表示各个营员愿意把自己获得的资料拷贝给其他哪些营员。即输入数据的第 \(i+1\) 行表示第 \(i\) 个营员愿意把资料拷贝给那些营员的编号，以 \(0\) 结束。如果一个营员不愿意拷贝资料给任何人，则相应的行只有 \(0\)。一行中的数之间用一个空格隔开。
## 输出格式
一个正整数，表示最少要刻录的光盘数。
WriteUp：
R 简化一下题目：给定N个人，每个人都和一些人有联系，联系是单向的，问：若要分发文件，最少分发多少个，可以使所有人都有文件的拷贝；
T 我们先考虑一种情况，假如A愿意让B拷贝，C愿意让B拷贝，在这种情况下，如果是普通的并查集，三个人显然共集，只需要一份即可；but，这里显然需要两张；
T 也就是说，这里的图变成了有向图，而并查集是双向的（也就是无向）；
T 我们需要解决这个问题；
T 让我们修改一下fa数组的定义：fa 代表x可以从fa得到数据；
T 每次增加关系时，只能单向操作，当然，路径压缩仍然可用；
T&P：修改点：合并只能是u设为v的fa;
E 开始编写；
M 过了3个点，其余WA，28pts；
M 随便改改，91pts，还剩一个点；
E 现在让我们想想为什么；
T 还是单向的问题：合并时，若A集中u和B集中v合并，只能让v及其以下的节点接入A集，即fa = uroot；
T 好吧，翻了翻题解，这道题没法用纯并查集做，还要加上floryd
T 37min，结束，91pts；
第五题：P2256 一中校运会之百米跑
难度：提高-，评价：数据不猎奇，题目挺猎奇
题目背景
在一大堆秀恩爱的 ** 之中，来不及秀恩爱的苏大学神踏着坚定（？）的步伐走向了 \(100\) 米跑的起点。这时苏大学神发现，百米赛跑的参赛同学实在是太多了，连体育老师也忙不过来。这时体育老师发现了身为体育委员的苏大学神，便来找他帮忙。
可是苏大学神需要热身，不然跑到一半就会抽（筋）、于是他就找到了你。如果你帮助体育老师解决了问题，老师就会给你 \(5\) 个积分。
## 题目描述
假设一共有 \(N\)（\(2\leq N\leq 2\times 10^4\)）个参赛选手。
老师会告诉你这 \(N\) 个选手的名字。
接着会告诉你 \(M\)（\(1\leq M\leq 10^6\)）句话，即告诉你学生 A 与学生 B 在同一个组里。
如果学生 A 与学生 B 在同一组里，学生 B 与学生 C 也在同一组里，就说明学生 A 与学生 C 在同一组。
然后老师会问你 \(K\)（\(1\leq K\leq 10^6\)）句话，即学生 X 和学生 Y 是否在同一组里。
若是则输出 `Yes.`，否则输出 `No.`。
## 输入格式
第一行输入 \(N\) 和 \(M\)。
接下来 \(N\) 行输入每一个同学的名字。
再往下 \(M\) 行每行输入两个名字，且保证这两个名字都在上面的 \(N\) 行中出现过，表示这两个参赛选手在同一个组里。
再来输入 \(K\)。
接下来输入体育老师的 \(K\) 个询问。
## 输出格式
对于体育老师的每一个询问，输出 `Yes.` 或 `No.`。
WriteUp：
这道题，非常非常明显是并查集好吧；
R 给定N个人，以及M对人，代表两个人一队，随后维护K次询问，每次问两个人是否在一队中；
T 唯一的问题是，输入的是人名，我们需要换成数字，两种做法：1.哈希（双哈希，用孪生质数，说实话，这个应该是我唯一学会的高级技术）2.map；
T 这里当然用map啦。这么好用的东西，为什么不呢；
T 不过map我不太熟，先搜一下；
E 写完了，测样例；
M 哎？怎么没输出啊
E 好吧，原来nm一起输入啊；
E AC，用时30min；
总结经验：
1.遇到问题先看看输入输出是否有问题
2.map的插入可以用：map = key;
3.map有个find用法，返回一个pair类型，使用值需要用 it->second，当找不到时，返回尾迭代器（map.end()）;
4.注意，插入时是{key,value}，这样才能使用find(key)查找到对应的value；
5.map的本质：底层是pair；
第六题：P2814 家谱
难度：提高-，并查集基础题；
题目：
现代的人对于本家族血统越来越感兴趣。
## 题目描述
给出充足的父子关系，请你编写程序找到某个人的最早的祖先。
## 输入格式
输入由多行组成，首先是一系列有关父子关系的描述，其中每一组父子关系中父亲只有一行，儿子可能有若干行，用 `#name` 的形式描写一组父子关系中的父亲的名字，用 `+name` 的形式描写一组父子关系中的儿子的名字；接下来用 `?name` 的形式表示要求该人的最早的祖先；最后用单独的一个 `$` 表示文件结束。
## 输出格式
按照输入文件的要求顺序，求出每一个要找祖先的人的祖先，格式为：本人的名字 \(+\) 一个空格 \(+\) 祖先的名字 \(+\) 回车。
## 说明/提示
规定每个人的名字都有且只有 \(6\) 个字符，而且首字母大写，且没有任意两个人的名字相同。最多可能有 \(10^3\) 组父子关系，总人数最多可能达到 \(5 \times 10^4\) 人，家谱中的记载不超过 \(30\) 代。
WriteUp：
R 简化一下题目：给定N个父子关系，要求维护若干次提问，找到每个人的祖先（最早的那个）；
T 我们显然还是使用map转换键值对，然后用并查集维护父子关系（和一般的并查集相比，只有合并时的父子关系有严格要求）
T 怎么存储呢，每次描述父子关系时，若是map.find未找到，则加入map，并且更新；
T 这里虽然是单向图，不过应该没问题，毕竟一个人不会有大于一个的父亲；
E 我们开始编写；
T 写到一半，发现了个问题，map通过value找key好像很麻烦哎，那就维护两个map吧；
M 鬼知道我写了init没使用；
E 改；
M 样例没过，不过呢，这次非常容易就找到问题了：一个人可能连续多个儿子，我只输入了一个；
E 改呗;
T 这个输入真复杂啊，一直没调好；
T 设计一下输入吧：改成：读入一个字符串s1，若s1 为“#”，拷贝一份，读入s2，操作；若为“+”，那么证明还没结束这一组，对刚才的拷贝变量操作；
M 忘了continue了
E AC，用时51min；
总结一下：
1.map通过value找key很麻烦，可以维护两个map；
2.debug顺序：输入、输出、边界、continue、break；
今日总结：
1.stl得学；
2.渗透测试很帅；
3.菜就多练；
“梦想只要挑战，就能将其变成现实”–《强风吹拂》
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]