Table of Contents

1. 今日概述：
2. 第一題：P1551 親戚
   1. 題目：
   2. WriteUp：
3. 第二題：讓我又愛又恨的 P1455 搭配購買
   1. 題目描述
   2. WriteUp：
4. 第三題： P2078 朋友
   1. 題目背景
   2. WriteUp：
5. 第四題： P2835 刻錄光盤
   1. 題目背景
   2. WriteUp：
6. 第五題：P2256 一中校運會之百米跑
   1. 題目背景
   2. WriteUp：
   3. 總結經驗：
7. 第六題：P2814 家譜
   1. 題目：
   2. WriteUp：
   3. 總結一下：
8. 今日總結：

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：

[10:21 start]
由于 \(n,m,p \le 5000\) 所以我們可以放心的使用路徑壓縮的并查集來做；
R 簡化一下題目：給定m對元素，每次合并兩個元素所在集合，之后維護p次詢問，每次詢問兩個元素是否同集；
T 就是基礎的并查集操作，使用路徑壓縮后均攤常數級，完全沒問題；
E 開寫；
M 就A了兩個點；
E 找到問題了，union_set 函數寫錯了，我直接將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小時的攻關克難拿下了并查集，所以今天可以使用并查集解我心頭一念了；

[10:47 start]
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：

一開始我疑惑的點是：情侶數量是不是要按排列數計算，但是我發現它問的是對數，所以答案應該是男、女數量的最小值；
[11:33 start]
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：

[15:57 start]
R 簡化一下題目：給定N個人，每個人都和一些人有聯系，聯系是單向的，問：若要分發文件，最少分發多少個，可以使所有人都有文件的拷貝；
T 我們先考慮一種情況，假如A愿意讓B拷貝，C愿意讓B拷貝，在這種情況下，如果是普通的并查集，三個人顯然共集，只需要一份即可；but，這里顯然需要兩張；
T 也就是說，這里的圖變成了有向圖，而并查集是雙向的（也就是無向）；
T 我們需要解決這個問題；
T 讓我們修改一下fa數組的定義：fa[x] 代表x可以從fa[x]得到數據；
T 每次增加關系時，只能單向操作，當然，路徑壓縮仍然可用；
T&P：修改點：合并只能是u設為v的fa[x];
E 開始編寫；
M 過了3個點，其余WA，28pts；
M 隨便改改，91pts，還剩一個點；
E 現在讓我們想想為什么；
T 還是單向的問題：合并時，若A集中u和B集中v合并，只能讓v及其以下的節點接入A集，即fa[v] = 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[value] = 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：

[21:09 start]
R 簡化一下題目：給定N個父子關系，要求維護若干次提問，找到每個人的祖先（最早的那個）；
T 我們顯然還是使用map轉換鍵值對，然后用并查集維護父子關系（和一般的并查集相比，只有合并時的父子關系有嚴格要求）
T 怎么存儲呢，每次描述父子關系時，若是map.find未找到，則加入map，并且更新；
T 這里雖然是單向圖，不過應該沒問題，畢竟一個人不會有大于一個的父親；
E 我們開始編寫；
T 寫到一半，發現了個問題，map通過value找key好像很麻煩哎，那就維護兩個map吧；
M 鬼知道我寫了init沒使用；
E 改；
M 樣例沒過，不過呢，這次非常容易就找到問題了：一個人可能連續多個兒子，我只輸入了一個；
E 改唄;
T 這個輸入真復雜啊，一直沒調好；
T 設計一下輸入吧：改成：讀入一個字符串s1，若s1[0] 為“#”，拷貝一份，讀入s2，操作；若為“+”，那么證明還沒結束這一組，對剛才的拷貝變量操作；
M 忘了continue了
E AC，用時51min；

總結一下：

1.map通過value找key很麻煩，可以維護兩個map；
2.debug順序：輸入、輸出、邊界、continue、break；

今日總結：

1.stl得學；
2.滲透測試很帥；
3.菜就多練；

“夢想只要挑戰，就能將其變成現實”–《強風吹拂》