题解：P14952 过河卒

· · 题解

借鉴 CF715D 的做法，首先注意到，答案肯定有很多种，所以说考虑直接贪心每次找贡献最大的边删掉，算贡献可以使用前后缀 dp。

然后这么做直接炸了，因为有可能你删太多了后面没空间删了。所以说我们需要随机扰动。

对于上面那题的做法是，每次不是直接删最大值，而是给每个值从大到小加权概率来删，具体实现就是从小到大枚举所有合法的能删的点，然后有 k 的概率将候选点改成当前的点，然后跑若干遍直到恰好符合答案的就退出。

还有一个优化就是对于每一个方案数找到合适的正方形大小，这样子中间浪费的随机性更少一点，同时也要留一点修改的空间，如果取方案数的三倍，这样就获得了 85pts 。

发现这个做法没有前途了，然后仔细对比一下这两道题，发现一个是删点，一个是删边，这会有什么不同呢，删边对全局的影响比删点小很多所以说删边的问题主要在于如何精准的凑出来答案，所以说在选边的时候就要随机扰动。那删点呢？我们发现如果选点的时候随机扰动，扰动就太大了，那我们能不能在开始的时候扰动呢？我们把随机化的方式改成开局随机撒几个点，然后直接贪心跑，然后就轻松通过了。 ::::info[Code]

#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int N=35;
int t,n,T,f[N][N],g[N][N];
bool p[N][N];
vector< array<int,3> > a;
mt19937 rnd(random_device{}());
void dp(){
    for(int i=0;i<=n+1;i++)for(int j=0;j<=n+1;j++)f[i][j]=g[i][j]=0;
    f[1][1]=1;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i+j>2&&!p[i][j])f[i][j]=f[i-1][j]+f[i][j-1];
    g[n][n]=1;
    for(int i=n;i>=1;i--)for(int j=n;j>=1;j--)if(i+j<2*n&&!p[i][j])g[i][j]=g[i+1][j]+g[i][j+1];
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin>>t;
    while(t--){
        cin>>T,n=1;
        if(!T){cout<<"2\n1 0\n0 1\n";continue;}
        while(1){
            dp();
            if(f[n][n]>=2*T)break;
            n++;
        }
        int S=0;
        while(1){
            for(int i=1;i<=rnd()%10;i++){
                int x,y;
                do x=rnd()%n+1,y=rnd()%n+1;
                while(x+y==2||x+y==2*n);
                p[x][y]=1;
            }
            while(1){
                dp(),S=f[n][n];
                for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){
                    int x=f[i][j]*g[i][j];
                    if(x&&x<=S-T)a.pb({x,i,j});
                }
                if(!a.size())break;
                sort(a.begin(),a.end());
                int x=a.size()-1;
                p[a[x][1]][a[x][2]]=1,a.clear();
            }
            if(S-T)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)p[i][j]=0;
            else break;
        }
        cout<<n<<'\n';
        for(int i=1;i<=n;i++,cout<<'\n')for(int j=1;j<=n;j++)cout<<!p[i][j]<<' ',p[i][j]=0;
    }
}

::::