Table of Contents

1. 今日概述：
2. 取模的學習：
3. CTF之index.php.bcp泄露：
4. 第一題：# P1455 搭配購買
   1. 題目描述
   2. WriteUp：
5. 今日總結：

P.S.:挑戰3個月沖擊省一的第13天，當前階段：動態規劃之背包問題；

今日概述：

1.修了kali
2.打了3個CTF弱智題
3.完成了1個題目

取模的學習：

干了一篇blog，這里不再貼了

CTF之index.php.bcp泄露：

writeup我就不寫了，這道題很弱智；
主要是檢查一下我的Kali Linux是否可用

第一題：# P1455 搭配購買

難度：提高-

題目描述

明天就是母親節了，電腦組的小朋友們在忙碌的課業之余挖空心思想著該送什么禮物來表達自己的心意呢？聽說在某個網站上有賣云朵的，小朋友們決定一同前往去看看這種神奇的商品，
這個店里有 \(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\) 朵。

## 輸出格式
一行，表示可以獲得的最大價值。

## 說明/提示

• 對于 \(30\%\) 的數據，滿足 \(1 \le n \le 100\)；
• 對于 \(50\%\) 的數據，滿足 \(1 \le n, w \le 10^3\)，\(1 \le m \le 100\)；
• 對于 \(100\%\) 的數據，滿足 \(1 \le n, w \le 10^4\)，\(0 \le m \le 5 \times 10^3\)。

WriteUp：

[21:30 start]
R 仍然是按照我們的慣例，簡化一下題目：

給定n個物品，共有m種搭配，搭配的物品必須一起購買，一共w元，最多可以買多少的物品

T 如果去除搭配，這就是普通的01背包，所以接下來的重點就是如何處理搭配問題
T 一個顯然的做法是：將這幾個物品視為一個，價值和價錢均為各個子物體的和；
T 但是，問題在于，多物品會互相捆綁，如何最后視作一個；
T 如果我對圖論的印象沒錯的話，這里可以建圖，隨后強聯通分量，但是我已經一年沒打過圖論了，因此不考慮（而且今天的訓練目標是01背包）
T 這玩意跟那個apt（超級牛力的apt）似的，就是處理依賴
T 顯然需要一個去重的東西，這讓我想到了并查集，但是。。。我不會寫（蒟蒻本蒻）
T 那就用set吧，不用白不用；
T 我們給每個物品都開一個set，而后遍歷set中的所有成員，將他們的set也加入進來；
T 下一個問題是：可能有環，我們這里就不能再怎么做了；
T 再想想別的做法呢？
T 仍然是建圖（都是雙向的，等于無向圖），隨后對每個未訪問點執行一遍dfs，將其加入這個點的依賴關系數組，標記已訪問（這里不會出現環無法處理的情況，因為起始節點已標記）
T 完成之后做一遍01背包即可；

E AC,27min（當然，代碼是AI寫的，我沒這么多時間了，得睡覺，不過思路沒什么問題）

今日總結：

1.CTF真好玩
2.Kali真帥
3.獨立思考出來一個提高-的題目，朕甚是欣慰啊
4.圖論得學