本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-22 22:12:34

11.17 ~ 11.23

11.17 限时训练

T1

P12016 [NOISG 2025 Finals] 震踏 - 洛谷

用到了曼哈顿距离和切比雪夫距离的转化，对于这种需要旋转坐标系的问题非常有帮助，然后就是发现相对位置是不变的，所以直接前缀加单点查，树状数组维护即可。

T2

P12194 [NOISG 2025 Prelim] Snacks - 洛谷

直接写了个大力线段树维护，每次操作区间赋值单点加，区间求和。

T3

P12017 [NOISG 2025 Finals] 可达性 - 洛谷

一个不错的树形 dp，考虑设 $f_{i,j}$ 表示 $i$ 子树内可达 $j$ 个点是否合法，转移根据 $l_u = l_v$ 分类讨论，然后按照每条边是否连通分类讨论即可。

T4

P12018 [NOISG 2025 Finals] 机器人 - 洛谷

发现对于最右边的每个点，能到达他的点是一段连续的区间，于是问题变成了给定 个区间 ， 次询问区间 ，询问覆盖区间 需要最少区间数量，可以直接倍增维护。具体的维护倍增从每个点出发，向后最远能到哪，然后跳倍增数组即可。

11.18 模拟赛

T1

Problems

发现一个性质是，最大值要么是 $0$，要么是 $1$，于是问题变成我们需要找到有多少个区间满足 $mex = len + 1$，也就是整个区间排序后是 $0,1,2,3,4,\dots,len - 1$。

发现必须经过 $0$，于是考虑按每个 $0$ 分段处理，由于知道了区间最大值就可以知道区间长度，因此我们亲定最大值位于左边，右边的情况我们反转序列再做一遍即可。

之后我们考虑枚举左端点的位置，维护前后缀 $\max$，这样我们可以求出区间长度，也就求出了右端点位置，然后判断右端点的最大值是否合法，这样我们就只需要知道，这段区间是不是数字各不相同即可。

如何维护这个东西呢？其实可以直接对每个位置 $i$ 维护 $i$ 向后最远到哪能满足这段区间内每个数只出现一次，然后就做完了。

T2

Problems

考虑把变化维护到折线上，每次分治暴力枚举区间，时间复杂度 $n \log n$，还需要主席树维护一下前后缀信息，具体的可以去看官解，感觉口胡太麻烦了。

T3

反射容斥，还不会 \kk ~~。

11.19 限时训练

T1

P9350 [JOI 2023 Final] 宣传 2 / Advertisement 2 - 洛谷

考虑贪心的从大到小做，然后变成了一个二维数点？实则发现合法转移式子两个是肯定同时满足的，于是维护两个值，一个排序，另一个维护单调栈即可。

T2

P14294 [JOI2024 预选赛 R2] 白色灯 2 / White Light 2 - 洛谷

很简单的一个 dp，考虑设 $f_{i,0/1/2}$ 表示前 $i$ 个灯合法，最后一个是 $0/1/2$ 颜色的最小花费，转移是好写的，注意把 $f_{i,2}$ 初始化成前缀全都熄灭的花费即可。

T3

P7405 [JOI 2021 Final] 雪球 / Snowball - 洛谷

很有难度的一个题。

首先你需要发现一个性质：每个雪球的贡献点是一段区间。

然后发现当两个雪球之间的区间端点确定了，就不会再变了，于是我们可以考虑暴力维护这个东西，复杂度 $O(nq)$。

考虑怎么优化呢？这一步非常困难，你发现这东西是具有可二分性的，二分最终确定端点的时间，就可以处理出每个端点，时间复杂度 $O(n \log q)$。

T4

P7804 [JOI Open 2021] 决算报告 / Financial Report - 洛谷

发现题目其实就是要让我们找一个上升子序列，我们发现对于 $i$ 能转移过来的 $j$ 是一段区间，我们可以用并查集维护这个东西，然后我们按照值从小到大去做，每次转移找到转移区间，线段树维护即可。

T5

P12196 [NOISG 2025 Prelim] Lasers 2 - 洛谷

哇好牛的一个题，考虑最大的这个块一定要被挡住，然后考虑 dp。

设 $f_{i,j,0/1}$ 表示前 $i$ 列，有 $j$ 个位置是能照到的，有没有出现 $mx$ 长度的照不到区间，不需要移动的贡献和最大值，发现转移实际上时对于右端点位于 $i$ 的区间，覆盖到的范围加上一个它的权值，于是线段树维护即可。

P12196 [NOISG 2025 Prelim] Lasers 2 题解 - 洛谷专栏

T6

哇这题太难了，我们发现当我们使用 $3$ 个数字一组，用 $4$ 组凑一个人，那么我们需要满足任意 $4$ 组组成的一个序列一定有一个人，否则我们可以先走这个东西，然后再走到某个位置，这样就确定不了一个必定赢的人了。

然后拿背包把这些合并起来即可，感觉代码太难写了，直接盒了。

11.20 模拟赛

T1

Problems

简单题，考虑排序后双指针指一下即可。

T2

Problems

发现排序后后面的是前面的倍数，类似一个进制形式的东西，同时发现这样的 $v$ 只会有 $\log$ 种，于是我们考虑对于 $v = a_i$ 如果他没被选中，可以把 $k$ 个合并成一个 $v = a_{i + 1}$ 的物品，同一类按照性价比选即可。

T3

不会啊，反射容斥（刚刚那个 T3 好像不是反射容斥）。

T4

Problems

