BigHead
0%

HDU 5725 Game (16多校第一场)

Posted on Edited on In , Views: Valine:

$Time Limit:1000MS~~Memory Limit:65536KB $

题意

一个 $n \times m $的棋盘上有若干个守卫,每行每列至多只有一个守卫,现在问你除了守卫点,其他任意两点最短距离的期望. $ (2\leq n,m\leq 1000)$

分析

  • 第一眼看只考虑到守卫会对每一行每一列的格子最短距离有影响,而忽略了下面这种情况
1
2
3
4
5
6
7
1
5 8
########	###A####
###G####	##CG####
######G#	######GD
####G###	####G###
########	####B###

  • 如上A -> B 以及C -> D 也会被影响,所以这里还要考虑行的情况下列中G递增和递减对期望贡献的影响,列情况下也一样

  • 还有就是写的时候可能写搓了就会T,这题987ms~780ms擦边过

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
/*************************************************************************
    > File Name: cc.cpp
    > Author: liangxianfeng
    > Mail:   liangxianfeng96@qq.com
    > Created Time: 2016年07月23日 星期六 14时39分42秒
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<stack>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<cmath>
using namespace std;
#define ll long long
#define rep(i,n) for(int i =0; i < n; ++i)
#define rep_1(i,n) for(int i =1; i <= n; ++i)
#define CLR(x) memset(x,0,sizeof x)
#define MEM(a,b) memset(a,b,sizeof a)
#define pr(x) //cout << #x << " = " << x << " ";
#define ii (n-i+1)
#define jj (m-j+1)
#define prln(x) //cout << #x << " = " << x <<  endl; 
const int maxn = 1e3+100;
const int INF = 0x3f3f3f3f;
ll l[maxn][maxn], r[maxn][maxn], up[maxn][maxn], down[maxn][maxn];
int a[maxn][maxn];
int n, m;
const int MOD = 1e9+7;
char s[maxn][maxn];
struct Node{
    int x, y;
    Node(){}
    Node(int _x, int _y){
        x = _x;
        y = _y;
    }
}rr[maxn], cc[maxn];
int cntc, cntr;
void calcnt(){
    cntc = cntr = 0;
    rep_1(i,n){
        rep_1(j,m){
            if(s[i][j]=='G'){ 
                a[i][j] = 0;
                rr[cntr++] = Node(i,j);
            }
            else a[i][j] = 1;
        }
    }
    rep_1(j, m){
        rep_1(i, n){
            if(a[i][j]==0)cc[cntc++] = Node(i,j);
        }
    }
    for(int i = 0; i <= n; ++i){
        l[i][0] = 0;
        l[i][1] = 0;
        r[i][m+1] = 0;
        r[i][m] = 0;
    }
    for(int i = 0; i <= m; ++i){
        up[0][i] = 0;
        up[1][i] = 0;
        down[n+1][i] = 0;
        down[n][i] = 0;
    }
    rep_1(i, n){
        rep_1(j, m){
            l[i][1+j] = a[i][j] + l[i][j]; 
            up[i+1][j] = a[i][j] + up[i][j];
            down[ii-1][jj] = a[ii][jj] + down[ii][jj];
            r[ii][jj-1] = a[ii][jj] + r[ii][jj];
        }
    }
}
inline int getremove1(int x, int y){
    return x*y*(x+y)/2;
}
inline ll getremove(int x, int y){
    ll ans = 0;
    ans = (ans + getremove1(x-1,y) + getremove1(x,m-y) + getremove1(n-x+1,y-1) + getremove1(n-x,m-y+1));
    return ans;
}
ll getadd(){
    ll ans  = 0;
    bool flag = true;
    ll last = 0;
    for(int i = 0; i < cntr; ++i){
        Node& g = rr[i];
        ans += l[g.x][g.y]*r[g.x][g.y]*4;
        if(i == 0){
            last = l[g.x][g.y];
        }else{
            if(g.x-rr[i-1].x>1){
                last = l[g.x][g.y];
                flag = true;
                continue;
            }
            if(flag && g.y > rr[i-1].y){
                ans += last*r[g.x][g.y]*4;
                last += l[g.x][g.y];
                flag = true;
            }else if(flag && g.y < rr[i-1].y){
                last = r[rr[i-1].x][rr[i-1].y];
                ans += last*l[g.x][g.y]*4;
                last += r[g.x][g.y];
                flag = false;
            }else if(!flag && g.y > rr[i-1].y){
                last = l[rr[i-1].x][rr[i-1].y];
                ans += last*r[g.x][g.y]*4;
                last += l[g.x][g.y];
                flag = true;
            }else {
                ans += last*l[g.x][g.y]*4;
                last += r[g.x][g.y];
                flag = false;
            }
        }
    }
    flag  = true;
    last = 0;
    for(int i = 0; i < cntc; ++i){
        Node& g = cc[i];
        ans += up[g.x][g.y]*down[g.x][g.y]*4;
        if(i == 0){
            last += up[g.x][g.y];
        }else{
            if(g.y-cc[i-1].y>1){
                last = up[g.x][g.y];
                flag = true;
                continue;
            }
            if(flag && g.x > cc[i-1].x){
                ans += last*down[g.x][g.y]*4;
                last += up[g.x][g.y];
                flag = true;
            }else if(flag && g.x < cc[i-1].x){
                last = down[cc[i-1].x][cc[i-1].y];
                ans += last*up[g.x][g.y]*4;
                last += down[g.x][g.y];
                flag = false;
            }else if(!flag && g.x > cc[i-1].x){
                last = up[cc[i-1].x][cc[i-1].y];
                ans += last*down[g.x][g.y]*4;
                last += up[g.x][g.y];
                flag = true;
            }else {
                ans += last*up[g.x][g.y]*4;
                last += down[g.x][g.y];
                flag = false;
           
            }
        }
    }
    return ans;
}
ll solve(){
    calcnt();
    ll ans = 0;
    ll add = 0;
    ll x = getremove(1,1);
    ll sumx = x;
    for(int i = 2; i <= m; ++i){
        x -= (m-2*i+2)*n;
        sumx += x;
    }
    ll sum = sumx;
    for(int i = 2; i <= n; ++i){
        sumx -= (n-2*i+2)*m*m;
        sum += sumx;
    }
    for(int i = 0; i < cntr; ++i){
        sum -= 2*getremove(rr[i].x, rr[i].y);
    }
    add = getadd();
    ans = sum + add;
    return ans;
}
int main(){
#ifdef LOCAL
	//freopen("/home/zeroxf/桌面/in.txt","r",stdin);
	//freopen("/home/zeroxf/桌面/out.txt","w",stdout);
#endif
    int t;
    scanf("%d", &t);
    while(t--){
        scanf("%d%d", &n, &m);
        rep_1(i, n){
            scanf("%s", s[i]+1);
        }
        ll temp = solve();
        double ans = (ll)n*m-cntc;
        ans = ans*ans;
        ll gadd = 0;
        for(int i = 0; i < cntc; ++i){
            for(int j = 0; j < cntc; ++j){
                gadd += abs(cc[i].x-cc[j].x)+abs(cc[i].y-cc[j].y);
            }
        }
        temp += gadd;
        ans = temp*1.0/ans;
        printf("%.4f\n",ans);

    }
	return 0;
}