UOJ Logo hehezhou的博客

博客

UOJ NOI Round #6 Day1 题解

2022-08-06 17:57:28 By hehezhou

面基之路

idea from he_____he, data,solution from hehezhou

算法一

首先需要注意到最重要的结论:题意等价于所有人走到同一位置所需最短时间。证明只需要让所有网友在面基成功之后跟随 hehe 蚤行动即可。

对于子任务 $1$,不难发现最终汇合点一定在某个点上或某条边正中。如果汇合点在边的非中点位置,移动到端点或中点,一定有一种更优。

只需要求出会合到每一个位置的答案即可。时间复杂度 $O(k(n\log n+m))$,期望得分 $30$。

算法二

对于子任务 $2$,不难发现 $T$ 就是最远点距离除以二。

首先会合时间不可能更早,因为 $1$ 和最远点的距离达到了 $2T$。而只需要让所有人移动到 $1$ 和最远点的带权中心就是一组合法方案。

算法三

首先汇合点在点上的情况是简单的,考虑汇合点在边上的情况。

定义边的左右侧是它的两个端点,枚举每个人是从哪一侧进入这条边的,每侧只需要考虑最晚进入的人即可,答案不难计算。

时间复杂度 $O(m2^k+kn\log n)$,期望得分 $85$。

算法四

由于每侧只需考虑最晚进入的人,对于每条边,一定存在一种最优方案,将所有人按照到达左侧时间排序后,一个前缀从左侧进入而剩余的后缀从右侧进入。

时间复杂度 $O(kn\log n+mk\log k)$,期望得分 $100$。

bonus

如果 hehe 蚤的速度是 $a$ 而网友们的速度是 $b$,这个问题又该怎么解决呢?

这个问题会在数日后被加入 uoj 题库。

机器人表演

idea, data from djq_cpp, solution from hehezhou