发现这东西一定是从小到大推平，我们推出式子，发现从两边先搞一定是更优的，然后就是要维护前后缀最小值，区间修改，线段树维护即可。

11.21 限时训练

P14333 [JOI2021 预选赛 R2] 安全检查 / Safety Inspection - 洛谷

考虑这东西可以二分，然后 check 考虑从后往前做，这样走到后面的人过来就不需要花费路程，只需要花费工时。

P14331 [JOI2021 预选赛 R2] 煎饼 / Pancake - 洛谷

数据范围很小，状态数可以搞得下，直接搜索就行了。

一些杂题

P14566 【MX-S12-T1】取模 - 洛谷

简单题，发现答案是 $\max(x - y,z)$，这里 $x = \max(a_i),y = \min(a_i)$，$z$ 为严格次小。

P13520 [KOI 2025 #2] 存放箱子 - 洛谷

考虑相当于是给了一些区间，要求最少集合，使得同一集合内区间不相交，线段树维护即可。

P4317 花神的数论题 - 洛谷

考虑数位 dp，然后统计答案即可。

P2610 [ZJOI2012] 旅游 - 洛谷

将这棵树建出来之后，其实就是求树的直径。

T686591 「IDT41-D」旧影 - 洛谷

感觉这题没啥营养啊，就是直接 $f_i$ 表示以 $i$ 结尾的最大权值，然后动态开店权值线段树维护 $dp$ 值即可。

P3116 [USACO15JAN] Meeting Time S - 洛谷

图上 dp 板子题，按照 topu 序 dp。

P10613 [PA 2008] Cliquers - 洛谷

整数拆分的模板，这个要好好看一下。

P5290 [十二省联考 2019] 春节十二响 - 洛谷

dsu on tree 好题，考虑两棵子树该如何合并，按照这种方式合并起来即可。

P2061 [USACO07OPEN] City Horizon S - 洛谷

考虑从前往后维护一下当前最大值，貌似还可以 ODT？直接维护一下最大值和贡献区间即可。

P7924 「EVOI-RD2」旅行家 - 洛谷

P1407 [国家集训队] 稳定婚姻 - 洛谷

几个简单的 tarjan。

ABC

感觉没什么好题，其中 E 是个大模拟，F 是组合数推式子，用组合恒等式优化一下就行了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-29 21:44:06

省流

输麻了被 T2 创飞了，打的不好，可能会继续冲。

某一天，我不再把离开当作失去。

Day.-4 （11.24）

考前一周模拟赛每天只有 $100$ 出头，mx 模拟赛太难了，回去 wfyz 了，感觉开摆了。

其实没有想到 NOIP 会这么难，但这些都是后话了。

夕阳无限好，只是近黄昏。

Day.-2 （11.26）

晚上依旧举办了神秘仪式，这一次隆重了很多啊，还上去唱了歌，感觉很好玩，机房老资历全都回来了，玩的很开心，不知不觉已经开摆两天了。

听了 KSCD_ Iceturky Pigsyy 和 lzx 合唱的 蜂鸟，超级好听，发现宝藏歌曲，KSCD_ 延迟有点难崩。

人生天地间，忽如远行客。

Day.0 （11.28）

早上没睡太晚，吃了个饭就去学校了，去找了 typ 玩，然后就在机房玩了一会 2k，中午吃饭记错时间了，急急忙忙吃完了，有点难崩。

下午坐车去酒店，发现酒店居然给我们开成了家庭房，后面才告诉我们原来是开错了。拍完合照就去吃饭了，吃了必胜客不是说吃完必胜客就必胜吗，呆了一会就去试机了。

进考场发现考场好大啊，面基了 xz，居然还有一套模拟赛，场上的 NOI Linux 这么丝滑，后悔没有多玩一会。出考场看到了 qqqaaazzz，在大门口合照，喊出了我们的口号：编程不复杂，难题找阿史。

收到了来自各个地方的祝福。

晚上回去十点就睡了，悲剧就此发生——

何处合成愁？离人心上秋。

半夜很久都没睡着，可能也是想了很多事情，也想起了很多以前的东西， 总而言之，心里有很多事情，而且感觉试机看到题没有任何感觉，可能内心很慌。

半夜 $1:19$ 醒了一次，感觉有点冷，心里想了很多东西，感觉睡不大着。

月落乌啼霜满天，江枫渔火对愁眠。

半夜 $3:29$ 又醒了，尝试重新睡觉无果，起来走了走，实在感觉睡不着了，可能是感受到了发自内心的某种感觉，又过了很久，一会冷一会热，就是睡不着。

终于在 $4:16$ 左右突然发现脑子里想的东西不那么多了，然后开始睡觉，一直睡到起床。

Day.1 （11.29）

“蜂鸟是唯一能向后飞的鸟”

早上起来状态还不错，给自己打气，早餐没吃太多，然后就去考场了。

进场很顺利，只是最开始怎么还不让上厕所，xz 说我已经高一了，让我加油打！

进场开题，先看了看 T1，很快发现只会选一个取多块糖果，于是很快做完了，但是明显能感觉到自己做题做的很急，非常害怕后面没时间，好在是几乎没调试就过了大样例，此时 $8:50$，以为这把要赢麻了。

然后看了 T2，这题怎么这么难，T3 一看也是困难题，而且感觉最近 T3 都是难于 T4 的，看了看 T4，觉得有很多可写的暴力，于是决定先想 T4 暴力。

很快想到了对于 $len$ 分类维护，但是最开始只想到了用 ST 表，发现貌似过不去，不知道该咋搞。

想到了单调栈，很快想到了单调队列，然后就会了一个复杂度 $O(n \times len + nq\times len)$ 的做法，发现可以有 $40$ 决定开写，此时大约 $9:15$。

发现直接写会爆空间，精心计算分讨了一下，最终把空间压到了 $470M$，终于能过了，于是开始写，写完输出调试了一会，改了几个错误，很快调出来了，然后大约已经 $10:00$ 了。

Day.1.3 （11.29）

心里太多事我不会表达，但我把错归结于自己，我怪不了任何人。

然后开始开 T2，很快发现可以对于 $x,y,z$ 计数，这里表示最后选的 $1$ 和最前面不选的 $0$，然后推了推复杂的式子，写了 $3$ 张草稿纸，决定开写，初步给自己定的时间是到 $11:35$ 就去打暴力。

时间到了，但是还是没调出来，此时觉得想到队线必须要切 T2，实在是有些急了，心里不知道该怎么办，思索片刻决定继续冲正解，毕竟本身感觉不能到队线，省一没啥用。

最后写了 T3 $8pts$ 暴力，然后 T2 没调出来遗憾离场。结束之前都觉得自己要完蛋了，直到结束那一刻 xz 告诉我他 T2 也没调出来，并且和我大样例输出一样，终于感觉可能这题确实很难调。

总而言之，这一次又炸了，不知道该咋办，出门很难过，也很不知所措，不知道将来到达应该如何是好，内心充斥了空虚和犹豫。

上车一问，莫非我的 T1 也假了，这下彻底玩完了，预估分数 $[0,100] + 20 + 8 + [0,40]$，总共 $[28,168]$，看了看云斗榜单在 FJ 能排 60 左右，在 SD 感觉可能和 S 差不多，在 90 上下吧。

如果向花礼拜，能和你在春天相遇吗？

中午出去吃了烧烤，很好吃，但是没太有心情吃，感觉很无奈啊，不知道该说什么。

回家立刻就开始研究 T1，从脑子里写下自己代码，交上去一看怎么真 WA 了一个点，仔细研究发现自己忘记判断 $pre > m$ 了，好在是场上写了，拍了 $13010$ 组没挂，于是把拍子关了。

晚上 ABC 娱乐打法，写了 $5$ 个就跑路了，想不到今晚 FG 都这么难，居然排到了 rk300，也算是有点安慰，看云斗还没出 SD 榜，希望明天起床能看到吧。

结束了吗？

此情可待成追忆，只是当时已惘然。

或许比起沉浸在过去，我们更应该着眼未来，过去固然值得留恋，可时间的齿轮不会停止转动。NOIP 打输了，希望省选能翻盘吗，亦或者，等待明年再次相遇。

后记

只恐双溪舴艋舟，载不动许多愁。

未来就在眼前，过去已成历史，lcw 说过，打 OI 是长远的事情，或许当我们把目光放长远，就能看到不一样的世界。当然在最后的最后，还是要：

过去已经凝固

我带着回忆向前

只是时常疏于保管

回忆也在改变着各自的形态

这给我的追忆旅程带来些许挑战。

我该在哪里停留？

我问我自己。

希望能让我排名不要太靠后~

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-20 19:28:32

CF1249D2 Too Many Segments (hard version) 题解

原题链接

题目描述

给定 $n$ 个区间以及一个数字 $k$，每对 $l,r$ 覆盖的区间会 $+1$，求至少要删除多少个区间才能使得每个位置的值都不超过 $k$，输出删除的最小个数 $m$ 及删除的方案。

做法

看到数据范围，$n$ 是 $2\times10^5$ 的级别，我们需要一个 $O(n \log n)$ 的做法。

首先我们处理区间加减，这一点可以使用差分数组实现，我们在需要修改开头 $l$ 位置 $+1$，在结尾 $r + 1$ 位置 $-1$。

然后我们来考虑怎么样删除可以使得删除数量最少。由于删除的先后没有影响，所以我们可以从左往右依次检验每个点，所以要先把区间按照左端点从小到大排序。

我们考虑，对于一个点，我们考虑删除包含它的区间，我们可以每次将所有左端点小于等于当前点位置的区间都存起来。

那么我们怎么删除一些区间可以使得结果更优呢？

不难想到，对于所有位于当前点 $i$ 前面的点都已经被处理完了，所以我们删除的区间要尽可能地对 $i$ 后面的点产生贡献。

所以删除的方法就显而易见了，我们每次在所有的存储下来的对 $i$ 有贡献的区间里面，优先选择右端点 $r$ 靠右的区间，这样可以使得这个区间尽可能对后面较多的点产生贡献。

于是我们可以使用优先队列来存储这些区间，在优先队列中我们按照右端点从大到小排序。每次取出堆顶区间，由于当前区间对 $i$ 前面的所有点都没有了贡献，所以我们可以直接在差分数组上把 $i$ 处 $-1$，并把 $r$ 处 $+1$，直到当前节点值 $\le k$，再继续往后处理。

在处理同时将每次选出的堆顶区间记录下来，让 $cnt + 1$，最后输出即可。

AC Code

#include<bits\/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int maxn = 2e5 + 10;
struct note{
	int l,r,id;
}se[maxn];

bool cmp(note a,note b)
{
	return a.l < b.l;
}

struct ccmp{
	inline int operator () (const note &a,const note &b) const
	{
		return a.r < b.r;
	}
};

int d[maxn];
priority_queue<note,vector<note>,ccmp> q;
vector<int> ans;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	int n,k;
	cin >> n >> k;
	for(int i = 1;i <= n;i++)
	{
		cin >> se[i].l >> se[i].r;
		se[i].id = i;
		d[se[i].l]++;
		d[se[i].r + 1]--;
	}
	sort(se + 1,se + n + 1,cmp);
	int now = 1;
	int cnt = 0;
	for(int i = 1;i <= 2e5;i++)
	{
		d[i] += d[i - 1];
		while(now <= n && se[now].l <= i)
		{
			q.push(se[now]);
			now++;
		}
		while(d[i] > k && !q.empty())
		{
			note p = q.top();
			q.pop();
			d[i]--;
			d[p.r + 1]++;
			cnt++;
			ans.push_back(p.id);
		}
	}
	cout << cnt << endl;
	for(int i = 0;i < cnt;i++) 
	{
		cout << ans[i] << " ";
	}
	return 0;
}

