DaMing

分类

题解(25)

/ 注册

全部文章（共25篇）

题解 | #Bheith i ngra le#

来一发B题的组合数学的解法首先考虑比较朴素的做法，枚举区间l,r枚举这个区间的值，然后用隔板法计数，复杂度O(n^3)我们用公式表示（来自官方题解）我们发现第一个式子和j没关系，第二个式子和i没关系操作一个这个公式变成那么我们只需要预处理出计为num[i][k]那么最后答案的计算可以变成这里如何处...

2021-06-14

4 873

十三届河南省赛C-Alice and Bob（尺取、前缀和、二分）

C-Alice and Bob 题目大意： m次询问，每次询问一个区间中有多少个连续的的子区间不同数的个数大于等于k（强制在线）思路：首先考虑朴素做法假设i作为左端点时向右扩展到f[i]这个区间有k个数字枚举区间[L,R]内的所有的数字作为左端点对于[L,R]内的一个点t， f[t]<...

二分前缀和尺取法

2021-06-01

5 896

CCA的搬运

题目大意：选两个节点u,v，使得两个节点的子树和权值最大，且fa[u]!=fa[v] 思路：对于一个节点u假设有子节点v1,v2,v3..... 我们用mx[u] 记录u的子节点及其孙子节点中（反正就是u点下面的）任意一点为根的子树和最大值；有没有大佬帮我用术语描述一下上面的句子 sum[u]...

DFS

2021-03-12

6 783

最短路-（生成树+最短路+LCA）

题目描述n 个点，m条边， q个询问，每次输出 x,y的最短距离思路首先看一个弱化版的给你n个点，n-1条边构成一颗树，q个询问，每次输出树上两点x,y的距离这个题就是一个裸的LCA，lca的dfs完之后可以直接输出 int dis(int x, int y) { return de...

DFS 最短路 LCA

2020-07-08

2 877

字符串（尺取法）

题目描述：给一字符串，选出一段区间包含26个小写字母，求最短区间长度Slove：用尺取法，从l=r=1开始，如果【l,r】中不足26个小写字母 r++，否则先记录答案，然后l++；代码 #include <map> #include <set> #include <c...

尺取法

2020-06-15

1 839

超市（堆）

题目描述超市里有N件商品，每件商品都有利润pi和过期时间di,每天只能卖一件商品，过期商品不能再卖。求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。输入格式输入包含多组测试用例。每组测试用例，以输入整数N开始，接下来输入N对pi和di，分别代表第i件商品的利润和过期时间。在输入中，...

堆

2020-06-12

2 1115

背包（优先队列/排序）

Slove：要求价值的中位数，那首先要对价值进行排序，m为奇数的情况下然后我们枚举每个位置，如果该位置是中位数的最大，那么这个位置前面选m/2个的重量加上后面m/2个重量，使他们小于V就说明这个位置可以取得的，只需要维护一个大小为m/2 的堆就行，每次pop掉堆中最大的m为偶数的时候同理但是中间需要...

排序堆

2020-06-12

3 1149

失衡天平（DP）

题目描述：有一个长度为n的序列，从中选择任意个数字将其分成两堆使两堆的和最大（且两堆的差值不超过m）先证明一下取两次转化成一次的正确性假设第一次取了 a ,b第二次取了 c ,da-b=mc-d=m-1那么如果我们把c放在a这端明显是错误的我们把c放在b端( a+d )- (c+b)=-(m...

dp

2020-06-10

2 915

SCOI2005]最大子矩阵(dp)

一开始思路错了，想着把k当成1 求了一个最大子矩阵然后对最大子矩阵所在的一行用最大k段子序列，后来发现思路错了，因为这样所求的子矩阵的终点行一定都相同了正确的思路：因为m（列）是1&amp;amp;lt;=m&amp;amp;lt;=2，只有两种情况，对于m==1时候...

dp

2020-06-07

1 803

漂亮的公园(LCA+思维)

题目描述一棵树，每个节点有一个颜色，q个询问每次询问x，y求树上距离最长的两点其中一点color【i】=x;另外一点color【i】=y；思路1.对于求树上两点之间的距离可以用lca，倍增法求lca也不再介绍2.求max(color[i],color[j]]如果只看一种颜色x求最长的距离可以枚举是x...

LCA 离散化

2020-06-05

0 782