Codeforces Round #449 (Div. 2) C. Nephren gives a riddle 二叉树、回溯、分类讨论
C. Nephren gives a riddle 二叉树、回溯、分类讨论 My Solution 题意：用一个前缀s1，中间部分s2，后缀s3，fi = s1 + fi-1 + s2 + fi-1 + s3来构造字符串 fi，q个询问(n, k)，每次询问第n个字符串的第k…
2016 UESTC Training for Data Structures D – 卿学姐与魔法 优先队列、构造
D - 卿学姐与魔法 优先队列、构造 My Solution 用STL里的优先队列直接维护前n+1小的数字 ptr = 0 先 i = ptr 然后A + B1 + B2 + …… B(n-1) 然后 j = 1 B1 + A2 + ……A(n-1) 这样依次下去， 当 Aptr + B(ptr+1) …
UESTC 1584 Washi与Sonochi的约定 树状数组+排序
Washi与Sonochi的约定 Source 17暑假前集训-数据结构专题 By AutSky_JadeK 2017 UESTC Training for Data Structures UESTC 1584 Washi与Sonochi的约定 My Solution 题意：在二维平面上，某个点的rank被定…
HDU – 6191 Query on A Tree 可持久化字典树+dfs序
Query on A Tree 可持久化字典树+dfs序 Source HDU - 6191 2017ACM/ICPC广西邀请赛-重现赛（感谢广西大学） My Solution 题意：给出一颗树，每个节点有一个权值，q个询问，询问以点u为根的子树中的节点权…
Codeforces 620E New Year Tree dfs序+线段树+状态压缩
E. New Year Tree dfs序+线段树+状态压缩 My Solution 题意：给定一棵树，每个节点都有颜色，然后询问子树上有多少种不同的颜色。 dfs序+线段树+状态压缩 由于只有60种颜色（2^60 < 2^63），所以可以直…
SPOJ – COT Count on a tree 树上主席树+LCA+任意路径问题
Count on a tree 树上主席树+LCA+任意路径问题 Source: SPOJ - COT [kuangbin]主席树] My Solution: 题意：给出一个树和树上每个点的权值，给出m个询问(u,v,k)，询问在树上从点u到点v所构成的路径上权值…
HDU – 6203 ping ping ping LCA倍增算法+dfs序+线段树
ping ping ping LCA倍增算法+dfs序+线段树 Source HDU - 6203 My Solution 题意：给出一颗以0为根有n+1个节点的树，给出p个条件，每个条件表示u,v之间有一个坏的节点，根据这p个条件求出树上至少有多少坏…
HDU – 3887 Counting Offspring dfs序+线段树
Counting Offspring dfs序+线段树 Source HDU - 3887 My Solution 题意：问对于每个节点，它的子树上标号比它小的点有多少个。 dfs序+线段树 关于dfs序： dfs序是处理树上问题很重要的一个工具，主要能够解决对于…
POJ – 3321 Apple Tree dfs序+线段树 简单题
Apple Tree dfs序+线段树 简单题 Source POJ - 3321 My Solution 题意：初始时树上每个节点都有1个苹果，然后对一个节点操作，如果有苹果，就拿走，没苹果，就放上，然后询问以x为根的子树上有多少个苹果。 …
UESTC 1591 An easy problem A ST表、简单题
An easy problem A ST表、简单题 Source 2017 UESTC Training for Data Structures UESTC 1591 An easy problem A My Solution 题意：每次查询区间内极差。 ST表、简单题 可以用2个ST表，分别维护区间最大值…
UESTC 1583 曜酱的心意 树状数组求逆序数
曜酱的心意 树状数组求逆序数 Source 17暑假前集训-数据结构专题 By AutSky_JadeK 2017 UESTC Training for Data Structures UESTC 1583 曜酱的心意 My Solution 题意：给出2个序列，问从一个序列到另一个…
Gym – 100507H H. Pair: normal and paranormal 栈
H - Pair: normal and paranormal 栈 Source Gym - 100507H My Solution 题意：给一个字符串，要求把大写字母和小写字母一一配对，要求不交叉。 用栈来模拟，不要写挂了就没问题，^_^ 复杂度 O(n) #i…
UESTC 1299 Date 预处理、打表、找周期、前缀和
Date 预处理、打表、找周期、前缀和 Source The 14th UESTC Programming Contest Preliminary My Solution too young too simple，当时初赛的时候，觉得必定会有一个周期，然后想不出该是怎样的周期，就…
POJ – 2104 K-th Number 主席树基础题
K-th Number 主席树基础题 Source POJ - 2104 My Solution 题意：给出一个数组，每次询问这个数组的区间[L, R]内第k大的数是什么。 主席树基础题 主席树，又称可持久化线段树，是对于数组的每个前缀a[1...i]建立…
HDU – 4417 Super Mario 主席树+二分
Super Mario 主席树+二分 Source HDU - 4417 My Solution 题意：给出一个长度为n(1<=n<=1e5)的数组，m(1<=m<=1e5)次询问，每次询问在区间[L,R]中小于等于X的数的个数。 主席树+二分 朴素的主席树是…
HDU – 3487 Play with Chain __ Splay
Play with Chain Splay Source HDU - 3487 My Solution 题意：对1~n这n个数，进行m次操作，分别可以进行区间移动和区间反转，求最终的序列。 Splay Splay的基础题，按照要求进行区间移动和区间反转即可。 复杂度 O…
UESTC 1593 老司机破阵 优先队列+双端链表
老司机破阵 优先队列+双端链表 Source 2017 UESTC Training for Data Structures UESTC 1593 老司机破阵 My Solution 优先队列+双端链表 cf原题，直接贴的以前的代码 反向做，按着反的顺序把元素一个一个的…
Codeforces Round #420 (Div. 2) C. Okabe and Boxes 栈+last标记+贪心
C. Okabe and Boxes 栈+last标记+贪心 My Solution 题意：有1~n这n个数，给出一个stack的push和pop的序列，要求在执行的过程中用尽可能少的重排次数，使得能够使pop的顺序是1~n的顺序。 栈+last标记+贪心 …
Gym – 101173F Free Figurines 思维题+并查集
Problem F: Free Figurines 并查集 Source Central Europe Regional Contest 2016 Zagreb, November 1820, 2016 Gym - 101173F My Solution 题意：给出一个序列ai 表示i的父节点是ai, 再给出一个序列bi…
UESTC 1592 An easy problem B 线段树区间合并
An easy problem B 线段树区间合并 Source 2017 UESTC Training for Data Structures UESTC 1592 An easy problem B My Solution 题意：区间更新把该区间内所有的数异或1，区间查询该区间内最长连续1的长度…