如果想要看弱化（数据范围较小）版本，请移步 CF1249D1 Too Many Segments (easy version)。

感谢阅读，希望对你有所帮助。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-20 19:30:15

CF1249D1 Too Many Segments (easy version) 题解

原题链接

题目描述

给定 $n$ 个区间以及一个数字 $k$，每对 $l,r$ 覆盖的区间会 $+1$，求至少要删除多少个区间才能使得每个位置的值都不超过 $k$，输出删除的最小个数 $m$ 及删除的方案。

做法

看到数据范围 $n \le200$，我们可以接受 $O(n^3)$ 的做法。

首先我们处理区间加减，这一点可以使用差分数组实现，我们在需要修改开头 $l$ 位置 $+1$，在结尾 $r + 1$ 位置 $-1$。因为可以接受 $O(n^3)$，所以也可以直接暴力修改。

我们直接枚举每个位置，看每个位置上该点是否符合条件，如果不符合条件，那么我们优先删除包含当前点，未被删除，右端点尽可能大的区间。

为什么要右端点尽可能大呢？

我们考虑当前枚举到 $i$ 那么它前面的所有点一定都符合条件，所以我们应该让删除的区间尽可能包含更多后面的点，显然这样更优。于是我们直接把所有区间按照右端点排序，然后暴力枚举判断即可。

