洛谷食用
博客食用
简介：这是一个正在学习C++的OIer（很蒻很蒻）的日常记录。
(注：2024.7.5-7.20集训日更)
放在前面：
本贴只是记录一下本蒟蒻的生活，（太菜了），佬们轻喷谢谢~
浏览次数：（由于网站原因可能无法显示，属于正常现象）
Day 0
期待集训ing 。
0-上午
在来的路上听歌（摆。
中午到了 JZYZ 。
午饭：黑椒肉拌面+冰镇石榴水，好吃，好喝，好评。
0-下午
班里好多去年 HAJX[2023] 的同学，zzy大佬居然也在，膜拜
0-开幕仪式
好多厉害的人物和教练还有学生代表讲话。
膜拜D组（省队）的五位dalao。
晚上
晚饭：螺蛳粉+有椰奶茶 好吃 ！
（另：又迷路了…食堂还是lcx带我去的
晚上都是自习，只说了说注意事项，做了做模拟和动态规划的题
动规：A掉一道线性dp绿题，区间dp写挂了
模拟：写到最后也是20pts，炸了……
（班里好多高中生，膜拜dalao）
Day 1
上午
早餐：肉夹馍+烤肠+大米汤
早自习写了点背包dp。
今天讲“贪心和堆”
啊啊啊，好难QAQ
讲的也好快，仨小时过了十几道题 还都挺难的
本蒟蒻表示非常崩溃
不过中午又推了一中午过了两道题好多了）
中午饭：忘了名字的面+柠檬水
ps：虽然忘了名字，但是好吃！
（中招可以查分了，但人太多网站被挤出来了qaq）
下午
下午起来，查分网站还是查不到）
下午讲的二分和倍增，同上午，好快！好难！好崩溃！两个多小时又过了十几道题，剩下时间就慢慢写了。
记录：
T1：上课听懂了，过得很顺
T2：卡了半天49pts，最后发现题目的数据范围给小了，题目写2e5，实际上2e6，浪费将近1h（怒
T3：栈不能为空！！！要第一特判！！！气死了，又卡我0.5h
T4：挺有意思的一道题P4801 [CCO2015] 饥饿的狐狸 · 链接，洛谷评的难度在
[提高+/省选?]也就是蓝题，这也是我在洛谷上A掉的第一道蓝题嘿嘿。大概梳理一下思路，本题若不考虑水温，就是一道经典的贪心问题（其实加上也是贪心，不过复杂好多），因为没有顺序，我们先对温度进行sort排序。对于最小值，只需按顺序逐个计算即可，形式化地：
ans_{min} = | T_1-T_2 | + | T_2-T_3 | + ......+| T_{n-1}-T_n |
因为数列有序，所以可以化简为
ans_{min} = T_2-T_1 + T_3-T_2 + ......+T_n-T_{n-1}
化简得 ans_{min} = T_n -T_1
然后考虑加上水温，有三种情况：(水温为 w )
1. 当 t[1]<=w and w<=t[n] 时，我们会发现喝不喝水不会影响最小值，加上的 w 最终都会被抵消，故答案为ans_{min} = T_n -T_1 .
2. 当 w<t[1] 时，第一次喝水会影响结果，对结果多加上一个 T_1-w ，故答案为
ans_{min} = T_n -T_1+T_1-w = T_n - w
3. 当 w>t[n] 时， 同上
答案加上 w-T_n，即：
ans_{min} = T_n -T_1+w-T_n = w-T_1
至此，最小值讨论结束
再来看 最大值
我们要得到最大美味值，第一反应是对应经典模型，应该先交错吃温度最大的和最小的饼干，其中如果能喝水可以让答案变大，就尽量喝水。
因为要先喝一口水注意左右端点谁先开始，可能得到两个答案，分两步计算，再取个 max即可。
例如这个，是从左开始的部分代码（模板），主要是注意细节问题
// 从左开始 （左右交替）
int lst,ansl = 0,ansr = 0,t1 = 1,t2 = n;
/*lst储存上一个食物的温度，第一次要喝水，中间二者分别对应左右两端的答案，最后取max后二者是两个指针，方便左右交替 */
ansl+=abs(w-t[t1]);
lst = t[t1++]; // 从a[1]开始
for(int i = 2;i<=n;i++)
{
if(i%2 == 0)//比较喝不水和喝水的价值，取max ↓
ansl+=max(abs(lst-t[t2]),abs(w-t[t2])),lst = t[t2--];
else
ansl+=max(abs(lst-t[t1]),abs(w-t[t1])),lst = t[t1++];
}
最后输出 max(ansl,ansr) 即为最大值。
到这里，本题两问都已解决， 华丽结束 ！！！
还是挺有意思的
晚上
晚饭：兰州牛肉面+有椰奶茶
打了Atcoder（外国优质OJ）的 abc（高质量比赛）
但由于语言只有英文和日文 没有中文题面
只看懂了第一题，（也就是A题）A了，
记录，一百昏！！！
Day 2
今天讲hash（哈希）和KMP
上午
早饭：（由于高中部的放假了，食堂好多地方都关门了QAQ）
鸡肉卷+烧麦+米酒蛋花汤（没汤圆版）
早自习做了做昨天的题，加油
ps：今天换老师了
今天的老师虽然比昨天讲的慢，但讲的好模糊，表示没听懂……
（没太理解讲的到底是什么，概念好像理解了，但一看题还是不知道怎么用……
午饭：墨西哥什么饭（米做的）+啥来着（好像是喝的）
下午
下午讲了一会 KMP 自动机，彻底放弃（烦
学不会一点……
做其他题去了，做了点 hash 和 KMP 的模板就去做dp和模拟了
晚饭：麻辣烫+忘了不知名的西瓜汁
晚上做了点杂事，补了补之前没过的模拟题，各种水题，可恶啊被一个鸡兔同笼卡成80pts，死活调不对（大悲），最后无奈放弃，明天讲 dfs ，后天 bfs ，终于来点可以做的题了（希望是这样），期待ing。
关于字符串：
hash 和 KMP 先放一放，结训或者有时间再看，因为有前置知识哈希表没学过，所以现在很难学后面的。
打了个洛谷上的比赛，难度在提高组+左右（好像），做了30min，只打了 T1:20pts （暴力打的），（暴力超时记录）满分 400，希望能加 rated（做梦）
好累
今天就先这样了，明天加油！
Day 3
今天讲DFS（深度优先搜索算法/回溯算法）
上午
早饭：饼+椰果奶茶（热热的，好喝！）
上午ZZWGY的杨老师，讲题目DFS的图论遍历方法，讲了如何剪枝，从爆搜一步步改为正解（挺难的，但貌似听懂了几道
总结 一下：（搜索的优化方法）
- 优化搜索顺序（如提前排序/倒置等，如小木棍P1120，预处理从大到小排序，省好多时间）
- 排除等效冗杂（如小木棍P1120，虽然我是卡这时限260ms过的…同等长度木棍只需判断一次即可）
- 可行性剪枝（如贪心优化）
- 最优性剪枝（如若搜索答案已经劣于现已知最优答案，果断回溯）
- 记忆化搜索（把答案记录下来，避免重复减少时间）
午饭：牛肉面+茉莉绿茶（纯茶，但好喝）
下午
又讲了一点搜索和拓展，没太听懂，是和位运算结合的，基本不怎么考，不管了。
晚饭：肉夹馍+关东煮+茉莉绿茶（纯茶，好喝）
下午打了点搜索的题，写了篇 题解 P10490
晚上写了几道模拟，顺手把上次没过的模拟调过了
Day4
今天讲BFS（广度优先搜索算法/宽度优先算法）
上午
早饭：饼+石榴汁
讲了双向搜索，deque队列
还讲了道搜索用 康托展开 优化，没一个人做出来，所以老师说那道题用 map<string,string> 也可以，我俩都不会%%%
午饭：蛋包饭（米）+可乐鸡肉+土豆咖喱+鸡米花（三掺）+茉莉绿茶
下午
先把上午的deque双向搜索调过了
几乎没讲课，只点了几句话，都在自己做题，这会在自学 map
晚饭：麻辣烫+茉莉绿茶（纯茶好喝）
战果： map 概念懂了，看题还是不会，明天应该是讲图论，有空的话看看 （如果有时间的话），
做了三道搜索，写了点模拟
加油加油加油
Day 5
今天是学习图论的第一天……
上午
早餐：鸡肉卷+小米粥
一上来就讲稍微进阶一点的图论了 （对于我这个0图论基础的蒟蒻很不友好）
不会
没听懂
又看了看 洛谷kkksc03的《深入浅出》 和 oi-wiki 上写的非常好的解释，基础稍微懂一点了
午餐：红烧肉米饭+茉莉绿茶（纯茶好喝）
下午
接着讲图论，差分约束好像有点懂的意思，思路大概理解了
晚饭：鸡蛋卷烤肠（就是煎鸡蛋裹着的烤肠啦） + 黑米粥 + 酱香饼（不是太饿）
刷题ing
持续更新ing（2024.7.10-19:20）
这几天做过的dp：
01背包
| 线性dp1 | 线性dp2