Chrety

数据结构

C++(8) DOS(2) Python(2) 动态规划(12) 图论(8) 字符串(1) 学习笔记(10) 数学(10) 未归档(2) 杂(1) 算法(13) 详尽的思路(1) 题解(1)

/ 注册

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

P2995 [USACO10NOV]牛的照片(树状数组,逆序对)

题目： P2995 [USACO10NOV]牛的照片Cow Photographs P4545 [USACO10NOV]奶牛的图片Cow Photographs SP7809 COWPIC - Cow Photographs 解析：一个环形的逆序对最大的数可以放在最小的数的左边而不贡献逆序...

树状数组逆序对

2019-10-21

0 641

BZOJ1832: [AHOI2008]聚会(LCA)

题目： 1832: [AHOI2008]聚会解析：偶尔做做水题挺爽的两两之间先求出LCA，发现至少有两个LCA是相同的，这个重复LCA也是深度最浅的那个，那我们就选择那个不重复的LCA，因为若选这个重复的LCA的话，这个重复的LCA到另一个LCA的路径会走两遍，反之只会走一遍三点间的距...

LCA 树链剖分

2019-08-19

0 484

The Xor-longest Path(trie树)

题目： #10056. 「一本通 2.3 练习 5」The XOR-longest Path 解析：做完#10051后就不是很难了继续利用异或的性质有\(dis(u,v) = dis(1,u)\oplus dis(1,v)\) 把边权放到点上，然后字典树求最大异或值代码 #inclu...

trie树字符串

2019-07-29

0 654

Nikitosh 和异或(trie树)

题目： #10051. 「一本通 2.3 例 3」Nikitosh 和异或解析：首先我们知道一个性质\(x\oplus x=0\) 我们要求\[\bigoplus_{i = l}^ra_i\]的话，相当于求\[(\bigoplus_{i = 1}^la_i)\oplus (\bigoplu...

字符串 trie树

2019-07-29

0 589

P3121 [USACO15FEB]审查(AC自动机)

题目： P3121 [USACO15FEB]审查（黄金）Censoring (Gold) 解析：多字符串匹配，首先想到AC自动机建立一个AC自动机因为有删除和拼接这种操作，考虑用栈维护顺着文本串匹配的方向走，将经过的节点放入栈中，若匹配到一个模式串，就将这个模式串弹出，从栈顶开始继续走...

AC自动机字符串

2019-07-29

0 510

The XOR Largest Pair(tire树)

题目 The XOR Largest Pair 解析一年前听学长讲这道题，什么01trie，好高级啊，所以没学，现在一看。。。。看到xor就应该想到二进制，一看数据\(A_i< 2^{31}\)，考虑把所有的数都处理成长度为32的二进制数，插入字典树中，查询的时候就逐位比较，有不同的...

字符串 trie树

2019-07-27

0 596

P2801 教主的魔法 (线段树)

题目 P2801 教主的魔法解析成天做水题线段树，第一问区间加很简单第二问可以维护一个区间最大值和一个区间最小值，若C小于等于区间最小值，就加上区间长度，若C大于区间最大值，就加0 ps:求教指针线段树，我的空间怎么那么大代码 #include <bits/stdc++.h...

数据结构线段树

2019-06-05

0 522

P2184 贪婪大陆 (树状数组)

题目 P2184 贪婪大陆解析差分？在所修改的区间的开头位置+1，表示从这个位置开始往后开始埋一种地雷，在结尾位置+1，表示在这个位置有一种地雷被埋完查询的时候我们就只需要查询 \([1,r]\)中开头的位置，表示\(1\)到r***埋了多少种类型的地雷 \([1,l-1]...

数据结构差分树状数组

2019-06-01

0 607

SP375 QTREE - Query on a tree (树剖)

题目 SP375 QTREE - Query on a tree 解析也就是个蓝题，因为比较长树剖裸题（基本上），单点修改，链上查询。顺便来说一下链上操作时如何将边上的操作转化为点上的操作：可以看到这个题然我们对边进行操作，我们的树剖是对节点进行操作的，所以我们考虑把边权变为点权。 ...

树链剖分数据结构

2019-05-04

0 541

[JLOI2014]松鼠的新家 (树剖)

题目 P3258 [JLOI2014]松鼠的新家解析非常裸的一道树剖题链上修改+单点查询的板子记录一下所经过的点\(now[i]\)，每次更新\(now[i-1]到now[i]\) 我们链上更新时上一次到的终点，是这一次一次更新的起点，又因为在\(a_n\)处可以不放糖，所以我们...

树链剖分

2019-05-03

0 514