beckyUp

数据结构

--------------作业---------------(4) ACM算法(15) c++(16) codeforces(8) CSP(2) fft(1) java(8) java图像(1) KMP(4) tcp/ip(4) 二分(5) 二分图匹配(1) 分块(1) 分治(2) 前缀和(2) 动态规划(18) 区间dp(3) 博弈(2) 后缀数组(1) 图论(8) 字典树(1) 字符串(8) 小技巧(9) 并查集(2) 感悟(13) 操作系统(2) 数据库(3) 数论(10) 未归档(7) 构造(2) 树形dp(1) 水题(22) 状压dp(2) 脑洞(1) 自然语言处理(2) 计算几何(5) 计算方法(4) 读书笔记(2)

/ 注册

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

CCPC-Wannafly Camp #2 J Princess Principal 【离线+栈】

分析：这个题目，我们离线处理所有的查询区间，将所有区间按照右端点排序，然后通过栈去匹配括号，左括号直接入栈，右括号的话，如果匹配上了，就出栈，如果没有匹配上了，就留在栈中，当我们扫描到第i个的时候，对于右端点为i的询问，我们判断它的左区间是否比栈顶元素要小，如果小的话，就不能够匹配上了，如果大的话 ...

2018-08-06

0 672

牛客网暑期ACM多校训练营（第一场） D Two Graphs（图的同构）

题目大意：给你两个图 G1 G2，让你在G2中找有多少个子图与G1 同构题目分析首先这个题目的数据量非常小 n=8 ，所以我们可以采取非常暴力的做法，由于G2中如果有点与G1同构的话，我们发现只要改变G2中点的序号，此时的新图中如果有一部分与G1完全相同，那么这些点构成的图就会与G1同构。...

2018-07-29

0 431

牛客网暑期ACM多校训练营（第三场） C Shuffle Cards (SPLAY)

这个题就是每次把一段区间移动到区间的最前面，问你若干次操作后的序列按照题解说，这个题就是一个平衡树的操作题，之前没有做过平衡树的题，但是移动区间的时候想到了连续的翻转操作可以使得区间移动，所以，然后找了一个splay区间翻转的板子过了这个题，赛后发现stl 中有十分简单的工具可以实现。看来要...

2018-07-27

0 509

TREAP 的基本操作

struct Node { Node *ch[2]; //左右子树 int r,v,s; //r 表示优先级数值越大，优先级越高，v表示键值 int cmp(int x)const { if(x==v) return -1; retu...

2018-07-27

0 369

数据结构-BST UVA 11020

查找某一点其左下方没有其他点的点的个数其实是平衡数的添加删除查找的操作，用系统自带的multiset自动完成该任务 #include <bits/stdc++.h> using namespace std; const int maxn=1e5+50; const int inf=...

2018-07-27

0 331

codeforces 1000C [经典题目]【排序，数据结构】

据说是一个非常经典的题目，我竟然疑似第一次做，emmmm，看来还是题目做的太少，也是学习太不系统了【毕竟靠自己摸索。。。】题目分析：给你n个区间，问你区间中被覆盖的次数恰好为K的点的个数有多少个对于每一个k 属于[1…n] 输出这样的点的个数我们随意画一个图，就可以发现，如果我们将所有点...

2018-06-28

0 428

HDU 5266 pog loves szh III [lca 倍增算法]

之前我们在面对一个查询的时候，直接采用最暴力的搜索去完成此工作，现在，当我们面对有很多组数据的时候，发现一个一个的查询效率实在是太慢了，所以我们采用了一种新的方式，那就是倍增这个题就是给定Q个查询，查询一棵树上两个点的LCA Q<3e5 and N<3e5 这时候，我们就可以采取...

lca 倍增

2018-06-26

0 448

LCA的最暴力解法—openjudge 1330

题目大意：给一棵树，给定两个点，找到他们的最近公共祖先题目分析：这个题目的查询只有一次，我们只需要用最暴力的方法去完成就可以了题目详解：给定一棵树，我们想要找到他的最近公共祖先，我们用一个数组来记录每个结点的父亲结点。那么我们要想找的最近公共祖先，一定在该结点的祖先结点及其本身之内（祖先...

lca dfs

2018-06-25

0 516

OpenJ_Bailian - 2805 正方形【map】

题目大意，给你n个点，让你判断有几个正方形 n<=1000 题目分析：这个题就简单暴力枚举任意两个点，判断剩下两个点是否在内就可，一开始试图用hash去判断是否存在，后来没有找到合适的hash方式=-= 还是太菜，这个题的话，直接用map就可以了，先对点进行排序，然后放到map里，然后再判...

2018-06-22

0 429

2016湖南省赛 G Parenthesis [RMQ]

这个题，给你一串括号序列问你交换 ai,bi两个位置的括号，原串是否依然匹配题目分析，对于一个括号序列，我们只要找到一个右括号，在它之前没有左括号与它匹配，那么就是不匹配的序列，将左括号记为-1 右括号记为1 求前缀和如果前缀和 >=1 那么一定就不匹配了由于有很多查询，所以，我...

rmq

2018-05-01

0 359