这样外层枚举位置 $i$，内层枚举区间并暴力删除，这样最劣的复杂度是 $O(n^3)$ 的，可以通过。

同时我们可以使用差分优化掉暴力修改的一维，时间复杂度为 $O(n^2)$。

但是显然在加强版中还是无法通过，所以还可以继续优化下去，我们分析可以知道代码主要的复杂度在枚举每一个区间上面。我们考虑怎么样避免枚举的复杂度。

这时候就需要使用数据结构及一些技巧了。

我们考虑既然从左到右判断每个点，那么当我们把整个区间都按照 $l$ 值从左到右排序，那么每次这个点只会使用到左端点小于它的区间。

同时我们要使得右端点尽可能的大，所以我们可以维护出一个优先队列。我们在优先队列中按照区间的右端点排序，这样每次取出堆顶都是满足条件的右端点最大的区间，我们再差分删除这个区间即可。

这样外层枚举位置为 $O(V)$（值域），内层优先队列为 $O(\log n)$。由于值域 $V$ 和 $n$ 同阶，所以复杂度为 $O(n \log n)$，足够通过强化版本。

AC Code

#include<bits\/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int maxn = 2e5 + 10;
struct note{
	int l,r,id;
}se[maxn];

bool cmp(note a,note b)
{
	return a.l < b.l;
}

struct ccmp{
	inline int operator () (const note &a,const note &b) const
	{
		return a.r < b.r;
	}
};

int d[maxn];
priority_queue<note,vector<note>,ccmp> q;
vector<int> ans;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	int n,k;
	cin >> n >> k;
	for(int i = 1;i <= n;i++)
	{
		cin >> se[i].l >> se[i].r;
		se[i].id = i;
		d[se[i].l]++;
		d[se[i].r + 1]--;
	}
	sort(se + 1,se + n + 1,cmp);
	int now = 1;
	int cnt = 0;
	for(int i = 1;i <= 2e5;i++)
	{
		d[i] += d[i - 1];
		while(now <= n && se[now].l <= i)
		{
			q.push(se[now]);
			now++;
		}
		while(d[i] > k && !q.empty())
		{
			note p = q.top();
			q.pop();
			d[i]--;
			d[p.r + 1]++;
			cnt++;
			ans.push_back(p.id);
		}
	}
	cout << cnt << endl;
	for(int i = 0;i < cnt;i++) 
	{
		cout << ans[i] << " ";
	}
	return 0;
}

如果想要看强化（数据范围较大）版本，请移步CF1249D2 Too Many Segments (easy version)。

感谢阅读，希望对你有所帮助。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-05-13 08:40:54

P3806 【模板】点分治 1 题解

什么是点分治

当一道树上题目可以离线，想要求得子树内或路径上的某些信息时，就可以使用点分治。

来看这道题目。

题目描述

给定一棵有 $n$ 个点的树，询问树上距离为 $k$ 的点对是否存在。

• 对于 $100\%$ 的数据，保证 $1 \leq n\leq 10^4$，$1 \leq m\leq 100$，$1 \leq k \leq 10^7$，$1 \leq u, v \leq n$，$1 \leq w \leq 10^4$。

做法

暴力做法非常简单，我们先把询问离线下来，然后用 $O(n^2)$ 去枚举两个点 $u,v$，利用树上差分求解，总时间复杂度 $O(n^2\log n)$。

