XP05-01 DY02
2025-08-14 10:10:35
发布于：浙江
今天上午大概分为了两个部分：
1.动态规划优化的讲解
2.CF 题目Red Light,Green Light 的两个版本的讲解。
所以先总结一下第一个部分的大概内容：
动态规划的优化有两种：
1.空间优化
2.时间优化
空间优化并不常见，通常使用滚动数组进行。
时间优化占比更大，有很多种方法：
0.记忆化搜索（这个其实不算，不过上课时有同学提到了，所以记一下）。
1.单调栈&单调队列。
单调栈的作用是寻找第个比大/小的数字在XXX位置。例题：玉蟾宫。
单调队列的作用是寻找长度确定/递减的区间最值。例题：琪露诺。
今天晚上有时间就重新做一遍。
2.优先队列，这个没有详细的讲解，据说后面会有例题。
然后就是CF的题目。
说实话我感觉没太听懂，所以就打算重新看一下。
链接描述 这个是普通版本。
这道题实际上有两个版本，但是还是先看了第一个，第二个版本的难度我自己估计大概是S组第三题的水平。
第一个版本也够到第二题。
本题的意思大概是说，一条路上有几个红绿灯，这几个红绿灯会有一个周期，一个延时和一个位置。
大概这样：
一个红绿灯会变红，当且仅当现在的时间为：（的范围从0开始）。
你现在有一个初始位置，一开始你会往右边走，知道你碰到了一个红灯，此时你掉头往左走，直到你再次碰到一个红灯后掉头往右走。
现在有次询问，想问如果起点在，你是否能走出这条街道。
也就是说绿色正常通行，红色特殊处理。
那么只需要关注在你往一个方向走的时候，什么时候会遇到红灯即可。
如果一路畅通无阻，那么就可以出去了。
那么思路大概形成，你需要预处理出两个数组：在位置为并碰到红灯掉头后，往左/右走第一个碰到的红灯的位置。
然后对于每一个，先往右走，看碰到的第一个红灯在哪里，记录为。
并且添加一个变量来记录此时的方向。
然后就可以开始使用预处理过的数组。
注意你可能会来回经过同一个红灯，那么此时可以使用一个的数组记录一下，后面的是指你是从什么方向过来的。
如果来到一个已经来过的红灯就可以直接输出了，不然会一直死循环。
这是普通版的大致做法。
然后困难版的需要一些优化。
首先，普通版的预处理数组的时间复杂度是的，这里不能使用。
然后就可以考虑一下
下午就是考试。考试内容大概是60%模版题目+40%各种DP。
我凭借着XP04的记忆拿了模版题的满分，并凭借着高超的骗分技巧在400分的DP题目中获得84分的高分。
我的DP应该是除了很多提高组算法之外最差的算法。
对，就是非常差。
那就补。
对于动态规划，其实我的掌握是差的。
那么就分析差在哪里。
首先对于线性，我就掌握的不好，基本上每次做题都先看题解中的思路部分，缺少自己分析的过程。
更别提树状，区间等其他DP。因为缺少练习量，可以说是更本没做过。
所以我应该提升练习量。
但是在XP05短暂的10天中，我没有任何时间去提练习量。
做好每天的复习已经是极限了。
所以在离开集训后，我应该提高练习量。
而在集训营中，我应该将老师上课讲述的DP相关的题目全部听懂。
我没有时间焦虑。
继续看早上的题目。大概花了一个这样的图;
那么总时间大概是，既然到达时要求其为红灯，那么也就是说：
%
化简一下，变成：%
再化简一下，变成：%%。
然后就差不多了。
接着就是优化。
优化分为两个部分：
1.预处理部分：（数组）
原本可变成.
优化大概是这样：把这个%%
变成这个：
或者是这样：
然后就对于每个，用上面的两个公式去看，并且配合使用。
代码大概这样：
map<ll,int>mp;
for(int i=1;i<=n;i++){
ll temp=(d[i]+p[i])%k;
l[i]=mp[temp];
mp[temp]=i;
}
mp.clear();
for(int i=n;i>=1;i--){
ll temp=((d[i]-p[i])%k+k)%k;
if(mp.count(temp))r[i]=mp[temp];
else r[i]=n+1;
mp[temp]=i;
}
这边再对代码进行一个解释：
%%。
这边是因为不在的范围内了，所以为了保证结果正确+不是负数，所以需要这么写。
注：使用神秘会错。
然后就是次询问部分的优化：
这里又分为两个部分：
1.找到第一个红灯的优化。
2.判断能不能出去的优化（暴搜变记忆化搜索）
那就先搞找第一个红灯的优化：
从循环变成分组+二分。
下午的考试：
T01：详见笔记本P10.
T02：详见笔记本P11.
T03：（传纸条）详见笔记本P11.
T04：（Bill的挑战）详见笔记本P12
这里空空如也
有帮助，赞一个