Eirlys_North-CSDN博客

转载 splay tree

类别：二叉排序树空间效率：O(n)时间效率：O(log n)内完成插入、查找、删除操作创造者：Daniel Sleator和Robert Tarjan优点：每次查询会调整树的结构，使被查询频率高的条目更靠近树根。注：所有图片来自wiki。http://blog.csdn.net/cyberzhg/article/details/8058208

2016-12-21 09:25:48 485

转载平衡树之splay讲解

原文作者为BLADEVIL学长：http://www.cnblogs.com/BLADEVIL/p/3464458.html　首先来说是splay是二叉搜索树，它可以说是线段树和SBT的综合，更可以解决一些二者解决不了的问题，splay几乎所有的操作都是由splay这一操作完成的，在介绍这一操作前我们先介绍几个概念和定义　　二叉搜索树，即BST(binary search tr

2016-12-20 19:52:33 946

原创求SG模板（附：HDU1848 &HDU1536）【pascal】

关于SG函数的理论知识以及理解，请见这里，目前我没有看见比这个说得更棒的=w=这里只是用来贴模板的首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Grundy函数g如下

2016-11-07 19:49:11 476

转载博弈问题及SG函数（怒赞，耐心地仔细看一定能看懂）

博弈问题若你想仔细学习博弈论，我强烈推荐加利福尼亚大学的Thomas S. Ferguson教授精心撰写并免费提供的这份教材，它使我受益太多。（如果你的英文水平不足以阅读它，我只能说，恐怕你还没到需要看“博弈论”的时候。）Nim游戏是博弈论中最经典的模型（之一？），它又有着十分简单的规则和无比优美的结论，由这个游戏开始了解博弈论恐怕是最合适不过了。Nim游戏是组合游戏(Comb

2016-11-07 10:50:40 596

原创尼姆博弈（附：HDU1850）

尼姆博弈：有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。这种情况与二进制有着很大的关系，我们用(a,b,c)来表示某种局势，那么(0,0,0)必然为奇异局势，(0,n,n)也是种奇异局势。因为如果对手在其中一堆取m个石子(m直接说结论吧：对于任意的奇异局势(a,b,c)，都有a^b^c=0。(^为异或运算)。

2016-11-07 10:02:04 556

原创威佐夫博弈（附POJ1067）

威佐夫博弈：有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。我们用(ak,bk)(ak局势。如果甲面对局势(0,0)，说明甲输了，我们把这种情况叫做奇异局势。现在的问题我给你一个局势(a,b)，我们怎么判断它是不是奇异局势呢？判断公式为：ak=[k(1+√5)/2](向下取整)，bk=ak+k（k=0，1

2016-11-07 09:36:18 678

原创巴什博弈（例：HDU1846&HDU1847&HDU2188&HDU2149）

巴什博弈：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。显然，如果n=m+1，那么由于一次最多只能取m个，所以，无论先取者拿走多少个，后取者都能够一次拿走剩余的物品，后者取胜。换句话说，也就是面对这个局面的先手必输（谁面对这个局面谁一定输）=。=因此我们发现了如何取胜的法则：如果n=（m+1）r+s，（r为任意自然数，s≤m)

2016-11-07 09:33:28 552

转载搞懂树状数组

引用请注明出处：http://blog.csdn.net/int64ago/article/details/7429868 写下这个标题，其实心里还是没底的，与其说是写博帖，不如说是做总结。第一个接触树状数组还是两年前，用什么语言来形容当时的感觉呢？……太神奇了！真的，无法表达出那种感觉，她是那么的优雅，10行不到的代码，却把事情干的如此出色！没有了解她原理的前提下即使把

2016-10-29 07:12:39 382

原创 Fibonacci数列

Fibonacci数列，一个让了解它的人无数次称赞它的神奇并且让人深深着迷的数列一个让不了解它的人无数次惊叹它的规律并且让人倍感呵呵的数列一、公式1、递推公式：f[i]=f[i-1]+f[i-2]2、通项公式：(一个完全是自然数的数列的通项公式却是用无理数表达的=w=）二、优美的神奇的性质1、与黄金分割如果做过黄金分割的题的童鞋来讲，即使你不知道黄金分割与

2016-10-26 13:54:38 724

原创快速乘法&快速幂&矩阵快速幂简单讲解

快速幂算法可谓是基础但极其巧妙而优美并且非常有用的的一类算法=w=这里介绍三种相关应用：1、快速乘法2、快速幂3、矩阵快速幂一、整数运算(a*b) mod c == ( (a mod c) * (b mod c) ) mod c对于2进制，2^n可用1后接n个0来表示、对于8进制，可用公式i+3*j == n （其中0），对于16进制，可用i

2016-10-26 00:25:27 1218

原创链表学习笔记

链表学习笔记链表的定义和特点链表定义链表特点链表分类链表的实现链表的定义和特点链表定义和数组一样，链表也是一种线性表。从内存结构来看，链表的内存结构是不连续的内存空间，是将一组零散的内存块串联起来，从而进行数据存储的数据结构。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域，即后继指针next和前驱指针prev链表特点链表在插入、删除的时候可...

2019-12-03 16:37:24 325

原创洛谷 P1629 spfa + 正难则返（反向建图）

题意：n个点，m条有向边，求从点1到各点再从各点回到点1的最小路程和从点1到个点——单源最短路从各点回到点1——由于是单向边，所以去和回所经过的路程可能不一样且都回到1——反向建图，重新转化成1到各点——单源最短路#include<stdio.h>#include<string.h>struct rec { int x; int y; ...

2019-09-23 09:04:12 351

原创洛谷P3905 Floyd

题意：n个点，m条边，每条边有自己的权值，删除其中d条边，问重新使点A到点B联通所需要恢复的边的最小权值和这个数据范围，只和删除的边的边权有关，不删除的边只需要记录联通情况即可以删除的边做floyd搞起将原来就有的m条边边权记录下来，f中记录成0——表示两点可以联通且经过不需要代价将删除的边在f中改成边权——表示两点可以连通且经过时需要花费原边权的代价#include&l...

2019-09-22 19:20:59 327

原创洛谷 P1090 合并果子堆维护动态最小值

题意：n个数，每次任取两个数合并，合并两个数的代价即为两数和，直至只剩下一个数，即进行（n-1）次合并。求代价和最小贪心，每次合并最小值和次小值（取两次当前最小值），并将合并所得的新数加入比较利用堆动态维护最小值#include<stdio.h>int n;int c[500010];int lowbit(int x) { return(x & ...

2019-09-20 23:24:44 219

原创洛谷 P2863 tarjan求强连通分量个数

题意：给定一个n个点，m条边的有向图，求大小大于1的强连通分量个数tarjan模板#include<stdio.h>#include<string.h>#define maxn 10010#define maxm 50010int time = 0, top = 0;int l = 0;int last[maxn], dfn[maxn], low[m...

2019-08-11 16:57:19 250

原创常用排序总结——比较排序

常说的排序一般指内部排序算法，即记录在内存中进行排序排序大体分为两种：比较排序，时间复杂度O（nlogn）~O（n^2），主要有：冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序非比较排序，时间复杂度：O（n），主要有：基数排序、计数排序、桶排序排序算法的稳定性排序算法的稳定性简单定义为：如果Ai = Aj,排序前Ai在Aj前，排序后Ai还在Aj前，则称这种排序算法是稳定...

2018-10-08 22:19:29 435

原创 noip2017提高组初赛（答案+选择题题目+个人分析）

被学弟学妹们逼着填坑的我瑟瑟发抖...一、单项选择题（共15 题，每题1.5 分，共计22.5 分；每题有且仅有一个正确选项）1. 从( )年开始，NOIP 竞赛将不再支持Pascal 语言。A. 2020 B. 2021 C. 2022 D. 2023C这让学Pascal的我感到了一丝不友好….2.在8 位二进制补码中，10101011 表示的数是十进制下的( )。A...

2018-06-12 14:29:01 53327 21

原创 bzoj 3339 线段树离线处理

题意：给定一个n个数的序列，多次询问，每次询问区间[l,r]的mex直接暴力显然不可区间[l,r]和区间[l',r']mex的情况：（1）[l,r]和[l',r']的mex值不同：[l,r]的mex值在[l',r']中出现或原本在[l,r]中存在而不在[l',r']中存在从而成为[l',r']的mex值（反之同理）（2）[l,r]和[l',r']的mex值相同：区间内出现的元

2017-05-04 10:46:28 788

原创 bzoj 3943 最大生成树

题意：给定n个数，每次任选两个数，将这两个数的xor累加到ans里并删除其中一个数，重复操作直到只剩一个数，求ans的最大值...一开始sb的写了个暴力贪心，在改了1h对拍后才发现naive的贪错了...于是果断放弃挣扎如果把比赛的两个人之间连边的话，n-1次操作后就会得到一棵树，实质上一棵树就对应着一种比赛的安排方案那么这题实际上就是求n*（n-1）边、n个点的最大生成树，边权为

2017-05-04 09:40:54 575

原创 bzoj 3132 二维树状数组

题意：一个n*m初始为空的矩阵，资磁两种操作：（1）某个子矩阵的值都增加c （2）输出某个子矩阵的权值和用a[i,j]表示（i,j）~（n,m）的增量，则对于（1,1）~（x,y）的权值和ansans=sigma（a[i,j]*(x-i+1）*（y-j+1））(1 =sigma(a[i,j]*(x+1)*(y+1)-j*(x+1)*a[i,j]-i*(y+1)*a[i,j]+

2017-05-04 07:47:41 721

原创 bzoj 1046 dp

题意：给定序列ai，m个询问，每次询问是否存在长度问len的上升子序列，如果存在多个输出位置字典序最小的那个判断是否存在长度为len的上升子序列只需要判断len与最长上升子序列的大小即可对于这种最后要求字典序最小的答案自然是尽量把字典序小的放前面那么我们就需要判断当前位置能否放在答案里也就是以当前位置开始的最长上升子序列的长度是否不小于当前所需要的长度也就是需要求出每个位置

2017-05-02 17:18:16 482

原创 bzoj 1016 kruscal+乘法原理

题意：求n个点、m条边的不同的最小生成树的方案数每种边权的边数量固定、作用固定先做一遍最小生成树，求出每种边权在最小生成树中的数量num[i]再从小到大对每种边权进行dfs，求出对于第i种边权，有多少种满足num[i]的取法根据乘法原理乘上即可对于已经处理完的第i种边权，把该种边权所有的边能加到最小生成树的就加进去，再进行下一种边权的判断注意并查集不要用路径压缩，不然不方便

2017-05-02 15:50:03 532 1

原创 bzoj 1211 prufer编码+排列组合

题意：n个点，允许任意两点之间连边，给定每个点的最终度数，求所有满足要求的树的个数bzoj 1005的简化版，关于prufer序列及答案化简请戳（我才不说我是懒得写了呢...）var ans :int64; i,j :longint; n,sum :longint;

2017-05-02 11:29:17 371

原创 bzoj 1005 prufer编码+排列组合+高精

题意：n个点，允许任意两点连边，给出某些点最终的度数，求所有满足要求的树的个数先介绍prufer编码：（一）将树转成prufer编码任意一棵n个点的树都会转成长度为（n-2）prufer编码度数为m的点，在prufer编码中出现的次数为m-1第i布时，删去叶子节点中标号最小的点及与它相连的边，并把与它相邻的点加入prufer数列（二）将prufer编码转成树设{a1,a

2017-05-02 11:23:05 541

原创 bzoj 4031 矩阵树定理

Description你突然有了一个大房子，房子里面有一些房间。事实上，你的房子可以看做是一个包含n*m个格子的格状矩形，每个格子是一个房间或者是一个柱子。在一开始的时候，相邻的格子之间都有墙隔着。你想要打通一些相邻房间的墙，使得所有房间能够互相到达。在此过程中，你不能把房子给打穿，或者打通柱子（以及柱子旁边的墙）。同时，你不希望在房子中有小偷的时候会很难抓，所以你希望任意两个房间之间

2017-05-02 08:18:21 457

原创 bzoj 2275 Fibonacci博弈齐肯多夫定理

题意：两个人进行Fibonacci博弈，若先手要有必胜策略，求他第一次至少要取多少个由Fibonacci博弈可知，如果当前石子数是fibonacci数，则先手必败，所以此时当前的先手必须全部取走齐肯多夫(zeckendorf)定理：任何一正整数都能拆成一堆互不相同的正整数的和，且一定存在一种取法取到不超过它的最大Fibonacci数var n,t :int64; f

2017-05-02 07:34:38 1275

原创 bzoj 3594 树状数组

题意：给定一个n个数的序列，可以最多任意选择k个区间并将区间内的数都加1，求操作后LIS的长度我们用f[i,j]表示前i个数被操作k次后LIS的长度f[i,j]=max(f[k,l])+1 (1三维偏序..用二维树状数组优化取max的过程注意：用二维树状数组第一维的上界是max（a[i]）+k,，第二维不能是[0,k]而是[1,k+1]uses math;var

2017-04-25 14:29:17 514

原创 bzoj 2705 欧拉函数

题意：给定一个n，求sigma（gcd（i,n））(1显然，sigma(gcd(i,n))=sigma(g*f[g]) (n mod g=0) ，其中f[g]表示gcd（i,n)=g 的个数g可以通过O（sqrt（n））的时间枚举出来，关键是求f[g]f[g]=sigma(1) (gcd(i,n)=g) =sigma(1) (gcd(i/g,n/g)=1) (“/”表示整除

2017-04-20 18:07:29 495

原创 bzoj 2190 欧拉函数线性筛

根据图显然如果我们沿着对角线把它切开，新形成的这两部分是对称，每一部分的答案为sigma（phi（i））（1那么整体的答案ans=2*sigma（phi(i)）+1 (对角线上只能看到一个点（1,1））（1线性筛1~n-1的欧拉函数即可var n :longint; ans :int64;

2017-04-20 17:42:35 404

原创 bzoj 3689 trie树+堆

题意：给定一个非负整数序列，两两异或，求前k小的异或值显然，如果一个数想和其他数异或尽量小，肯定是化为二进制后，从最高位起能选这一位相同的就选能和这一位相同的，实在没有再选和这一位不同的（当这一位不同，异或后的答案一定有2^i），这一位确定后再看下一位那么我们就对所有数的二进制建trie树，同时统计size（有几个数的这一位和当前数是相同的）然后所有数与其他数异或值的第二小（第一小是自

2017-04-20 14:50:13 427

原创 bzoj 2453 && bzoj 2120 分块

题意：给定一个序列，支持两种操作：（1）多次询问某个区间所含数字种类数（2）单点修改强行分块...对每个位置维护一个pre数组，表示当前位置颜色的上一个位置如果pre[i]每个块内对pre数组排序，询问时，在整块里每次二分找到l的严格下界，加到答案里；两边的散块暴力找对于修改就把影响到的块暴力修改即可..uses math;var n,m,q,x,y

2017-04-19 08:16:03 382

原创 bzoj 2594 LCT+离线处理+Kruscal

题意：给定n个点、m条边的无向图，支持两种操作：（1）删去一条边（2）询问当前图中（当前存在的边）最小生成树上的最大边权动态维护最小生成树如果暴力LCT套Krusacal，简直可以直接T到下辈子了..考虑删边离线，倒着做就变成了添边先求出删去所有需要删去的边后的的最小生成树，倒着加边，每加一条边判断是否与当前最小生成树形成环，如果没有就直接加入，如果有考虑是否需要更新最小生成

2017-04-18 21:25:02 448

原创 bzoj 3282 LCT

题意：Ｎ个点，每个点有一个权值，支持四种操作：（1）询问x到y的路径上的点的权值xor和（2）连接x到y（3）删除边（x,y）（4）将x的权值改成yLCT维护一下即可var n,m,op,x,y :longint; i :longint; w :array[0.

2017-04-18 21:05:53 463

原创 bzoj 1180 LCT

给出n个结点以及每个点初始时对应的权值wi。起始时点与点之间没有连边。有3类操作： 1、bridge A B：询问结点A与结点B是否连通。如果是则输出“no”。否则输出“yes”，并且在结点A和结点B之间连一条无向边。 2、penguins A X：将结点A对应的权值wA修改为X。 3、excursion A B：如果结点A和结点B不连通，则输出“impossible”。否则输出结点A到结点B

2017-04-18 20:58:17 322

原创 bzoj 2809 左偏树

题意：给定一棵n个点的树，每个点有各自的代价和价值，对以每个点为根的子树里最多能选多少点使得这些点的代价和不超过限制乍一看是维护代价小根堆，能选小的就选小的，然而复杂度原地爆炸那么换个角度，一开始对一个子树全选，最少丢弃多少点使得它们的代价和不超过限制显然是维护一个代价的大根堆我们就从下往上进行处理显然我们需要资磁合并、删除、快速找到代价最大的点显然左偏树uses ma

2017-04-18 08:13:16 435

原创 bzoj 3887 tarjan+拓扑排序

题意：给定一张有向图，从1开始随便走最后回到1，有一次机会可以反向沿着某条边走一次，求最多能经过多少个点，（每个点最多对答案贡献一次）如果不能反向走，那么答案就是１所在的强连通分量的大小当我们反了一条边后，答案就是反边后含１所在强连通分量的环如果我们断开我们所反的边和1，那么会形成两部分——从1所在强连通分量走出和回到1所在强连通分量所以我们先缩点再利用拓扑排序分别求出缩点后的

2017-04-17 20:51:50 477

原创和平委员会 2-sat

按照2-sat的套路直接写就好了...由于要求输出字典序最小的方案数，所以在新图上处理的时候按字典序最小的拓扑序进行染色（不用dfs进行传递）uses math;var n,m,l,x,y,tt :longint; time,top,size :longint; i :longint; vi

2017-04-17 14:33:58 774

原创 bzoj 3155 树状数组

题意：对序列ai维护一个前缀和序列Si，再对Si维护一个前缀和序列Ti，支持两种操作：（1）修改ai的值（2）查询Ti∑((x - i + 1) * ai) = ∑( (n - i + 1) * ai ) - (n - x) * ∑ai分别用两个树状数组维护var n,m :longint; i

2017-04-16 16:01:07 367

原创 bzoj 3333 树状数组+线段树

题意：给定一个序列，每次选择一个位置，把这个位置之后所有不大于这个数的数抽出来，排序，再插回去，求每次操作后的逆序对数对于我们每次选择的位置p，无论怎么操作，都不会对位置p之前的数的逆序对造成影响，也不会对[p,n]中大于a[p]的数的逆序对造成影响同时很容易发现，没进行一次操作逆序对数都是只减不增的所以我们能够得到一个结论：每次答案会减去参加重新的排序的数形成的逆序对数而且很容易

2017-04-16 15:13:11 370

原创 bzoj 2762 树状数组

题意：给出一些形如 ax+b（1）新加入一个不等式（2）删除一个不等式（3）询问当x=k时满足的不等式的个数对于每一个不等式，通过变形就可以得到使它成立的x的范围那么就变成区间修改，单点查询，树状数组维护就好注意：（1）讨论a=0、a>0、a （2）由于k有非正数，所以要加上10^6+1，树状数组的范围也改为2*10^6+1，而由于满足不等式条件的x

2017-04-16 14:54:02 377

空空如也

空空如也