HDU 5725 Game

1. 笔记

题意是求距离的期望（距离仍指连接两点且有效的路径长度的最小值）。直观想象可以发现，该距离与曼哈顿距离相比最多多2（可以构造这样的路径）。

答案=（任意两点曼哈顿距离的总和 - 至少有一点是守卫的距离总和 + 因守卫的存在比曼哈顿距离多出的部分）/（任选两点均不是守卫的情况数）

任意两点曼哈顿距离的总和=\(\frac{mn(m+n)(mn-1)}{3}\)，O(1)

至少有一点是守卫的距离总和：临时跑，O(n^2)

任选两点均不是守卫的情况数=非守卫点数^2，O(1)

比较tricky的是因守卫的存在比曼哈顿距离多出的部分。通过简单的实验可以得到这样一个猜想（实际上也是正确的）：如果从左上走到右下，比如说从第一排第一列走到第n排第m列，那么需要绕路的必要条件是守卫的列数随着排数的增加而增加。证明如下：

设前k-1排都满足“守卫的列数随着排数的增加而增加”的性质，而第k排不满足，其中k>1。不难发现，一定可以从起点(1,1)走到第k排守卫的右侧一位(k,r)而不绕路（记(k,r)表示第k排第r列）。Claim：(k,r)开始走到终点也是不绕路的。要证明这一点，只要对列数从m到r做归纳，得出结论：从(k,r)走到终点(n,m)需要绕路，当且仅当长方形区域(k,r)-(n,m)内的每一列都必须有守卫，并且守卫的排布满足“守卫的列数随着排数的增加而增加”的性质。但这是不可能的，因为必有一个守卫会和前k-1排的某个守卫位于同一列。#

由此可以得出绕路的充要条件 （还是从左上走到右下）：要么每一排、要么每一列都有一个守卫，并且守卫的排布满足“守卫的列数随排数的增加而增加”的性质。证明如下：

若第一排第一列都有守卫，由必要条件知，不需要绕路。若第一排或第一列有一个为空，则由必要条件的证明知，守卫的排布必满足上述性质。逆命题是显然的。#

实现时只要考虑满足“绕路性质”的守卫让多少条路径绕路即可。O(n^2)

总复杂度为O(n^2)。可以通过。

2. 代码

#include<bits/stdc++.h>

using namespace std;

const int maxn=1e3+5;

typedef long long ll;

int m,n;

ll a,b,c,d;

int l[maxn],r[maxn];

int main()

{

    //freopen("Input.txt","r",stdin);

    int T;scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&n,&m);

        memset(l,0,sizeof l);memset(r,0,sizeof r);

        char tmp[maxn];

        int cnt=0;

        //printf("Input:\n");

        for(int i=1;i<=n;++i)

        {

             scanf("%s",tmp);

             for(int j=0;j<m;++j)if(tmp[j]=='G'){l[i]=j+1;r[j+1]=i;cnt++;}

        }

        //printf("End\n");

        a=1LL*m*n*(m+n)*(m*n-1)/3;

        d=1LL*(m*n-cnt)*(m*n-cnt);

        b=0;

        for(int i=1;i<=n;++i)

        {

            if(l[i])b+=1LL*m*n*n-2*m*n*i+2*m*i*i+m*n-2*m*i+n*m*m-2*m*n*l[i]+2*n*l[i]*l[i]+m*n-2*n*l[i];

        }

        //printf("b=%d\n",b);

        for(int i=1;i<=n;++i)

        {

            if(l[i])

            {

                for(int j=i+1;j<=n;++j)

                {

                    if(l[j])b-=2*abs(i-j)+2*abs(l[i]-l[j]);

                }

            }

        }

        c=0;

        for(int i=1;i<=n;++i)

        {

            if(l[i]==0)continue;

            c+=4*(l[i]-1)*(m-l[i]);

            int j=i+1;

            while(j<=n&&l[j]&&l[j]>l[j-1])c+=4*(l[i]-1)*(m-l[j++]);

            j=i+1;

            while(j<=n&&l[j]&&l[j]<l[j-1])c+=4*(l[j++]-1)*(m-l[i]);

            //printf("i=%d,c=%d\n",i,c);

        }

        for(int i=1;i<=m;++i)

        {

            if(r[i]==0)continue;

            c+=4*(r[i]-1)*(n-r[i]);

            int j=i+1;

            while(j<=m&&r[j]&&r[j]>r[j-1])c+=4*(r[i]-1)*(n-r[j++]);

            j=i+1;

            while(j<=m&&r[j]&&r[j]<r[j-1])c+=4*(r[j++]-1)*(n-r[i]);

            //printf("j=%d,c=%d\n",i,c);

        }

        double ans=a-b+c;

        ans/=d;

        printf("%.4f\n",ans);

    }

}

巴特西

HDU 5725 Game

最新文章

热门文章