num73

题解

/ 注册

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

小A的柱状图

小A的柱状图区间[L,R]中矩形的高度取决于[L,R]中高度的最小值。如果下一个矩形高度比当前矩形高度小，这块矩形的高度就不可能再成为满足条件的矩形的高度。于是就可以把高度比下一块矩形大的矩形都删掉，用一个高度为下一个矩形的高度，宽度为删掉的矩形宽度和下一个矩形宽度的累加和代替。用单调栈维护，更新...

题解

2020-07-26

1 707

生日快乐题解

生日快乐题解题解：这个题数据范围较小，可以直接尝试枚举所有切割情况。题目中有要求，将蛋糕分成大小相等的n块，每一次切割的线一定与一条边平行。所以首先每一刀有两种切法，与长边平行和与短边平行。为了能够将蛋糕n等分，那么当前这一刀可以是过长边的一个n等分点并与短边平行，或过短边的一个n等分点与长...

题解

2020-07-17

1 932

点权和题解

点权和题解题目分析：一道以空间换时间的题目。关键在维护什么和怎么维护才能高效地得到答案。通过仔细又认真地观察，再加上一点灵感，可以发现。每个点位置处地答案可以由这个点和与它距离小于等于2点的更新次数马上得到。设有一个点，记为v，如果我们知道下面几个量，那么此时v处的答案可以在O(1)的时间马上得...

2020-07-16

0 696

[SCOI2007]压缩题解

[SCOI2007]压缩题解很显然是一个dp。。。很妙的一个dp,很难的一个dp。。。因为M，R存在造成的不同结果，需要分类讨论。记: dp[i][j][0]为区间[i,j]不加M时最短长度 dp[i][j][1]为区间[i,j]有M时最短长度那么转移方程为：dp[i][j][0]=min(...

2020-07-15

0 773

I 1 or 2

I题题解这道题和HDU 3551是一样的。关键在拆点建图上把点v拆成d[v]个点。同时将每条边拆成2个点分别为。将相连。同时将与拆成的个点连边，将与拆成的个点连边。如题目中样例的第三组数据： 3 21 1 21 32 3 第1个点拆成1个点，编号为1。第2个点拆成1个点，编号为2。第3个点拆成...

2020-07-13

9 1166

NC19810 kingdom题解

分析：开始看到这个题的时候，我就想着去构造这样一棵树，可是构造失败了。这个题的数据范围是8000，其实已经提示了构造可能是不可行的，否则这个数据范围要更大才对。于是看了大佬的题解,想了好长时间才恍然大悟。树形结构有着很好的对称性，这种对称性是指当拿掉一个结点后，这个结点所连接的几个部分仍然是树...

2020-07-12

0 629

NC13950 Alliances题解

题目描述：一颗个节点的树。给定个点集（个帮派），编号为。第i个点集代表第i个帮派占据的点的集合。定义一个节点被占领当且仅当满足下面其中一个条件：该结点被一个帮派所占据。该结点位于被占领的两个结点的路径上。 Q个询问，每个询问给出一个点，一个数，和个数（），代表在这个询问中选取（）这个帮派，...

2020-07-08

7 949

树

分析：这个题用到了树的以下性质：如果两个节点位于同一个节点的两个不同子树上，那么这连接两个点的最短路径一定经过这个节点。根据这个性质，很显然在树中新加入一个点时，只有两种情况使用一种新的颜色使用和相连的点相同的颜色设f[i][j]表示前i个点使用j种颜色涂色的方案数于是就有了转移方程： ...

2020-05-03

1 819

数学考试dp解法

题目大意：有一个长度为n的数列，要求在这个数列中选2个不相交且长度都为k的区间，求这两个区间中数字和最大的值算法过程 A[i]表示长度为k且以i为最后一个元素的这个区间元素值的和dp[i]表示选择的第二个区间以第i个元素结尾所求和的最大值维护一个tmp，表示在前i-k个元素中长度为k的区间和最大...

2020-05-02

1 908

合并回文子串

题目大意：有两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。需要求出所有可能的C中长度最大的回文子串（这里的字串是指连续的），输出这个最大长度即可算法过程嗯，区间dp。以前没写过。学会了区间dp要按...

2020-05-02

1 882