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 (ab)\bmod k(ab)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输入 #12 3 10 0 0 D 10 1 L输出 #110.0 10.0 0.0输入输出样例 #2输入 #24 3 7 1 0 D 3 0 D 4 1 L 6 2 D输出 #210.0 4.0 1.0输入输出样例 #3输入 #34 4 5 1 1 D 3 3 L 4 2 D 5 0 L输出 #32.5 4.0 2.5 4.0说明/提示【样例 1 解释】两只变色龙在行走了5 55米之后发生碰撞。在此之后1 11号变色龙的颜色变为0 002 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⩽1051 ⩽ k ⩽ 40 1\leqslant k\leqslant 401⩽k⩽401 ⩽ L ⩽ 10 6 1\leqslant L\leqslant 10^61⩽L⩽1060 ⩽ d i ⩽ L 0\leqslant d_i\leqslant L0⩽di​⩽L0 ⩽ b i k 0\leqslant b_ik0⩽bi​kd i − 1 d i d_{i-1}d_idi−1​di​。【题目来源】本题来源自COCI 2015-2016 CONTEST 4 T6 ENDOR按照原题数据配置满分160 160160分。由 Eason_AC 翻译整理提供。C实现#includebits/stdc.h#defineintlonglongusingnamespacestd;doublecnt[50],ans[50];signedmain(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);intn,k,l;cinnkl;intlst0,del0;for(inti1;in;i){intd,col;charop;cindcolop;if(opL){ans[col](d-lst)/2.0;ans[(coldel)%k]d/2.0;for(inti0;ik;i)ans[(icol)%k]cnt[i];}else{ans[col]l-d;rotate(cnt,cntk-col,cntk);cnt[col](d-lst)/2.0;del(delcol)%k;lstd;}}for(inti0;ik;i)coutfixedsetprecision(1)ans[i]\n;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容