BZOJ3224 Tyvj1728 普通平衡树

BZOJ3224

Tyvj1728

本题可以使用平衡树,线段树,甚至std::vector通过。

splay的话直接做就可以了。

对于1操作,直接插,注意无需重复插入同一数字,用cnt数组统计数字出现次数即可。

对于2操作,先将要删的点splay至根节点,然后分4种情况。1.若根节点的cnt值大于1,将其-1;2.若根节点的cnt值等于1且无左右子节点,清空整棵树;3.若根节点的cnt值等于1且左右子节点无其中一个,将根结点一直另一子节点;4.若根节点的cnt值等于1且左右子节点都存在,找出根节点的前驱,将其splay至根节点,即可删除原来的根节点。注意在2,3,4情况时处理好父子节点的关系。

对于3,4,5,6操作,应用类似普通二叉查找树的方法即可。注意在5,6操作中可能存在查询不在树中的数字。

继续阅读BZOJ3224 Tyvj1728 普通平衡树

BZOJ1588 [HNOI2002]营业额统计

BZOJ1588

splay。

把每天的营业额加入splay,查找前驱和后继,统计即可。

注意使用双旋的splay,因为单旋在链状树的情况下时间复杂度会退化。具体证明去问Tarjan。

也可使用其他平衡树或双向链表。双向链表的做法可参考 朱晨光《基本数据结构在信息学竞赛中的应用》。

继续阅读BZOJ1588 [HNOI2002]营业额统计

[FJWC2016] 树上三角形

树上三角形

不妨设三条线段的长度分别a, b, c,且满足abc,由几何知识可知,若a + b > c这三条线段即可构成一个三角形。那么若要使得若干线段无法构成三角形,令a + b = c即可使线段总数最大。由于点权范围满足,那么当线段长度分别为1, 1, 2, 3, 5, 8, 13······时,线段总数最大。显然这个数列为斐波那契数列。由计算可知,斐波那契数列的第47项>,那么当u和v的简单路径上有大于46个点权时,必定存在以其中三个权值为边长构成的三角形。

预处理出每个节点的子节点来计算深度。

对于修改操作,直接修改即可。

对于查询操作,暴力枚举u,v的路径,若总数大于46即可输出Y,否则排序后判断。注意两边权相加后可能会溢出int/longint。

时间复杂度为

继续阅读[FJWC2016] 树上三角形

01 背包问题——遗传算法

一种仿生(?)的模拟优化算法。

Reference:

https://www.cnblogs.com/heaad/archive/2010/12/23/1914725.html

http://blog.csdn.net/v_july_v/article/details/6132775

遗传算法的0-1背包问题(c语言).doc

具体内容参考资料已经讲得很详细了,我就不再赘述了。

注意遗传算法是一种随机算法,需要适当地选择参数与迭代次数才能尽可能地保证答案准确性。

代码实现(较长):

继续阅读01 背包问题——遗传算法

字符串编码

字符串编码

day1里的T1。

字符串哈希+暴力。

对S,T这两个字符串进行哈希,令数字0...25表示小写字母a...z,设f[i][j]表示串S前i位的j字符的哈希值,g[i]表示串T的i字符的哈希值。那么对于一个从x起始的S的子串,若选中字符i,j,此子串与T匹配的充要条件是S[x+|T|-1][i]-S[x-1][i]=T[j]且S[x+|T|-1][j]-S[x-1][j]=T[i]。

在判断时只需枚举每个起始位置,枚举两个字符i,j,判断选中i,j能否使S的子串与T匹配即可。

时间复杂度

继续阅读字符串编码

3167逃离陷阱

题意:

给出n个点,求出到最近的 给出点 距离最长的点的坐标。

可以通过模拟退火来实现:

先随机出一个点A,再在以A为圆心,以R为半径,随机出一个点B。若ans(B)>ans(A),则用B来更新A。若ans(B)<ans(A),则以一定的概率P(dE) = exp( dE/T )来更新A,其中exp为自然指数,T是一个自己定的数,dE是ans(B)>ans(A)。

在每次随机点B后,R、T都要适当的减小,以便缩小随机范围和结束求解。

简单来说,模拟退火就是以一定的概率接受一个不是最优的解,来跳出之前的最优解,避免把局部最优解当成全局最优解

最后要注意常数T,和随机范围R的选取

继续阅读3167逃离陷阱

[NOIP2016]换教室

换教室

任意最短路算法预处理出任意两点最短路径,dist[u][v]即为点u与点v的最短距离。

求最小期望使用DP。

设f[i][j][0/1]到第i个时间段为止一共有j次申请,此刻不申请/申请的最小期望。显然f[i][j]与任意f[i-1][k],(k<=min(j,m))有关,还与申请是否被通过以及前后两教室的距离,即w[i]与dist[u][v]有关。

由期望的定义可知,

时间复杂度为

继续阅读[NOIP2016]换教室

[BZOJ 2734] [HNOI 2012] 集合选数

状压 DP

考虑如何构造出题目要求的集合。构造这样一个矩阵:


     i         3i        (3^2)i     ...
    2i       2*3i      2*(3^2)i     ...
(2^2)i   (2^2)*3i   (2^2)(3^2)i     ...
   ...        ...           ...     ...

注意矩阵中不能存在大于 n 的数,故矩阵各行列数不一定相等

则在该矩阵中题目给的选数规则等价于选取矩阵中横、纵向不相邻的数。

因为实际上矩阵长宽较小,故可以考虑用状压 DP 解决方案数统计问题。

令 f[i][j] 表示该矩阵第 1~i 行,第 i 行选取情况为 j 时的方案数,其中 0 < j < 2^(矩阵第 i 行列数

易知若 j & (j>>1) != 0,即 j 中存在连续两位为 1 时, f[i][j] = 0

f[i][j] = f[i][j] + f[i-1][k],即 f[i][j] 由 f[i-1][k] 转移得到当且仅当 j & k == 0,即 j 与 k 不重叠。

那么这个矩阵中的方案数即为所有 f[r][j] 的和(r 为矩阵行数)。

但是发现这个矩阵中并不包含所有 1~n 的数。因此要以每个当前没有出现过的数为第一个数构造矩阵。由乘法原理可知,总答案为所有矩阵方案数的积。

代码如下:

继续阅读[BZOJ 2734] [HNOI 2012] 集合选数

[POJ 1379] [CEOI 1999] 逃离陷阱

模拟退火。

概念见大白话解析模拟退火算法

实现:

首先随机在平面中取一个点 A,每轮都以这个点为圆心,R 为半径(每轮递减)随机选取若干个圆上的点 B。若点 B 已经优于 A,则直接用 B 更新 A,否则以一个概率 P(每轮递减)决定是否以 B 更新 A。这样就可以得到一个近似最优解。

在实现过程中,可以同时维护 20 个点,最后取这些点中的最优值作为答案。具体 R 与 P 的初始值与更新方式见代码。

代码如下:

继续阅读[POJ 1379] [CEOI 1999] 逃离陷阱