一.写在前面

如果说廿四10天集训，对于我，是完成了从入门（虽然可能我比别人入门更早？）到准OIer的蜕变，那么，HL7天，可以说是真正成为了OIer，虽然是被小学生、初中生（南方的）薄纱的那种高中OIer……

二.目录

Day 1：周赛一

Day 2：基础数据结构

Day 3：树状数组和线段树

Day 4：倍增问题

Day 5：字符串

Day 6：根号问题+杂选

Day 7：周赛二

好好好，都是我最弱的……

三.知识

我在我的日祭中写道，会在最后的总结中对知识进行汇总，我来兑现我的诺言了。

Day -1：

报道，学术无论

Day0：粥赛I

本以为T1是个签到题，结果数据造的四舍五入是真的很坑，好好好，就我没AC

T2：简单约数题，结合map还有Div性质很快AC了（数论还真好玩）

T3：10min看出是倒着贪心，跟正解想的一样，将最后结果入B，直到break；（AC_Love）：

T4：暴搜20+pts，如果开O2-30+pts，沉默了一会是状压dp？但是怎么调都是73pts（能有20times？）后来搜状压dp的板子（原谅我）发现其实区间dp更符合题目要求，毕竟区间max才58，然后对答案进行修剪80pts+1个RE，数组再大10，90pts，最后一个O2，过了

T5：想歪了，以为是dij缩点+贪心，后来明白dp更好，但是就很唐，dij怎么缩点来着？结果TLE了（这里指的是比赛进程）后来订正，懂了：

T6： 没时间了，要不然10pts的平凡dp分是可以拿到了，其实本题有思路，后来实测30pts，可能是不够优，答案思路写完就过了，这是好的：

Day1：寄储数据结构

对，存储我寄的结构

个人认为STL 一直是我最烂的部分（与之相反的是数论）

是我不爱背板子吗？

好像不是，毕竟文化课我都挺过来了。

但是又感觉STL跟背没关系。

如果背为主，信息怎为理科？

但是总是要面对的啊！

我要承认困难，我要客服困难！

当天的题就不写了，主要写写新知识——笛卡尔树（实在没想到一个理论数学家又和OI有关系了@欧拉先生）

首先要明确笛卡尔树是二叉树！如果这点忘的话很可能构树时会RE（别问我怎么知道的）

定义（stO OIWiki）：

笛卡尔树是一种二叉树，每一个结点由一个键值二元组 (k,w) 构成。要求 k 满足二叉搜索树的性质，而 w 满足堆的性质。一个有趣的事实是，如果笛卡尔树的 k,w 键值确定，且 k 互不相同，w 互不相同，那么这个笛卡尔树的结构是唯一的。

即：

在一棵笛卡尔树中，定义根节点是所有的元素中数值最小的那一个元素。笛卡尔树中每一个节点可以有 0，1，2 个节点。

对于根节点，假设它在原数组中左边不存在任何的一个元素，那么根节点就是没有左儿子的，否则，根节点的左儿子就是它在原数组中左边的所有元素中数值最小的那一个节点；右儿子同理，如果根节点在原数组中左边不存在任何的一个元素，那么根节点就是没有右儿子的，否则，根节点的右儿子就是它在原数组中右边所有的元素中数值最小的那一个点。对于一个非根节点，建立其左右儿子的步骤和对于根节点建立左右儿子的步骤是完全相同的。

性质（部分来源于Google）：

  构建

不能比OIWiki写的更明白了！

新建一个大小为 n 的空栈。用 top 来标操作前的栈顶，k 来标记当前栈顶。
For i := 1 to n
    k := top
    While 栈非空 且 栈顶元素 > 当前元素 
        k--
    if 栈非空
        栈顶元素.右儿子 := 当前元素
    if k < top
        当前元素.左儿子 := 上一个被弹出的元素
    当前元素入栈
    top := k

for (int i=1;i<=n;i++) 
{
  int k=top;
  while(k>0&&h[stk[k]]>h[i]) 
  k--;
  if(k)
  rs[stk[k]]=i;  // rs代表笛卡尔树每个节点的右儿子
  if(k<top) 
  ls[i]=stk[k+1];  // ls代表笛卡尔树每个节点的左儿子
  stk[k++]=i;
  top=k;
}

板子传送门：Problem - 1506 (hdu.edu.cn) 

Day2：术状数组和线断树

原谅我的懒惰，但是一看就懂，一懂就会的好资源为什么不用呢：

树状数组 - OI Wiki (oi-wiki.org)

线段树 - OI Wiki (oi-wiki.org)

Day3：被增+LCA

以下为正确理解个人理解：

倍增算法，顾名思义，就是不断地翻倍。

虽然是一种基础算法，但它能够使得线性的处理转化为对数级的处理，大大地优化时间复杂度，在很多算法中都有应用，其中最常见的就是ST表以及LCA（树上最近公共祖先）（在本part中无其他含义）了。

个人在网上找了个例题，感觉易于理解（不戳）！

