[COCI2015-2016#4] ENDOR 题解
首先要发现一个很重要的性质，那就是两只变色龙碰撞后回头，等效于两只变色龙继续往前走，其中向右走的颜色不变，而向左走的要改变颜色。
那这样就有一种 \(O(n^2)\) 的做法：对于向右的变色龙，直接贡献答案；对于向左的变色龙，我们按照碰到的先后顺序枚举它前面所有向右走的变色龙，这样每只向右走的变色龙都会给当前的颜色贡献 \(\frac{1}{2}(d_{i+1} - d_i)\) 的路程，当然这里的 \(d\) 是相邻的两只向右走的变色龙。注意开头和结尾都要特殊处理。
然后我们发现 \(k\) 很小，而 \(d_{i+1} - d_i\) 仅与向右走的变色龙有关，这启示我们去按照模 \(k\) 意义上去记录贡献。我们约定后面所说的关于颜色的运算均为模 \(k\) 意义下的。具体地，我们设 \(w_i\)，表示如果初始颜色为 \(0\)，则当前的变色龙会给颜色 \(i\) 造成 \(w_i\) 的贡献。那对于颜色为 \(x\) 的变色龙，就会给颜色 \(x+i\) 造成 \(w_i\) 的贡献。
我们考虑维护这个 \(w_i\)。假设我们现在已经有 \(t\) 只向右走的变色龙，当加入一只新的向右走的变色龙 \(p\) 时，它的颜色会导致 \(w\) 数组集体平移，因为每个颜色都在模 \(k\) 意义下加了 \(c_p\)。所以 \(w'_{i+c_p} = w_i\)，同时还会在 \(c_p\) 位置上新增 \(\frac{1}{2} (d_{t+1} - d_t)\) 的贡献。这样，每个向左走的变色龙就可以通过 \(k\) 次枚举统计答案了。还是注意开头和结尾的特殊处理，具体看代码。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+100;
int read() {
int x = 0, f = 1; char ch = getchar();
while(ch<'0' || ch>'9') {if(ch == '-') f = -1; ch = getchar();}
while(ch>='0'&&ch<='9') {x = x * 10 + (ch-48), ch = getchar();}
return x * f;
}
struct xwx {
int d, col, dir;
bool operator < (const xwx &b) const {
return d < b.d;
}
} a[N];
int n, K, L;
int c[N];
double ans[50];
double w[50];
int sum;
int dr[N], totr, cr[N];//记录向右走的变色龙的信息
void change(int del) {
double b[50];
for(int i = 0; i<K; ++i) {
b[(i+del)%K] = w[i];
}
for(int i = 0; i<K; ++i) {
w[i] = b[i];
}
}//平移数组
int main() {
n = read(), K = read(), L = read();
for(int i = 1; i<=n; ++i) {
a[i].d = read(), a[i].col = read();
char op[3];
scanf("%s", op);
if(op[0] == 'L') a[i].dir = 0;
else a[i].dir = 1, ans[a[i].col]+=(L-a[i].d);
}
sort(a+1, a+n+1);
for(int i = 1; i<=n; ++i) {
c[i] = a[i].col;
}//完全没有意义的一步（
for(int i = 1; i<=n; ++i) {
if(a[i].dir) {
++totr;
dr[totr] = a[i].d;
cr[totr] = a[i].col;
sum = (sum + a[i].col)%K;//用来确定颜色最后会变成什么
if(totr > 1) {
change(a[i].col);
w[a[i].col]+=(0.5*(dr[totr] - dr[totr-1]));
}
continue;
}
// dr[totr+1] = a[i].d;
// for(int j = totr; j>=1; --j) {
// ans[c[i]]+=(0.5*(dr[j+1] - dr[j]));
// c[i] = (c[i] + cr[j])%K;
// }
// ans[c[i]]+=0.5*(a[i].d + dr[1]);//n^2做法
for(int j = 0; j<K; ++j) {
ans[(c[i]+j)%K]+=w[j];
}
ans[c[i]]+=(0.5*(a[i].d - dr[totr]));//第一只遇到的向右走的变色龙
ans[(c[i] + sum)%K]+=(0.5*(a[i].d + dr[1]));//走过最后一只变色龙后还要一直走到终点。
}
for(int i = 0; i<K; ++i) {
printf("%.1lf\n", ans[i]);
}
return 0;
}