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
比较板。考虑对 J、O、I 三个字符做前缀和，记为 \(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
声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