有一个环状的操场，操场被分割为 [1,n] 个小块，每个小块上写着一个数字。
有一只小白兔站在操场的起点，它每次可以跳 k 个小块，然后拿走等同于它所站小块上数字数量的胡萝卜，问它跳 m次，总共可以拿到几个胡萝卜？
如果能够算出来的话，小白兔就能把所有的胡萝卜都带回家吃啦！

———————————————————————————————————————————

本题吧，暴力当然可以，就是让小白兔一次一次的跳，每次+=，直到m次。

但是，数据max有10^18欸，小白兔不出意外会累死，还吃不到胡萝卜。

所以就是倍增了

只需要记录从1开始2，4，8，16 =》 2^logm就可以了（请原谅我不会用CSDN数学式的编辑）

所以，复杂度降低至O(nlogm）

至于dp式嘛：

代码自然不是问题。

Day4：自服串

烂的自己都服。

hash+kmp+manacher（马拉车）+exkmp

本来上午没太听懂挺荒的，但是听到才队也不会，心宽了很多。

hash

字符串哈希 - OI Wiki (oi-wiki.org)

kmp

前缀函数与 KMP 算法 - OI Wiki (oi-wiki.org)

exkmp

Z 函数（扩展 KMP） - OI Wiki (oi-wiki.org)

马拉车

Manacher - OI Wiki (oi-wiki.org)

真的不是我又懒又烂，而是真心感觉OIWiki上讲的很透彻，不能奢望我讲的更好了，因为字符串本来就是我的WApart（回想3个月前gets怎么改卡了两周）

Day5：总结杂项

数列+数论+根号问题

我很舒服，毕竟yn学长的数论真的是一言难尽……在这的数论简单多了，自认为完全掌握，所以不总结

但是晚上你SE几个意思？？

Day6：粥赛II

T1：水的要命，5minAC

T2：也挺水的，建个栈然后vector存储，最后按题模拟就行，15min

T3：根本不会，本次周赛的两个唯一，一个唯二：

唯一根本没敢提交的

唯一讲解后也还是不会的

唯二没过的题

其余九位大佬谁能给我讲讲啊……

T4：

有两个子问题，恰好为k，最多为k

对于Q1：

设F[i][j]为到i换j的排列数

所以F[i][j]=F[i-1][j]

但是i到1后就变成了：

F[i][i+j]-=F[i-1][j]

所以：

F[i][j]+=F[i][j-1]

所以：

答案F[n][i]

对于Q2：

记得要%1000000007，否则只能过一个点！！！！

T6：

自己懂了，但是讲不出来，这种感觉真的很崩溃！！本文更新，等到会了会更新！

四.同学

这是本人第一次进入全日制学校进行集训，相信其他十个OIer也一样？

HL优美的校园环境留下了很好印象（除了第一天的午饭和比天的物价）

刘某人评价是211水平，可以

决战HL之巅，有生活广场，马场（这很难评，但是赞一个）

HL真的是很爱篮球，HBA有150+39场比赛，和电荷、潇寞、小陌、Qwehhh233打的很好

宿舍不错

309的同志们都是我想的那样

更是直面了410的大佬们，包括：

才队，湘湘，HB，Kazdale，cx330，james，yingxue-cat等大佬

还有Eric和两位福建的大佬

才队睡我下铺

本来以为他是个很凶的人呢（机房114514那次是真的不知道在玩梗）

结果：

嗯，他也是金梗频出：

吾日三省吾身:能不能拖到明天做?能不能给别人做?能不能不做?

唉，我都已经一周没有见我的npy了

还有很多，但是不知道能不能过审，就不说了

湘湘，真的好温柔，人很帅很高，跟才队一捧一逗

HB，额，感觉不太正经，但是学习时很投入，感谢你教我机惨！HB-Viki-Merlin爆内存法不戳！

Kazdale，才队的父亲和才队的儿子，外表豪放但看头像内心应该很细腻……

记得那晚他给我们讲他零基础OI的故事，直到HLgg来查寝并把viki带走了（恐）

其余的九位队友，一如既往，不必评价，因为你们几乎完美，附，合照（请允许我使用诸位的肖像权）：

五.趣事

详见每日更新的HL小祭记：

HL小祭記0216-0218 - MerlinLee 的博客 - 洛谷博客 (luogu.com.cn)

HL小祭記0219 - MerlinLee 的博客 - 洛谷博客 (luogu.com.cn)

HL小祭記0219 - MerlinLee 的博客 - 洛谷博客 (luogu.com.cn)

HL小祭記0222 - MerlinLee 的博客 - 洛谷博客 (luogu.com.cn)

请原谅0223没有写出来，但是会写的，请关注我的csdn和洛谷，本文也会实时更新

六.总结

24集训的诺言达成：

我身在

当时你

幻想的

未来里

还有，很喜欢的一首歌的前语：

劃過偏見與爭端，我們靜默航行。

當諸神背過身，當百鬼夜行狂歡，當人間掀起更甚海洋的巨浪，捧起微弱的理智之光，

我們將航行在耳語「之間」、在極端「之間」、在絕對「之間」；

繁星失語的午夜，也許沒有方向、卻能安適靜待遠方天光。

Merlin·Lee

于大连市中山区

2024年2月24日