ComplexPug

未归档

做题记录(1)

/ 注册

全部文章 / 未归档（共273篇）

luogu P2486 [SDOI2011]染色

树剖做法：就是两个dfs+一个线段树难度的取决基本==线段树的维护难度所以对有点线段树基础的，树剖也不难做吧这里操作有二一：两点间路径染***r> 线段树的区间赋值操作二：查询路径段的个数考虑线段树如何做我们发现两端区间的合并取决于他们相连接的那两个颜***r> 比如这张...

线段树树链剖分

2018-12-25

0 442

CF 1087解题报告

cf解题报告记录一下吧做出：T1 rating ：-97 想起几个月前做不出T1还是有点小搞笑呀2333 T1 双指针+特判 T2 发现k特别小，枚举剩余系还要判断是否是能被n整除移项发现可以算出整除是多少然后\(整除*k+剩余数=n\)算出答案，复杂度\(O(k)\) T3...

CF

2018-12-24

0 469

后缀自动机

https://oj.zrt.io/problem/44 比较容易懂得文档新浪

后缀自动机

2018-12-21

0 405

poj2774

思路求出height之后只要相邻两个子串是本串不同的来更新就好因为这样一定是最优啊、、取min显然越长越不好（这里'%'当成‘{’吧） abc%bca height i sa belong 0 1 a 7 2 1 2 abc...

后缀数组

2018-12-21

0 410

4698: Sdoi2008 Sandy的卡片

前言总之这个东西说起来很麻烦就是了，思路差分合并+后缀数组+二分(dddl) 类似于那个bzoj1031的复制子串和那个poj1743的差分来看个例子 3 5 1 2 3 4 5 4 1 1 1 2 4 1 2 3 4 变成了这个(最后一个INF最好删掉吧，应该不影响的吧) ...

数据结构 ST表后缀数组

2018-12-20

0 402

poj1743

思路不得不说，罗穗骞太厉害了他写的论文比哪一篇博客都好去看吧，也别看我的了里面有这题目详解论文代码 // 不得不说，罗穗骞nb哇,%%%%%%%%% /* 0 0 1 1 2 2 3 3 4 10 1 2 3 4 5 1 2 3 4 5 差分 1 1 1 1 0 1 1 1 1...

后缀数组二分

2018-12-20

0 540

luogu P4051 [JSOI2007]字符加密

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

2018-12-18

0 453

后缀数组学习笔记

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

学习笔记

2018-12-18

0 452

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

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

学习笔记

2018-12-18

0 470

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

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

线段树离散化

2018-12-17

0 619