RBTREE'S HOME

Snowflake

◆◆ 祝大家 2024 新年快乐！
新的一年，大家有事没事多留点评论吧（
这个可能稍微有点小错位不要太在意（划掉

数学杂记（更新于 20241122）

3 条评论 杂事 No tags
@1 强迫症的投掷器 20240420$n$ 个东西，每次等概率随机一个东西摸一下。问期望几次能摸过所有 $n$ 个东西。显然第一次一定会摸到一个新东西。考虑期望多少次操作能拿到第二种新东西。显然有 $\frac{n - 1}n$ 的概率摸到新东西，于是期望次数就是 $\frac n{n - 1}$ 次。再摸到第三个东西的期望次数就是 $\frac n{n - 2}$ 次。于是总答案就是$$...

Dantzig's Simplex Method

0 条评论 学习笔记 Matrix Math Linear Programming
OverviewDantzig's simplex method is used to solve the following linear programming problem.Minimize $z = \mathbf c^{\mathrm T} \mathbf x$Subject to $A\mathbf x \leq \mathbf b$ and $\mathbf x \geq 0...

CF1519F Chests and Keys

0 条评论 做题笔记 Dynamic Programming Flows
Problem StatementAlice and Bob play a game. Alice has got $n$ treasure chests (the $i$-th of which contains $a_i$ coins) and $m$ keys (the $j$-th of which she can sell Bob for $b_j$ coins).Firstly,...

CF2147E Maximum OR Popcount

0 条评论 做题笔记 Greedy
Problem StatementYou are given an array of $n$ non-negative integers.You want to answer given $q$ independent scenarios. In the $i$-th scenario, you are allowed to perform the following operation a...

Boids Algorithm

0 条评论 杂事 No tags
OverviewLet us watch a demo first. Go to https://boids.rbtr.ee/ to see further.As you can see, the Boids algorithm is a method to simulate the movements of social creatures.AlgorithmThe Boids algo...

CEOI 2023 Grading Server

0 条评论 做题笔记 Dynamic Programming
Grading ServerDespite running low on oil, the opening ceremony was a great success. Now, the committee is looking forward to the first competition day. But what’s this? The chairman of the Technica...

BalticOI 2022 Vault

0 条评论 做题笔记 Dynamic Programming DP-Optimize
VaultThere are $2M + 1$ kinds of weights, whose mass are $-M, -M + 1, \ldots, M - 1, M$. However, you do not have an infinite number of weights. For each mass $\ell$, there are only $A_{\ell}$ such...

CSES 2421 Counting Reorders

0 条评论 做题笔记 No tags
Counting ReordersCalculate the number of ways you can reorder the characters of a string so that no two adjacent characters are the same.For example, the answer for aabc is $6$, because the possibl...

CSES 2429 Grid Completion

0 条评论 做题笔记 No tags
Grid CompletionYour task is to create an $n \times n$ grid whose each row and column has exactly one $\texttt A$ and $\texttt B$. Some of the characters have already been placed. In how many ways c...

CSES 2176 Counting Bishops

0 条评论 做题笔记 Dynamic Programming
Counting BishopsYour task is to count the number of ways $k$ bishops can be placed on an $n \times n$ chessboard so that no two bishops attack each other.Two bishops attack each other if they are o...

CSES 3400 Raab Game II

0 条评论 做题笔记 Dynamic Programming
Raab Game IIConsider a two player game where each player has $n$ cards numbered $1, 2, \ldots, n$. On each turn both players place one of their cards on the table. The player who placed the higher ...