2023-08-25

树套树小结

树套树小结 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132501426 树状数组套权值线段树，实现过程类似主席树，采用动态开点实现 https://www.luogu.com.cn/problem/P3380 树状数组部分 线段树部分

2022-04-25

【GDOI2022PJD2T4 机器人】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16191401.html D2T4 机器人 题目 刚上初一的小纯特别喜欢机器人，这周末，她报名了学校的“小机器人俱乐部”，而进入俱乐部需要通过一场考试。 考试场地可以看作一个 n×mn \times mn×m 的网格图，行从上往下标号为 1,…,n1, \dots, n1,…,n，列从左往右标号为 1,…,m1, \dots , m1,…,m。每个格子有三种可能：空地，障碍物，机器人（有且只有一个），分别用“.”、“*”、“R”表示。现在小纯需要...

2021-11-24

【P1270 “访问”美术馆】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15600574.html 题目链接 典型的树形dp。 设 dp(x,i)dp(x, i)dp(x,i) 表示 xxx 的子树内逗留 iii 秒的作品最大值。 dp(x,i)=max⁡y∈xmax⁡i=0smax⁡j=2×zidp(y,j−2×z)−dp(x,j−i)dp(x, i)=\max_{y\in x}\max_{i=0}^s\max_{j=2\times z}^i dp(y,j-2\times z)-dp(x,j-i) dp(x,i)=y...

2022-04-29

【CF339D Xenia and Bit Operations】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16207447.html 题目链接 题目 Xenia the beginner programmer has a sequence $ a $ , consisting of $ 2^{n} $ non-negative integers: $ a_{1},a_{2},…,a_{2^{n}} $ . Xenia is currently studying bit operations. To better understand how they ...

2023-08-05

兔队线段树：楼房重建

兔队线段树：楼房重建 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132126096 https://www.luogu.com.cn/problem/P4198 本质：在线段树上每个节点维护信息时再深入到底部，加个 log⁡\loglog O(nlog⁡2n)O(n\log^2n)O(nlog2n) 总比 O(n2)O(n^2)O(n2) 优。 抽象到本题，就是对于每个线段树节点单独维护只考虑这个区间的答案。 合并的过程，显然左子树可以直接继承，所以可以...

2023-08-10

颜色类问题与分治：P7215

颜色类问题与分治：P7215 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132221132 https://www.luogu.com.cn/problem/P7215 化为点分治后，把原问题变成钦定一个点必选的问题 转化这一步是点分治维护颜色类题目的一个性质，如果某种颜色外面有，就会在外面被考虑，不需要在此层 对朴素分治也有启发，对于在大区间统计了的答案，就不需要在小区间统计了 考虑在钦定一个点必选时，怎么做，首先把它定义为根。 把每种颜色丢入一个...