？！省选！？Day1最低分？？

· · 生活·游记

Day -2

停留？己。

Day -1

定个计划吧。

不到啊，正解的话肯定会 0 题。

但是高达 5h 的时间，光拼部分分都能拼出不少吧。

那就争取把部分分拿满，两天能水过 300pts 就算胜利。

从暴力开始，每 20 分钟拿下一个 Subtask。

Day 0

跳过剧情。

试机。

复习了遍对拍，并惊讶的发现 time(0) * 100000 没用。

14:00 准时大战 replace。

先口胡一遍，就是分成左右相等前后缀和中间那一坨然后查询串被势在必得串的数量拆成前后缀和中间那一坨每个 map 开俩 Trie dfn 转化成区间查扫描线 O(L\log L)。

但不想写哈希怎么办。

我有一计，把中间那一坨加在前后缀的字符串前面，然后一起加入查询就行了。这样就只用开两个 Trie 了。但这样大小应该开到 2L+2n 以上。

666 空间爆了。Trie 大小先降到 6\times 10^6，写完再改回去。

写写写。

我去怎么 40min 了还没写到扫描线部分啊。如此速度，如何省选？

不对，怎么第一个答案是 1。我测我特么弄反了。查询是包的，不是被包的。

没事问题不大，按查询的字符串建 Trie，然后就变成矩形加单点查了，小改一下就行。

刚改完试机就结束了。遗憾离场。最终代码

注意到这 60min 我过了 0 个 Subtask。我省选药丸了。

Day 1

省流：竞选 Day1 非零最高分。

上次两天都是蓝黑黑，今天这个不会是紫黑黑，黑黑紫，黑黑黑之类的吧。

不知道，反正我又不可能进队，所以挑感觉有意思的去做得了。

T1 什么神秘树形 DP+期望，精准戳我雷点，还不是线性或者 polylog 复杂度的，就算是红我也不做，滚😡

T2 啥玩意啊，看着挺可做的样子，但是 n 这么小，一定有坑，不做。

T3 感觉挺有意思的，部分分还多，可以一战。

蓝黑紫吧，那就把T3过了就行，可以吹一年了（

性质 A 感觉没啥用，直接开性质 B。

最左边全是 1 那就说明不能对这几个 1 操作，所以必须从右边的开始操作。

然后想了一下发现就是两个栈来回倒，手模一下发现不管怎么倒最终的序列异或的下标还是有序的，而且每个数对应的下标长度一定是 3k+1。然后定义 dp[i][j] A_4,...,A_i 是否可以凑成 B_4,...,B_j，如果可以其中一种可行的 k 是什么。显然可以 O(n^2m) 转移。显然吧，但我写了 1h。

好了，然后是性质 C。发现这也是双栈，只是两个栈都有元素。然后会发现最多存在一个栈的元素最终出现在另外一个栈内，并且是栈顶。然后我们可以把其中一个栈的元素加到另一个栈，对两个栈都调用一次性质 B，然后枚举加入多少个元素即可。对了，奇数情况也得考虑，再特判一下，调用几次性质 B 即可。

诶怎么样例没过啊。调调调。诶怎么比赛就结束了啊😰😰😰

Day 1 成绩：0+0+20=20。

Day2

我不行了。这次再不切题我真没了。

卧槽 T1 怎么是小交互。直接看。

好像也没啥可以操作的啊，那就逐个枚举吧。

我去还卡 n+\log n，这么毒瘤。

猜一波，既然是求 \text{mex}，那一定要找 0，n+\log n 部分肯定是先找 0 然后再在 0 的位置左右枚举。

询问 [idx,idx]，[idx,idx+1]，…… 显然不对。

这种查区间的一般不可能难到哪里去，所以考虑尝试 [0, idx]，[0, idx+1]，……，[0,n-1] 和 [idx,n-1],[idx-1,n-1]，……，[0,n-1]。这样是询问 n+1 次的，但我们不需要询问 [0,n-1]，所以 n-1 次。

这几次查询好像已经可以构造出来所有确定的数了，中间那些不确定的随便填就行。

然后 \log n 二分找 0 就是 n+\log n 次了。这个能不能优化掉？

诶我们倒序枚举一下是不是在第一种询问的时候就可以顺便得出 idx 了？这样会多问 1 次，n-1+1 刚刚好。

写写写。

1h 调过了样例。样例过了那就不管它了。

我去 T2 T3 怎么看不懂。我没猜错的话这场应该是黄黑黑，致敬 NOIP 黄紫黑黑。

跳过剧情。

T3 看懂了。比字典序是吧。好，题目没给权值，默认权值是编号。那这样它的子树肯定比不过，在它的子树外面找到子树有比它最大值大的节点的点的数量就行了。

诶等等前面的题面怎么有一堆空集符号。卧槽我读错题了。

这是要按子树的形状比大小吗，我不会啊。

干坐了 4h 然后写了 T3 的测试点 2,3,4。

第 2 个点显然只有 s=t 的时候才满足条件，然后就变成了求链的长度，O(m\log n)。

第 3,4 个点写了个神秘递归比较函数，疑似 \sout{O(n\uarr\uarr\uarr n)}，反正过了样例。

Day 2 成绩：100+0+12=112。

最终成绩：0+0+20+100+0+12=132。

？！弱弱！？