Feng003

分类

codeforces(2) DP(3) 图论(2) 基础数据结构(2) 字符串(1) 数据结构课程(1) 概率期望(1) 算法课课程作业(4) 题解(6)

/ 注册

全部文章（共22篇）

各大排序模板

快速排序 int a[N];//待排序数组 inline void swap(int& x, int& y) { int tmp = x; x = y; y = tmp; } void quick_sort(int l, int r) { if (l...

排序算法

2020-04-19

0 448

Array Without Local Maximums（codeforces1068D）计数类DP

题意：给你一个长度为n的数组a,（1<=n<=1e5 ,1<=a[i]<=200 or a[i]=-1）。a[i]=-1代表i这个位置的数是未知的否则已知，对于每个未知的数你可以把它设置成1-200之间的任意整数。问你有几种设置方法可以使得整个序列满足：a[1]<=a[...

计数类dp DP

2020-04-19

0 568

平衡树之splay

　　Splay这个名字在我很早的时候就听说过了，是寒假的时候在lyd的蓝书上学平衡树章节的时候，他在那一章节的最后强力推荐的一种平衡树。"Splay(伸展树)灵活多变，应用广泛，能够很方便地支持各种动态的区间操作，是用于解决复杂问题的一个重要的高级数据结构。"(原话)。当时就使...

平衡树 Splay

2020-04-16

0 576

Coloring Brackets CodeForces - 149D （区间dp）

问题：给你一个长度为n的合法括号序列，你要对每一对括号的其中一个半括号（必须并且只能为一个）染色，有两种颜色可以选择。要求染完色后，序列里不存在相邻的位置是同种颜色的（两个都未染色的算合法）。求一共有几种染色方案。答案取模1e9+7。思路: 区间dp。记dp[l][r][i][j]为对区间[l,r...

括号匹配区间dp

2020-04-12

0 544

分层最短路（计蒜客 - A1958 ）

问题：给定一张有n个点，m条有向边的图。一个整数k。（n<=1e5,m<=2e5,k<=10）。你有k次机会使得图中的某一条边权值变为0。求1号点到n号点的最短距离。保证至少存在一条路径从1到n。思路：dijkstra算法+dp转移　　这其实就是一道分层最短路的模板题。普通的d...

dijkstra 分层最短路

2020-04-12

0 570

一类字典树解决序列异或问题（CodeForces - 665E）

问题：给定一个长度为n的序列（1<=n<=1e6）,一个整数k(1<=k<=1e9),让你求出这个序列里有几个不同的区间满足区间内的数异或和大于等于k。思路：转化前缀异或和。然后利用二进制和字典树解决。　　一段区间的异或和x[l,r]=x[1,l-1]^x[1,r]。所以...

字典树区间异或

2020-04-12

0 778

找区间第k大（小）的数

问题：给定n个整数，如何用最快的方法求出第k大的数？　　我们当然可以对这n个整数排序然后直接输出第k大的数，时间复杂度为O(nlog n)。　　但是实际上我们可以用基于快速排序所用到的思想，在每一层递归中，随机选取一个数为基准值，把比它大的数交换到左半段，把其余的数和基准值自身一起作为右半段。在这...

区间第ｋ大

2020-04-01

0 873

HDU - 6534 Chika and Friendly Pairs (莫队+树状数组)

题目大意：给你一个长度为n的序列a（1<=n<=27000,1<=a[i]<=1e9）,m(1<=m<=27000)个查询，k（1<=k<=1e9）,每次查询给出li,ri。需要回答在[li,ri]这个区间内有多少对（i，j）满足i<j并且a[i...

树状数组莫队

2020-03-29

1 542

一类静态查询区间里有几个不同的数（较详细适合萌新）

问题：给出一个长度为n(1<=n<=1e5)的序列，接下来有q(1<=q<=1e5)个查询，每次查询给出一个区间[l,r],你需要输出在区间[l,r]里有几个不同的数。解决这个问题的方法，目前就我所知道的有三种。一、树状数组+离线　　首先我们把所有查询一次性读入，然后...

静态查询区间不同的数个数

2020-03-29

1 1238

HYSBZ 2438杀人游戏（tarjan 缩点 + 思维）

理解完题意后，能容易想到答案就是1 - 未知身份人数 / 总人数。所以我们就把问题转换成求一共有几个人是身份是未知的（即他的身份是无法从他人那里获取的）。因为其他人我们可以通过这些人来安全的推导出他的身份。所谓的递推吧... 于是我们把n个人看成图上的n个点，认识关系看成点与点之间的有向边。容...

2020-02-10

0 431