[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;
}