熠丶

题解

未归档(32)

/ 注册

做想做的事，见想见的人

全部文章 / 题解（共156篇）

Sand Fortress 来自专栏

做法：二分思路主要讲一下如何二分分三种情况1）一直下降2）先上升再不变后下降，且不变的长度为13）先上升后下降设第2、3种情况的最高峰为t此时，从而求得注意会爆long long 代码 #include <bits/stdc++.h> using namespace st...

2021-03-18

1 932

[HAOI2015]树上染色来自专栏

做法：树形dp 思路设siz[i]为以u为根的子树大小（包括u），dp[i][j]为以u为根的子树有j个黑点的最大收益之后是对于下面代码的解释for(int i=min(k,siz[u]);i>=0;i--)对于该节点子树的黑点的枚举（逆序可以考虑一维01背包做法）for(int j=0;j...

2021-03-17

0 678

Tower of Hay 来自专栏

思路设cnt[i]表示当前层摆放的宽度，h[i]表示当前层摆放的最大高度因为上层的宽度不能超过下层的宽度，所以我们可以从后往前优先考虑上层宽度利用前缀和的思想来求放在同一层合并后的宽度代码 // Problem: Tower of Hay // Contest: NowCoder // ...

2021-03-16

2 730

[HNOI2004]打鼹鼠来自专栏

做法：dp 思路设dp[i]为打死第i个鼹鼠时，最多打死鼹鼠的个数（一定打死第i个鼹鼠的情况）因为游戏开始时，你可以自由选定机器人的初始位置，一定会打死一只鼹鼠，所以初始化把dp[i]设为1 之后枚举前后两只鼹鼠，如果距离小于等于时间，说明在这时间内能打死两只鼹鼠，同时更新答案即可代...

2021-03-16

2 662

[HAOI2012]容易题(EASY) 来自专栏

做法：数论+快速幂+离散化思路如果不删任何数的话就是设不能取的值和为那么结果就是不能取的值最多有1e5，我们可以采用离散化来存没有限制的数我们可以采用快速幂来计算注意要判重代码 // Problem: [HAOI2012]容易题(EASY) // Contest: NowCo...

2021-03-13

1 759

[HAOI2016]字符合并来自专栏

做法：状压dp+区间dp 样例解释第 3 行到第 6 行表示长度为 2 的 4 种 01 串合并方案。00→1，得 10 分，01→1 得 10 分，10→0 得 20 分，11→1 得 30 分。思路设是在区间中状态为的最大分数因为m个字符能合并成1个字符所以我们可以求出在len...

2021-03-12

0 800

Tree Decoration 来自专栏

思路叶结点只能挂在叶结点上，而父结点可以挂在父结点上也可以挂在叶结点上所以优先从叶结点开始挂装饰品，利用叶结点的花费来更新父结点的花费，并记录该父结点下的叶结点装饰品的数量代码 // Problem: Tree Decoration // Contest: NowCoder // URL:...

2021-03-08

0 641

区区区间来自专栏

做法：线段树思路：看到区间修改区间查询联想到线段树区间内加上一个首项为k公差为1的等差数列在pushdown操作可以在左子树的lazy为当前结点的lazy，右子树的lazy为当前结点的lazy加上左子树的长度sum利用等差数列求和公式代码 #include <bits/stdc++...

2021-03-08

1 781

Tallest Cow 来自专栏

题意有n个数，其中位置b的数一定大于等于位置a的数,且a和b之间的数都比a小。已知最大的数的位置及大小。求这n个数的可能的最大值。做法：差分思路因为每个数要尽可能大，所以a和b相等，且a+1~b-1的数比a小1 区间内的数同时增大或减小某一个数可以用差分处理代码 #include &l...

2021-03-05

0 714

网格

思路把左右和上下选择分开讨论先考虑左右的情况如果右边的点选左方向，左边的点选右方向，这样的话需要计算w其他情况求最大即可上下也是这种情况代码 // Problem: 网格 // Contest: NowCoder // URL: https://ac.nowcoder.com/ac...

2021-03-02

0 606