【ACM-ICPC】World Final 2019 完全题解(三)

ACM World Final 2019 完全题解之 C、F、I、K 四题。

上下文

这篇博客继续更新 ICPC World Final 2019 的剩下几个题。之前的内容可以在 【ACM-ICPC】World Final 2019 完全题解(一) 找到。

剩下的题有C、F、I、K 四题,其中 C、I 是两个讲故事题,带大家领略一下世界级的大模拟长什么样;F、K 是两个很好很难的算法题,做出来的人很少,我收集翻译了一些网上能找到的题解资料,以后有空争取把他们给 A 了。

 

Problem C: Checks Post Facto

题目大意

这是一道比赛时无队伍 AC 的题,主要是题面看起来比较恐怖,细节也比较复杂。

题目首先详细地描述了国际跳棋的规则,包括兵只能向前走、兵触底升王、有吃必吃,和平时玩的国际跳棋规则相同,不熟悉的同学可以自行百度。

现在说你下了一局国际跳棋,记录了棋谱,但弄丢了一部分,想要复盘。也就是给出一局国际跳棋的棋谱的一部分,让你给出一个合法的局面作为开局,使得这个棋谱可以正常地走完。

题目保证一定有解。

数据范围

棋谱步数

解法

首先贪心。考虑从棋谱的最后一步开始倒着推,从一个空棋盘开始:

  1. 如果某一步要动某个子而那个位置没有这个子,就给他加上。
  2. 如果某一步要吃某个字而那个位置没有这个子,也给他加上(对面的子)
  3. 如果某一步棋子触底,那么说明在此之前这个子一直是王。

这三步都是贪心的,没有不确定性。唯一一条引起不确定性的规则是有吃必吃。如果某一步吃完某个子后没有接着吃,则说明它周围的对方子的后面都有棋子挡住了路。但挡路的棋子既可能是对方的,也可能是自己的。

对于这种不确定性,简单地进行一个暴力搜索就可以了:分两种情况讨论,继续搜索直到找到一个合理的解。

由于棋盘一共 32 个空位,最多每两个位置中会产生一次不确定性,因此整个题目的复杂度上限为 。实际上由于保证有解,很难构造出不确定性非常大且大多数情况无解的样例,因此程序的实际执行速度很快。

 

Problem I. Karel the robot

题目大意

本题是为了纪念“机器人”的概念被提出100周年。它定义了一种用于操作机器人的编程语言:

<program> := "" | <command> <program>
<command> := "m" | "l" | <proc-call> |
"i" <condition> "(" <program> ")(" <program> ")" |
"u" <condition> "(" <program> ")"
<condition> := "b" | "n" | "s" | "e" | "w"
<proc-call> := <uppercase-letter>
<proc-def> := <uppercase-letter> "=" <program>
 

其中 m 表示向前走一步、l 表示向左旋转90度;其他字母表示条件判断、循环和函数定义。这个程序可以用于操纵机器人行动。

现在给出一个地图,和机器人初始的位置、朝向,然后给出若干段代码,问代码执行后机器人会停在什么位置,或者机器人根本不会停止(因为循环的存在;此时输出inf)。

样例

解法

这也是一个超级大模拟。这题在算法上没什么难度,但全场碰这道题的队伍只有个位数,最后 AC 了五个队。为什么没人碰呢?上面放了一组样例给大家感受一下就知道了。

这道题分为两个部分。首先是个编译原理的工作,要把题目给出的代码“编译”,使得我们的程序可以模拟地一步一步执行机器人的动作。由于题目不允许函数递归,因此不需要模拟栈,只需要模拟当前程序指针,把判断和循环语句都解释成“判断并跳转”就可以。

第二个部分是判断无限循环。本题的数据范围较小,使得有限的部分直接一步步模拟就可以搞定。但程序有可能进入无限循环,因此要进行一个记忆化操作。将 <程序执行PC, 机器人位置与方向> 作为一个关键词进行记忆化存储,当遇到与之前一样的状态,就可以直接输出 inf 了。

参考代码

对这题挺感兴趣的,有空写一下,待补。

 

Problem F: Directing Rainfall

题目大意

一块葡萄田的上方有一些挡板,雨水会顺着挡板往下流。现在希望能在挡板上挖一些孔,使得葡萄田正上方的区域内有雨水能流到田野里。问最少需要挖多少个孔。

如图:至少要挖两个孔,然后雨水可以顺着挡板流下。


