纪念死去的智商（虽然本来就没有吧……）
三重循环枚举将哪三个fix string作为数字、字母和符号位。记下最小的值就行了。
预处理之后这个做法应该是O(n^3)的，当然完全足够。不预处理是O(n^3*m)的，也够。
我写了一个O(n^2+n*m)的分类讨论贪心做法……蜜汁错，容我查一下。
现在查出个错，交了一下在in queue……容我明天看看对不对。
如果对的话，这题的加强版今年留作趣味赛题吧，嘿嘿嘿……
UPDATE：果然过了……我就是傻逼
#include#include using namespace std;int n,m;char a[55][55];int dis[55][4],type[55];int main(){// freopen("c.in","r",stdin); scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%s",a[i]+1); for(int i=1;i<=n;++i) { if(a[i][1]>='a' && a[i][1]<='z') type[i]=1; else if(a[i][1]>='0' && a[i][1]<='9') type[i]=2; else type[i]=3; dis[i][1]=dis[i][2]=dis[i][3]=10000000; for(int j=2;j<=m;++j) if(a[i][j]>='a' && a[i][j]<='z') { if(type[i]!=1) dis[i][1]=min(dis[i][1],min(j-1,m-j+1)); } else if(a[i][j]>='0' && a[i][j]<='9') { if(type[i]!=2) dis[i][2]=min(dis[i][2],min(j-1,m-j+1)); } else if(type[i]!=3) dis[i][3]=min(dis[i][3],min(j-1,m-j+1)); } bool flag=1; for(int i=1;i<=n;++i) if(type[i]!=1) { flag=0; break; } if(flag) { int ans=10000000; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(i!=j) ans=min(ans,dis[i][2]+dis[j][3]); printf("%d\n",ans); return 0; } flag=1; for(int i=1;i<=n;++i) if(type[i]!=2) { flag=0; break; } if(flag) { int ans=10000000; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(i!=j) ans=min(ans,dis[i][1]+dis[j][3]); printf("%d\n",ans); return 0; } flag=1; for(int i=1;i<=n;++i) if(type[i]!=3) { flag=0; break; } if(flag) { int ans=10000000; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(i!=j) ans=min(ans,dis[i][1]+dis[j][2]); printf("%d\n",ans); return 0; } flag=1; for(int i=1;i<=n;++i) if(type[i]==1) { flag=0; break; } if(flag) { int ans=10000000; int cnt[4]={0}; for(int i=1;i<=n;++i) ++cnt[type[i]]; if(cnt[2]==1) { int id; for(int i=1;i<=n;++i) if(type[i]==2) { id=i; break; } for(int i=1;i<=n;++i) if(type[i]==3) ans=min(ans,dis[i][1]); int tmp=10000000; for(int i=1;i<=n;++i) if(type[i]==3) tmp=min(tmp,dis[i][2]); ans=min(ans,tmp+dis[id][1]); } else if(cnt[3]==1) { int id; for(int i=1;i<=n;++i) if(type[i]==3) { id=i; break; } for(int i=1;i<=n;++i) if(type[i]==2) ans=min(ans,dis[i][1]); int tmp=10000000; for(int i=1;i<=n;++i) if(type[i]==2) tmp=min(tmp,dis[i][3]); ans=min(ans,tmp+dis[id][1]); } else { for(int i=1;i<=n;++i) ans=min(ans,dis[i][1]); } printf("%d\n",ans); return 0; } flag=1; for(int i=1;i<=n;++i) if(type[i]==2) { flag=0; break; } if(flag) { int ans=10000000; int cnt[4]={0}; for(int i=1;i<=n;++i) ++cnt[type[i]]; if(cnt[1]==1) { int id; for(int i=1;i<=n;++i) if(type[i]==1) { id=i; break; } for(int i=1;i<=n;++i) if(type[i]==3) ans=min(ans,dis[i][2]); int tmp=10000000; for(int i=1;i<=n;++i) if(type[i]==3) tmp=min(tmp,dis[i][1]); ans=min(ans,tmp+dis[id][2]); } else if(cnt[3]==1) { int id; for(int i=1;i<=n;++i) if(type[i]==3) { id=i; break; } for(int i=1;i<=n;++i) if(type[i]==1) ans=min(ans,dis[i][2]); int tmp=10000000; for(int i=1;i<=n;++i) if(type[i]==1) tmp=min(tmp,dis[i][3]); ans=min(ans,tmp+dis[id][2]); } else { for(int i=1;i<=n;++i) ans=min(ans,dis[i][2]); } printf("%d\n",ans); return 0; } flag=1; for(int i=1;i<=n;++i) if(type[i]==3) { flag=0; break; } if(flag) { int ans=10000000; int cnt[4]={0}; for(int i=1;i<=n;++i) ++cnt[type[i]]; if(cnt[1]==1) { int id; for(int i=1;i<=n;++i) if(type[i]==1) { id=i; break; } for(int i=1;i<=n;++i) if(type[i]==2) ans=min(ans,dis[i][3]); int tmp=10000000; for(int i=1;i<=n;++i) if(type[i]==2) tmp=min(tmp,dis[i][1]); ans=min(ans,tmp+dis[id][3]); } else if(cnt[2]==1) { int id; for(int i=1;i<=n;++i) if(type[i]==2) { id=i; break; } for(int i=1;i<=n;++i) if(type[i]==1) ans=min(ans,dis[i][3]); int tmp=10000000; for(int i=1;i<=n;++i) if(type[i]==1) tmp=min(tmp,dis[i][2]); ans=min(ans,tmp+dis[id][3]); } else { for(int i=1;i<=n;++i) ans=min(ans,dis[i][3]); } printf("%d\n",ans); return 0; } puts("0"); return 0;}