Educational Codeforces Round 106 個(gè)人題解

2021-03-19 13:55 作者:俊杰_Charles 0人讀過 | 我要投稿

比賽鏈接：https://codeforces.com/contest/1499/

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

難度：Edu

A. Domino on Windowsill

題意：給一個(gè)? $2%5Ctimes%20n$ 的格子圖，第一排前? $k_1$ 個(gè)格子是白色，后面是黑色；第二排前? $k_2$ 個(gè)格子是白色，后面是黑色。有? $w$ 個(gè)白色? $2%5Ctimes1$ 骨牌， $b$ 個(gè)黑色? $2%5Ctimes1$ 骨牌，白色骨牌只能放在白色格子上，黑色骨牌只能放在黑色格子上，且骨牌間不能重疊，問能否將所有骨牌放到格子上。

題解：求白色區(qū)域和黑色區(qū)域分別最多能放多少骨牌，與輸入比較即可。

B. Binary Removals

題意：給一個(gè)? $01$ 串，問能否去掉一些位置，任意兩個(gè)位置不相鄰，使得最終串是單調(diào)不降的。

題解：找一個(gè)分界線，分界線左邊的? $1$ 全部去掉，右邊的? $0$ 全部去掉。如果答案存在，那么就存在一條分界線，其左邊不存在相鄰的? $1$ 且右邊不存在相鄰的 $0$ 。

C. Minimum Grid Path

題意：從? $(0%2C0)$ 走到 $(n%2Cn)$ ，只能向右或向上走，且走出的折線每段長度都為整數(shù)。若最終路線由? $k$ 條線段組成，第? $i$ 條長度為 $l_i$ ，那么總花費(fèi)為 $%5Csum_%7Bi%3D1%7D%5Ekc_il_i$ ，其中? $c_i$ 為第? $i$ 條線段的單位長度花費(fèi)，由輸入給定。在? $k%5Cle%20n$ 的條件下，求最小花費(fèi)是多少。

題解：由對(duì)稱性，不妨設(shè)最開始向右走，此時(shí)如果向右的線段有? $x$ 條，那么向上的線段就有? $x$ 或? $x-1$ 條。此時(shí)我們可以嘗試解決子問題，即當(dāng)向右的線段有? $x$ 條時(shí)的最小花費(fèi)是多少，向上的線段同理。由于這? $x$ 條線段的單位長度花費(fèi)是確定的，我們只需要讓單位長度花費(fèi)最小的線段盡量長，其他線段長度為? $1$ 即可。遍歷? $x$ 的過程需要維護(hù)最小值與花費(fèi)和，時(shí)間復(fù)雜度 $O(n)$ 。

D. The Number of Pairs

題意：給定 $c%2Cd%2Cx$ ，求有多少對(duì)正整數(shù) $(a%2Cb)$ ，使得 $c%5Ccdot%5Ctext%7Blcm%7D(a%2Cb)%E2%88%92d%5Ccdot%5Cgcd(a%2Cb)%3Dx$ 。

題解：令 $%5Cgcd(a%2Cb)%3Dg$ ， $a%3Dpg$ ， $b%3Dqg$ ，可知? $p$ 和? $q$ 互質(zhì)， $%5Ctext%7Blcm%7D(a%2Cb)%3Dpqg$ 。原式化為 $cpqg-dg%3Dx$ ，即 $pq%3D%5Cfrac%7B%5Cfrac%7Bx%7D%7Bg%7D%2Bd%7D%7Bc%7D$ 。由此可知， $g$ 一定為? $x$ 的因數(shù)。枚舉 $g$ ，可以確定? $pq$ 的值，然后算出有多少對(duì)? $p$ 和? $q$ 滿足條件即可。令 $pq%3Dy$ ，此時(shí)則需要解決? $y$ 能夠分解為多少對(duì)互質(zhì)數(shù)的乘積，可以推出答案與? $y$ 的不同質(zhì)因子個(gè)數(shù)有關(guān)，一個(gè)數(shù)不同質(zhì)因子個(gè)數(shù)可以通過歐拉篩進(jìn)行預(yù)處理，最終時(shí)間復(fù)雜度 $O(x%2BT%5Csqrt%7Bx%7D)$ 。