数据范围

挡板数量 ,坐标

解法

本题可以分为两个子问题解决,总体的思路如下:由于挡板不能互相交叉,因此可以根据雨水的上下流动关系对挡板进行排序,使得排在前面的板子上的水一定落在后面的板子上;然后用 dp[i][j] 来维护对于从上到下的第 i 块板子,横坐标 j 点上有雨水落下至少需要挖几个洞。这个过程中需要用到一些数据结构。最后的答案就是 dp[N][L] 到 dp[N][R] 间的最大值。下面详细分析一下。

首先,对挡板的排序过程,考虑从左往右扫描所有板子,遇到板子的左侧时把它放进一个 set,按照板子的上下排序(由于板子不会交叉,因此与同一根扫描线相交的板子之间有严格的上下顺序,可以定义一个cmp函数判断);遇到板子的右侧时,也就是某一块板子退出 set 时,我们观察 set 中剩余的板子中所有比它小的,这些就是在最终的排序中要在它前面的。为此我们对每个板子维护一个有序集合,存比这个板子大的一些板子。在这里由于只会在后端插入,因此集合的数据结构选用链表或者 vector 都可以。这样,在一个板子退出时,只要把它和它的链表一起接到 set 里上一个板子的链表最后就可以了。实现上为了方便起见,可以在所有板子的下面放一块地板(0, -1)->(inf, -1),那么最终排序了的板子就是地板的链表。

通过第一步对挡板的排序,我们就可以扔掉板子的 y 坐标,把这道题当做一个线段问题了。不过这里的线段是有方向的,也就是水下落的方向。第二步是动态规划。如上面所说的,dp[i][j] 表示对于从上到下的第 i 块板子,横坐标 j 点上有雨水落下至少需要挖几个洞。那么一开始对于 , dp[0][j] = 0。 对于其他的点,dp[0][j]=inf。每个板子对 dp 的贡献为:假定板子的范围是 [a, b],方向向右,则对 [a, b) 的点,雨水要落到地上就得多挖一个洞了,也就是这些位置的 dp 值加一;此外,由于雨水可以顺着板子往下滑,因此对于任意的 ,有 dp[y] = min(dp[y], dp[x]),换句话说就是将 dp 数组的 [a, b] 这一段变成单调不增的。最终答案是 dp[N][L] 到 dp[N][R] 的最大值。

这里需要一种数据结构来支持这两种操作:区间 +1 、区间“单调化”,最终查询区间最小值。区间 +1 操作可以通过差分变成两个单点修改。差分之后,区间“单调化”就变成了“把区间里所有正数变成 0 并减到后一位上”。这个操作可以通过在 set 中存储所有正数和负数的位置来完成,修改时直接枚举 L 到 R 中所有的正数位置,然后操作一番(不好描述,细节请看代码)。 看似比较暴力,但由于数组中一开始都是 0,而且单点修改的次数 O(N),因此整个算法的均摊复杂度是合理的。

