洛谷 P8048 题解

· · 题解

洛谷 P8048 题解

\text{Link}

思路分析

很好的思维题

首先考虑一个经典的 trick，假设两只相遇后的变色龙没有掉头，而是使用对方的颜色继续向前走，那么效果如下：

我们发现：此时向右走的变色龙相当于没变色，而向左走的变色龙的颜色加上了向右走的变色龙的颜色

所以每个向右走的变色龙对答案的贡献都能够快速统计，问题转化成统计每个向左走的变色龙对答案的贡献

注意到所有变色龙的速度都是相等的，因此考虑一次性维护当前向右走的所有变色龙可以让某一条向左走的变色龙对每种颜色的贡献，为了方便，假设在 0 处有一条颜色为 0 的变色龙，不妨假设最开始有一条颜色为 0 的变色龙直接和最右边的变色龙相遇，然后直到这条变色龙与最后一条变色龙相遇后，在途中分别对每种颜色 i 造成了 cnt_i 的贡献

那么再加入一条颜色为 col 的变色龙向右走，则有 cnt_{i+col}\gets cnt_{i}，记录一下上一个向右走的变色龙的位置 l，那么 cnt_{col}\gets cnt_{col}+\dfrac{d-l}{2}

那么此时实际出现了一只颜色为 col 的变色龙向左走，除去相遇第一只变色龙之前和相遇最后一只变色龙之后，中间过程对颜色 i 的贡献就是 cnt_{i-col}，那么这只变色龙在相遇第一只变色龙之前对 col 的贡献是 \dfrac {d-l}2，而且这只变色龙与第一只在 0 处的变色龙相遇恰好在 \dfrac d2 处，所以我们记录一下某条颜色为 0 的变色龙最终会变成的颜色 \Delta，此时这只变色龙走到 0 的时对颜色 col+\Delta 有 \dfrac d2 的贡献

然后模拟即可，时间复杂度 \Theta(nk)

代码呈现

#include<bits/stdc++.h>
#define int long long
using namespace std;
double cnt[50],ans[50];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n,k,l;
    cin>>n>>k>>l;
    int lst=0,del=0;
    for(int i=1;i<=n;++i) {
        int d,col;
        char op;
        cin>>d>>col>>op;
        if(op=='L') {
            ans[col]+=(d-lst)/2.0;
            ans[(col+del)%k]+=d/2.0;
            for(int i=0;i<k;++i) ans[(i+col)%k]+=cnt[i];
        } else {
            ans[col]+=l-d;
            rotate(cnt,cnt+k-col,cnt+k);
            cnt[col]+=(d-lst)/2.0;
            del=(del+col)%k;
            lst=d;
        }
    }
    for(int i=0;i<k;++i) cout<<fixed<<setprecision(1)<<ans[i]<<'\n';
    return 0;
}