12月集训游记

Day 1

　　好好好，今天没有爆零，这真是一个良好的开局，接下来的集训我一定会学有所得的哈哈哈哈哈哈哈哈哈…

　　总结一下今天的题目

　　T1 反正是个动态规划

　　首先，怎么看出来这是个动态规划的……因为计数问题不是组合数就是dp，而显然，如果这道题存在组合数做法我更不会

显然，有解的一个必要条件是 n∣h，因为一个位置恰好被涂一次，一次涂 n 个位置。

如果把一个 bi +1=bi+1 的连续段称作一个块，那么所有块的大小必须相等（显然），如果不相等后面就会出现冲突。

当块大小 >1>1 的时候，那么间距都要是块大小的倍数。因此，我们可以直接将整个状态“缩小”。我们设 F(h,n) 表示块大小 >1 的答案，G(h,n)是块大小 =1 的答案，于是得到：

　　F(h,n)=sum k|n,k>1 (G(h/k,h/n))

　　那么接下来考虑 G(h,n) 该如何计算

&emsp;&emsp;我们把一支笔刷的{dn-1}数组最前面添加一个0，再做前缀和，得到数组{pn}，将每次选择的数组{}的第一个元素bi构成递增序列{at}，其中 n*t = h。

&emsp;&emsp;一支笔刷合法当且仅当 pi＋qj 互不相同且覆盖[0, h]，容易发现对于合法的笔刷，{qt}存在且唯一。

&emsp;&emsp;于是我们可以考虑一个这样的双射:当我们交换p,q，这对应了一支nl =t的合法笔刷。

&emsp;&emsp;在块大小为1的时候，首先 p1=q1=0，而p2 > p1＋1=1，由于pi＋qj覆盖[0,h]，从而q2=1。

&emsp;&emsp;也就是说，当我们交换p,q之后，恰好对应一支n'=t且块大小>1的笔刷，于是可以得到转移 G(h,n)=F(h,h/n)

　　题解中说到了记忆化即可，但是由于平时用来写记忆化的都是线性转移，这种多维的dp想要记忆化就要用一个map+pair去维护

　　考试的时候因为没有理清头猪所以最后就打了一个基础的暴力，拿了点部分分，我认为这种做法是积极的、合理的，因为等到我真正到赛场上很有可能再次因为脑抽就没想到正解，这个时候能够沉稳的把部分分尽可能地拿到是非常重要的，正如向老师所说，得分是第一位的

　　T2 是个恶心的数据结构

　　在考试的时候我的思路完全错了，而且后来还没调出来

　　首先这道题的想法很朴素，就是建立一棵线段树用来求带修RMQ问题，对于每次插入“观察者”就是在区间内的节点上打上一个标签用来记录该观察者插入后该节点范围内的历史最大值

　　很显然一个节点上的“观察者”标签记录的值，按照打标签的时刻来排序，这些值应该是不严格单调递减的，那么我们就可以想到我们只需要维护某个节点的最后一个值，如果这个值在某次修改后大于了前面的值，那就把前面的值弹出，保持这个序列是不严格单调递减的

　　然后查询的时候就是在对应的节点上用 lowerbound，原理显然就不赘述了

　　我在考试的时候把这个问题想的太复杂了，因为我没想到线段树的每个节点上可以再额外开一个数组维护很多信息，因为这种做法用传统静态数组是无法实现的，大多数节点上的数组空间实际上是用不到的，这就会造成大量的空间浪费；但是使用vector动态数组就可以有效避免空间浪费，虽说常数大了一点，但是并不影响，这题的复杂度很充裕

　　我在考场上打了一波动态开点的主席树，然后对主席树的时间戳分了块，每一块上建了一棵线段树，外套了一个线段树求和，然后就非常愉快地 MLE 了

T3 字符串工业科技&emsp;&emsp;

　　什么叫做字符串工业科技呢，首先字符串不用解释，科技指的是十级算法，工业指的是复杂的码量……所以我还没学会SAM啊可恶，附上题解开头的第一句话

　　最后说说今天模拟赛的启示吧

　　首先，省选题都是很恶心的，代码都比较长，如果没有较强的代码能力是绝对不会有很大的提升的

　　其次，今天的 T1T2 都有点意思，我很早的时候就想过用map储存一些用数组无法储存但是我有很需要快速查改的东西，比如用 map+pair 判断重边，再比如就是今天用到的记忆化，T2中用 vector 扩展了线段树储存信息的极限这个也是我之前就有类似想法的，但是当时不喜欢用 vector。这两个不知道算不算常见的 trick，但是同样是想到了这些奇怪的主意，别人立刻将它实现了并且出了题，而我却只是想过实现却没有真正的实施，正如向总说过的，如果有什么想法，一定要把它用代码实现一下，这样代码能力才能增强，事实也确实如此

　　关于动态规划的问题，我请教了同学，也算是有点收获吧，获得了一些建议，回头都可以安排上

　　感觉上我现在的水平场切题目难度是很高的，但不意味着不能拿分，甚至如果对问题的分析还比较到位的话，一题正解都不会也未必不能拿高分

　　最后数据结构题挺混沌邪恶的

Day 2

　　今天又没有爆零，可喜可贺

　　T1 依然是动态规划

　　看得出来，动态规划真挺常见的

　　这道题我和正解的分叉是从题解的第二句话开始的

首先一次操作至少删去一半点，所以m ≤ log n。事实上，m <10时答案才可能不为0。

进一步发现一次操作相当于删去当前笛卡尔树上所有儿子数 <2 的点……

　　先来说说什么是笛卡尔树

　　笛卡尔树的每个节点有两个参数，就暂且表示为(a,b)

　　笛卡尔树满足对于a来说构成二叉搜索树的性质，对于b来说构成二叉堆的性质，具体的见这幅图

至于如何建树，暂时还不重要，这道题主要运用的是这个思想，我们可以发现一次操作相当于删去当前笛卡尔树上所有儿子数 <2 的点（特别的，对于下标最小 / 最大的点，其不存在儿子才会被删去）

标签：12,笔刷,emsp,集训,gt,nbsp,数组,游记,节点
From： https://www.cnblogs.com/qj-Network-Box/p/17903128.html

Day 1

T1 反正是个动态规划

T2 是个恶心的数据结构

T3 字符串工业科技&emsp;&emsp;<br />

最后说说今天模拟赛的启示吧

Day 2

T1 依然是动态规划

相关文章

赞助商

阅读排行