[DMY]2024 CSP-S 模拟赛 Day 9

T2 调了 1h 没调出来，丢了一坨没分的shi扔了。

我想放一下作为开头：

include <bits/stdc++.h> #define int long long using namespace std; inline int read() { int w=1,s=0;char ch=getchar(); while(!isdigit(ch)){if(ch'-')w=-1;ch=getchar();} while(isdigit(ch)){s=s10+(ch-'0');ch=getchar();} return ws; } const int mod=998244353; const int maxn=3e3+10; const int inf=1e9+7; int n,m; char a[maxn][maxn]; bool hang[maxn],lie[maxn]; bool f[maxn][maxn]; map<string,int> mp; int dfs() { bool can=1; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!f[i][j]){can=0;break;} if(can){return 0;} string s; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) { if(f[i][j])s=s+'W'; else s=s+a[i][j]; } if(mp[s])return mp[s]; vector hangr,hangb,lier,lieb; for(int i=1;i<=n;i++) { if(hang[i])continue; bool r=1; for(int j=1;j<=m;j++)if(a[i][j]'B'&&!f[i][j]){r=0;break;} if(r)hangr.push_back(i); } for(int i=1;i<=n;i++) { if(hang[i])continue; bool b=1; for(int j=1;j<=m;j++)if(a[i][j]'R'&&!f[i][j]){b=0;break;} if(b)hangb.push_back(i); } for(int i=1;i<=m;i++) { if(lie[i])continue; bool r=1; for(int j=1;j<=n;j++)if(a[j][i]'B'&&!f[j][i]){r=0;break;} if(r)lier.push_back(i); } for(int i=1;i<=m;i++) { if(lie[i])continue; bool b=1; for(int j=1;j<=n;j++)if(a[j][i]'R'&&!f[j][i]){b=0;break;} if(b)lieb.push_back(i); } int res=inf; for(auto i : hangr) { for(int j=1;j<=m;j++) { f[i][j]=1; } hang[i]=1; res=min(res,dfs()+1); for(int j=1;j<=m;j++) { f[i][j]=0; } hang[i]=0; } for(auto i : hangb) { for(int j=1;j<=m;j++) { f[i][j]=1; } hang[i]=1; res=min(res,dfs()+1); for(int j=1;j<=m;j++) { f[i][j]=0; } hang[i]=0; } for(auto i : lier) { for(int j=1;j<=n;j++) { f[j][i]=1; } lie[i]=1; res=min(res,dfs()+1); for(int j=1;j<=n;j++) { f[j][i]=0; } lie[i]=0; } for(auto i : lieb) { for(int j=1;j<=n;j++) { f[j][i]=1; } lie[i]=1; res=min(res,dfs()+1); for(int j=1;j<=n;j++) { f[j][i]=0; } lie[i]=0; } return mp[s]=res; } void Sub1() { int ans=inf; mp.clear(); for(int i=1;i<=n;i++)hang[i]=0; for(int j=1;j<=m;j++)lie[j]=0; for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)f[i][j]=0; ans=dfs(); printf("%lld\n",(ansinf?-1:ans)); } void Main() { n=read(),m=read(); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>a[i][j]; } } bool f=0; for(int i=1;i<=n;i++){bool ff=1;for(int j=2;j<=m;j++)if(a[i][j]!=a[i][j-1]){ff=0;break;}if(ff)f=1;break;} for(int i=2;i<=m;i++){bool ff=1;for(int j=1;j<=n;j++)if(a[j][i]!=a[j][i-1]){ff=0;break;}if(ff)f=1;break;} if(!f){puts("-1");return ;} Sub1(); } signed main() { #ifdef Lydic freopen(".in", "r", stdin); freopen(".out", "w", stdout); // #else // freopen("mst.in", "r", stdin); // freopen("mst.out", "w", stdout); #endif int T=read(); while(T--)Main(); return 0; }

好了，开始写总结。

赛时

T1 刚刚看出来 \(\mathcal{O}(n^2)\) 的 DP，就发现 AKIG 叕 AK 了,我大惊。

写出来以后发现没挂，于是开始考虑优化。但是我傻傻的一直盯着 DP 的内层循环优化，丝毫没发现这东西能直接找规律构造。

然后最终得分 60pts。

T2 的话看不出来什么东西，想先写一下暴力，然后就有了上面的一大坨东西。

T3 的话感觉是一个很可做的数据结构计数问题，然后纸上推推画画就莫名其妙过掉了大样例。赛时感觉比 T1 简单。（我猜某鸡不会看这篇文章，所以在这里口嗨一下：\(\Large \color{red}{菜}\)）

T4 看了一眼，感觉 T2 的分可以拿到，所以决定死盯 T2，然后到最后也没盯出来，使得最基本的暴力分数也没拿到。

赛后

发现我是为数不多过 T3 但是没过 T1 的人，我太菜了。

一听别人的思路就会 T1 了，花了不到 5min 就过了。我更菜了。

现在在订 T2，努力在下个国庆节日期是完全平方数之前订出来（3026.10.01）。

最近的比赛时间不够的问题逐渐显现出来，不知道说明了什么。

写完了，溜了。