UVA13257 License Plates题解

思路

一看题面，我先写了一发暴力，复杂度：

O(n^3logn)

。想着 set 自去重这么好用然后：

CPP

#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)

。

代码实现

CPP

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

UVA13257 License Plates题解

文章操作

思路

代码实现

相关推荐

评论

UVA13257 License Plates题解