题解：UVA13257 License Plates

题意

给你

T

个字符串，每个字符串为

S_i

，要在

S_i

中找长度为

3

的不同字符串（

3

个字符可以不连续）的个数。

暴力思路

依次枚举用

3

个标记变量标记每一位，用

1

个桶，存储每一个出现的字符串，如果之前没有出现，字符串的可能性

+1

。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,c[30][30][30];
string s;
signed main()
{
    cin>>t;
    while(t--)
	{
        cin>>s;
        int ans=0;
        memset(c,0,sizeof c);
        for(int i=0;i<s.size();i++) 
        {
            for(int j=i+1;j<s.size();j++)
            {
                for(int k=j+1;k<s.size();k++) 
                {
                	if(c[s[i]-'A'][s[j]-'A'][s[k]-'A']) continue;
                	c[s[i]-'A'][s[j]-'A'][s[k]-'A']=1;
                    ans++;
				}
            }      
		}
        cout<<ans<<endl;
    }
    return 0;
}

因为字符串长度较大，如果按上述方法，一定会超时。所以考虑开

3

个桶，分别开一维，二维，三维数组各一个。

如果 $a_i$ 出现过了，表示开头的字符串，已经被标记了，就不需要往下继续考虑了。
如果 ${b_i}_j$ 出现过了，表示开头的字符串，已经被标记了，就不需要往下继续考虑了。
如果 ${{c_i}_j}_k$ 出现过了，表示开头的字符串，已经被标记了。

这样可以使不需要浪费的时间收集起来，让代码速度变快。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,a[30],b[30][30],c[30][30][30];
string s;
signed main()
{
    cin>>t;
    while(t--)
	{
        cin>>s;
        int ans=0;
        memset(a,0,sizeof a);
        memset(b,0,sizeof b);
        memset(c,0,sizeof c);
        for(int i=0;i<s.size();i++) 
        {
        	if(a[s[i]-'A']) continue;
            a[s[i]-'A']=1;
            for(int j=i+1;j<s.size();j++)
            {
                if(b[s[i]-'A'][s[j]-'A']) continue;
				b[s[i]-'A'][s[j]-'A']=1;
                for(int k=j+1;k<s.size();k++) 
                {
                	if(c[s[i]-'A'][s[j]-'A'][s[k]-'A']) continue;
                	c[s[i]-'A'][s[j]-'A'][s[k]-'A']=1;
                    ans++;
				}
            }      
		}
        cout<<ans<<endl;
    }
    return 0;
}

题解：UVA13257 License Plates

文章操作

相关推荐

评论

题解：UVA13257 License Plates