洛谷P1220

传送门 题意:一个人一开始在一个灯柱那边,每一个灯具有一个功率,他现在要去挨个关灯,问关完所有灯的时候,这些灯泡消耗的最小功率是多少 解答:很明显的区间DP,乍一看感觉类似于P3205 [HNOI20 阅读更多…

洛谷P1654

传送门 题意:给定个概率,表示每一位是1的概率,连续个1对答案的贡献为,问贡献的期望是多少 解答:考虑DP,用表示在x位置的分数的期望,我们很容易得到,对这个式子利用概率公式展开,得到递推式,同理,得 阅读更多…

洛谷P2698

传送门 题意:一个小朋友在树上面走,从点0开始,最多可以走v步,问最多经过多少个点 解答:每走一步要么增加一个,要么不增加,那么贪心的取的话,优先走最长路径即可(保证经过的点数最多),然后对于每一个点 阅读更多…

洛谷P5322

传送门 题意:给个玩家,个城堡,个士兵,每一个玩家向每一个城堡派出士兵数量已知,你要赢某个玩家的条件是你在这个城堡派出了大于这个玩家派出士兵数量的两倍,这个时候你在第个城堡就会获得分,你有个士兵,问你 阅读更多…

P1637 三元上升子序列

传送门 题意:给一个数组,要你找到三元上升子序列,三元上升子序列的定义是对任意有,数据规模, 解答:范围太大需要离散化,离散化后表示k=j的位置的i元上升子序列有多少个,使用树状数组维护前面i-1元上 阅读更多…

牛客新生赛第六场题解

A 配对 题意:给定两个数列,求出这两个数列第K大的和的最大值 解答:从大到小排列,因为要使得前K大尽可能的大 那么范围一定是在两个数组前K大的数里面进行选择 相当于这K对数字的最小值要最大 那么只需 阅读更多…