2016 Pre-summer Training Ⅳ - Data Structure

前言

数据结构亦可赛艇!我已经中了树的煮粥XD坐等官方题解,学习一波剩下的题Orz 丧病韬面向AC出数据,至今不会那题TAT


B. 发糖游戏1+1

题意

两种姿势发糖,具体看题目描述= =

分析

  1. 线段树 单点更新,区间查询 + 区间更新,单点查询

思考

  1. 坑点: 无。
  2. 技巧: 基础。

E. 组队方案数

题意

寻找公比为k的三个数的个数(这三个数根据相对位置从左到右排列)。

分析

  1. 找等比数列。相对位置确定,如果当前数字为x,那么我们从后往前统计的话,就能知道有多少个kx,顺带也能统计出kx之后有多少个kkx。使用两个map,一个存kx,一个存kkx。2. 设两个map分别为ans和cnt,ans[i]记录i和$i\times k$的组合个数,cnt[i]记录到目前位置i出现了多少次。
  2. 所以有转移:
    答案 += ans[当前值 $\times k$];
    ans[当前值] += cnt[当前值 $\times k$];
    ++cnt[当前值];

思考

  1. 坑点: 公比为0、1之类的。之前转移没考虑清楚还特判这种情况,现在的转移不需要特判。
  2. 技巧: 思考。

F. goozy挑战最强大脑

题意

初始总值为1,操作1:总值乘X,操作2:总值除第X次出现的乘数。给出每次操作之后总值模72807249之后的值。

分析

  1. 除一个以前乘的数,相当于那个数变成了1。
  2. 线段树单点更新,区间查询。

思考

  1. 坑点: 区间查询用query会慢,由于是总区间值,直接输出sum[1]就好了。
  2. 技巧: 转换思维。

G. 线段树写个爽

题意

如题,各式区间更新。

分析

  1. 操作1需要全部加上一个值c,最基础的区间标记。
  2. 操作2标记区间左值和右值以及公差
  3. 操作3标记是否转换即可
  4. 操作4,区间查询

思考

  1. 坑点: 记得开long long啊,不然WA个爽!另外细节要考虑清楚!
  2. 技巧: 凡是涉及到修改数据的操作,都要标记下传。如果有操作3存在,那么它之前的其它操作都无效。

H. 这是一个标题

题意

求区间最大连续和。

分析

  1. 三个标记,lsum从左开始的最大和,sum区间最大和,rsum从右开始的最大和。区间合并经典题。

思考

  1. 坑点: 无。
  2. 技巧: 设定状态,好好转移。

K. 这是一颗普通的树

题意

这是一颗普通的树,普通到需要树链剖分才能解决。

分析

  1. 树链剖分之后就是基础的线段树操作了。

思考

  1. 坑点: 无。
  2. 技巧: 树链剖分。

L. 数列维护

题意

完成对数列的五种操作。

分析

  1. splay。推荐hiho一下 104 周和 105 周的splay专题。
  2. 基于splay的特点,每次都能将需要操作的一段区间旋转到特定子树上,所以操作就好进行了。

思考

  1. 坑点: 无。
  2. 技巧: splay。

具体代码点击下方传送门:)

传送门


广告时间

Java学习网站: how2j

VPS: VPS

梦想世界上每个人都能给我一元钱,2333