Absoler

分类

Java开发(1) MFC(1) 动态规划(5) 图论(7) 基本算法(6) 字符串(3) 思维(2) 搜索(7) 数学(2) 数据结构(4) 未归档(29) 杂项(1) 树(2) 模板(3) 真题(9) 计算几何(1)

/ 注册

TA的专栏 9篇文章 0人订阅

9篇文章 1279人学习

全部文章（共9篇）

NC20663 dp 来自专栏

这题数据还是有点水啊，，四重循环过了。看到有大佬做了优化不过暂时没研究。关键步骤是想到我们按列划分子状态，每处理一个子三角后可以在它右边“贴上”一列技能点，贴上的边不能长于原三角右侧边长度+1，我们用dp[i][j][k]表示从左至右的第i列选了j个技能，总使用技能点数k情况下的最大收益，就可以写出...

每日一题 dp

2020-08-25

1 675

NC19798 前缀和来自专栏

https://ac.nowcoder.com/acm/problem/19798 水题。推推公式发现，最终的答案等于求和（数列a的所有区间和w(区间长度)）。对于每一个区间长度k，共有n-k+1个区间和它对应。并且这些区间的区间和总和呈现出一种累加的、三角形式的关系，例如样例中k=2时区间和总和...

每日一题

2020-07-20

0 730

NC20265 计数+记忆化搜索来自专栏

https://ac.nowcoder.com/acm/problem/20265 补充数据范围：k<=15, c<=5我们尝试着模拟给砖块着色的过程，已经处理完[1,l]区间时，l+1位置可以安放除了color[l]之外任何一种颜色的砖块。这是一个很显然的状态转移的过程，接下来思考如...

每日一题

2020-07-17

0 665

NC14393 基础树上问题来自专栏

https://ac.nowcoder.com/acm/problem/14393 最初看到题目说父节点序号一定小还以为要搞什么大动作用树剖……结果想多了。在树上相距小于1的店就是自己、父亲、孩子们。为了O（1）计算每次这些点的权值和，我们记录三个数组（看代码,,cnt123），分别表示x被选中次...

每日一题

2020-07-15

0 600

NC20272 简单dfs 来自专栏

给一块矩形蛋糕，要求切成等面积的n个矩形，且长宽比的最大值最小。首先题目中的切n-1刀是很自然的，不需要去管，因为每一刀只能把一块切成两块，所以任何分割情况都是合法的。接下来看到n最大是10，那就很可能是指数级或阶乘级的算法，自然想到dfs。怎么搜呢？我们枚举每一刀的位置即可，对于当前矩形假如要把它...

每日一题

2020-07-14

0 867

NC20252 区间dp 来自专栏

https://ac.nowcoder.com/acm/problem/20252 字符串最长50，求压缩后的最短长度。这题的关键在于M。如果只有R，那么就是基础的区间dp，每次可以压缩时令dp(l,r) = min(dp(l,r), dp(l,mid)+1)，三重循环搞定。多出了规定“M”改变...

每日一题区间dp

2020-07-13

0 790

NC19810（dp）来自专栏

https://ac.nowcoder.com/acm/problem/19810这题有个结论比较好猜……题目大意是，给定n要求构造一棵权值最大的树，如果一个点是父亲的重儿子，那么权值等于父亲，否则等于父亲权值+1，根权值=0。设i个节点的树的最大权值是dp[i]，然后当我们想构造一棵大小为n的树时...

每日一题

2020-07-10

0 688

NC16645（基础区间dp+高精度）来自专栏

https://ac.nowcoder.com/acm/problem/16645 这道题唯一需要注意的就是高精度了吧……思路很简单，首先发现可以每行单独处理，用dp[l,r]表示选择lr区间内的最大收益，有公式然后就在n2内处理一行，n3处理整个矩阵即可。值得一提的是高精度__int128不能在...

每日一题

2020-07-09

0 703

NC14254 Color（Vizing定理）来自专栏

题目链接 https://ac.nowcoder.com/acm/problem/14254 题目大意：给一个二分图（n<=1e3，m<=2e3），要求对它的边进行染色，相邻边（即有公共点的边）不能是同一种颜色，问最少用多少种颜色（k）能完成染色任务，并输出一组可行解（每条边的颜色为1...

每日一题二分图 Color

2020-07-09

2 1279