题解：P14317 「ALFR Round 11」A 浴眼盯真 (dingzhen)

思路

考虑用桶记录，细节看代码。

这里重点讲代码第 20 行。

只需检查去掉第一个字符或去掉最后一个字符的

s

是否满足条件 1。

原因是若去掉第一个字符或去掉最后一个字符的

s

包含 26 个不同字母，则条件 2 成立。

若两者都不满足，则任何非自身子串都无法同时包含所有 26 个字母。

因为缺少的字母仅存在于字符串的首尾，非自身子串无法同时覆盖首尾。

所以判断

s

的第一个字母与最后一个字母是否都只出现一次即可。

时间复杂度

O(\sum n)

。

代码

CPP

#include<bits/stdc++.h>
#define endl "\n"
#define int long long
#define f(n) for(int i=1;i<=n;i++)
#define IOS cin.tie(0),cout.tie(0),ios::sync_with_stdio(0)
using namespace std;
int T,len,t[200],cnt;
string s;
bool if1(){
	cnt=0;//记录出现过几个字符
	for(int i='a';i<='z';i++)cnt+=(1&&t[i]);//若t[i]不是0，即s中存在字符i，cnt就+1 
	return (cnt==26);//若26个字母都有则返回1 
}
signed main(){
	IOS;cin>>T;
	while(T--){
		memset(t,0,sizeof(t));//多测未清空，害的作者2024CSP-J挂100pts 
		cin>>s,len=s.length(),s=" "+s;//获取字符串长度 
		f(len)t[s[i]]++;//用桶记录各个字符出现的次数 
		if(if1()&&(t[s[1]]!=1||t[s[len]]!=1))cout<<"Yes\n"; 
		else if(if1())cout<<"No\n2\n";//易得若满足2，必满足1
		else cout<<"No\n1 2\n";
	}
	return 0;
}

题解：P14317 「ALFR Round 11」A 浴眼盯真 (dingzhen)

文章操作

思路

代码

相关推荐

评论

题解：P14317 「ALFR Round 11」A 浴眼盯真 (dingzhen)