T1
简单题，排序后直接枚举两个有画面格子之间的间隔数，即为可能节省的行数或列数，移动次数也易求。
点击查看代码
#include<bits/stdc++.h>
#define MAXN 500005
#define int long long
const int inf=1e18;
using namespace std;
int n,m,k,mina,minb,ansa,ansb,a[MAXN],b[MAXN];
signed main(){freopen("video.in","r",stdin);freopen("video.out","w",stdout);scanf("%lld%lld%lld",&n,&m,&k);for(int i=1;i<=k;i++){scanf("%lld%lld",&a[i],&b[i]);}sort(a+1,a+k+1);sort(b+1,b+k+1);mina=n-(a[1]-1)-(n-a[k]);ansa=0;for(int i=2;i<=k;i++){if(a[i]!=a[i-1]){int tmp=n-(a[i]-a[i-1]-1),tmpa=min(a[i-1],n-a[i]+1);//cout<<tmp<<' '<<tmpa<<"\n";if(tmp<mina||(tmp==mina&&tmpa<ansa)){mina=tmp,ansa=tmpa;}}}minb=m-(b[1]-1)-(m-b[k]);ansb=0;//cout<<minb<<"\n";for(int i=2;i<=k;i++){if(b[i]!=b[i-1]){int tmp=m-(b[i]-b[i-1]-1),tmpb=min(b[i-1],m-b[i]+1);if(tmp<minb||(tmp==minb&&tmpb<ansb)){minb=tmp,ansb=tmpb;}}}printf("%lld %lld\n",mina*minb,ansa+ansb);return 0;
}
T2
写了题解。
点击查看代码
#include<bits/stdc++.h>
#define MAXN 505
#define int long long
const int inf=1e18,mod=998244353;
using namespace std;
int n,m,fac[MAXN],ifac[MAXN],pre[MAXN],f[MAXN][MAXN],t[MAXN][MAXN],ans;
int fpow(int a,int b){int tans=1;while(b){if(b&1)tans=tans*a%mod;a=a*a%mod;b>>=1;}return tans;
}
void init(){fac[0]=ifac[0]=1;for(int i=1;i<=n;i++)fac[i]=fac[i-1]*i%mod,ifac[i]=ifac[i-1]*fpow(i,mod-2)%mod;
}
int C(int n,int m){return fac[n]*ifac[n-m]%mod*ifac[m]%mod;
}
signed main(){freopen("card.in","r",stdin);freopen("card.out","w",stdout);scanf("%lld%lld",&n,&m);t[0][0]=1;for(int i=1;i<=m;i++){for(int j=0;j*2<=i;j++){t[i][j]=t[i-1][j];if(j>0)t[i][j]=(t[i][j]+t[i-1][j-1])%mod;}}for(int i=0;i<=m;i+=2){pre[i]=t[m][(m-i)/2];//cout<<i<<' '<<pre[i]<<"\n";}f[1][0]=1;for(int i=2;i<=n;i++){for(int j=0;j<=m;j+=2){for(int k=0;k<=j;k+=2){f[i][j]=(f[i][j]+f[i-1][j-k]*pre[k]%mod)%mod;}}}for(int i=0;i<=m;i+=2){int sum=t[m][(m-i)/2]*f[n][i]%mod;ans=(ans+sum)%mod;}printf("%lld\n",ans);return 0;
}