由题目可知，每一列最多有两个草种子，每一行最多有两个草种子。
设当前要在 $n$ 行 $m$ 列 $(n>=m)$ 上填充草种子，我们在第一行和第二行的第一列上填充两个草种子。这样，第一行，第二行，第一列就再也不能填充其他种子了，问题规模就缩减到了$(n-2,m-1)$，然后递归求解即可。
递归边界：
当 $n=m=1$ 时，$ans=1;$
当 $n=1,m=2$ 时，$ans=2;$
当 $n=2,m=1$ 时，$ans=2;$
当 $n=m=2$ 时，$ans=2.$
$code:$
#include<iostream> #include<cstdio> using namespace std; long long t,n,m; long long dfs(long long a,long long b){ if(a==1&&b==1) return 1; else if(a==1&&b==2) return 2; else if(a==2&&b==1) return 2; else if(a==2&&b==2) return 2; if(a<b) swap(a,b); long long d=a-b; if(a>=b*2) return b*2; if(d>0) return dfs(a-d*2,b-d)+d*2; if(d==0) return dfs(a%3,b%3)+a/3*4; } int main(){ //freopen("dendro.in","r",stdin); //freopen("dendro.out","w",stdout); scanf("%lld",&t); while(t--){ scanf("%lld%lld",&n,&m); if(n<m) swap(n,m); printf("%lld\n",dfs(n,m)); } fclose(stdin);fclose(stdout); return 0; }
# T2 数列(seq)
不难发现这道题需要搜索，但是如果是正常的搜索会超时，所以我们需要双向搜索。具体细节见代码。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; long long n,a[15],s,rsum[15],ans,f[15][50],cnt,sum[2000005],n1; bool cmp(long long x,long long y){ return x>y; } long long fast_mul(long long x,long long y){ long long sum=x;x=1; while(y){ if(y&1){ x*=sum; if(x>1e9) return 2e9; } sum*=sum; y>>=1; if(sum>1e9&&y) return 2e9; } return x; } void dfs1(long long x,long long y){ if(y>s) return ; if(x==n1+1&&y<=s){ sum[++cnt]=y; return ; } for(int i=1;y+f[x][i]<=s;++i) dfs1(x+1,y+f[x][i]); } void dfs2(long long x,long long y){ if(y>s) return ; if(x==n+1&&y<=s){ long long pos=upper_bound(sum+1,sum+cnt+1,s-y)-sum; while(pos>cnt||sum[pos]+y>s) --pos; ans+=pos; return ; } for(int i=1;y+f[x][i]<=s;++i) dfs2(x+1,y+f[x][i]); } int main(){ //freopen("seq.in","r",stdin); //freopen("seq.out","w",stdout); scanf("%lld%lld",&n,&s); for(int i=1;i<=n;++i) scanf("%lld",&a[i]); sort(a+1,a+n+1,cmp); for(int i=1;i<=n;++i) for(int j=1;j<=35;++j) f[i][j]=fast_mul(a[i],j); n1=(1+n)>>1; dfs1(1,0); sort(sum+1,sum+cnt+1); dfs2(n1+1,0); printf("%lld\n",ans); fclose(stdin);fclose(stdout); return 0; }
# T3 虚空终端(terminal)
我们将生论派看作 0 号节点，名论派看作 $n+1$ 号节点。容易发现答案只有四种情况：
只有$1$~$n$号节点的最小生成树；
只有$0$~$n$号节点的最小生成树；
只有$1$~$n+1$号节点的最小生成树；
有$0$~$n+1$号节点的最小生成树
分别按照上述四种情况连边，然后跑四次最小生成树，答案就是四次最小生成树的最小值。
$code:$
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; long long n,m,tot,x[500005],y[500005],a[500005],b[500005],z[500005],fa[500005],ans,sum,cnt; struct node{ long long u,v,w; } e[1000005]; bool cmp(node a,node b){ return a.w<b.w; } long long _find(long long x){ if(fa[x]==x) return x; return fa[x]=_find(fa[x]); } void f(long long edge){ sort(e+1,e+tot+1,cmp); for(int i=0;i<=n+1;++i) fa[i]=i; sum=cnt=0; for(int i=1;i<=tot;++i){ long long a=_find(e[i].u),b=_find(e[i].v); if(a!=b){ fa[a]=b;++cnt;sum+=e[i].w; } if(cnt>=edge) break; } if(cnt==edge) ans=min(ans,sum); } int main(){ //freopen("terminal.in","r",stdin); //freopen("terminal.out","w",stdout); scanf("%lld%lld",&n,&m); ans=1e18; for(int i=1;i<=n;++i) scanf("%lld",&x[i]); for(int i=1;i<=n;++i) scanf("%lld",&y[i]); for(int i=1;i<=m;++i){ scanf("%lld%lld%lld",&a[i],&b[i],&z[i]); e[++tot].u=a[i],e[tot].v=b[i],e[tot].w=z[i]; } f(n-1); tot=0; for(int i=1;i<=m;++i) e[++tot].u=a[i],e[tot].v=b[i],e[tot].w=z[i]; for(int i=1;i<=n;++i) e[++tot].u=0,e[tot].v=i,e[tot].w=x[i]; f(n); tot=0; for(int i=1;i<=m;++i) e[++tot].u=a[i],e[tot].v=b[i],e[tot].w=z[i]; for(int i=1;i<=n;++i) e[++tot].u=n+1,e[tot].v=i,e[tot].w=y[i]; f(n); tot=0; for(int i=1;i<=m;++i) e[++tot].u=a[i],e[tot].v=b[i],e[tot].w=z[i]; for(int i=1;i<=n;++i){ e[++tot].u=0,e[tot].v=i,e[tot].w=x[i]; e[++tot].u=n+1,e[tot].v=i,e[tot].w=y[i]; } f(n+1); printf("%lld\n",ans); fclose(stdin);fclose(stdout); return 0; }