神仙构造题不是人能场上做出来的……

[CF 715D]

题意简述

一个四联通的 $n\times m$ 的迷宫，相邻的两个位置之间可能有墙阻隔使得这两个位置不能直接互达，一共有 $k$ 堵墙。从 $(1,1)$ 进入迷宫，而出口是 $(n,m)$ ，假设现在在 $(x,y)$ ，下一步只能走到 $(x + 1,y)$ 或 $(x,y + 1)$ ，当然不能走出迷宫且下一步走到的位置和现在位置之间不能有墙。通过一些计算，得出从入口 $(1,1)$ 走到 $(n,m)$ 共有 $T$ 种走法。

现在给出 $T$ ， $1\le T\le 10^{18}$ ，希望你构造出一个迷宫，使得从入口 $(1,1)$ 走到 $(n,m)$ 共有 $T$ 中走法，限制 $1\le n,m\le 50, 0\le k\le 300$ 。

一道神仙题，场上只想到一半不到……

[LOJ 3115]

[Luogu 5362]

题意简述

$\text{Thue−Morse}$ 序列是一个无限长度的序列 $\left\langle T_n\right\rangle$ ：

• $T_0 = 0$ ；
• $T_{2n} = T_n$ ；
• $T_{2n + 1} = 1 - T_n$ 。( $n > 0$ )

显然这是一个 $\text{01}$ 序列。现在给定一个 $01$ 序列 $S$ 和一个非负整数 $k$ ，求 $\text{Thue-Morse}$ 序列中有多少本质不同的连续子序列 $T$ 满足：

• $S$ 是 $T$ 前缀；
• $|T| = |S| + k$ ，其中 $|x|$ 表示 $\text{02}$ 序列 $x$ 的长度。

数据组数 $case \le 100$ ， $|S| \le 100$ ， $0\le k\le 10^{18}$ ，答案模 $10^9+9$ 。

所以这个题场上没写出来就是完全蠢了吧……

而且为啥加了各种优化还是跑不过最优解……

[LOJ 6499]

题意简述

给定一个长 $n$ 的整数序列， $m$ 次询问，每次给定 $k_i$ 个区间 $[i_{i,j},r_{i,j}]$ ，求这些区间中一共出现了多少种不同的数字。

部分数据强制在线。 $1\le n,m,a_i,\sum k_i\le 10^5$ 。

ML : 8MiB, TL : 1000ms.

在这里必须吐槽一下组题人和出题人的语文水平……愣是把这场打成了语文场……

最后一次 NOIP 没写游记，简直亏大了……

第二道 ynoi ……前前后后不知道写了多久。

自从半年前装了 VS Code (下称 VSC ) 以后，只用 VSC 来写一些yml,json,html啥的。从来没有用过来写cpp。

这几天突然心血来潮，在家里配置了一下 VSC ，现在可以在家使用 VSC 写代码了。

神仙p_b_p_b发现了一种神奇的分块思路，然后发现给别人造了轮子。

给你一个长度为 $n$ 的序列 $\left\langle a _i\right\rangle^{n} _{i=1}$和一个满足结合律的运算 $\circ$ 。Sqrt Tree可以在 $O(n \log_2\log_2n)$ 的时间内预处理，并在 $O(1)$ 的时间回答计算 $a _l\circ a _{l+1}\circ\cdots\circ a _r$ 的询问。

区间众数是和分块脱不了干系的。

谈到分块，不得不说说 $\text{hzwer}$ 学长的「数列分块入门」系列。