(COCI 2015/2016 4) ENDOR

题解

题意

在一根长度为 L 米的棍子上，有 N 只变色龙，初始位置、颜色和运动方向给定。所有变色龙以 1 米/秒 的恒定速度运动，遇到棍子末端即离开。

运动规则：

• 相遇即碰撞，碰撞后两者调转方向。
• 颜色变化规则（设碰撞前向左的变色龙颜色为 a，向右的为 b）：
  • 碰撞前向左的变色龙，碰撞后颜色变为 b。
  • 碰撞前向右的变色龙，碰撞后颜色变为 (a + b) mod K。

共有 K 种颜色（编号 0 至 K-1）。对于每种颜色，统计所有曾拥有该颜色的变色龙，在离开棍子前各自行走的路程之和。

数据范围

• 1 ≤ N ≤ 10⁵
• 1 ≤ K ≤ 40
• 1 ≤ L ≤ 10⁶
• 0 ≤ dᵢ ≤ L，dᵢ 严格递增给出
• 0 ≤ bᵢ < K
• 方向字符：'L' 表示向左，'D' 表示向右
• 对于 50% 的数据：N ≤ 3000

解法

思维题。

此题一眼看上去非常不可做，但是仔细思考会发现一些神秘性质。

首先，有一个非常关键的性质，当左右两个变色龙相撞，向左的变色龙会变成向右的变色龙的颜色。

而对于此题来说，我们不关心哪只变色龙走了多远，我们只关心某个颜色走了多远。

那么我们发现，如果两个变色龙相撞，相撞前颜色$a$向左走，颜色$b$向右走。相撞后颜色$(a+b)\mod k$向左走，颜色$b$向右走。

此时我们发现了一个华点。

无论是相撞前还是相撞后，颜色$b$都是向右走。于是我们可以将相撞等价成这样一个形式。

当两个变色龙相撞，向左的变色龙的颜色会变为$(a+b) \mod k$

这样我们就解决了变色龙会来回走的问题。

由于向右走的变色龙颜色不变，会一走到底，所以每一只向右的变色龙是十分好计算的。

而对于向左的变色龙，就相对麻烦。

向左的变色龙每次遇到一个向右的变色龙，颜色都会变化，这样他的贡献就会被拆成几段。

如果每次暴力计算这几段的贡献，那么时间复杂度会退化成$O(n^2)$级别。

接下来，就要搬出这道题的第二个性质，每个变色龙速度相等且不变。那么所有向右的变色龙是相对静止的,也就是说他们的相对位置不会发生变化。

这样对于任意一个向左的变色龙，他每一段的贡献都是它左边的每一对相邻的向右变色龙之间的距离除以$2$

但是还有一个问题，就是这些段贡献的是那些颜色呢？

我们观察这个式子$(a+b) \mod k$,我们把$0$到$k-1$这些整数看作一个环，那么这个式子就相当于将环上每个节点的贡献向右移动$b$个单位。

我们将所有变色龙按从左到右的位置排序，记录一个全局的$val$数组，表示当前如果出现一个向左的变色龙，在不考虑这只变色龙的颜色的情况下(默认为:0)这条变色龙会对每种颜色贡献的距离数。

如果我们遇到一个向左的变色龙颜色为$b$，那么我们就将所有颜色的贡献都右移$b$格再加入到答案里。记得单独处理起点到碰到第一只变色龙的段和与最后一只变色龙相撞后走到结尾的段。

如果我们遇到一个向右的变色龙颜色为$b$，那么首先第一步是直接算贡献，然后我们将$val$数组集体向右移$b$格，再将$val$中$b$这个颜色的贡献增加与上一个向右变色龙的距离的一半。这个操作相当于是在之前每一段对应的颜色后面增加了一个$b$多想想应该能理解这样做的正确性。

时间复杂度$O(nk)$但是$k$很小，故能通过此题。

代码

code

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e5+10;
int n,k,l;
struct node{
    ll x,color,opt;
    bool operator<(const node &b) const
    {
        return x<b.x;
    }
} a[N];
ll ans[50];
ll val[50];
int main()
{
    // freopen("endor.in","r",stdin);
    // freopen("4.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k>>l;
    l*=10;
    for(int i=1;i<=n;i++)
    {
        char c;
        cin>>a[i].x>>a[i].color>>c;
        a[i].x*=10;
        if(c=='L') a[i].opt=0;
        else a[i].opt=1;
    }
    sort(a+1,a+n+1);
    int lst=0,color=0,s=0;
    for(int i=1;i<=n;i++)
    {
        if(a[i].opt)
        {
            ans[a[i].color]+=l-a[i].x;
            color=(color+a[i].color)%k;
            ll b[50];
            for(int j=0;j<k;j++)
            {
                b[(j+a[i].color)%k]=val[j];
            }
            for(int j=0;j<k;j++) val[j]=b[j];
            if(lst) val[a[i].color]+=(a[i].x-a[lst].x)/2ll;
            else s=i;
            lst=i;
        }
        else
        {
            if(s)
            {
                ans[a[i].color]+=(a[i].x-a[lst].x)/2ll;
                for(int j=0;j<k;j++)
                {
                    ans[(j+a[i].color)%k]+=val[j];
                }
                ans[(color+a[i].color)%k]+=(a[i].x-(a[i].x-a[s].x)/2ll);
            }
            else ans[a[i].color]+=a[i].x;
        }
    }
    for(int i=0;i<k;i++) cout<<ans[i]/10ll<<'.'<<ans[i]%10ll<<'\n';
    return 0;
}