实现过程中有一个小细节:由于数据范围中 L, R 是 级别的,显然要离散化处理。但本题不能直接简单地离散化端点,因为每两个端点间的“那一段”也是有意义的,因此需要在每两个端点间插入一个数,表示这两个端点间的空隙。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int, int>;
static char B[1<<16], *S=B, *T=B;
#define getchar() (S==T&&(T=(S=B)+fread(B,1,1<<16,stdin),S==T)?0:*S++)
inline int read(){
    register int res=0, c;
    while(c=getchar(), c<'0'||c>'9');
    do{
        res=(res*10)+(c^48);
    } while(c=getchar(), c>='0'&&c<='9');
    return res;
}
int main(){
    int ll=read(), rr=read(), N=read();
    vector<pair<pii, pii>> Seg(N+1);
    vector<pii> X(N+N+1);
    Seg[0]={{0, -1000}, {1e9+1, -1000}};
    for(int i=1; i<=N; i++){
        int a=read(), b=read(), c=read(), d=read();
        Seg[i]={{a,b},{c,d}};
        if(a>c)swap(Seg[i].first, Seg[i].second);
        X[i]=make_pair(Seg[i].first.first, i);
        X[i+N]=make_pair(Seg[i].second.first, -i);
    }
    sort(X.begin(), X.end());
    int nowx;
    auto point = [&](int i, int x){
        return Seg[i].first.second + ((double)(x-Seg[i].first.first))/(Seg[i].second.first-Seg[i].first.first)*(Seg[i].second.second-Seg[i].first.second);
    };
    auto cmp_Set = [&](const int a, const int b){
        auto x = point(a, nowx), y = point(b, nowx);
        return x < y;
    };
    set<int, decltype(cmp_Set)> Set(cmp_Set);
    Set.insert(0);
    vector<int> to(N+1), tail(N+1);
    for(int i=0; i<=N; i++){
        to[i]=tail[i]=i;
    }
    for(int _=1; _<=N+N; _++){
        int i = X[_].second;
        nowx = X[_].first;
        if(i>0) Set.insert(i);
        else{
            i=-i;
            auto p = Set.find(i);
            int j = *--p;
            to[tail[j]]=i;
            tail[j]=tail[i];
            Set.erase(i);
        }
    }
    for(int x=1; x<=N+N; x++){
        int i = X[x].second;
        if(i>0)
            Seg[i].first.first=x<<1;
        else
            Seg[-i].second.first=x<<1;
    }
    vector<pair<pii, bool>> Ban(N+1);
    for(int i=to[0], j=N; j; i=to[i], j--){
        Ban[j]={{Seg[i].first.first, Seg[i].second.first}, Seg[i].first.second>Seg[i].second.second};
    }
    int inf=0x3f3f3f3f, l, r;
    if(ll<X[1].first || rr>X[X.size()-1].first)return puts("0"), 0;
    auto rightL = lower_bound(X.begin()+1, X.end(), make_pair(ll, -inf));
    l = (rightL - X.begin())*2 - (rightL->first != ll);
    auto leftR = lower_bound(X.begin()+1, X.end(), make_pair(rr+1, -inf)) -1;
    r = (leftR - X.begin())*2 + (leftR->first != rr);
    vector<int> dp(N*4+3, 0);
    set<int> Neg, Pos;
    dp[0]=inf;
    dp[l]=-inf;
    dp[r+1]=inf;
    Pos.insert(r+1);
    Neg.insert(l);
    for(int i=1; i<=N; i++){
        int L = Ban[i].first.first, R=Ban[i].first.second;
        if(Ban[i].second){
            auto i=Pos.lower_bound(L+1);
            while(i!=Pos.end() && *i<=R){
                auto j=i; j++;
                auto k=Neg.lower_bound(*i+1);
                int pos = R+1;
                if(j!=Pos.end() && *j<pos)pos=*j;
                if(k!=Neg.end() && *k<pos)pos=*k;
                dp[pos]+=dp[*i];
                dp[*i]=0;
                Pos.erase(i);
                if(dp[pos]>0)Pos.insert(pos), Neg.erase(pos);
                else if(dp[pos]<0)Neg.insert(pos), Pos.erase(pos);
                else Neg.erase(pos), Pos.erase(pos);
                i=Pos.lower_bound(L+1);
            }
            dp[L]++;
            if(dp[L]==0)Neg.erase(L);
            else if(dp[L]==1)Pos.insert(L);
            dp[R]--;
            if(dp[R]==0)Pos.erase(R);
            else if(dp[R]==-1)Neg.insert(R);
        }
        else{
            auto i=Neg.lower_bound(R+1);
            while(i!=Neg.begin() && *--i>L){
                auto j=i;
                auto k=Pos.lower_bound(*i+1);
                int pos = L;
                if(j!=Neg.begin() && *--j>pos)pos=*j;
                if(k!=Pos.begin() && *--k>pos)pos=*k;
                dp[pos]+=dp[*i];
                dp[*i]=0;
                Neg.erase(i);
                if(dp[pos]>0)Pos.insert(pos), Neg.erase(pos);
                else if(dp[pos]<0)Neg.insert(pos), Pos.erase(pos);
                else Neg.erase(pos), Pos.erase(pos);
                i=Neg.lower_bound(R+1);
            }
            dp[L+1]++;
            if(dp[L+1]==0)Neg.erase(L+1);
            else if(dp[L+1]==1)Pos.insert(L+1);
            dp[R+1]--;
            if(dp[R+1]==0)Pos.erase(R+1);
            else if(dp[R+1]==-1)Neg.insert(R+1);
        }
    }
    for(int i=1; i<=N*4; i++){
        dp[i]+=dp[i-1];
    }
    int ans = N;
    for(int i=l; i<=r; i++){
        ans = min(ans, dp[i]);
    }
    printf("%d\n", ans);
}