P7701 [CCC 2014] 提前交卷题目描述你正在一个狭窄而又长的礼堂里考试礼堂一共有nnn排标号从前到后分别为111到nnn。每排有666个座位左边333个右边333个中间是过道。每个座位都有一个从 A 到 F 的字母标识其中最左的座位的标识是 A最右的座位的标识是 F过道在座位标识为 C 和 D 的座位之间礼堂同时还有两个保密室一个在最前面第一排前面一个在最后面第nnn排后面。礼堂里的每个座位一开始被刚好一个考生占用。然而在考试过程中mmm个不同的考生决定完成所有他们会做的题后依次离开礼堂。第iii个考生在座位ricir_ic_iri​ci​其中cic_ici​是 A 到 F 的字母之一。当考生离开礼堂时他们必须在任意一个保密室等待到考试结束。幸运的是保密室能容下任意多的考生。考生不仅关心试题本身他们还关心怎么样可以最舒服的考试。因此他们协作以最小化他们的不满度之和。一个考生的不满度的计算方式是AxByAxByAxBy其中A,BA,BA,B为常数xxx为去往保密室时经过的考生人数具体将在下面详述yyy是在考生进入保密室之前保密室内的人数。注意如果一个考生不离开他的考位那么他的不满度为000。当一个考生从一个考位走往保密室时他在去往过道时必须先经过同排的考生然后走过从这行到第一行或第nnn行取决于所选的保密室的邻近过道的考生。注意走过空的座位不影响xxx值。你能帮助他们最小化他们的不满度之和吗输入格式第一行四个整数n,m,A,Bn,m,A,Bn,m,A,B以空格分隔分别表示礼堂内的排数、提前离开的考生数、不满度计算参数。接下来mmm行每行一个整数rir_iri​和一个字母cic_ici​其中1≤i≤n1\le i\le n1≤i≤n。输出格式输出一个整数表示最小的不满度之和。输入输出样例 #1输入 #15 5 3 4 3E 1D 5C 1E 4A输出 #155说明/提示其中一个最优策略是第一个提前离开的考生去最前面的保密室经过666个考生分别是3D、3C、2D、2C、1D、1C不满度为3×64×0183\times64\times0183×64×018。第二个提前离开的考生也去最前面的保密室只经过111个考生即1C然后他发现保密室里有111个考生不满度为777。第三个提前离开的考生去最后面的保密室经过111个考生不满度为333。第四个提前离开的考生去最前面的保密室经过111个考生因为座位1D是空的不满度为111111。最后第五个提前离开的考生去最后面的保密室经过444个考生发现保密室里有111个人不满度为161616。所有考生总的不满度为555555。对于60%60\%60%的数据1≤m≤50001\le m\le50001≤m≤5000对于100%100\%100%的数据1≤n≤1051\le n\le 10^51≤n≤1051≤m≤6n1\le m\le6n1≤m≤6n1≤A,B≤1091\le A,B\le 10^91≤A,B≤109。C实现#includebits/stdc.husingnamespacestd;#defineN100005#definelowbit(x)(x(-x))#defineintlonglongintn,m,a,b,ans,r[N*6],f[N],x[N*6],sum[N*6];boolok[N][6];charc[N*6];voidupdate(intx,inty){while(xn)f[x]y,xlowbit(x);}intquery(intl,intr){l--;intans0;while(l)ans-f[l],l-lowbit(l);while(r)ansf[r],r-lowbit(r);returnans;}signedmain(){cinnmab;for(inti1;im;i)cinr[i]c[i];for(inti1;in;i)update(i,2);for(inti1;im;i){inttmp10,tmp20;if(c[i]A)tmp1tmp2!ok[r[i]][1];if(c[i]F)tmp1tmp2!ok[r[i]][4];ok[r[i]][c[i]-A]1;if(c[i]C||c[i]D)update(r[i],-1);tmp1query(1,r[i]),tmp1*a;tmp2query(r[i],n),tmp2*a;anstmp1;x[i]tmp2-tmp1;}sort(x1,xm1);for(inti1;im;i)sum[i]sum[i-1]x[i];intminn1e18;for(inti0;im;i)minnmin(minn,sum[i](i*(i-1)/2(m-i)*(m-i-1)/2)*b);coutansminn;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容