我们考虑以 $u$ 为根的子树内路径都有哪些情况，发现只有两类：

• 经过树的根 $u$，
• 不经过树根，在某棵子树内

不难发现，对于第二种情况，我们可以在子树内某个点为树根时统计到它的贡献，因此我们只需要考虑如何计算第一种情况。

首先我们需要求出子树内每个点到根的距离，在这里使用 $d$ 数组表示，这样我们就可以使用两条路径拼成一条长的路径。

\/\/统计出每个点路径长度
int cnt;
int dis[maxn],d[maxn];
void getdep(int u,int fa)
{
	dis[++cnt] = d[u];
	for(auto nxt : G[u])
	{
		int v = nxt.v;
		int w = nxt.w;
		if(v == fa || vis[v]) continue;
		d[v] = d[u] + w;
		getdep(v,u);
	}
}

但是如果两个点 $u,v$ 在树根的同一棵子树内，那么就会产生前面的第二种情况，也就是与自己子树内的点计算贡献。因此我们考虑在计算完当前点与之前点的贡献后，再统一把这棵子树的距离值加进去。

我们使用一个 $dis$ 数组来记录当前树上已经遍历过的路径长度，那么我们每次计算完路径长度，就可以统计答案。

具体的，外层循环枚举路径长度，内层枚举每个询问。
我们令 $dis[i]$ 表示当前枚举的路径长度，$k$ 表示当前询问的长度，那么我们需要查询长度为 $k - dis[i]$ 的路径是否存在，使用一个桶记录一下就好。

int q[maxn];\/\/队列 存储当前子树内产生贡献的点 
bool judge[10000010];\/\/判断一个数是否存在 

void getans(int u)
{
	judge[0] = 1;\/\/长度为0的路径存在，目的是统计长度为k的路径
	int p = 0;\/\/队列长度
	for(auto nxt : G[u])
	{
		int v = nxt.v;
		int w = nxt.w;
		if(vis[v]) continue;
		cnt = 0;\/\/记录路径数量
		d[v] = w;
		getdep(v,u);
		for(int i = 1;i <= cnt;i++)
			for(int j = 1;j <= m;j++)
				if(que[j] >= dis[i]) ans[j] |= judge[que[j] - dis[i]];\/\/统计答案
				
		for(int i = 1;i <= cnt;i++)
		{
			if(dis[i] <= 1e7)
			{
				judge[dis[i]] = 1;
				q[++p] = dis[i];\/\/加入队列
			}
		}
	}
	for(int i = 1;i <= p;i++) judge[q[i]] = 0;\/\/全部处理完后要清空
}

要注意，当我们处理完所有子树后，对根的分治就完成了，此时为了避免当前子树内的路径对其它子树产生贡献，我们需要清空它的贡献。注意不要使用 memset，否则时间复杂度就假了。

由于我们需要递归的去做，所以复杂度是和树的深度与子树大小密切相关的，因此我们需要找出一种最优的方案，来减少递归。

在树型结构中，重心具有很多优秀的性质，删掉重心后，其他的子树都尽可能地保持平衡，最大子树大小最小。

因此我们对一棵子树，选择重心进行点分治，这样对于整棵树，只需要进行 $O(\log n)$ 次。

int siz[maxn],f[maxn];\/\/siz子树大小，f最大子树 
int vis[maxn];\/\/表示每个点是否已经被分治过 

\/\/求重心 
void getroot(int u,int fa)
{
	siz[u] = 1;
	f[u] = 0;
	for(auto nxt : G[u])
	{
		int v = nxt.v;
		int w = nxt.w;
		if(vis[v] || v == fa) continue;
		getroot(v,u);
		siz[u] += siz[v];
		f[u] = max(f[u],siz[v]);
	}
	f[u] = max(f[u],s - siz[u]);
	if(f[u] < f[rt]) rt = u;
}

到这里基本已经完成了，接下来只需要完善一下分治以及主函数即可。

我们发现点分治大致有四个步骤：

• 求出当前子树重心
• 求出子树内点到重心的距离
• 统计答案、清空
• 向下分治

到这里，我们已经做完了这道点分治模板题。

AC Code

#include<bits\/stdc++.h>

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 1e4 + 10;

struct note{
	int v,w;
};
vector<note> G[maxn];

int n,m;
int que[maxn];\/\/question 
int s,rt;\/\/存储当前子树大小及重心 
bool ans[maxn];\/\/存储问题答案 

int siz[maxn],f[maxn];\/\/siz子树大小，f最大子树 
int vis[maxn];\/\/表示每个点是否已经被分治过 

\/\/求重心 
void getroot(int u,int fa)
{
	siz[u] = 1;
	f[u] = 0;
	for(auto nxt : G[u])
	{
		int v = nxt.v;
		int w = nxt.w;
		if(vis[v] || v == fa) continue;
		getroot(v,u);
		siz[u] += siz[v];
		f[u] = max(f[u],siz[v]);
	}
	f[u] = max(f[u],s - siz[u]);
	if(f[u] < f[rt]) rt = u;
}

int cnt;
int dis[maxn],d[maxn];

\/\/统计出每个点路径长度 
void getdep(int u,int fa)
{
	dis[++cnt] = d[u];
	for(auto nxt : G[u])
	{
		int v = nxt.v;
		int w = nxt.w;
		if(v == fa || vis[v]) continue;
		d[v] = d[u] + w;
		getdep(v,u);
	}
}

