散文網(wǎng) » 生活 »日常 » AtCoder Beginner Contest 251（D ~ F）

AtCoder Beginner Contest 251（D ~ F）

2022-05-15 16:43 作者:Asunataisiki 0人讀過 | 我要投稿

D.At Most 3 (Contestant ver.)

題意：給一個值 $W$ ，要求構(gòu)造一個大小不超過300的數(shù)組，并且每個數(shù)不超過1e6，從數(shù)組中最多選擇三個數(shù)求和后，保證1- $W$ 之間的所有數(shù)都至少出現(xiàn)過一次，輸出數(shù)組大小以及數(shù)字

思路：考慮6位數(shù)如何去構(gòu)造，一個六位數(shù)可以形如abcdef，那么最多選三個數(shù)，很容易想到將六個位置分成三份，即ab0000 + cd00 +?ef，那么單獨(dú)看ab, cd, ef，都可以用1~99來表示，這樣總共就99*3個數(shù)字，不會超過300個

?

E.Takahashi and Animals

題意：有 $W$ 個物品，每個物品有自己的價(jià)格，如果花費(fèi) $a_i$ 的價(jià)格購買第 $i$ 個物品，那么可以免費(fèi)獲得第 $i%2B1$ 個物品，且如果購買第 $n$ 個物品，那么可以免費(fèi)獲得第一個物品，問獲得所有物品的最小花費(fèi)

思路：考慮? $dp%5Bi%5D%5B0%2F1%5D$ ?表示前? $i-1$ ?個物品已經(jīng)是最小花費(fèi)，第? $i$ 個物品是否購買的最小花費(fèi)是多少，如果不購買第? $i$ ?個，那么第? $i-1$ ?個物品必須購買，那么轉(zhuǎn)移方程為 $dp%5Bi%5D%5B0%5D%20%3D%20dp%5Bi%20-%201%5D%5B1%5D$ ，如果購買第? $i$ ?個，那么第? $i-1$ ?個物品可以買也可以不買，取小的轉(zhuǎn)移過來就行了， $dp%5Bi%5D%5B1%5D%20%3D%20min(dp%5Bi%20-%201%5D%5B0%5D%2C%20dp%5Bi%20-%201%5D%5B1%5D)%20%2B%20a%5Bi%5D$ ，對于最后一個物品，我們單獨(dú)拿出來討論，進(jìn)行兩次? $dp$ ，取最小值就可以了

F.Two Spanning Trees

題意：給出一張圖 $G$ ，現(xiàn)在要對這張圖求兩個生成樹 $T_1%2CT_2$ (可以相同)，要求如下

$T_1$ ?：對于在 $G$ 中的邊 $%5C%7Bu%2Cv%5C%7D$ 并且這條邊不在 $T_1$ 中，生成樹中 $u%0A$ 是的祖先節(jié)點(diǎn) $v$ ，或者 $v$ 是的祖先節(jié)點(diǎn) $u%0A$

$T_2$ ?： $T_2$ 中沒有不包含 $G$ 的邊 $%5C%7Bu%2Cv%5C%7D$ ，使得 $u%0A$ 和 $v$ ?中的一個是 $T_2$ 中另一個的祖先（沒有在生成樹中的邊 $%5C%7Bu%2Cv%5C%7D$ ，在生成樹中? $u%0A$ （ $v$ ）也不是 $v$ （ $u%0A$ ）?的祖先）

思路：對于 $T_1$ ，就是求一個 $dfs$ 樹，因?yàn)榉?img type="latex" class="latex" src="http://api.bilibili.com/x/web-frontend/mathjax/tex?formula=dfs%0A" alt="dfs%0A">樹邊都是返祖邊，正好符合題意； $T_2$ 就是求 $bfs$ 樹，如果根節(jié)點(diǎn)是1，同層節(jié)點(diǎn)如果連邊，而不連1到這個節(jié)點(diǎn)，那么這個節(jié)點(diǎn)與1還是存在祖孫關(guān)系；如果不是同層節(jié)點(diǎn)，如果兩個點(diǎn)沒有連邊，那么這兩個點(diǎn)也就沒有祖孫關(guān)系。