CF 593A 2Char-蒲公英云

CF 593A 2Char

题目网址：http://codeforces.com/problemset/problem/593/A

题目大意：给定n个由小写字母组成的串，从中取任意个字符串拼成一封信，这封信中最多有两种字符，输出信的最大长度。

首先想到了用STL中的各种容器，统计每个字符串含有哪两种字符(或者一种)作为map的first，对应的second是这个字符串，有相同first的字符串合在一起。然后遍历map，对first进行分解得到两种长度为1的字符串，以这两个字符串为first，找出他们的second加到遍历map的second里，最后找出second长度最大的，就是最终结果了。但是还有一些细节问题，比如当n个字符串都为单一一种字符的时候，我都是进行了特判，感觉A的很勉强。后来我在网上查这道题才发现这是一道A题。。。。。。又看了别人的代码，才感觉自己将题目写复杂了，用数组会更方便清晰。

My Code：

#include<stdio.h>
#include<iostream>
#include<set>
#include<map>
#include<string>
using namespace std;
int main()
{
    map<string,string> ma;
    set<string> se;
    string str,str_t,s[101];
    int n,i,j,k,maxx;
    while(cin>>n)
    {
        maxx=0;
        ma.clear();
        for(i=0;i<=100;i++)
            s[i].clear();
        for(i=0,k=0;i<n;i++)
        {
            cin>>str;
            se.clear();
            for(j=0;j<str.size();j++)
            {
                string ttt;
                ttt+=str[j];
                se.insert(ttt);
            }
            if(se.size()>2)
                continue;
            str_t.clear();
            for(set<string>::iterator it=se.begin();it!=se.end();it++)
                str_t+=(*it);
            if(ma[str_t].size()>0)
                ma[str_t]+=str;
            else
            {
                ma[str_t]+=str;
                s[k++]=str_t;
            }    
        }
    //    for(i=0;i<k;i++)
        //    cout<<s[i]<<endl;
        int x=0,y=0,flag=0;
        for(i=0;i<k;i++)
        {
            if(s[i].size()==1)
            {
                if(ma[s[i]].size()>x)
                {
                    x=ma[s[i]].size();
                    flag=i;
                }
            }
        }
        for(i=0;i<k;i++)
        {
            if(s[i].size()==1)
            {
                if(ma[s[i]].size()>y&&i!=flag)
                {
                    y=ma[s[i]].size();
                }
                int num1=ma[s[i]].size();
                if(num1>maxx)
                    {maxx=ma[s[i]].size();}
            }
            else
            {
                string a,b;
                a+=s[i][0];
                b+=s[i][1];
                ma[s[i]]+=ma[a];
                ma[s[i]]+=ma[b];
                int num2=ma[s[i]].size();
                if(num2>maxx)
                    {maxx=ma[s[i]].size();}
            }
        }
        if(maxx>x+y)
            {cout<<maxx<<endl;}
        else
            {cout<<x+y<<endl;}
    }
    return 0;
}

Other Code：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char s[1005];
int  a[30][30];
int  vis[30];
bool cmp(int x,int y)
{
    return x>y;
}
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s",s);
        memset(vis,0,sizeof(vis));
        int len=strlen(s);
        int ans=0;
        int pos[3];
        memset(pos,-1,sizeof(pos));
        int i;
        for(i=0;i<len;i++)
        {
            if(!vis[s[i]-‘a‘])
            {
                vis[s[i]-‘a‘]=1;
                pos[ans++]=s[i]-‘a‘;
            }
            if(ans>2) break;
        }
        if(i==len) a[pos[0]+1][pos[1]+1]+=len;
    }
    int cnt=0;
    for(int i=1;i<27;i++)
        for(int j=i+1;j<27;j++)
        {
            int sum=0;
            sum+=a[i][j];
            sum+=a[j][i];
            sum+=a[i][0];
            sum+=a[j][0];
            cnt=max(sum,cnt);
        }
    cout<<cnt<<endl;
    return 0;
}