UVA13257 License Plates题解

SP_beyond_xxxx · 2025-08-14 10:01:02 · 题解

思路

一看题面，我先写了一发暴力，复杂度：O(n^3logn)。想着 set 自去重这么好用然后：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    string s;
    while(n--){
        cin>>s;
        set<string>st;
        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++){
                    string a;
                    a.push_back(s[i]);
                    a.push_back(s[j]);
                    a.push_back(s[k]);
                    st.insert(a);
                }
            }
        }
        printf("%d\n",st.size());
    }
    return 0;
} 

TLE。

那么就想着优化吧。

注意题面：找长度为 3 的不同子串个数。

如果 s 中出现了 2 次及以上的同一个字符，那么算一次就够了，若 s_i 之前出现过 s_j = s_i 那么 s_i 后面的所有数一定已经被算过一遍直接判重即可。

那么我们可以在每层循环分别设计 1 个桶，表示 s_i 在此层循环中是否被计算过。被我们优化到了 O(n^3)。

代码实现

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    string s;
    while(n--){
        cin>>s;
        int ans=0;
        bool fi[110]={0};
        for(int i=0;i<s.size();i++){
            if(fi[s[i]]==1)continue;
            fi[s[i]]=1;
            bool fj[110]={0};
            for(int j=i+1;j<s.size();j++){
                if(fj[s[j]]==1)continue;
                fj[s[j]]=1;
                bool fk[110]={0};
                for(int k=j+1;k<s.size();k++){
                    if(fk[s[k]]==1)continue;
                    fk[s[k]]=1;
                    ans++;
                }
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}