ComplexPug

分类

做题记录(1) 未归档(274)

/ 注册

全部文章（共277篇）

luogu P4051 [JSOI2007]字符加密

前言其实就是个后缀数组模板题可还是有几个的地方不太明白思路先将子串复制一遍，组成长度为2*n的子串给出的子串一定会在前n个后缀而且后面的优先级不会影响前面的相对大小然后求得sa输出就好输出的时候把没有必要输出的忽略掉就好代码 #include <bits/stdc+...

2018-12-18

0 458

后缀数组学习笔记

目录前置重点及其目标分析目标&&正题代码前置纯属博主虎的的罗穗骞2009NOI集训队论文还是原版的最明白啊先了解基数排序和倍增求sa思想并且有一定的看别人博客的基础(对，没错，就是这么不要脸) 基...

学习笔记

2018-12-18

0 457

## 基数排序--------无人问津的优秀算法

基数排序--------无人问津的优秀算法在这个被stl的sort独霸的c++世界(毕竟stl的sort太过好用) 似乎所有普通排序算法都被挤到了一边，但毕竟各有各的优点这个排序算法还是不错的但最近学习后缀数组的时候遇到了这个算法，就简单学习一下吧介绍多关键字排序中有两种方法：最高位...

学习笔记

2018-12-18

0 476

luogu P5105 不强制在线的动态快速排序

前言考试的时候居然想错了区间贡献，mdzz 思路题目看着很方啊，难道要树套树？但数据范围提醒我们，是nlogn的复杂度 Sort(S)的定义是不是很鬼畜但我们不动脑子的打表容易发现连续区间[1，n]内\(a_i^2-a_{i-1}^2\)为连续的奇数（其实这里直接用初中的完全平方公...

线段树离散化

2018-12-17

0 638

luogu1975 [国家集训队]排队

思路序列中 |i | 1| 2| 3| 4| 5| 6| 7| 8| 9| 10| |----|--|--|--|--|--|--|--|--|--|--| |a[i]| a| b| c| L| d| e| f| R| g| h| 现逆序对为ans,要交换L,R 则\([1,3],[9,10]\...

树套树

2018-12-14

0 389

luogu P2713 罗马游戏

思路模拟就好左偏树合并并查集寻找代码 #include <bits/stdc++.h> #define FOR(i,a,b) for(int i=a;i<=b;++i) using namespace std; const int maxn=1000005; int ...

左偏树并查集

2018-12-13

0 477

luogu P3521 [POI2011]ROT-Tree Rotations

思路合并时候统计逆序对贡献代码 #include <bits/stdc++.h> #define FOR(i,a,b) for(int i=a;i<=b;++i) #define ll long long using namespace std; const int ma...

线段树线段树合并

2018-12-13

0 558

luogu P3168 [CQOI2015]任务查询系统

思路又是强制在线--主席树每一次操作建一棵树但实际用的的rt只有n个所以实际内存是n230 我见到只开n*30的,不会，错误 debug 以为每一秒建立一颗树第一次 query没有递归第二、三次权值线段树的查询处理,就是到叶子节点的处理代码 // luogu-judger...

数据结构-主席树

2018-12-12

0 472

luogu P2633 Count on a tree

思路强制在线--主席树以1为root建主席树 (就是在树上建树，差不多) rt[i]就是1到i的路径上的一棵树的root 其实我感觉，主席树之间的运算差不多于加减类似lca的运算 root(1到x)+root(1到y)-root(lca）-root(fa[lca]) 查询他们的第k小就OK ...

数据结构-主席树 lca

2018-12-12

0 464

P3567 [POI2014]KUR-Couriers

思路区间内x出现次数大于一半区间内排序，则x一定会在(一半+1)的位置上出现找到那个数，再检查一下就好错误快读写错了、、，又浪费了1h 代码 #include <bits/stdc++.h> #define FOR(i,a,b) for(int i=a;i<=b...

数据结构-主席树

2018-12-12

0 538