P3361 Cool loves maids

题目背景

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

题目描述

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

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

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

输入格式

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

输入包含两行：

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

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

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

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

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

输出格式

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

输入输出样例 #1

输入 #1

6
3 5 7 11 13 17

输出 #1

17.52167

说明/提示

数据范围及约定

对于全部数据，保证 $1\le n\le 5\times 10^6$。

C++实现

#include<bits/stdc++.h>
using namespace std;
int n,rxa,rxc,rya,ryc,rza,rzc,rp=2333333,f[45][45];
long long x,y,z,num;
double mzx,mzy,a[45][45],b[45][45],ans;
int main(){
    scanf("%d%d%d%d%d%d%d",&n,&rxa,&rxc,&rya,&ryc,&rza,&rzc);
    for(register int i=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(register int i=0;i<=20;i++)
        for(register int j=0;j<=20;j++)
            for(register int k=i+1;k<=20;k++)
                for(register int l=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考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容