int q[maxn];\/\/队列 存储当前子树内产生贡献的点 
bool judge[10000010];\/\/判断一个数是否存在 

void getans(int u)
{
	judge[0] = 1;
	int p = 0;
	for(auto nxt : G[u])
	{
		int v = nxt.v;
		int w = nxt.w;
		if(vis[v]) continue;
		cnt = 0;
		d[v] = w;
		getdep(v,u);
		for(int i = 1;i <= cnt;i++)
			for(int j = 1;j <= m;j++)
				if(que[j] >= dis[i]) ans[j] |= judge[que[j] - dis[i]];
				
		for(int i = 1;i <= cnt;i++)
		{
			if(dis[i] <= 1e7)
			{
				judge[dis[i]] = 1;
				q[++p] = dis[i];
			}
		}
	}
	for(int i = 1;i <= p;i++) judge[q[i]] = 0;
}

\/\/递归分治
void divide(int u)
{
	vis[u] = 1;\/\/标记当前点 
	getans(u);\/\/统计当前点的答案 
	for(auto nxt : G[u])
	{
		int v = nxt.v;
		int w = nxt.w;
		if(vis[v]) continue;
		s = siz[v];
		f[rt = 0] = inf;
		getroot(v,0);
		divide(rt);
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i = 1;i < n;i++)
	{
		int u,v,w;
		cin >> u >> v >> w;
		G[u].push_back({v,w});
		G[v].push_back({u,w});
	}
	for(int i = 1;i <= m;i++) cin >> que[i];
	f[rt = 0] = inf; \/\/初始化 
	s = n; \/\/当前子树点的数量 
	getroot(1,0);\/\/找到重心 
	getroot(rt,0);\/\/从重心进行一遍dfs，求出每个点子树大小等信息 
	divide(rt);\/\/分治 
	for(int i = 1;i <= m;i++) \/\/输出答案 
		cout << (ans[i] ? "AYE" : "NAY") << '\n';
	return 0;
}

需要注意的细节：

函数调用不要调用错误。
记得及时清空变量及数组，函数运行前初始化信息。

希望对你有所帮助。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-06-18 19:23:31

P11116 [ROI 2024] 割草 (Day 2) 题解

模拟赛 T1，场上想了二十分钟，有点困出去喝口水想出来了。

题意

给定 $n$ 个机器人，每个机器人有三个属性：位置、能走的距离、初始方向，在起点和终点各有一个机器人，机器人按照位置从左向右依次给出。

所有机器人会同时开始向初始方向运行，中途不会改变方向，不能越过其他的机器人，也不能超过自己能够走到的距离。

我们有一种操作，每次可以修改一个机器人的初始方向。询问我们能否在一些次操作之后，使得所有区域都被覆盖，需要求出操作次数。

思考过程

看到部分分有很多，优先思考了部分分，在反复观察题面的时候发现了一个性质——面朝右侧运行的机器人是序列的一个前缀，而面向左侧的机器人是序列的一个后缀。

为什么呢？

题干里说到，机器人位置是严格递增的，也就是不会有重复。

想象一下，如果一个机器人面向左侧，它后面的机器人面向右侧，那么这两个机器人之间的部分就无法被覆盖到，因此得出了结论。

根据这条性质，我们可以找到面向右侧的机器人中，最靠后可以放在哪里，以及面向左侧的机器人中，最靠前可以放在哪里。

我们分别从前往后、从后往前各扫一遍，每次判断当前朝向能否覆盖到下一个位置（这里的当前朝向指的是前后缀的朝向，即前缀向右，后缀向左）。找到端点处两个位置，即最靠前/后的位置。如果这两个位置之间还存在机器人，那么这个机器人朝向左侧和右侧就都不合法了，因此无解，输出 $-1$。

判断完无解的情况，剩下的就是求出最小的操作次数。

不难发现，我们把面朝左侧这段后缀的左端点放在求出的两个位置之间都是合法的，因此我们只需要在这些方案里面取一个最小的即可。

我们直接枚举后缀的左端点所在的位置（第一个面朝左侧的机器人位置），随后把答案与每种方案的贡献比较并更新一下即可。

如何计算贡献，也就是如何快速数出这段前/后缀中有多少个方向不符的，我们使用前缀和维护出区间内操作之前初始状态面向右边的机器人数量，也可以快速求出一段区间内不合法的数量。

到这里就做完了，代码。

