JOI 2019 Final 合集

#3010. 「JOI 2019 Final」勇者比太郎

其实如果读懂题了就是水题了

题目就是让你求满足条件的\(JOI\)，使得\(O\)在\(J\)同行的右侧，\(I\)在\(J\)同列的左侧。

弄个前缀和什么的就好了啊....

这个题是个贪心。

我们发现一定是把画框从大到小排序然后一个一个填最优是吧

而且显然我们选取的画一定是按照权值排序后的子序列。

这就随便贪一贪就好了，附上代码链接：代码

这个题的暴力非常给面子啊.....

把拟对象都通过暴力给出了(我还是没想出来....

通过两个颜色的情况我们发现相同颜色的相对位置一定不发生变化

这个性质很重要啊，之后我们就可以\(dp\)了。

\(f_{(i,j,k,l)}\)表示前面三个颜色分别有\(i,j,k\)种，最后一个颜色是\(l\)的最小交换次数。

转移转移就好了。

这个题就很神仙了。

首先如果是只有一行的话

我们就暴力维护一个桶就好了。

两行其实也同理，每一个硬币一定会进入离他最近的合法区域，故此在第一行都填满的时候我们直接换行，然后把桶整体加\(1\)就好了。

长链剖分，挖坑代填。