首页 > 代码库 > 【枚举】Codeforces Round #394 (Div. 2) C. Dasha and Password
【枚举】Codeforces Round #394 (Div. 2) C. Dasha and Password
纪念死去的智商（虽然本来就没有吧……）
三重循环枚举将哪三个fix string作为数字、字母和符号位。记下最小的值就行了。
预处理之后这个做法应该是O(n^3)的，当然完全足够。不预处理是O(n^3*m)的，也够。
我写了一个O(n^2+n*m)的分类讨论贪心做法……蜜汁错，容我查一下。
现在查出个错，交了一下在in queue……容我明天看看对不对。
如果对的话，这题的加强版明年留作趣味赛题吧，嘿嘿嘿……
#include<cstdio>
#include<algorithm>
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;
}
【枚举】Codeforces Round #394 (Div. 2) C. Dasha and Password
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。