abcdhhhh

分类

ACM(11) 工具(1) 机器学习(1) 离散数学(1) 题解(7)

/ 注册

全部文章（共21篇）

题解 | #牛牛的分配#

题意长度为的数组，每次可以选择若干元素使元素的值变为这些元素的和的平均值给出数组和数字，求经过操作数组中最多有多少数字不小于解法1：暴力如果有一堆元素不小于，那它们的平均值一定不小于。可以枚举所有子集，分别计算平均值。代码 class Solution { public: ...

C++

2021-09-18

0 556

题解 | #牛牛找子集#

题意一个元集合（允许元素相同），要找一个元子集，使得能在原集合中选出尽可能多的该集合。多种方案输出字典序最小的。解法1：枚举答案（本该TLE却没有）可以考虑枚举相同子集的数目。（范围在）对于每个待验证的答案，统计各相同元素最多分别能在每个子集中放几个。若它们的和不小于则为合法方案...

C++

2021-09-18

0 653

题解 | #牛牛摆木棒#

题意称一个的排列为波浪形的排列当且仅当，。求的第个波浪形的排列。解法1：DFS（TLE）不妨把波列形的排列看成小虫的游走。小虫从的任意点，任意方向出发，选择前方任意一个未访问过的点，到达后掉头。这样最终产生一个排列。可以按字典序暴力搜索所有排列，第个排列即为答案。下...

C++

2021-09-18

0 501

题解|#牛牛的冰激凌

题意有个冰淇淋需要运输，每个冰淇淋有一个完成时间。货车一次能运个，来回均要分钟，求运走所有冰淇淋的时间。解法1：DP 将冰淇淋按完成时间排序，显然最优方案每次运送的一定是时间相邻的一段冰淇淋。记 dp[i] 为运送完第个冰淇淋再返回的最早时间。可以得到递推式，另外用数组计...

C++

2021-09-16

0 521

题解 | #数列求值#

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

C++

2021-09-15

0 518

题解 | #序列取反问题#

题意给定数组满足，特别地，。或。起初这些数均未被标记。每次可以在未标记的数中任选一个，并标记下标在中的所有数。求将所有数均标记所需的期望次数。解法1：状压DP（MLE+TLE）我们用一个位二进制数表示中元素被标记的状态（第位的表示被标记，...

C++

2021-09-06

0 555

题解 | #组合数第k小#

题意在所有不同的组合数值中，求出第小的值。解法1： set（TLE+MLE）注意到，因此只需考虑第行的所有值，输出其中第大的值即可。求一般有如下几种方法（代码中采用了第3种）：利用公式直接求。利用公式进行递推。利用公式进行递推。由于可能出现重复值（...

2021-09-05

0 486

BSUIR Open 2017 Finals补题

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为...

2021-05-26

0 495

NAIPC 2017补题

D 给定一棵 n ( n ≤ 2 e 5 ) n(n\le 2e5) n(n≤2e5)个点的有根树，每个点有点权，选出一些点，使得这些点的满足大根堆的性质，求最多可以选多少点。如果是一条链，就是求LIS，做法是维护一个单调队列。树的话，其实也可以用单调队列，不过需要对不同儿子节点的队列进行...

2021-05-26

0 644

Jagiellonian U Contest补题

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 +...

2021-05-26

0 553