【codeforces】数据结构杂题

2016年10月23日2,8680

一些数据结构简单题:

570C.Replacement
427B.Prison Transfer
519B.A and B and Compilation Errors
650A.Watchmen
466C.Number of Ways
CHSEQ22.Chef and Favourite Sequence
460C.Present
459D.Pashmak and Parmida’s problem
528A.Glass Carving
704A.Thor
339D.Xenia and Bit Operations 527
527D.Clique Problem
718D. Andrew and Chemistry

570C.Replacement

给定一个长为n的字符串(包含小写字母和’.’),有m次操作
每次操作可以修改字符,并询问修改后有多少对相邻的’.’
\(1\leq n,m \leq 10^5\)

题解

每次修改的时候判断一下与其相邻的两个字母,更新答案

427B.Prison Transfer

给定长为 n 的序列,以及 c,t
问你有多少个连续的长度为 c 的子串,且序列中没有一个超过 t

\(1\leq n,c \leq 10^5,1\leq a_i,t\leq 10^9\)

题解

从左往右扫过序列,记录最后一个超过 t 的元素位置

519B.A and B and Compilation Errors

给定三个序列,长度分别为 n,n-1,n-2,每一行是上一行的序列去掉一个元素

要求输出去掉的元素
\(1\leq n \leq 10^5,1\leq a_i,b_i,c_i\leq 10^9\)

题解

排序,双指针对比

用个hash/map统计下元素出现次数

650A.Watchmen

给定二维平面的n个坐标,求满足\(|xi-xj|+|yi-yj| = \sqrt{(xi-xj)*(xi-xj)+(yi-yj)*(yi-yj)}\)的点对数

\(1\leq n \leq 10^5,1\leq x_i,y_i\leq 10^9\),可能有重点

题解

发现符合条件的点对在同一行/列
排序/用map/哈希表统计

466C.Number of Ways

给定长为n的序列\(a_i\),将其分成3个连续子串,要求每个子串的和相同,求划分的方案数

\(1\leq n \leq 10^5,-10^9\leq a_i\leq 10^9\)

题解

求出前缀和,后缀和,整个序列的和sum
找出等于sum/3的前缀和,以及其后有多少个sum/3的后缀和
可以通过预处理或者,或树状数组/线段树在线维护查询

CHSEQ22.Chef and Favourite Sequence

一长度为n的0,1序列,初始时所有元素为0。
有m个区间\([L_i,R_i]\),可以任选若干个区间进行区间翻转操作(0变1,1变0),问可以得到多少种不同的序列
答案对\(10^9+7\)取模
\(1\leq n,m \leq 10^5\)

题解

考虑将一段区间取反,相当于将它的差分序列的l和r+1俩个位置取反

如果某一项操作可以用其它一些操作替代的话,它就可以直接被舍弃了,可以用一个并查集来维护

最后剩下k个操作,答案就是\(2^k\)

460C.Present

有n盆花,编号1到n,每盆花都有高度值\(h_i\)
浇m次水,每次只能浇连续的w盆花,每浇一次,被浇的花高度值+1。
要求让其中最矮的花最高

\(1\leq n,m,w \leq 10^5,1\leq a_i\leq 10^9\)

题解

二分最优解,贪心判定
从左到右,如果某盆花小于二分值,将其以及后面的w盆花+1
用线段树/差分+前缀和维护

459D.Pashmak and Parmida’s problem

给定长为n的序列\(a_i\),定义\(f(l,r,x)\)为\(a_i\)的下标l到r之间,等于x的元素数。
问数对i,j的数目,符合\(f(1,i,a[i])>f(j,n,a[j])\)。
\(1\leq n\leq 10^5,1\leq a_i\leq 10^9\)

题解

用map/离散化预处理出\(f(1, i, a[i])\)和\(f(j, n, a[j])\)
类似求逆序对,树状数组/线段树维护

528A.Glass Carving

给定w*h的玻璃,m次操作
每次操作,给出一条平行于坐标轴的直线切割玻璃,询问切割后剩下的最大面积的完整玻璃

题解

行列分开,用set维护横纵坐标差值的最大值

可以离线倒序处理

704A.Thor

给定n个邮箱,m个操作:
1.给x号邮箱塞1封信
2.把x号邮箱的信全部读完
3.把接受到的所有信的前x封读完
每个操作之后输出当前未读的信件数量
\(1\leq n,m\leq 3*10^5\)

题解

对每个邮箱维护一个队列,记录这些邮件的编号,并且记录每个编号邮件在哪个邮箱
每次模拟操作,每个邮件进队/出队各一次

339D.Xenia and Bit Operations

给定长度为\(2^n\)的序列,第一次操作将相邻的n对数字进行或运算,第二次操作将相邻的n/2对数字进行异或运算,以此类推

有m次询问,每次修改原序列一个数字,问进行操作以后剩下的最后一个数字

\(1\leq n\leq 17,1\leq a_i\leq 2^30,1\leq m\leq 10^5\)

题解

线段树模拟
每次询问可以自底向上修改

527D.Clique Problem

给n个点,坐标\(x_i\),权值\(w_i\),求最大的子集大小,该集合中任意两点满足\(w_i + w_j\leq |x_i - x_j|\)。
\(1\leq n\leq 2*10^5,1\leq x_i,w_i \leq 10^9\)

题解

按\(x_i-w_i\)排序之后,树状数组优化dp
将每个点视为线段\([x_i-w_i,x_i+w_i]\),问题就转换为最多的不重叠的线段数
排序贪心解决

树的同构

给定两棵n个点的有根树,求两棵树是否同构(相同)

\(1\leq n\leq 10^5\)

自下而上哈希

对于一个父亲节点,将其所有子树的hash值排序,其得到的数组用各种方法hash即可计算出父亲节点所代表的整个子树的hash值

无根树?

寻找树的重心,将其变为有根树!

 

718D. Andrew and Chemistry

给定一棵树,每个结点的度数小等于4

要在树上加一个结点,加完后度数依然小于4

问有多少不同构的加法

\(1\leq n\leq 10^5\)

题解

树的同构有经典的哈希做法,我们设法通过预处理,快速求得『在每个结点上加上一个结点后,新树的哈希值』

在树形递推的时候加上记忆化,mp(x,y)表示y的子树x的哈希值

由于树的度数很小,可以直接把每个结点x的儿子的哈希值一起放在vector里排好序,再把vector放到map里编x的哈希值