hrdate

题解

/ 注册

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

题解 | #数组中的逆序对#

归并排序 public class Solution { int res = 0; int [] temp; public int InversePairs(int [] array) { int n = array.length; if(n ...

Java 归并排序

2022-03-27

0 445

题解 | #单链表的排序#

插入排序O(n ^ 2) import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** ...

Java

2022-03-26

1 461

大家一起来数二叉树吧简单dp

题意：n个节点，m个叶子，问有多少种形态的二叉树题解：二叉树的每一次延伸一个节点相当于加上一棵子树，考虑到是二叉树，所以考虑一左一右相当于*2。所以当你需要x个节点，其中有y个叶子时候，就需要考虑x个节点y个叶子拆分后分配到左右子树上，而且拆分后又变成了一个子子树，这个子子树又有它本身多种形态，所以...

2020-07-17

3 840

相聚 DFS找01分块输

记得把遍历过的点从1变成0 #pragma GCC optimize(2) #include <bits/stdc++.h> #define ll long long #define endl '\n' using namespace std; const int inf=0x3f3f...

2020-07-11

2 702

兔子的名字 dp子序列

通过find在字符串的指定位置开始查找，在字符串t中一个字符一个字符的寻找可爱子序列，每次找到后改变find字符串t的位置，直到找全一个可爱子序列，可爱值+1，再接着遍历一下可以可爱子序列。 #pragma GCC optimize(2) #include <bits/stdc++.h>...

2020-07-10

3 715

解方程二分暴力

#pragma GCC optimize(2) #include <bits/stdc++.h> #define ll long long #define endl '\n' using namespace std; ll a[1005],n,x; bool solve() { ...

2020-07-09

2 912

take 树状数组+概率统计

题意:有n个盒子，每个盒子有p概率使得盒子里面有一个大小为d的钻石，每次遇到遇到比你手中更大的钻石你需要进行交换。现在你可以从第1个盒子开始，一直任意选到第n个，求交换次数的期望值是多少。题解:每个盒子的概率p的乘100后的值，考虑到大数，就可以考虑用乘法逆元对于期望高中已学过E(X+Y)=E(X)...

2020-07-08

3 729

Tree Recovery 树状数组区间操作求和模板题

先对原数组a进行差分，得到差分数组b，才对b[i]和b[i]*i分别维护一个树状数组tb和tc，而l到r的和变为[(r + 1) * sum(tb, r) - sum(tc, r)]-[(l + 1) * sum(tb, l) - sum(tc, l)]需要注意的是开vector<>后靠...

2020-07-06

5 775

情人节的电灯泡树状数组统计矩阵

水题。 #pragma GCC optimize(2) #include <bits/stdc++.h> #define endl '\n' #define ll long long using namespace std; ll tree[1000050],a[1000050],n,...

2020-07-06

4 769

华华开始学信息学树状数组分块

直接for（int i=x;i<=n;i+=x）add(i,y)；最坏是o(n^m)=1e10，会爆掉所以需要用个lazy[]进行分块统计小于sqrt(n)复杂度较大的那一部分y，最后在算range_sum(x,y)的时候加上[x,y]中lazy[]数组的贡献 #pragma GCC opti...

2020-07-06

3 764