前言

数据结构亦可赛艇！我已经中了树的煮粥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×ki\times k的组合个数，cnt[i]记录到目前位置i出现了多少次。
  2. 所以有转移：
    答案 += ans[当前值 ×k\times k];
    ans[当前值] += cnt[当前值 ×k\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