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...

2023-08-05

线段树分治

线段树分治 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132126153 https://www.luogu.com.cn/problem/P5787 理解： 操作离线 用时间线段树维护 整体统计答案，进入到某个节点加入，离开时撤销 可以用可撤销数据结构维护（可能可以可持久化或LCT维护？以后再学）

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”表示。现在小纯需要...

2023-08-06

线段树合并思想

线段树合并思想 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132135188 直接维护很大，所以每个节点动态开点。 合并时按顺序，一个有一个没直接把有那个连上去。 否则递归。

2023-08-10

点分治过程中维护李超线段树：CF1303G

点分治过程中维护李超线段树：CF1303G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132219909 https://www.luogu.com.cn/problem/CF1303G 看到这题，首先很容易想到树形dp，但发现要维护两个值，一个为末项，一个为和，很好分析出这个东西有凸性。 这个时候有两种做法，维护凸包或李超线段树。 之所以用李超线段树，是可以想象出维护末项（k）和和 （b）之后最终的答案其实之和队对面的深度（x）有关，而这个大胆猜测可以...

2022-01-10

【CF5E Bindian Signalizing】题解

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15784242.html 题目链接 题目 Everyone knows that long ago on the territory of present-day Berland there lived Bindian tribes. Their capital was surrounded by n n n hills, forming a circle. On each hill there was a watchman, who watch...