题目链接   题意就是一个简单的平衡树的板子，但是在实现上有很多细节,蒟蒻的我竟然debug了3天，只能说自己的板子不硬，更新下板子 因为细节挺多的(至少我觉得是，所以就直接以注释的形式写在代码里了)但是要注意，这里说的子列是连续的子列。 因为看网上的题解说的好像在bzoj上一直开新点会内存超限，为了防止也出现这个情况，我特意学了一手节点回收分配(虽然最后也没啥用好像) 超长代码(捂脸) #include <bits/stdc++.h> #define ss system("pause"); using namespace std; const int maxn...

题目链接 思路:   第一个问题很好解决，就是最长不上升子序列，利用贪心 + 二分的dp就可以解决，这里给一个二分查找的函数  二分查找  第二个问题是问给出的序列最少可以分成几个不上升子序列，其实这里有一个定理 由Dilworth 定理，不上升子序列的最小划分数为 a 的最长上升子序列长度。所以第二个问题就转化为了求这个序列的最长上升子序列，其实如果要省事的话，可以把这个序列颠倒过来，然后就转化为第一个问题 code #include <bits/stdc++.h> using namespace std; const int maxn = 100000 + 5; int dp[...

题目链接 思路:   这个题一开始一点思路没有，感觉模拟的话是不太可能的，直接选择看题解，在看完题解后恍然大悟  1 dp状态 `dp[i,j] //n个结点，m个叶子结点有多少种形态 2 状态方程 dp[i,j] = dp[i,j] + dp[x][y] * dp[i - x - 1][j - y] (x < i && y <=j)也就是说我们不需要去模拟，只需要暴力跑到dp[i,j]时，从小到大枚举左子树结点和左子树叶子结点个数有多少种形态以及对应剩下的结点和叶子结点组成的右子树有多少种形态，利用排列组合的思想，累加即可  但是要注意，我们求相对应的右子树结点时...

题目链接 题意：  中文的，而且说的很明白，但是要注意，这个数组中的数可以重复 思路：  1、dp状态 dp[i,j]表示了长度为i并以j结尾的数组符合条件的方案数有多少种 2、状态转移方程 dp[i,j] = sum(dp[i - 1][k] (k <= j) + dp[i - 1][x] (j % x != 0))  最暴力的dp方式是跑3个循环，这样时间复杂度是O( * )由于时间是1000ms所以暴力dp肯定是过不了的所以我们可以转化一下思路 采用 dp[i,j] = sum - dum 其中 sum = Sum(dp[i - 1][x]) (x >=1&&...

题目链接 题意：  题目是中文的，不用我再进行赘述，但是这里要注意：删除的'('和')'必须是相邻的 思路：  说实话，要不是这个题被分到动态规划的题单里面，我是绝对不信这是一个dp题首先,我们先定义好dp变量,dp[i,j,k]表示1串前i在删除的'('数量-删去的')'为k时是否与2串的前j项相等，可以采用bool类型的数组且初值是dp[0][0][0] = true 递推公式如下:  当dp[i,j,k] = true && k == 0时 说明1，2两串上一次是匹配的，而且删除的括号也是成对的  1如果str1[i + 1] == str2[j + 1] &&a...

题目链接 1、dp变量 dp[len][m] 表示前len长度中，子序列各位和对3求余为m的子序列数量 2 递推公式,  1、当 (s[i] - '0') % 3 == 0时 dp[i][0] = dp[i - 1][0] + dp[i -1][0] + 1 dp[i][1] = dp[i - 1][1] + dp[i -1][0] dp[i][2] = dp[i - 1][2] + dp[i -1][0] 2、 当 (s[i] - '0') % 3 == 1时 dp[i][1] = dp[i - 1][1] + dp[i -1][0] + 1 dp[i][0] = dp[i - 1][0] ...

题目链接 题意：   给一个二叉树序列，判断是不是一颗二叉搜索树 思路：   根据给的二叉树序列先把树建立出来，然后前序遍历二叉树，如果这是一颗搜索二叉树的话，那么前序遍历的序列一定是单调不递减的，所以我们只需要判断这个序列是不是单调不递减即可，还是考察对搜索二叉树的结构的理解 代码 #include <bits/stdc++.h> using namespace std; const int maxn = 80000 + 5; const int inf = 1e9 + 7; const int mod = 1e9 + 7; const double PI = acos(-1.0...

题目链接 题意很清晰，抽象一下的话就是求每个数左边和右边比它小的数能组成几个'v'型序列，每个数左边和右边比它大的数能组成几个'^'型序，利用树状数组正向和反向求一边这个数左边比它小(大)和右边比它小(大)的数，然后按照排列组合求出每个数可以得到几个'V'和 ' ^ '即可，跟求逆序对差不多 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 200005; ll tree[maxn],premax[maxn],premin[maxn]; ll a[maxn]; i...

题目链接 文字转载于 题意:有n个盒子，每个盒子中有p[i]的概率有d[i]大小的钻石，初始有大小为0的钻石，每遇到一个比自己当前大的钻石就要进行交换，求交换的期望。 题解:对于每个钻石进行讨论，这个钻石进行交换的可能性是前面所有比这个大的钻石都不产生且这个钻石产生的概率，那么根据d从大到小进行排序，然后求出每个钻石交换的概率求和即可，还要注意概率是p[i]*100，那么直接乘100的逆元即可，可以用树状数组维护前缀积，维护当前钻石前方比自己大的钻石的不产生的概率的乘积，因为维护乘积所以树状数组要初始化为1. 代码 #include <bits/stdc++.h> using na...

题目链接 下面的题解转于传送门对于想要学习区间修改和单点输出的同学们可以去看这篇文章  传送门 假设数组a是原数组，b是a的差分数组，由前缀和的定义，我们求前n个元素的和，即  详细过程如下：a1 + a2 + ... + an = b1 + (b1 + b2) + ....+ (b1 + b2 + b3 + ... bn) ->n * b1 + (n - 1) * b2 + ... + bn 所以我们要先对原数组a进行差分，得到差分数组b，才对b[i]和b[i]*i分别维护一个树状数组tb和tc，而l到r的和变为[(r + 1) * sum(tb, r) - sum(tc, r)]-[...

题目链接参考博客 这里先给出 __int128和利用vector的unqiue 配合erase 去重__int128 , vector的unqiue 配合erase 去重 刚开始看这个题，就是简单的求逆序对 所产生的贡献，对于一个逆序对 [i , j]他们所产生的贡献是 l * (n - j)个，所以我们可以枚举j如果 j 前面有m个数大于它，那这m个数字与j所产生的贡献即为这m个数字的下标和 乘以 (n - j + 1),所以我们在用树状数组求逆序对的时候，要去维护它们的下标和但是由于这个题的数据范围是1e9但是数字的数量只有1e6所以要进行离散化，而且答案的数据太大了long long 也...

题目链接 其中借鉴的图片和部分说明来自传送门先用manacher把两个串都预处理一遍,求出Len数组，然后再遍历第一个字符串(第二个按道理来说也可以，但是没试过)因为要求l1 = r2 所以再遍历到第i点时,我们要把比较第二个字符串的第i - 2位置的回文串长度，选择最长的一个当作回文中点，然后以这个回文中点的串的起始长度就是它的回文长度，然后再从当前回文串的左侧去跟第二个字符串在当前回文串的右端的位置进行比较，如果相等，那么回文串长度加1  因为以 i 为中心 PA / PB 为半径的回文串中，它的最小回文长度就达到了 PA / PB - 1所以只要从 PA / PB 两端拓展看还能找到多少...