P8048 [COCI 2015/2016 #4] ENDOR
题目描述
如果我们相信《吉尼斯世界纪录大全》的话，在布满森林的 Endor 卫星上，有一根全银河系最长的棍子。在那根L LL米长的棍子上有n nn只欢快的变色龙。每只变色龙以1 11米/秒的恒定速度沿着棍子在两个可能的方向（左或右）中的一个方向上移动，并以可能的k kk种颜色之一着色。
众所周知，Endor 卫星上的变色龙崇拜古老的蚂蚁法则，该法则规定变色龙必须沿着棍子行走直到走到棍子的末端，并且当与另一只变色龙发生碰撞时，该变色龙必须转过180 180180度，继续朝相反的方向行走。此外，在向左移动着色为a aa的变色龙与向右移动的着色为b bb的变色龙发生碰撞后，碰撞前向左移动的变色龙采用碰撞前向右移动的变色龙的颜色b bb，而在碰撞前向右移动的变色龙会采用新的颜色( a + b ) m o d k (a+b)\bmod k(a+b)modk。
如果给你所有变色龙的初始位置、颜色和运动方向，对于每种颜色，确定采用该种颜色的变色龙在离开棍子之前的总行程。
输入格式
第一行输入三个整数n , k , L n,k,Ln,k,L，分别表示变色龙的只数，颜色的种数和棍子的长度。
随后n nn行，每行两个整数d i , b i d_i,b_idi,bi和一个字符L或D，其中d i , b i d_i,b_idi,bi分别表示第i ii只变色龙到棍子左端的距离和第i ii只变色龙的颜色，字符如果是L，则表示第i ii只变色龙初始时面朝左边，否则表示第i ii只变色龙初始时面朝右边。保证d i d_idi两两不同且按升序给出。
输出格式
输出k kk行，第i ii行输出一个实数，表示采用第i − 1 i-1i−1种颜色的变色龙离开棍子之前的总行程，保留一位小数。可以证明，答案要么是整数，要么是形如x.5 \texttt{x.5}x.5的一位小数。
输入输出样例 #1
输入 #1
2 3 10 0 0 D 10 1 L输出 #1
10.0 10.0 0.0输入输出样例 #2
输入 #2
4 3 7 1 0 D 3 0 D 4 1 L 6 2 D输出 #2
10.0 4.0 1.0输入输出样例 #3
输入 #3
4 4 5 1 1 D 3 3 L 4 2 D 5 0 L输出 #3
2.5 4.0 2.5 4.0说明/提示
【样例 1 解释】
两只变色龙在行走了5 55米之后发生碰撞。在此之后，1 11号变色龙的颜色变为0 00，2 22号变色龙的颜色变为1 11，然后它们各又继续走了5 55米然后离开棍子。因此，采用第0 00种颜色和第1 11种颜色的变色龙各走了10 1010米，在此过程中不存在采用第2 22种颜色的变色龙。
【数据范围】
对于50 % 50\%50%的数据，保证1 ⩽ n ⩽ 3000 1\leqslant n\leqslant 30001⩽n⩽3000。
对于所有数据，1 ⩽ n ⩽ 10 5 1\leqslant n\leqslant 10^51⩽n⩽105，1 ⩽ k ⩽ 40 1\leqslant k\leqslant 401⩽k⩽40，1 ⩽ L ⩽ 10 6 1\leqslant L\leqslant 10^61⩽L⩽106，0 ⩽ d i ⩽ L 0\leqslant d_i\leqslant L0⩽di⩽L，0 ⩽ b i < k 0\leqslant b_i<k0⩽bi<k，d i − 1 < d i d_{i-1}<d_idi−1<di。
【题目来源】
本题来源自COCI 2015-2016 CONTEST 4 T6 ENDOR，按照原题数据配置，满分160 160160分。
由 Eason_AC 翻译整理提供。
C++实现
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;doublecnt[50],ans[50];signedmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);intn,k,l;cin>>n>>k>>l;intlst=0,del=0;for(inti=1;i<=n;++i){intd,col;charop;cin>>d>>col>>op;if(op=='L'){ans[col]+=(d-lst)/2.0;ans[(col+del)%k]+=d/2.0;for(inti=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(inti=0;i<k;++i)cout<<fixed<<setprecision(1)<<ans[i]<<'\n';return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
