Monoxer Programming Contest 2022（AtCoder Beginner Contest 249）

2022-04-24 21:33 作者:Asunataisiki 0人讀過 | 我要投稿

A.Jogging

水題

B.Perfect String

題意：給你一個(gè)字符串，要求必須有大小寫字母，且不能出現(xiàn)重復(fù)的字母，符合條件輸出Yes，否則No

思路：水題

C.Just K

題意：有? $n$ ?個(gè)字符串，現(xiàn)在你可以從中隨意選取一些字符串，并且統(tǒng)計(jì)其中字符出現(xiàn)次數(shù)等于 $k$ ?的字母的數(shù)量，求這個(gè)數(shù)量的最大值

數(shù)據(jù)范圍：

$1%5Cleq%20N%5Cleq%2015$

$1%5Cleq%20K%5Cleq%20N$

思路：可以觀察到? $N$ 的范圍很小，所以可以用二進(jìn)制數(shù)直接暴力枚舉所有組合

D.Index Trio

題意：給一個(gè)長(zhǎng)度為 $n$ ?的數(shù)組? $A$ ?，求 $%5Cfrac%7BA_i%7D%7BA_j%7D%20%3D%20A_k%20$ ?的三元組? $(i%2Cj%2Ck)$ ?的個(gè)數(shù)

$1%5Cleq%20N%5Cleq%202*10%5E5$

$1%5Cleq%20a_i%5Cleq%202*10%5E5$

思路：觀察到每個(gè)數(shù)字的數(shù)字都不大，所以直接統(tǒng)計(jì)每個(gè)數(shù)字的數(shù)量，然后暴力枚舉 $A_k$

F - Ignore Operations

題意：初始 $x$ ?= 0，有 $n$ 組操作，每組操作有? $t_i%E5%92%8Cx_i$ ， $t_i$ ?? $%3D1$ ?時(shí)， $x%20%3D%20y_i$ ； $t_i$ ?? $%3D2$ 時(shí)，

$x%20%3D%20x%20%2B%20y_i$ ，你可以最多跳過? $k$ ?次操作，求最后 $x$ 的最大值

思路：可以發(fā)現(xiàn)，當(dāng) $t_i$ ?? $%3D1$ 的時(shí)候，在這之前的所有操作對(duì)之后的答案時(shí)沒有貢獻(xiàn)的，所以我們從后往前枚舉最后一次不跳過 $t_i$ ?? $%3D1$ 的操作，同時(shí)對(duì)于 $t_i$ ?? $%3D2$ ?的操作，如果已經(jīng)跳過了 $a$ 個(gè)操作，那么我們選擇前 $k-a$ 個(gè)小的數(shù)字跳過，這里可以用優(yōu)先隊(duì)列來維護(hù)前 $k-a$ ?個(gè)小的數(shù)字