专栏文章

题解：UVA13257 License Plates

CChenxuhang_play
UVA13257题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio262fz
此快照首次捕获于
2025/12/02 12:08
3 个月前
此快照最后确认于
2025/12/02 12:08
3 个月前
查看原文

题目大意

在字符串 ss 中找长度为三的不同子串个数（可以不连续）。

思路

暴力肯定是过不了的，考虑使用其他方法。
可以发现在 ss 中，只包含 AA 至 ZZ 的字符，考虑设计 33 个桶：
桶 aa：若 xix_i 为真，表示以 xix_i 开头的子串已被统计
桶 bb：若 yi,jy_{i,j} 为真，表示以 yi,jy_{i,j} 开头的子串已被统计
桶 cc：若 zi,j,kz_{i,j,k} 为真，表示以 zi,j,kz_{i,j,k} 开头的子串已被统计
将上述桶放至循环内，可以大幅度优化时间复杂度，单组数据的时间复杂度约为 O(263)O(26^3)。
整体程序的时间复杂度为 O(T×263)O(T\times 26^3)。

关键代码

CPP
for(int i=0;i<s.size();i++)
{
	if(!a[s[i]-'A'])
	{
        a[s[i]-'A'] = 1;
        for(int j=i+1;j<s.size();j++) 
        {
            if (!b[s[i]-'A'][s[j]-'A'])
			{
                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'])
					{
                        c[s[i]-'A'][s[j]-'A'][s[k]-'A']=1;
                        ans++;
                    }
				}
            }
		}           
    }
    cout<<ans<<endl;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...