题解：UVA13257 License Plates

_fallen_leaves_ · 2025-08-21 20:42:50 · 题解

UVA13257 License Plates

::::info[题意]{close} 给你 T 个字符串，每个字符串为 S_i，要在 S_i 中找长度为 3 的不同字符串（ 3 个字符可以不连续）的个数。 ::::

::::info[暴力思路]{close} 依次枚举用 3 个标记变量标记每一位，用 1 个桶，存储每一个出现的字符串，如果之前没有出现，字符串的可能性 +1。

#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 出现过了，表示开头的字符串，已经被标记了。

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

#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;
}