#include<bits\/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2e5 + 10;
int pre[maxn];
int x[maxn],p[maxn],d[maxn];
signed main()
{
\/\/	freopen("A1.in","r",stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++) cin >> x[i] >> p[i] >> d[i];
	for(int i = 1;i <= n;i++) pre[i] = pre[i - 1] + (d[i] == 1);
	int ls = n,pr = 1;
	for(int i = 1;i < n;i++)
		if(x[i] + p[i] < x[i + 1])
		{
			ls = i;
			break;
		}
		
	if(x[ls + 1] - p[ls + 1] > x[ls] + p[ls]) ls--;
	for(int i = n;i > 1;i--)
		if(x[i] - p[i] > x[i - 1])
		{
			pr = i;
			break;
		}
	if(x[pr - 1] + p[pr - 1] < x[pr] - p[pr]) pr++;
	if(pr > ls + 1)
	{
		cout << -1 << endl;
		return 0;
	}
	int ans = 0x3f3f3f3f3f3f3f3f;
	for(int i = pr;i <= ls + 1;i++)\/\/枚举  向左的部分的最左端的位置 
	{
		int sum = 0;
		int xy = i - 1;
		sum += xy - pre[xy];
		sum += pre[n] - pre[xy];
		ans = min(ans,sum);
	}
	cout << ans << endl;
	return 0;
	
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-06-29 20:37:42

P10804 [CEOI 2024] 玩具谜题 题解

原题

做法

在下文中，我们将横着的块称为横块，竖着的块称为竖块，将横块与竖块重叠的位置称为交点。

题目要求我们判断能否到达终点，我们考虑横竖块之间的交点是怎样移动的。也就是说，我们需要考虑横块和竖块的移动对交点位置移动的影响。

不难发现，横块横向左右移动不会对交点的位置产生影响，同理，竖块纵向上下移动也不会产生影响。因此我们在移动交点位置的时候，只需要判断是横块纵向移动了，还是竖块横向移动了。

注意到 $W,H \le 1500$ 的矩阵大小，在这个范围矩阵中我们可以使用广度优先搜索，在搜索过程中统计可达性。

具体的，我们首先找到交点的位置，随后枚举交点移动的四个方向。由前面的推断可知，交点横向移动是竖块移动引起的，纵向移动是横块引起的。

所以我们在搜索过程中，对每个方向判断相应块是否合法。例如向右移动时，我们就应该判断右边列障碍物能否放下竖块。

由于 $H,W$ 同阶，这里我们统一使用 $n$ 来表示。

暴力判断一次的复杂度为 $O(n)$，因此总时间复杂度为 $O(n^3)$，并不能通过。我们需要考虑如何快速判断移动是否合法，观察这个过程，判断的方式可以概括为：判断横向连续空间 $X$ 是否满足 $K \le X$，以及纵向连续空间 $Y$ 是否满足 $L \le Y$，也就是我们需要快速求出一段连续区间中空地的数量。

不难想到使用前缀和以及后缀和维护出每个位置向各个方向的连续空地长度，这样就可以在 $O(1)$ 的时间复杂度内快速判断是否能够移动，然后进行 BFS 维护可达性，这样就做完了。

贴代码

#include<bits\/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1510;
int w,h,k,l;
int pre[maxn][maxn],lst[maxn][maxn],top[maxn][maxn],dow[maxn][maxn];
#define pii pair<int,int>
#define fi first
#define se second
pii xx;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
char mmp[maxn][maxn];
bool vis[maxn][maxn];
bool bfs(pii s)
{
    queue<pii> q;
    q.push(s);
	while(!q.empty())
    {
		auto nx = q.front();
		q.pop();
        int x = nx.fi;
        int y = nx.se;
		if(mmp[x][y] == '*') return true;
		if(vis[x][y]) continue;
		vis[x][y] = 1;
		for(int i = 0;i < 4;i++)
        {
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(mmp[xx][yy] == '.' || mmp[xx][yy] == '*')
            {
                if(dx[i])
                {
					if(min(lst[x][y],lst[xx][y]) + min(pre[x][y],pre[xx][y]) > k) q.push({xx,y});
				}
				else if(min(dow[x][y],dow[x][yy]) + min(top[x][y], top[x][yy]) > l) q.push({x,yy});
            }
        }
    }
				
	return 0;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
	cin >> w >> h >> k >> l;
    cin >> t >> xx.fi >> xx.se >> t;
    xx.fi++;
    xx.se++;
	for(int i = 1;i <= h;i++)
        for(int j = 1;j <= w;j++)
            cin >> mmp[i][j];
	for(int i = 1;i <= h;i++)
		for(int j = 1;j <= w;j++)
			if(mmp[i][j] != 'X')
			{
                pre[i][j] = pre[i][j - 1] + 1,
				top[i][j] = top[i - 1][j] + 1;
            }
	for(int i = h;i >= 1;i--)
		for(int j = w;j >= 1;j--)
			if(mmp[i][j] != 'X')
			{
                lst[i][j] = lst[i][j + 1] + 1,
				dow[i][j] = dow[i + 1][j] + 1;
            }
	if(bfs(xx)) cout << "YES";
    else cout << "NO";
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-06-30 08:11:16

P5978 [CEOI 2018] Global warming 题解

题目传送门

考虑对于一个区间加上或减去一个正整数会对整个序列的 LIS 产生怎样的影响。

假设我们对于区间 $[l,r]$ 减去一个正整数，一个显然的结论是，区间 $[l,r]$ 对 $[r + 1,n]$ 造成的贡献会增加（或不变），而 $[1,l - 1]$ 对 $[l,r]$ 造成的贡献会减少。

因此如果想要对一个区间减少一个正整数值 $x$，我们希望尽量将 $l$ 向前移动，因此如果选择对一个区间减去一个正整数，那么选择 $[1,r]$ 一定是相对于 $[l,r]$ 不劣的。

我们再来考虑对区间进行加法，使用同样的办法分析，不难发现，对于一个区间 $[l,r]$ 加上 $x$ 和对区间 $[1,l - 1]$ 减去 $x$ 是等价的，因此我们可以简化题意，也就变成了，我们可以对区间 $[l,r]$ 减去一个值 $x$，求序列最长上升子序列长度。

还有一个需要分析的点是，减去的正整数值 $x$ 应该更大还是更小，不难发现，$x$ 的值更大显然是更优的，因此相当于我们需要对于一个 $i$，将区间 $[1,i]$ 全部减 $x$，随后求序列最长上升子序列长度。

我们考虑如何去做这件事情，暴力修改并求 LIS 的时间复杂度是 $O(n^2 \log n)$ 的，因此我们要考虑如何优化。

发现对区间 $[1,i]$ 进行修改，对这段区间内的 LIS 是没有影响的，因此我们可以把序列拆为 $[1,i]$ 和 $[i + 1,n]$ 两部分，我们分别求出上升子序列长度，随后合并更新答案即可，时间复杂度 $O(n \log n)$。

贴代码。

#include<bits\/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int maxn = 2e5 + 10;

int a[maxn];
int f[maxn],l[maxn];

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int ans = 0;
    memset(f,0x3f,sizeof(f));
    int n,x;
	cin >> n >> x;
	for(int i = 1;i <= n;i++) cin >> a[i];
	for(int i = 1;i <= n;i++)
	{
		int nowx = lower_bound(f,f + n,a[i]) - f;
		f[nowx] = a[i];
        l[i] = nowx + 1;
        ans = max(ans,l[i]);
	}
	memset(f,0x3f,sizeof(f));
	for(int i = n;i >= 1;i--)
	{
		int nowx = lower_bound(f,f + n,-a[i] + x) - f;
        int nowl = lower_bound(f,f + n,-a[i]) - f;
		f[nowl] = -a[i];
        ans = max(ans,l[i] + nowx);
	}
	cout << ans << endl;
	return 0;
}

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-06-30 20:07:14

CF1401E 严谨证明

本题结论是：分出区域的数量 = 交点数量 $+$ 贯穿边的数量 $+1$，想要感性理解请参考其他题解，这里给出严谨的证明。严谨证明来自 lzx（太强了）。

首先需要知道前置知识：
oi-wiki 平面图上的欧拉公式。
平面图上的欧拉公式。

前置定理部分

在本文中平面图的定义为：可以在一个平面上绘制的无向图，且任何两条边仅在顶点处相交。对于本题也就是说，两条边的交点也被计算为顶点。

下图使用黑色点表示平面图的顶点，左侧不是平面图，右侧是平面图。

在平面图中，我们设点的数量为 $N$，边的数量为 $M$，所划分成区域的数量为 $K$，要注意这里的 $K$ 不仅包含了图形内部，也包含了外部的区域，例如在下面图中 $K = 2$。

定理内容为：$N - M + K = 2$。

由于 $K$ 还包含了外部区域，这部分不是我们想要统计的，因此在这个题里面，实际上是 $N - M + K = 1$，进行移项，易得 $K = M - N + 1$。

这样我们就把问题转化为，对于给出的这张图，将其转化为一张平面图之后，要求出它的点的数量 $N$ 和边的数量 $M$。

下文中，我们把长度为 $10^6$ 的边称为贯穿边，其余称为普通边，假设贯穿边总共有 $l$ 条，并把交点的个数设为 $x$。

计算部分

我们分别来计算，先来考虑点的数量，分为矩形上的点和矩形内部的点两部分计算。

计算点的数量

对于矩形上的点，有以下几种：

• 矩形最初有 $4$ 个点。
• 加入一条普通边，会与矩形产生 $1$ 个交点。
• 加入一条贯穿边，会与矩形产生 $2$ 个交点。

将其相加，位于矩形上的点总共有 $4 + m + l$ 个。

矩形内部的点，也就是交点的个数 $x$。

将上述两部分相加，得到 $N = 4 + m + l + x$。

计算边的数量

我们依旧分开考虑，首先来看矩形上的。

最初的矩形有 $4$ 条边，随后往里加入边，发现每加入一条普通边，会与矩形产生一个交点，这个交点把一条边分成了两段，也就相当于每条普通边会额外产生 $1$ 条边。

再来看贯穿边，贯穿边会与矩形产生 $2$ 个交点，也就是将两条线段分别分成 $2$ 段，因此每条贯穿边会产生 $2$ 条边。

矩形上共有 $4 + m + l$ 条边。

接下来看矩形内部，每个交点会产生 $2$ 条边，如下图所示。

如图，两条普通边产生了 $1$ 个交点，这个交点对应着 $1,2$ 两条边。这里要注意，普通边在末端并没有与矩形另一边相交，因此伸出部分不被算作边，相当于实际上这幅图是这样的。

再来看贯穿边，贯穿边的每个交点会产生 $3$ 条边，因此两种边一共会产生 $2 \times x + l$ 的贡献，贯穿边具体如图。

那么边的数量 $M = 4 + m + 2 \times l + 2 \times x$。

我们把 $N,M$ 代回到本题的公式中，$K = M - N + 1 = l + x + 1$，也就是结论，分出的区域数量 $=$ 交点数量 $+$ 贯穿边的数量 $+1$。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-07-05 15:52:27

开始有点困，没静下来想题，想了一会 T1，发现了每天可以全部卖出去再买回来的转化。考虑 dp，写完发现挂了，于是去开了 T2。

T2观察了一会发现可以根据奇偶性去做，写了 bfs，只记录了奇偶的可行性，样例挂了发现需要研究 $l$ 和距离之间的关系，但没想到要计算距离。想到用 topu 和环长特判但感觉太麻烦了，于是去看其他的题。

T3 观察了一会，发现贡献是一条链，考虑怎么从父亲转移过来，但是还有不到一小时，于是先去调了 T1，最后发现把完全背包想成了 01 背包，枚举顺序错了所以挂了，心态不稳了，后面暴力看出来了也没有再争，研究了一会 T3 做法，没时间了。

应该注意时间的分配，同时多提高自己的思维能力，提高想题的速度和正确率，注意心态的调整。