MENU

贪心

Solution. LG10218 [省选联考 2024] 魔法手杖

Description

给你 $n$ 个 $[0,2^k)$ 中的整数 $a_1,a_2,\dots,a_n$,第 $i$ 个数对应代价 $b_i$。

你需要选取一个 $U=\{1,2,\dots,n\}$ 的子集 $S$,满足 $\sum_{i\in S} b_i\le m$,以及一个 $[0,2^k)$ 中的整数 $x$,最大化 $\min\{\min_{i\in S}\{a_i+x\},\min_{i\in U\setminus S}\{a_i\oplus x\}\}$。

共 $T$ 组数据。

$1\le n\le 10^5,1\le \sum n\le 5\times 10 ^5,0\le k\le 120,0\le m\le 10^9,0\le b_i\le 10^9$

Read More

做题笔记 2023.10

CF838C Future Failure

这个游戏性质非常好,因为两个操作其实是独立的,无论进行哪种操作都不会使游戏局面发生太大的变动。

Read More

Solution. CF802N&O April Fools' Problem

Description

两个长度为 $n$ 的序列 $a_{1\dots n}$ 和 $b_{1\dots n}$,选择 $i_{1\dots k}$ 和 $j_{1\dots k}$,使得 $i_p\le j_p$,最小化 $\sum (a_{i_p}+b_{j_p})$。

Medium $1\le k\le n\le 2200$ 4s

Hard $1\le k\le n\le 500000$ 10s

Read More

Solution. CF1329D Dreamoon Likes Strings

Description

我们称相邻字符不同的字符串是美丽的。

给定字符串 $s_{1\dots n}$,每次操作可以删除 $s$ 的一个美丽子串,剩下的字符会按照原来的顺序拼接起来。

求将 $s$ 变成空串的最小步数。

$n\le2\times10^5$

Read More