hannibal_Iecter
hannibal_Iecter
全部文章
分类
ac自动机(7)
bitset(2)
BSGS(1)
dfs(3)
DP(19)
ODT(1)
splay(1)
ST表(2)
tarjan(2)
中途相遇法(1)
主席树(4)
二分图(1)
二叉树(1)
分块(1)
分治(3)
回文树(1)
多校(1)
字符串(1)
容斥(2)
平衡树(5)
并查集(1)
快速乘(1)
数学(9)
整体二分(1)
树链剖分(2)
模拟退火(2)
水题(1)
爬山算法(1)
矩阵快速幂(2)
线性基(1)
线段树(10)
编译器(2)
背包(2)
莫队(1)
计算几何(1)
随机数(1)
高精度(1)
归档
标签
去牛客网
登录
/
注册
hannibal_Iecter的博客
全部文章
(共98篇)
普通平衡树【模板】【treap】
学了一下treap的模板感觉还算容易理解。 其实就是平衡二叉树+堆 每个节点都有一个随机的权值。 根据堆的特性,只有右旋和左旋操作。 个人觉得关键代码就插入和删除部分涉及旋转的维护代码需要理解一下,其他的询问操作都很好写。 #pragma GCC optimize(2) #include <...
2019-07-12
0
550
bzoj3173【树状数组】【平衡树】
树状数组解法 个人遇到的问题:虽然知道这种问题首先要倒着处理出依次的真实位置。但是想法错了。。 我认为是倒着处理每个位置的真实位置为:插入的位置+当前位置之后插入位置比当前插入的位置小的数量 结果一直wa 后来找到了一组样例 6 0 1 2 0 3 4 用上面的方法位置结果实际上是错的。 是因为当某...
2019-07-11
0
354
HDU-4757【倍增+可持续化字典树】【树剖+可持续化字典树】
这道题要处理节点与父亲节点的前缀,而不是dfs的区间前缀。 当查询的时候对每一位只需要查询sum[x][!t]+sum[y][!t] > sum[lca][!t]就行了。 倍增 #pragma GCC optimize(2) #pragma comment(linker, “/ STACK ...
2019-04-24
0
451
2019南昌网络赛【 Max answer】【单调栈+ST表】
一开始的思路只是单调栈+前缀和就好了,后来发现当最小值为负数的时候并不能找到最优解。 比如-3 7 -1 -2 -1这种情况 正确的想法是对前缀和建立st表,还是单调队列求最近的小于x的编号。 当最小值<0的时候,应该求【i, R[i]】范围内的前缀和的最小 减去 【L[i], i-1】范围内...
2019-04-22
0
438
st表模板
ll stmi[maxn][30], stmx[maxn][30]; void initst() { for(int i = 0; i <= n; i++) stmi[i][0] = stmx[i][0] = cc[i]; for(int j = 1; (1<<j)...
2019-04-22
0
383
vscode【c++配置】
之前写的太乱了,而且当时自己也不太清楚。。 如果不用debug的话,只需要下载Code Runner这个插件然后配置一下就行了。。 怎么配置呢,vscode和vim类似在工作区下可以配置一些字体环境之类,setting.json(vim下是.vimrc),我们在工作区内编辑或运行代码时编辑器会自动适...
2019-04-20
0
442
HDU-6191【可持续化字典树+DFS序】
传送门 和主席树的思路差不多,用前缀和的思想保存n颗字典树(当然要动态开点),用对第i颗字典树上的节点sum[j][0/1]表示前i颗树第j位0/1的个数。对于询问只需要按位贪心就行了。 #include <bits/stdc++.h> using namespace std; con...
2019-04-18
0
611
ZOJ - 3494【AC自动机+数位DP】
数据那么大肯定是数位DP呀。 DP状态很好分析出来,注意数位DP上判一下前导零的情况就行。 #include<bits/stdc++.h> using namespace std; const int maxn = 2005; typedef long long ll; char ss...
2019-04-11
0
274
HDU-2243考研路茫茫——单词情结【AC自动机+矩阵快速幂】
看到L那么大就应该想到矩阵快速幂。 而且这道题和之前的POJ 2778. DNA Sequence很想。 我们只需要计算一下长度小于等于n的不包含特殊串的个数(矩阵中要增加一维代表每一行的sum),然后用总的可能数减去不包含的就是答案了(总的可能数很多人都是用矩阵写的,其实用等比数列求和公式就行了啊...
2019-04-11
0
401
HDU-2457 DNA repair【AC自动机+DP】
第一次。。自己分析出来的dp。。。。。 和之前做过的题很像,感觉有关构造字符串的题都有套路。 dp中一定包含一维trie图中的节点状态(好像是废话) 这道题我们用dp[i][j]表示长度为i节点状态为j最少消去的数量。 状态转移就是dp[i][u] = min(dp[i][u], dp[i-1][j...
2019-04-10
0
428
首页
上一页
1
2
3
4
5
6
7
8
9
10
下一页
末页