dairuize-blogs

摘要： 題意 有一個 \(0 \sim n - 1\) 的排列 \(a_1 \dots a_n\)，有以下兩種詢問： 詢問一個集合 \(S\)，交互庫返回 \(\min_{x \in S} a_x + \operatorname{mex}_{x \in S} a_x\)。（這種詢問最多 \(35\) 次） 閱讀全文

摘要： 非常好玩的一道博弈論的題目，結(jié)論與證明都非常巧妙，在翻月賽題目時看到的。蒟蒻希望能盡可能地講清楚思考過程和結(jié)論的證明，如有問題請指出。 原題鏈接。 題目分析 為方便敘述，我們稱分割的人為先手，另外一個人為后手。 二分答案 \(x\)，將原序列中大于等于 \(x\) 的位置變?yōu)?\(1\)，反之變?yōu)? 閱讀全文

摘要： 蒟蒻的第一題狀壓DP紫題。 題目分析 題目轉(zhuǎn)化為在一個有權(quán)圖上，求一顆生成樹，并選擇一個根 \(rt\)，使 \(\sum_u w(u, fa_u) \times (dep_u - 1)\) 最小，其中 \(dep_{rt} = 1\) 設(shè) \(f_{i, S}\) 表示進行到深度為 \(i\)，已 閱讀全文

摘要： 非常好的一道數(shù)學(xué)題。 原題鏈接。 題目分析 我們要意識到的一點是，題目中要求的最優(yōu)策略，實際上是一個固定的報數(shù)的序列，即對于每一個數(shù)字 \(i\)，你要報 \(a_i\) 次這個數(shù)字，并要使得能拿走 \(k\) 張卡牌的概率最大。 那么最終的答案就是 \[\prod_{i = 1}^m \binom 閱讀全文