打卡信奥刷题（2715）用C++实现信奥题 P3361 Cool loves maids

P3361 Cool loves maids

题目背景

Cool 非常喜欢妹子，以至于 Cool 在百度上有一个非常神奇的 ID 【雾】。

题目描述

Cool 现在搞清楚了女生宿舍的地形。女生宿舍是由很多栋楼构成的，它们可以被抽象成20×2020\times 2020×20的方格。

Cool 的妹子们所处的地方可以被表示为实数类型的坐标。当一个妹子(x,y)(x,y)(x,y)在楼(i,j)(i,j)(i,j)中，当且仅当i≤x<i+1i \le x<i+1i≤x<i+1，j≤y<j+1j \le y<j+1j≤y<j+1，i,j∈Zi,j\in \Zi,j∈Z。两个妹子之间有距离，当且仅当一个妹子所在的楼的横纵坐标均小于另一个妹子所在的楼，此时她们之间的距离为她们自身坐标的曼哈顿距离。

现在 Cool 要搞一个大统计：求nnn个妹子之间所有距离之和。

输入格式

为了避免输入文件过大无法上传在读入方面消耗过多时间，本题采取数据生成方案。

输入包含两行：

• 第一行，一个整数nnn；
• 第二行，包含666个整数rxa,rxc,rya,ryc,rza,rzc\mathrm{rxa},\mathrm{rxc},\mathrm{rya},\mathrm{ryc},\mathrm{rza},\mathrm{rzc}rxa,rxc,rya,ryc,rza,rzc。

所有的实数都采用如下方式生成：

1. 初始化x=y=z=0x=y=z=0x=y=z=0；
2. 重复以下过程：
   • x=(y×rxa+rxc) mod rpx=(y\times \mathrm{rxa}+\mathrm{rxc})\bmod \mathrm{rp}x=(y×rxa+rxc)modrp；
   • y=(z×rya+ryc) mod rpy=(z\times \mathrm{rya}+\mathrm{ryc})\bmod \mathrm{rp}y=(z×rya+ryc)modrp；
   • z=(x×rza+rzc) mod rpz=(x\times \mathrm{rza}+\mathrm{rzc})\bmod \mathrm{rp}z=(x×rza+rzc)modrp。

每次得到的实数即为(x mod 20)+(y mod 10)÷10+(z mod 10)÷100(x\bmod 20)+(y\bmod 10)\div 10+(z\bmod 10)\div 100(xmod20)+(ymod10)÷10+(zmod10)÷100。rp=2333333\mathrm{rp}=2333333rp=2333333。

第iii个妹子将以第2i−12i-12i−1个生成实数为横坐标，第2i2i2i个生成实数为纵坐标。

输出格式

输出包含一行一个实数，表示nnn个妹子之间所有距离之和的平均值，保留555位小数。

输入输出样例 #1

输入 #1

6 3 5 7 11 13 17

输出 #1

17.52167

说明/提示

数据范围及约定

对于全部数据，保证1≤n≤5×1061\le n\le 5\times 10^61≤n≤5×106。

C++实现

#include<bits/stdc++.h>usingnamespacestd;intn,rxa,rxc,rya,ryc,rza,rzc,rp=2333333,f[45][45];longlongx,y,z,num;doublemzx,mzy,a[45][45],b[45][45],ans;intmain(){scanf("%d%d%d%d%d%d%d",&n,&rxa,&rxc,&rya,&ryc,&rza,&rzc);for(registerinti=1;i<=2*n;i++){x=(y*rxa+rxc)%rp;y=(z*rya+ryc)%rp;z=(x*rza+rzc)%rp;if(i%2==1)mzx=(double)(x%20)+((double)(y%10)/10.000000000)+((double)(z%10)/100.00000000);else{mzy=(double)(x%20)+((double)(y%10)/10.000000000)+((double)(z%10)/100.00000000);a[(int)mzx][(int)mzy]+=mzx;b[(int)mzx][(int)mzy]+=mzy;f[(int)mzx][(int)mzy]++;}}for(registerinti=0;i<=20;i++)for(registerintj=0;j<=20;j++)for(registerintk=i+1;k<=20;k++)for(registerintl=j+1;l<=20;l++){ans+=(a[k][l]+b[k][l])*(double)f[i][j]-(a[i][j]+b[i][j])*(double)f[k][l];num+=f[i][j]*f[k][l];}//按要求来就是了printf("%.5f",ans/num);}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容