手機(jī)站首頁散文詩歌雜文隨筆日記小小說

散文網(wǎng) » 科技 »學(xué)習(xí) » Codeforces Round #706 個(gè)人題解

Codeforces Round #706 個(gè)人題解

2021-03-11 01:00 作者:俊杰_Charles 0人讀過 | 我要投稿

比賽鏈接：https://codeforces.com/contest/1495? https://codeforces.com/contest/1496

官方題解：https://codeforces.com/blog/entry/88533

難度：Div1&2

Div2A Split it!

題意：給定一個(gè)長(zhǎng)度為 $n$ 字符串 $s$ 與 $k$ ，問這個(gè)字符串能否劃分為 $s%3Da_1%2Ba_2%2B%5Cdots%2Ba_k%2Ba_%7Bk%2B1%7D%2BR(a_k)%2BR(a_%7Bk%E2%88%921%7D)%2B%E2%80%A6%2BR(a_1)$ 的形式，其中? $R(x)$ 表示將串? $x$ 反轉(zhuǎn)得到的字符串。

題解：易得 $a_1%2Ba_2%2B%5Cdots%2Ba_k$ 與 $R(a_k)%2BR(a_%7Bk%E2%88%921%7D)%2B%E2%80%A6%2BR(a_1)$ 是互為反轉(zhuǎn)的串，中間需要插入一個(gè) $a_%7Bk%2B1%7D$ 。找到? $s$ 中最長(zhǎng)互為反轉(zhuǎn)的前后綴長(zhǎng)度，然后與? $k$ 作比較即可。注意特判 $a_%7Bk%2B1%7D$ 為空串的情況，時(shí)間復(fù)雜度 $O(n)$ 。

Div2B Max and Mex

題意：定義? $%5Cmax(S)$ 為集合? $S$ 中的最大值， $%5Ctext%7Bmex%7D(S)$ 為集合? $S$ 中未出現(xiàn)的最小非負(fù)整數(shù)。給定? $S$ 的初始情況，然后執(zhí)行? $k$ 次將? $%5Clceil%5Cfrac%7B%5Cmax(S)%2B%5Ctext%7Bmex%7D(S)%7D%7B2%7D%5Crceil$ 插入? $S$ 中的操作，求? $S$ 中最后有多少個(gè)互不相同的數(shù)。

題解：初始時(shí)若 $%5Cmax(S)%3C%5Ctext%7Bmex%7D(S)$ ，此時(shí)必有 $S%3D%5C%7B0%2C1%2C2%2C...%2Cn-1%5C%7D$ ， $%5Cmax(S)%3Dn-1$ ， $%5Ctext%7Bmex%7D(S)%3Dn$ ， $%5Clceil%5Cfrac%7B%5Cmax(S)%2B%5Ctext%7Bmex%7D(S)%7D%7B2%7D%5Crceil%3Dn$ ，則每次執(zhí)行插入操作都會(huì)將? $%5Ctext%7Bmex%7D(S)$ 插入，最終? $S$ 中會(huì)增加? $k$ 個(gè)數(shù)。初始時(shí)若 $%5Cmax(S)%3E%5Ctext%7Bmex%7D(S)$ ，則必有 $%5Ctext%7Bmex%7D(S)%3C%5Clceil%5Cfrac%7B%5Cmax(S)%2B%5Ctext%7Bmex%7D(S)%7D%7B2%7D%5Crceil%5Cle%5Cmax(S)$ ，此時(shí)插入操作并不會(huì)改變? $%5Ctext%7Bmex%7D(S)$ 與 $%5Cmax(S)$ ，因此最終? $S$ 中最多增加? $1$ 個(gè)數(shù)。我的代碼中使用了 set 求 $%5Ctext%7Bmex%7D(S)$ ，時(shí)間復(fù)雜度 $O(n%5Clog%20n)$ ，如果使用哈希表，則復(fù)雜度可降為 $O(n)$ 。

Div2C/Div1A Diamond Miner

題意： $x$ 軸上有? $n$ 個(gè)點(diǎn)， $y$ 軸上有? $n$ 個(gè)點(diǎn)，將? $x$ 軸上的點(diǎn)一一對(duì)應(yīng)地向? $y$ 軸上的點(diǎn)連線，求連出的線段長(zhǎng)度總和最小是多少。

題解：貪心，每次將? $x$ 軸上離原點(diǎn)最近的點(diǎn)與? $y$ 軸上離原點(diǎn)最近的點(diǎn)相連即可，證明建議看官方題解。時(shí)間復(fù)雜度 $O(n%5Clog%20n)$ 。

Div2D/Div1B Let's Go Hiking

題意：有? $n$ 個(gè)格子排成一排，每個(gè)格子有一個(gè)高度，高度各不相同。甲首先選擇一個(gè)起點(diǎn)，然后乙再選擇一個(gè)起點(diǎn)，然后甲乙兩人輪流移動(dòng)。每次可以往左或往右移動(dòng)一格，甲只能往比當(dāng)前位置低的格子移動(dòng)，乙只能往比當(dāng)前位置高的格子移動(dòng)。輪到某人時(shí)如果他不能移動(dòng)，則對(duì)方獲勝。若兩人都采取最優(yōu)策略，問甲要獲勝的話有多少種起點(diǎn)選擇方案。

題解：首先可以知道，甲的起點(diǎn)必須選在可以往左右兩邊走的位置，即“山頂”。因?yàn)槿绻椎钠瘘c(diǎn)只能往一個(gè)方向上走，那么乙在那個(gè)方向上更低一格堵住甲即可獲勝。

當(dāng)甲選擇某個(gè)山頂作為起點(diǎn)后，乙的選擇可以有以下兩種情況：

乙從某個(gè)“山腳”出發(fā)，往甲不在的“山頂”移動(dòng)。此時(shí)甲乙兩人的路線互不影響，找到乙能走的最長(zhǎng)路線和甲能走的最長(zhǎng)路線對(duì)比即可。

乙從甲附近的“山坡”出發(fā)，往甲所處的“山頂”移動(dòng)。此時(shí)乙所選的位置與甲的距離不能為偶數(shù)，否則甲就可以往乙的方向上走從而堵住乙。當(dāng)乙按正確策略選擇起點(diǎn)后，甲不能往乙的方向上走，否則會(huì)被乙堵住。兩者路線確定后比較長(zhǎng)度即可。

對(duì)于每個(gè)山頂，判斷甲以該山頂為起點(diǎn)時(shí)，乙能否有策略戰(zhàn)勝甲，若沒有則甲可獲勝，更新答案。時(shí)間復(fù)雜度 $O(n)$ 。（補(bǔ)充：事實(shí)上，如果甲想要獲勝，那么他的起點(diǎn)必須選在下山路徑最長(zhǎng)的“山頂”上，因此答案只有? $0$ 或 $1$ 。）

Div2E/Div1C Garden of the Sun

題意：給定一個(gè)花園，表示為? $n$ 行? $m$ 列的矩陣?；▓@內(nèi)有的位置種了花，有的位置為空地，初始時(shí)每個(gè)空地周圍的八個(gè)格子不會(huì)有別的空地?，F(xiàn)需要挖出更多空地，使得原本為空地的位置互相連通，且最終空地不會(huì)形成環(huán)路。構(gòu)造一組滿足條件的方案。

題解：每隔兩行將一整行都變成空地，行與行之間找合適的位置相連，注意邊界位置的處理。

后面的題目暫未解決。

標(biāo)簽：