P11937 题解

· · 题解

一些题外话：我提供了一份 hack 数据，但你可以当它不存在。理论上任何你认为正确并且能通过其他测试点的做法都能通过。

首先终点一定是黑格，考虑它所在的联通块，只有和这个联通块相邻的白点可以走过来，否则就必须要重开到另一个白点。当然，起点有可能可以直接走到终点，但此时用白格进行传送可能会更快。下文中只考虑需要走白格的情况。

所有白格都是一样的，所以肯定是先走到最近的一个。之后把白格分成两类：一种是旁边有其他白格的，此时走一步就可以重开；否则，需要走两步才能重开。

观察样例发现有时我们可以直接从白格走到终点但依然选择了重开，所以猜测对两类点都存在一个阈值，如果它到终点的距离小于等于阈值就直接往终点走，否则就重开。

具体地，假设原来两类点各有 s_1,s_2 个，小于等于阈值的点各有 a_1,a_2 个，它们到终点的总距离为 d，则第一次进入白格之后走到终点所需时间的期望为

\frac{d}{a_1+a_2}+\frac{s_1-a_1+s_2-a_2}{a_1+a_2}\cdot\frac{s_1-a_1+2(s_2-a_2)}{s_1-a_1+s_2-a_2}=\frac{d+s_1-a_1+2(s_2-a_2)}{a_1+a_2}

枚举所有可能的阈值，时间复杂度 O(\sum n^2m^2)，可以通过原题的所有数据，但不能通过 hack 数据。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=1007,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
struct frac{
    ll p,q;
}ans;
bool cmp(const frac& a,const frac& b){return a.p*b.q<a.q*b.p;}
ll T,n,m,dis[N][N],a[N][N],vis[N][N],s1,s2,c1[N*N],c2[N*N],stk1[N*N],top1,stk2[N*N],top2,sum;
char s[N];
queue<pair<int,int> > q;
frac operator +(const frac& a,const frac& b){return (frac){a.p*b.q+a.q*b.p,a.q*b.q};}
frac operator *(const frac& a,const frac& b){return (frac){a.p*b.p,a.q*b.q};}
frac calc(ll x,ll y,ll X,ll Y){
    return (frac){X+Y+sum-x-y*2,x+y}+(frac){dis[1][1],1};
}
void bfs(){
    for (int i=0;i<=n+1;++i) for (int j=0;j<=m+1;++j) dis[i][j]=vis[i][j]=0;
    q.push(make_pair(n,m));vis[n][m]=1;
    while(!q.empty()){
        auto p=q.front();q.pop();
        int x=p.first,y=p.second;
        if (a[x][y]==-1) continue;
        if (a[x][y]){
            if (a[x][y]==2) ++c2[dis[x][y]];
            else ++c1[dis[x][y]];
            continue;
        }
        for (int k=0;k<4;++k) if (!vis[x+dx[k]][y+dy[k]]){
            vis[x+dx[k]][y+dy[k]]=1;
            dis[x+dx[k]][y+dy[k]]=dis[x][y]+1;
            q.push(make_pair(x+dx[k],y+dy[k]));
        }
    }
}
int bfs2(){
    for (int i=0;i<=n+1;++i) for (int j=0;j<=m+1;++j) dis[i][j]=vis[i][j]=0;
    q.push(make_pair(1,1));vis[1][1]=1;
    while(!q.empty()){
        auto p=q.front();q.pop();
        int x=p.first,y=p.second;
        if (a[x][y]==-1) continue;
        if (a[x][y]){
            while(!q.empty()) q.pop();
            return dis[x][y];
        }
        for (int k=0;k<4;++k) if (!vis[x+dx[k]][y+dy[k]]){
            vis[x+dx[k]][y+dy[k]]=1;
            dis[x+dx[k]][y+dy[k]]=dis[x][y]+1;
            q.push(make_pair(x+dx[k],y+dy[k]));
        }
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>m;
        for (int i=0;i<=n+1;++i) a[i][0]=a[i][m+1]=-1;
        for (int i=0;i<=m+1;++i) a[0][i]=a[n+1][i]=-1;
        ans=(frac){1,0};
        for (int i=1;i<=n;++i){
            cin>>(s+1);
            for (int j=1;j<=m;++j) a[i][j]=(s[j]=='B'?2:0);
        }
        for (int i=1;i<=n;++i) for (int j=1;j<=m;++j) if (a[i][j]==2){
            for (int k=0;k<4;++k) if (a[i+dx[k]][j+dy[k]]>0) a[i][j]=1;
            if (a[i][j]==1) ++s1;else ++s2;
        }
        bfs();
        if (vis[1][1]) ans=(frac){dis[1][1],1};
        dis[1][1]=bfs2();
        if (s1||s2){
            sum=s1+2*s2;top1=top2=1;
            for (int i=1;i<=n*m;++i){
                if (c1[i]) stk1[++top1]=i;
                if (c2[i]) stk2[++top2]=i;
            }
            ll S1=0,S2=0,len1=0,len2=0;
            for (int i,_=1;_<=top1;++_){
                i=stk1[_];
                S2=len2=0;S1+=c1[i];len1+=c1[i]*i;
                for (int j,_=1;_<=top2;++_){
                    j=stk2[_];
                    S2+=c2[j];len2+=c2[j]*j;
                    auto p=calc(S1,S2,len1,len2);
                    if (cmp(p,ans)) ans=p;
                }
            }
        }
        int g=__gcd(ans.p,ans.q);
        cout<<ans.p/g<<'/'<<ans.q/g<<'\n';
        for (int i=0;i<=n*m;++i) c1[i]=c2[i]=0;s1=s2=0;
    }
    return 0;
}

