APIO2015 Solutions

巴厘岛的雕塑

分析发现或和的性质可以逐位确定,所以我们可以从最高位开始枚举。
假设当前确定到第位,确定的数的状态为,那么有表示前个数划分成段是否可行,转移方程为

这样dp可以拿到前4个subtask,考虑省掉一维,令表示将前i个数划分成若干段满足条件的块需要的最少块数。转移类似。

雅加达的摩天楼

根据建图。暴力Dijkstra。

巴邻旁的桥

显然,K=1的情况就是一个中位数问题。
考虑K=2,分析区间中点与两座桥的中点的关系,如果在左侧,那么区间对应的两座建筑物一定走左边的桥,反之亦然。
所以连续的一段必定归属到一座相同的桥上,对区间中点排序后使用四个set维护中位数,贪心即可。