CF 593A 2Char

旧城等待， 2022-08-23 04:55 164阅读 0赞

题目网址：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;
    }