题意 一个 元集合（允许元素相同），要找一个 元子集，使得能在原集合中选出尽可能多的该集合。多种方案输出字典序最小的。 解法1：枚举答案（本该TLE却没有） 可以考虑枚举相同子集的数目。（范围在 ）对于每个待验证的答案，统计各相同元素最多分别能在每个子集中放几个。若它们的和不小于 则为合法方案。若最后个数多于 ，去掉大的部分 代码 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 返回找到能够满足游戏胜利条件的子集，如果有多个子集满足条件，返回字典序最...

题意 称一个 的排列为波浪形的排列当且仅当 ，。求 的第 个波浪形的排列。 解法1：DFS（TLE） 不妨把波列形的排列看成小虫的游走。小虫从 的任意点，任意方向出发，选择前方任意一个未访问过的点，到达后掉头。这样最终产生一个排列。 可以按字典序暴力搜索所有排列，第 个排列即为答案。 下图为 的DFS树： 代码 const int N=25; class Solution { public: /** * * @param n int整型 木棒的个数 * @param k long长整型 第k个排列 * @return int...

题意 有 个冰淇淋需要运输，每个冰淇淋有一个完成时间。货车一次能运 个，来回均要 分钟，求运走所有冰淇淋的时间。 解法1：DP 将冰淇淋按完成时间排序，显然最优方案每次运送的一定是时间相邻的一段冰淇淋。记 dp[i] 为运送完第 个冰淇淋再返回的最早时间。可以得到递推式 ，另外用数组 计算运输次数。可以递推求解，最终答案是 代码 class Solution { public: /** * 两个数表示答案 * @param n int整型 一次运输的冰激凌数量 * @param m int整型 总冰激凌数 * @param t in...

题意 一个数列 满足递推关系 ，， 。给定 ，求 的值。 解法1：直接递推（TLE） 直接按递推式依次求出 。 代码 const int mod=1000000007; class Solution { public: /** * 输出序列的第n项 * @param n long长整型 序列的项数 * @param b long长整型 系数 * @param c long长整型 系数 * @return long长整型 */ long long nthElement(long long n, long lon...

题意 给定数组 满足 ，特别地， 。 或 。 起初这些数均未被标记。每次可以在未标记的数中任选一个 ，并标记下标在 中的所有数。求将所有数均标记所需的期望次数。 解法1：状压DP（MLE+TLE） 我们用一个 位二进制数 表示 中元素被标记的状态（第 位的 表示 被标记， 表示 不被标记）。 用 表示标记过程中出现 状态的概率， 表示出现 状态所需的期望步数。 设 为 状态中 的个数， 为选择 时可标记的集合，则有转移方程 转移方程中出现分数，因此需要利用逆元计算。线性递推逆元的公式为 代码 const int mod = 99824435...

题意 在所有不同的组合数值中，求出第 小的值。 解法1： set（TLE+MLE） 注意到 ，因此只需考虑第 行的所有值，输出其中第 大的值即可。 求 一般有如下几种方法（代码中采用了第3种）： 利用公式 直接求。 利用公式 进行递推。 利用公式 进行递推。 由于可能出现重复值（比如 ），因此需要进行去重。 可以用一个 set 进行维护。 代码 class Solution { public: /** * * @param k int整型 * @return int整型 */ int kthSamllest(int...

A 给定一棵 n n n个节点的树（ n ≤ 1000 n\le 1000 n≤1000），需要把所有边定向，使得恰好有m个点没有出边，求方案数。 Solution 记 d p [ u ] [ x ] [ 0 / 1 ] dp[u][x][0/1] dp[u][x][0/1]为以 u u u为节点的子树，除 u u u外有 x x x个节点没有出边，且 u u u有/无往子节点的出边的方案数。 若 v v v为 u u u的子节点，则状态转移方式如下: 连边为 v → u v\rightarrow u v→u d p [ u ] [ x + Δ x ] [ 0 ] + = d p...

D 给定一棵 n ( n ≤ 2 e 5 ) n(n\le 2e5) n(n≤2e5)个点的有根树，每个点有点权，选出一些点，使得这些点的满足大根堆 的性质，求最多可以选多少点。 如果是一条链，就是求LIS，做法是维护一个单调队列。 树的话，其实也可以用单调队列，不过需要对不同儿子节点的队列进行合并。 可以考虑用multiset，进行启发式合并。 E 有 n ( n ≤ 2 e 5 ) n(n\le 2e5) n(n≤2e5)个点，其中 s s s个是特殊点。有 m ( m ≤ 5 e 5 ) m(m\le 5e5) m(m≤5e5)条候选边。需要求一棵最小生成树，使得恰好有 w w ...

G 一个圆周的 m m m等分点编号分别为 1 ∼ n 1\sim n 1∼n， n n n只蟋蟀分别在编号 A 1 , A 2 , . . . , A n A_1,A_2,...,A_n A1​,A2​,...,An​的点上。每秒，第 i i i只蟋蟀跳到 A i A_i Ai​关于 A i + 1 A_{i+1} Ai+1​对称的点上。求 t t t秒后每个蟋蟀的位置。 首先，把编号 n n n改成 0 0 0。 即求 [ x k + t ] ( 2 − x ) t ∑ i = 0 n − 1 A i x i 1 − x n ( 0 ≤ k ≤ n − 1 ) [x^{k+t}] \f...

Day0 开幕式 就听了一大堆发言，就这么过去了。 热身赛 拿到题面，队友果断切了D题和C题，接下来我们就开始看B。 B题是一个博弈，就是有 n n n堆石子，每堆 A i A_i Ai​个，每个回合可以从1~2堆中取任意多个。然后问 L i ≤ A i ≤ R i L_i\le A_i\le R_i Li​≤Ai​≤Ri​的条件下先手必败局面的数目。 于是开始分析，起初以为取2堆的话必须取一样多，然后猜想是3进制的“异或”，对照一下样例发现不对，又重新读题。 后来开始从简单情况一步步分析： 1堆先手胜 2堆先手胜 3堆相等时后手胜，否则先手胜 4堆没推完 莫非，，3堆相等的可以消去？...

A 求满足 0 ≤ x ≤ a , 0 ≤ y ≤ b , 0 ≤ z ≤ c , 0 ≤ k ≤ d 0\le x\le a, 0\le y\le b, 0\le z\le c, 0\le k\le d 0≤x≤a,0≤y≤b,0≤z≤c,0≤k≤d的整数 x , y , z , k x,y,z,k x,y,z,k有多少组。 答案即： ∑ i = 0 d [ x i ] 1 − x a + 1 1 − x 1 − x b + 1 1 − x 1 − x c + 1 1 − x = ∑ i = 0 d [ x i ] ( 1 − x a + 1 ) ( 1 − x b + 1 ) ( 1...

Day 0 准备工作 环境懒得测了，听别的队说是C++14还是C++17的什么特性用不了？反正我们都是C语言码风，不怎么在乎。 队友FEZ嫌桌面不好看，换了个阳间的电脑桌面 打印机坏了，热身赛结束后又整了半天 热身赛 A 初始有 1 ∼ n 1\sim n 1∼n共 n n n个数，每次随机选取两个数删除，若它们互质则获得1分，求得分期望。 第一眼：这就不是 [ n 2 ] [\frac{n}{2}] [2n​]吗？后来发现是题面第2段断句断错了。不然题目也太水了吧 要判断两个元素是否互质，它们是完全随机选取的，那不就是算数学期望嘛？直接 O ( n 2 ) O(n^2) O(n2...

Erdos-Gallai定理 数列 ( d 1 , d 2 , . . . , d n ) ( n − 1 ≥ d 1 ≥ d 2 ≥ . . . ≥ d n ≥ 0 ) (d_1,d_2,...,d_n)(n-1\ge d_1\ge d_2\ge ...\ge d_n\ge 0) (d1​,d2​,...,dn​)(n−1≥d1​≥d2​≥...≥dn​≥0)可简单图化的充要条件是： ∑ i = 1 n d i \sum_{i=1}^nd_i ∑i=1n​di​为偶数 ∀ r ( 1 ≤ r ≤ n ) , ∑ i = 1 r d i ≤ r ( r − 1 ) + ∑ i =...

纯Markdown语法：Markdown官网 KaTeX语法：KateX官网 HTML语法（Markdown不完全支持）：HTML教程