散文網(wǎng) » 生活 »日常 » Educational Codeforces Round 99(A~E)

Educational Codeforces Round 99(A~E)

2022-06-23 18:35 作者:Asunataisiki 0人讀過 | 我要投稿

A.Strange Functions

題意：定義一個(gè)數(shù)? $x$ ?的翻轉(zhuǎn)? $f(x)$ ?為：將其從低位到高位寫成一個(gè)新數(shù)并去掉前導(dǎo)零。求對于所有的? $1%5Cleq%20i%5Cleq%20x$ ?，? $g(x)%20%3D%20%5Cfrac%7Bi%7D%7Bf(f(i))%7D%20$ 的取值有多少種。

思路： $f(f(x))$ 相當(dāng)于把x的后綴0給去除，所以有多少種那么就看這個(gè)數(shù)有多少位就可以了

B.Jumps

題意：

你當(dāng)前站在數(shù)軸的原點(diǎn)? $0$ ?處，你要移動(dòng)到數(shù)軸上的一個(gè)正整數(shù)點(diǎn)? $x$ ?處。

假如你當(dāng)前的位置是? $y$ ?，正在進(jìn)行第? $k$ ?次操作，你可以做出以下兩種移動(dòng)：

移動(dòng)到位置? $y + k$
移動(dòng)到位置? $y-1$

試求移動(dòng)到點(diǎn)? $x$ ?的最小步數(shù)。

思路：首先容易想到一直執(zhí)行第一個(gè)操作，如果正好跳到x那么直接輸出答案，如果跳遠(yuǎn)了再一步一步倒退，但是這是不正確的，我們考慮把其中某些步地?fù)Q成第二個(gè)操作

1 + 2 + 3 + 4 + 5 +... + k = sum

-1 + 2 + 3 + 4 + 5 + ... + k = sum - 2

1 + -1 + 3 + 4 + 5 + ... + k = sum - 3

可以發(fā)現(xiàn)，如果把第k步替換成第二種操作，那么對答案將會(huì)減少k + 1個(gè)貢獻(xiàn)，因此判斷sum與最后答案的差值即可，如果差一，那么最后需要倒退一步，輸出 k + 1，其余輸出k即可

C.Ping-pong

題意：

Alice 和 Bob 在玩乒乓球。

在一輪比賽中，發(fā)球的人開始比賽。發(fā)球員擊球，接球員回球。此后，發(fā)球員和接球員必須交替擊球，直到其中一方不擊球。不擊球的一方輸?shù)暨@輪比賽，獲勝方在下一輪比賽開始發(fā)球。由 Alice 開始第一輪比賽。

Alice 有? $x$ ?點(diǎn)體力， Bob 有? $y$ ?點(diǎn)體力，每次擊球會(huì)消耗 1 點(diǎn)體力。如果體力不足則不能擊球。每輪比賽開始的一方如果有體力必須發(fā)球。如果兩人都沒有體力則游戲結(jié)束。

Alice 和 Bob 都采取最優(yōu)策略進(jìn)行游戲。他們希望首先最大化自己獲勝的場數(shù)，其次最小化對方獲勝的場數(shù)。

計(jì)算 Alice 和 Bob 獲勝的場數(shù)。

思路：手摸一下a的體力大于b的體力，相等，小于三種情況發(fā)現(xiàn)，第一個(gè)輸出x - 1, 第二個(gè)輸出y就可以了，然后大膽交一發(fā)就過了

首先，如果雙方都要求勝場最多，那么一定是自己的所有發(fā)球?qū)κ侄疾唤樱敲丛诖饲闆r下，當(dāng)a的體力還剩下1的時(shí)候，b要a贏得少一些，那么就打回去，而a接不了，所以a贏x - 1次，b贏y次

D.Sequence and Swaps

題意：給出一個(gè)序列和?一個(gè) $x$ ，每次可以把序列中的一個(gè)大于 $x$ 的數(shù)與? $x$ ?交換，問最少操作多少次使得整個(gè)序列升序排序，如果不能輸出?-1。

思路：如果有 $a_%7Bi%20-1%7D%3Ea_i$ 且 $a_%7Bi-1%7D%20%3E%20x$ ，那么就需要將 $a_%7Bi-1%7D$ 與 $x$ 交換，那么可以發(fā)現(xiàn)，如果要操作后序列任然不降，那么還需要滿足 $a_%7Bi%20-%202%7D%20%5Cleq%20x$ ，那么遞推回去之后發(fā)現(xiàn)，對于每一個(gè)滿足 $a_%7Bi%20-1%7D%3Ea_i$ 且 $a_%7Bi-1%7D%20%3E%20x$ 都是要替換的，所以每次替換后檢查當(dāng)前序列是否滿足條件就可以了

E.Four Points

題意：在二維平面給出四個(gè)點(diǎn)，移動(dòng)其中的點(diǎn)，求讓這四個(gè)點(diǎn)成為一個(gè)邊平行于 $x$ 軸與 $y$ 軸的正方形的最小步數(shù)(邊長可以為0)

思路：4個(gè)點(diǎn)全排列枚舉所有組合，設(shè)左上、右上，左下，右下的點(diǎn)分別為 $p_0$ , $p_1$ , $p_2$ , $p_3$ ,先討論 $x$ 坐標(biāo)的情況， $y$ 坐標(biāo)同理

假設(shè)最終正方形左邊兩點(diǎn)的橫坐標(biāo)為 $x_1$ ，右邊兩點(diǎn)的橫坐標(biāo)為 $x_2$ ，那么四個(gè)點(diǎn)移動(dòng)的代價(jià)為 $%7Cp_0%20.x-%20x_1%7C%2B%7Cp_2.x-x_1%7C%20%2B%20%7Cp_1.x-x_2%7C%2B%7Cp_3.x-x_2%7C$ ，那么如果有 $min(p_0.x%2Cp_2.x)%5Cleq%20x_1%5Cleq%20max(p_0.x%2Cp_2.x)$ ，那么 $p_0$ 與 $p_2$ 在橫坐標(biāo)上的代價(jià)是最小的，代價(jià)為 $max(p_0.x%2Cp_2.x)%20-%20min(p_0.x-p_2.x)$ ?（兩點(diǎn)間橫坐標(biāo)的距離）， $x_2$ 同理，那么此時(shí)邊長就是 $%7Cx_2-x_1%7C$ 同時(shí)根據(jù)定義域也有一個(gè)取值范圍，縱坐標(biāo)同理，邊長為 $%7Cy_2-y_1%7C$

那么現(xiàn)在來討論 $%7Cx_2-x_1%7C$ 和 $%7Cy_2-y_1%7C$ 取值，如果二者有交集，那么就可以取到這個(gè)交集中的數(shù)，讓答案為 $%7Cp_0%20.x-%20x_1%7C%2B%7Cp_2.x-x_1%7C%20%2B%20%7Cp_1.x-x_2%7C%2B%7Cp_3.x-x_2%7C$

+? $%7Cp_0.y-y_1%2B%7Cp_1.y-y_1%7C%2B%7Cp_2.y-y_2%7C%20%2B%20%7Cp_3.y-y_2%7C$ ；如果二者不存在交集，那么就有一個(gè)取不到上述所說的最小值，如果離開這個(gè)最小值的范圍一個(gè)單位，那么就會(huì)產(chǎn)生兩個(gè)單位的代價(jià)，因?yàn)閮蓚€(gè)點(diǎn)都需要移出這個(gè)范圍，最后根據(jù)這些實(shí)現(xiàn)代碼即可

左圖為最小值，右圖為沒有交集而產(chǎn)生的2倍代價(jià)

標(biāo)簽：