JOISC 瞎写记录

感谢 @LPF 推荐!


「JOISC 2014 Day1」巴士走读

题目传送门

好题。待填坑。


「JOISC 2014 Day1」拉面比较

题目传送门

以为是分治,想了半天发现假了,其实正解很简单。

如果 \(n\) 是偶数,我们将原序列两两分成一组,询问一次每组内两个数的大小关系,将其中的较小者归入集合 \(A\),较大者归入集合 \(B\)。接下来,直接在 \(A\) 中寻找最小值,在 \(B\) 中寻找最大值即可,询问次数上限为 \(\lceil \frac{3x}{2} \rceil – 2\)

如果 \(n\) 是奇数,直接运用上述方法再将最大最小值与 \(n-1\) 比较即可。

提交记录


「JOISC 2014 Day3」JOIOJI

题目传送门

比较板。考虑对 JOI 三个字符做前缀和,记为 \(pre_{0, i}, pre_{1, i}, pre_{2, i}\)

一个连续子串 \(S_{[i, j]}\) 满足条件的充要条件为 \(pre_{0, j}-pre_{0, i-1} = pre_{1, j}-pre_{1, i-1} = pre_{2, j}-pre_{2, i-1}\),等同于

\[pre_{1, i-1} – pre_{0, i-1} = pre_{1, j}-pre_{1, j}, \ pre_{2, i-1} – pre_{1, i-1} = pre_{2, j}-pre_{1, j} \]

于是做法就很明显了:我们对于每个下标 \(i\),把 \(pre_{1, i}-pre_{0, i}\)\(pre_{2, i}-pre_{1, i}\) 打包进一个 pair 里,然后存进 map 中,快速查询第一个与它有相同值的下标。

提交记录


「JOISC 2015 Day2」建筑装饰 3

题目传送门

\(\operatorname{Key Observation}\):序列 \(h_i\) 存在的充要条件为 \(a_i\) 的前缀最大值增量不超过 \(1\)

接着瞎分讨一下就做完了。具体过程不再赘述。

提交记录

原文地址:http://www.cnblogs.com/SparkleZH-Blog/p/16823378.html

发表评论

您的电子邮箱地址不会被公开。