本题改编自 CPIdeas (https://codeforces.com/blog/entry/104374) 生成的题面:

You are given a string S consisting of 0 and 1. You can do the following operation on S any number of times: Choose a non empty substring T of S, and append 0 to the beginning and 1 to the end of T. The resulting string will be S again. How many different strings will S be after the operations? Find the count
modulo 998244353.

算法一

我会状压!

接下来令左括号对应 0,右括号对应 1,合法括号前缀是满足任意前缀 0 不少于 1 的串,合法括号串是 01 个数相等的合法括号前缀,$A$ 和 $B$ 可以合并出 $C$ 等价于 $C$ 可以被划分为两个子序列分别等于 $A$ 和 $B$。

首先我们考虑给定一个串 $T$,判断其是否可以通过合并串 $S$ 和某个括号串得到。这可以在 $O(|S||T|)$ 的时间内完成,具体的,设 $f_{i,j}(i\geq j)$ 表示是否存在一个合法括号前缀使得它和 $S[1:j]$ 可以合并出 $T[1:i]$。考虑转移,有以下两种转移:

  1. $f_{i,j}\to f_{i+1,j+1} (S_{i+1}=T_{j+1})$

  2. $f_{i,j}\to f_{i+1,j} (a_{i+1}\geq b_{j})$

其中若 $T_i$ 是左括号,$a_i=a_{i-1}+1$,否则 $a_i=a_{i-1}-1$,$b$ 是定义在 $S$ 上的类似序列。第一种转移显然正确,第二种转移是因为:所有合并方案中,合法括号前缀的两种数量都是固定的。

如果 $f_{|T|,|S|}=\text{true}$ 且 $a_{|T|}=b_{|S|}$,则串 $T$ 可以通过合并串 $S$ 和某个括号串得到。

对应这个 dp,我们可以列出求解原题的状压 dp。$dp_{i,j,V}$ 表示已经填好了 $T$ 的前 $i$ 位,$f_{i,k}$ 等于 $V$ 的第 $k$ 位,$a_i=j$,转移按照上述转移式对应转移即可。

时间复杂度 $O(2^nn(n+t)^2)$,可以通过子任务 $1,2,4$,期望得分 $45$。

如果省略无用状态,可以额外通过子任务 $3$,期望得分 $60$。

算法二

我是打表大师!我打表转移找到规律了!

规律就是:对于固定的 $S,i,j$,非零 $dp_{i,j,V}$ 两个后继状态的 $V$ 的最高位只和当前 $V$ 的最高位有关。

可以只记录 $V$ 的最高位,状态数减少为 $O(n(n+t)^2)$。

时间复杂度 $O(n^2(n+t)^2)$,进一步得到转移规律可以做到 $O(n(n+t)^2)$,期望得分 $75\sim 100$。

算法三

我喜欢严谨做题!我要证明这个结论!

先注意到几个重要性质:

  1. 两个合法括号前缀合成的串一定是合法括号前缀。考虑定义不难得出。

  2. 若 $f_{i,j}=1$,则有 $a_i\geq b_j$。考虑转移或考虑 dp 意义均不难得出。

考虑当前已经匹配了前 $i$ 位,$a_i$ 确定,并且可以匹配的 $S$ 的最长前缀是 $k$,考虑在算上第 $i+1$ 位 $x$ 以后,可以匹配的 $S$ 最长前缀:

  1. $S_{k+1}=x$:显然新的最长前缀是 $k+1$。

  2. 否则若 $x=0$(即左括号) 或 $a_i\gt b_k$:那么 $a_{i+1}\geq b_k$,新的最长前缀是 $k$。

  3. 否则有 $x=1$(即右括号)且 $a_i=b_k$,这种情况较为复杂。先给出结论:新的最长前缀 $k'=\max_{t\lt k,b_{t}\lt b_k} t$。第一步证明这个前缀是合法的:不难发现 $S[k'+1,k]$ 是一个合法括号前缀,否则就存在更大的位置满足 $b_{t}\lt b_k$。首先证明 $f_{i,k'}=\text{true}$,只需要将 $f_{i,k}$ 对应的合法方案中,$S[k'+1,k]$ 对应的子序列划为合法括号前缀部分,由性质 $1$ 我们就得到了 $f_{i,k'}$ 对应的一组方案,因此 $f_{i,k'}=\text{true}$ 且可以转移到 $f_{i+1,k'}$。然后我们证明不存在更长的前缀 $x$ 可以匹配 $T$ 的前 $i+1$ 个位置,否则 $b_x\geq b_k\gt a_i-1=a_{i+1}$,与性质 $2$ 矛盾。

至此我们证明了这个结论。

期望得分 $100$ 分。

稳健型选手

idea,data,solution from xyr2005

谢罪!谢罪!谢罪!谢罪!谢罪!

算法一

我会暴力!状压当前剩下哪些数,复杂度 $O(n2^n+q)$,可以通过子任务一获得 $10$ 分。

算法二

我会观察性质!先考虑单组询问。

首先,如果 $n$ 是奇数,那 QAQ 蚤会在最后一次取最后一个数,转化成前 $n-1$ 个数的问题,容易发现这是最优的。所以我们可以假设 $2\mid n$。

考虑 QAQ 蚤取的数的集合要满足什么条件。令序列 $b_i=0/1$ 表示这个位置最终 QAQ 蚤 取不取。

那 QAQ 蚤可以贪心每次取 $b_i=1$ 的最靠前的那个,那么可以发现 一个 $b$ 合法当且仅当 $\sum b_i=\frac n2$ 且 $\forall i\in[1,n],\sum_{j=1}^ib_j\le \lceil\frac i2\rceil$

我们可以 $dp_{i,j}$ 表示考虑了前 $i$ 个元素,总共取了 $j$ 个,和最大是多少,转移时保证 $j\le \lceil\frac i2\rceil$ 即可。

复杂度 $O(n^2q)$ ,可以通过子任务一二获得 $20$ 分。

算法三

考虑优化算法二。

可以使用反悔贪心,从前往后扫,维护 QAQ 蚤取了哪些数。

每次加进来两个数 $x,y$,首先假设 $x,y$ 都取了,这时候取了的数的总数是 $\frac{i}2+1$,再删掉一个最小的已经取了的数。

用堆维护上述过程,复杂度 $O(nq\log n)$ ,可以通过子任务一二三获得 $40$ 分。

算法四

我们发现,前 $2i$ 个取了 $\le i$ 个 $\Leftrightarrow$ 后 $2i$ 个取了 $\ge i$ 个。

于是算法三也可以倒着来做,从后往前扫,维护 QAQ 蚤没取哪些数。

每次加进来两个数 $x,y$,首先假设 $x,y$ 都没取,这时候取了的数的总数是 $\frac i2-1$,再取一个最大的没取的数。

于是我们现在可以在 $O(\log n)$ 复杂度内,向前加两个数,向后加两个数,使用不删除莫队维护。

复杂度 $O(n\sqrt q\log n)$,可以通过子任务一二三四获得 $70$ 分。

使用压位trie/veb 维护,复杂度 $O(n\sqrt q\log_wn)/O(n\sqrt q\log\log n)$,期望得分 $70$ 分,实际得分 $100$ 分。

算法五

继续优化算法四。

使用分治,用主席树对 $[l,mid]$ 的每个后缀维护取了哪些数,对 $[mid+1,r]$ 的每个前缀维护没取哪些数。

然后考虑合并 $[x,mid]$ 和 $[mid+1,y]$,那会发生的变化是,$[x,mid]$ 中一些取了的数现在不取了,$[mid+1,y]$ 中一些没取的数现在取了。假设 $[x,mid]$ 中发生变化的数的集合是 $S$,$[mid+1,y]$ 中发生变化的数的集合是 $T$,那么 $|S|=|T|$ , $\max S< \min T$,$S$ 是一段前缀,$T$ 是一段后缀。于是我们二分 $k$ ,找到最大的 $k$ 满足左边第 $k$ 小 $<$ 右边第 $k$ 大,然后就知道了 $S,T$,于是做完了。

复杂度 $O((n+q)\log^2n)$,可以通过子任务一二三四五获得 $100$ 分。

评论

Minion
其实 T3 的算法二卡卡常就能在 2.7s 左右过子任务 3,得到 40 分。 我的提交记录:https://uoj.ac/submission/570320(20 分是因为前两个子任务 WA 了,只过了子任务 3)。
Minion
这个是我过了前 3 个子任务的 O(n^2q) 代码:https://uoj.ac/submission/570953
ycx_akioi
提问:T2 题解什么时候发!
tzc_wk
提问:T2 题解什么时候发!
Minion
提问:T2 题解什么时候发!
JohnAlfnov
提问:T2 题解什么时候发!
Minion
将 0 表示成 '(',将 1 表示成 ')',加 $t$ 对 01 可以看成加 $t$ 对括号。 设 $f_{i,j,k}$ 表示长度为 $i$,与初始 01 串匹配长度为 $j$,新加的括号中左括号个数-右括号个数为 $k$ 的方案数,然后按照每个括号分别是原来的括号、新加的括号来转移。 但还有一种情况:当 $k$ 为 0 时,加入一个右括号不一定是不合法的,因为我们可以缩减匹配长度使得它合法。 直接做是 $O(n^3)$ 的。
Mathew_LJH
提问:T2 题解什么时候发!
xzggzh1
提问:T1 bonus 什么时候加!
myee
提问:T1 bonus 什么时候加!
Rainbow_sjy
提问:T1 bonus 什么时候加!

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。