但为了防止第二天一觉醒来发现自己题解被撤下来了还是给个复杂度有道理的做法吧。

令 s=s_1+2s_2，现在我们固定第二类点的阈值，计算最优的第一类点的阈值。

在原来的 \frac{d+s-a_1-2a_2}{a_1+a_2} 上面加入一个距离为 k 的第一类点，需要让答案变小，则

\frac{d+k+s-(a_1+1)-2a_2}{a_1+a_2+1}<\frac{d+s-a_1-2a_2}{a_1+a_2} k<\frac{d+s-a_2}{a_1+a_2}

不难发现，如果我们加入了一个距离较大的点，把它替换为距离更小的点一定不劣；观察式子还会发现，在从小到大加入点的过程中，距离相同的点要么都被加入要么都不被加入。并且右边的式子单调不增，左边的式子单调不降，可以二分。

时间复杂度 O(\sum(nm\log nm))。下面仅给出关键部分代码。应该可以做到更优但懒得搞了。

bfs();
if (vis[1][1]) ans=(frac){dis[1][1],1};
dis[1][1]=bfs2();
if (s1||s2){
    sum=s1+2*s2;
    for (int i=1;i<=n*m;++i){
        d1[i]=d1[i-1]+c1[i]*i;
        d2[i]=d2[i-1]+c2[i]*i;
        c1[i]+=c1[i-1];c2[i]+=c2[i-1];
    }
    for (int i=0;i<=n*m;++i) if (i==0||c2[i]!=c2[i-1]){
        ll l=1,r=n*m,pos=0;
        while(l<=r){
            ll mid=l+r>>1;
            if ((d1[mid-1]+d2[i]+sum-c2[i])>(c1[mid-1]+c2[i])*mid) pos=mid,l=mid+1;
            else r=mid-1;
        }
        auto p=calc(c1[pos],c2[i],d1[pos],d2[i]);
        if (cmp(p,ans)) ans=p;
    }
}
int g=__gcd(ans.p,ans.q);
assert(ans.q);
cout<<ans.p/g<<'/'<<ans.q/g<<'\n';
for (int i=0;i<=n*m;++i) c1[i]=c2[i]=d1[i]=d2[i]=0;
s1=s2=0;