JOI Final 合集

· · 个人记录

LOJ #2764. 「JOI 2013 Final」JOIOI 塔

二分答案 x，考虑检查 x 是否合法。

如果要凑出 x 个塔，必须有 x 个 I 作为最后的塔底，很明显这 x 个要越靠后越能塞进更多的塔。

选出 x 个 I 作为塔底之后，接着选出 x 个 O 作为塔身，这些 O 要满足从后往前数到任意下标时，O 的数量都不超过 I 的数量。

最后再选剩下的 I 和 J ，看个数即可。

bool check(int x){
    int cnt1=0,cnt2=0,cnt3=0;
    for(int i=n;i>=1;i--){
        if(str[i]=='J'){
            if(cnt3<cnt2)cnt3++;
        }
        if(str[i]=='O'){
            if(cnt2<cnt1)cnt2++;
        }
        if(str[i]=='I'){
            if(cnt1<x)cnt1++;
            else if(cnt1==x&&cnt3<cnt2)cnt3++;
        }
    }
    return cnt3>=x;
}

LOJ #2763. 「JOI 2013 Final」 现代豪宅

很明显 n\times m 个点处理不了；因为如果不按开关只能在一行或者一列里走，所以开关才是切入的关键。

把所有有开关的点拆成拆成两个，一个连同行的开关，一个连同列的开关，然后同一个开关的两个点连一条长度为 1 的边。

连边的时候只需要连上下左右离当前开关最近的开关就行，这样边数最大是 5k 条。

在建完的图上跑 dijkstra ，复杂度 O(k\log k)。

LOJ #2758. 「JOI 2014 Final」年轮蛋糕

二分答案 x ，考虑如何检验 x。（默认下标 \bmod \space n 同余）

换言之，我们要使三块蛋糕都不小于 x，首先枚举第一块起点 l，然后双指针可以得到最小的右端点 r，接着双指针移动出第二块的最小右端点 r'，再算剩下的够不够 x。

复杂度 O(n \log V)。

LOJ #2335. 「JOI 2017 Final」足球

如果 A>C，即传球比带球累，直接一条龙即可。

然后就是考虑怎么建图，对于球来讲，有三种状态（无人持球，有人持球，在传球途中）。

一种一种考虑如何建边，无人持球到有人持球，需要最近的人过来接应，边的长度是 C\times Dis，Dis 代表最近接应队员的距离。

在传球途中具体还需要分四个传球的方向，连向该方向的下一个格子即可。

有人持球到传球途中，代价是助跑的疲劳度 B。

传球途中球可以随时停下，有人持球向四个方向运球也连边。

这样连边可能会出现一个问题，就是一个人分身跑去两个地方接应；但仔细想一想，此时 C\ge A，传球的时候加力给到原本应该在两个分身之间接球的人，就可以看出分身不会让疲劳度减小。

总复杂度 O(HW \log H)，虽然常数大但 \text{LOJ} 神机可不是吹的。