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
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。