Day24h

数据结构

2019 Multi-University Training(2) 2019牛客暑期多校训练营(1) CF(37) Record My Feelings(5) 动态规划(23) 图论(4) 字符串(3) 数学(20) 未归档(5) 模板(23)

/ 注册

全部文章 / 数据结构（共8篇）

食物链

食物链因为不知道要输入的 x ，是属于A，B，C，哪个位置上的，所以把空间开了三倍，每一种状态都保存一下如果 x 与 y 同类，那么judge(x,y)为true。如果 x 吃 y 那么，judge(x,y+n)为true 这个题卡的点在于，poj会卡cin，所以应...

并查集

2020-01-15

0 517

Common Number

E - Common Number 参考：Codeforces Round #608 (Div. 2) E - Common Number (二分思维树结构) 具体做法可详见参考博客。关键在于在分了奇偶之后，就是有序的了在数据范围很大的时候，要尝试降低其复杂度，对答...

二分

2020-01-04

0 347

树状数组

树状数组 #define ll long long #define lowbit(i) (i&-i) const int maxn=1e5+5; int c[maxn], w[maxn], laz[maxn << 2]; ll n,mod=1e9+7; /*单点更新*/ vo...

树状数组

2019-12-03

0 390

Editor

E. Editor 我们把“(”用1表示，“)”用-1表示，其余字母用0表示，这样形成的一个数组，我们求出它的前缀和sum[]，只有当\(sum[n]==0\)且\(min(sum[])==0\)中的时候，才表示括号正好匹配，且最大嵌套数为\(max(sum[])\) 对于一个数...

线段树

2019-12-03

0 394

查找链表的中间结点

查找链表的中间结点题目：设计一算法查找链表的中间结点。要求该算法的时间复杂度为O(n)，空间复杂度为O(1)。当看到这个时候想了半天没想出来，时间复杂度是没问题的，但是空间复杂度要达到O(1)还是有一点不好办，然后百度了一下，发现有快指针和慢指针的写法，于是我就进去瞧了瞧，突...

2019-10-14

0 496

Tree

Tree 参考 xk 老哥的博客：POJ 1741 Tree 点分治找重心： void getrt(int fa,int u,int num) //num指的是这个节点的子树中有多少个节点 { siz[u]=1; int maxnum=0; ...

点分治重心容斥原理

2019-08-14

0 410

Housewife Wind

Housewife Wind 参考博客：POJ2763 Housewife Wind(树剖+线段树) 差不多是直接套线段树+树剖的板子，但是也有一些需要注意的地方建树： void build() { for( int i=1;i<n;++i) { ...

树链剖分线段树

2019-08-13

0 406

Aragorn's Story

A - Aragorn's Story 直接套线段树+树剖板子代码： // Created by CAD on 2019/8/12. #include <bits/stdc++.h> #define lson (p<<1) #define rson (p...

树链剖分线段树

2019-08-12

0 403