10.1
目录补题
得分情况
100 + 0 + 40 + 15 = 155
T1 3631: elective
看一下数据范围可以发现 \(O(2^n)\) 可过
直接枚举所有课的选择状态 概率大于一半的取最大值就好了
T2 3632: seq
每一位是独立的 把操作拆到每一位上
如果算出的利用 \(C\) 能弄出那些数组 记为 \(tot\) 直接计算 \(\sum tot * C\)
考虑 \(k = 0\) 的情况 只能对一个区间异或 \(0\) 或者 \(1\)
对序列进行差分 将区间异或消成单点
将一个操作变成 \(l\) 到 \(r + 1\) 的边 把所有边弄出来 不同连通块之间不会相互影响 对每个连通块进行考虑
考虑一个连通块的任意一棵生成树 设有 \(n\) 个节点 考虑这棵树有多少种方案 每次操作异或两个节点 所以树上 \(1\) 的个数一定是偶数 对一个连通块 考虑每条边是否操作 最多只有 \(2^{n - 1}\) 种方案 用一个点的父亲控制这个点的值是 \(0\) 还是 \(1\) 可以保证用操作将除了根以外的所有点弄成需要的颜色 而根的位置的颜色无法通过父节点改变 所以最少有 \(2^{n - 1}\) 中方案
其实意会一下就是 \(2^{n - 1}\) 种方案
即一个连通块恰好有 \(2^{n - 1}\) 中方案 相当于 \(\frac {2^n}2\)
统计连通块个数 记为 \(cnt\) 意会一下答案就是 \(\frac {2^n}{2^{cnt}}\)
代码木有写出来
T3 3633: tree
标程线段树合并
但是点分和树启发都能过
对于 \(|i - j| \leq dis_{i, j}\) 有两种情况
即:
\[i - j \leq dis_{i, j} \]或
\[j - i \leq dis_{i, j} \]对应到点分治过程中的距离 式子大概能化一下:
\[i - j \leq dep_i + dep_j \]或
\[j - i \leq dep_i + dep_j \]同变量化到一边
\[dep_i + i \leq j - dep_j \] \[dep_i - i \leq - j - dep_j \]维护两个树状数组 可以将查询优化到 \(\log\) 级别 大概就能过了
T4 3634: graph
三十分做法
显然没有什么好说的
法一
构造图
大概这个样子 将上面那个点与从左往右连第 \(i\) 个点相连就可以为这张图增加 \(2^{i - 1}\) 棵生成树 然后直接做
法二
曾想听懂
但是结果可想而知
知识点
-
根号数据结构
-
根号分治
-
根号重构
-
分块
-
回滚莫队
-
三元环计数
-
线段树分治
-
线段树合并
-
启发式合并
数据结构
线段树
bzoj 4239
按照长高的顺序排序 维护每个位置最后一次收割时间 每次割草的时候 线段树上二分并打标记
草的单调性不会变 长得高的永远高 割了也是割成一样的
loj 6029
维护区间的最大值和最小值 当 \(\max - \max / w = min - min / w\) 打标记为区间减 如果不相等 每个最大值减去最小值的差至少会 \(/2\)
均摊复杂度两只 \(\log\)
CF576E
考虑离线怎么动态的判定一张图加上一条边之后是否是二分图 线段树分治 插入的时候用并查集维护颜色 复杂度两只 \(\log\)
但是不知道每次操作是否执行 直接离线有问题
默认每次操作都执行 假定确定了每条边的起始与结束
对于正常的线段树分治 即知道加那些边 假定某个位置有一个改变边的颜色的操作 不清楚颜色 但是知道操作区间 根据是否操作可以判断这个区间的颜色 在插入的时候干一些奇怪的事情 不标记颜色 在 \(dfs\) 一次处理的时候 在对不确定颜色的位置标记颜色 从左到右进行 不会出现未标记颜色的边的出现区间 之后正常的线段树分治
扫描线 单调栈
bzoj 2383
从左到右 维护一个 \(r\) 的单调递减的栈 与下一个气球相交的气球具有单调性 具体看课件
弃疗++
bzoj 5259
典中典
连续段的性质: \(r - l + 1 = \max - \min + 1\)
有个 \(r - l + 1 \leq \max - \min + 1\)
\(\max - \min + l - r \geq 0\)
计算上面那个东西等于零的个数
维护后缀的 \(\min\) 和 后缀的 \(\max\)
\(r\) 扫描线枚举 \(l\) 初始化
弃疗++
绿菇领主
连续段的性质 ???
loj 3153
仅考虑 \(a\) 和 \(b\) 则 \(a\) 和 \(b\) 一定是区间最大和次大 考虑维护这个东西
对右端点做扫描线 如果左端点是最大值 一定在单调栈上
弃疗++
树上数据结构
bzoj 4127
维护区间负数的最大值 区间正数的和 区间负数的和 区间正数个数 负数个数
区间加的时候对于负数特殊考虑 如果由负数变成正数就直接递归到底 否则打标记
bzoj 3626
首先差分 \(lca\) 的深度转换为点的个数 相当于求两点到根的路径的并
bzoj 4241
回滚莫队板子
apio2019 桥梁
离线 在询问的时间轴上分块 按照根号个修改分块 维护带撤销的并查集 用栈维护并查集 每根号个一次
没有修改 按照承重依次加入
将桥梁按照承重一次加入 维护根号个修改的情况 每根号个修改维护一个状态
维护每个时间点的时候 ... 难以描述
注意一下怎么没有加或者没有减
CF896E
分块
每个块开桶 链表维护这个值的所有位置 散块直接重构 整块的减少 最大值 \(\geq 2 \times x\) 将小于等于 \(x\) 的扔到后面 反之将 \(>x\) 的扔到前面
每次归并复杂度块内最大值的减少量 总复杂度 \(O(\sqrt n (V + m))\)
某题目
给一个 \(n \times m\) 的矩阵 \(A\) 和一个 \(n\) 的数组 \(a_i\) 满足 \(A_{i, 0} = a_i, A_{i, j} = A_{i - 1, j} + A_{i, j - 1}\) 单点修改 \(A_{i, j}\) 或者询问一个 \(A_{i, j}\) 的位置
\(n \leq 10^5, m \leq 20, q \leq 10^5\)
根号重构 每根号次操作重构一下 预处理根号次操作中的修改位置
弃疗++
数三元环
给 \(10^5\) 的无向图 数有几个三元环
将点按照 \(\sqrt n\) 分组 考虑枚举两个点的出边 如果一个点的出边是小于根号的 直接枚举出边 如果三个点都是大点 大点只有根号个
..
枚举小点的出边 枚举大点???
..
按照度数排序 分为大点和小点
如果三个点都是小点 直接暴力枚举
考虑有大点的情况
一个大点 两个小点
小点枚举边 再枚举大点
一个小点 两个大点
对于每个大点 枚举一个小点 再枚举一个大点
三个大点 暴力枚举
弃疗++
另
给边定向 原来的三元环有两种情况
加入每条边的时候定向 由小的点指向大的点 每个点的出度不会超过根号
杂
gym 102331F
loj2461
补
三元环计数
咕~