社区讨论

站内 P11451 7分求助 急！！！

aa_middle
题目总版参与者 1已保存回复 0

讨论操作

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

当前回复
0 条
当前快照
1 份
快照标识符
@m57votkt
此快照首次捕获于
2024/12/28 15:46
去年
此快照最后确认于
2025/11/04 12:15
4 个月前
查看原帖

[USACO24DEC] It's Mooin' Time B

题目描述

Farmer John 正在试图向 Elsie 描述他最喜欢的 USACO 竞赛，但她很难理解为什么他这么喜欢它。他说「竞赛中我最喜欢的部分是 Bessie 说 『现在是哞哞时间』并在整个竞赛中一直哞哞叫」。
Elsie 仍然不理解，所以 Farmer John 将竞赛以文本文件形式下载，并试图解释他的意思。竞赛被定义为一个长度为 NN（3≤N≤200003≤N≤20000）的小写字母字符串。一种哞叫一般地定义为子串 cicjcjc_ic_jc_j，其中某字符 cic_i 之后紧跟着 22 个某字符 cjc_j，且 ci≠cjc_i≠c_j。根据 Farmer John 的说法，Bessie 哞叫了很多，所以如果某种哞叫在竞赛中出现了至少 FF（1≤F≤N1≤F≤N）次，那可能就是 Bessie 发出的。
然而，Farmer John 的下载可能损坏，文本文件可能存在至多一个字符与原始文件不同。将可能的误差考虑在内，输出所有可能是 Bessie 发出的哞叫，按字典序顺序排序。

输入格式

输入的第一行包含 NN 和 FF，表示字符串的长度以及 Bessie 的哞叫的频次下限。
第二行包含一个长度为 NN 的小写字母字符串，表示竞赛。

输出格式

输出可能是 Bessie 发出的哞叫的数量，以下是按字典序排序的哞叫列表。每行输出一种哞叫。

样例 #1

样例输入 #1

CPP
10 2
zzmoozzmoo

样例输出 #1

CPP
1
moo

样例 #2

样例输入 #2

CPP
17 2
momoobaaaaaqqqcqq

样例输出 #2

CPP
3
aqq
baa
cqq

样例 #3

样例输入 #3

CPP
3 1
ooo

样例输出 #3

CPP
25
aoo
boo
coo
doo
eoo
foo
goo
hoo
ioo
joo
koo
loo
moo
noo
poo
qoo
roo
soo
too
uoo
voo
woo
xoo
yoo
zoo

提示

样例 #1 解释

在这个样例中，任何字符变化都不会影响答案。唯一 Bessie 可能发出的哞叫是 moo\tt{moo}。

样例 #2 解释

在这个样例中，位置 88（从零开始索引）的 a\tt{a} 可能是由 b\tt b 损坏导致的，这使得 baa\tt baa 成为一种 Bessie 发出两次的可能的哞叫。此外，位置 1111 的 q\tt q 可能是由 c\tt c 损坏导致的，这使得 cqq\tt cqq 成为一种 Bessie 可能的哞叫。aqq\tt aqq 可以通过将 c\tt c 换成 a\tt a 来达到。

测试点性质

  • 测试点 1-3：样例。
  • 测试点 4-8：N≤100N≤100。
  • 测试点 9-13：没有额外限制。
CPP
#include<bits/stdc++.h>
using namespace std;
int sum[4000007];
bool sk[4000007];
int n,m,ans;
char s[100005],p;
int main() {
	cin>>n>>m;
	scanf("%s",s+1);
	for(int i=1; i<=n; i++) {
		s[i]-='a';
	}
	for(int i=1; i<=n-2; i++) {
		if(s[i+1]==s[i+2]&&s[i+1]!=s[i]) {
			sum[s[i]*10000+s[i+1]*100+s[i+2]]++;
		}
	}
	for(int i=1; i<=400005; i++) {
		if(sum[i]>=m) {
			sk[i]=1;
		}
	}
	for(int i=1; i<=n; i++) {
		p=s[i];
		for(int j=0; j<26; j++) {
			s[i]=j;
			int a=sum[s[i-2]*10000+s[i-1]*100+s[i]],b=sum[s[i-1]*10000+s[i]*100+s[i+1]],c=sum[s[i]*10000+s[i+1]*100+s[i+2]];
			if(s[i-1]==p&&p!=s[i-2] && !(s[i-1]==s[i]&&s[i]!=s[i-2])) {
				sum[s[i-2]*10000+s[i-1]*100+s[i]]--;
			}else if(s[i-1]==s[i]&&s[i]!=s[i-2] && !(s[i-1]==p&&p!=s[i-2])) {
				sum[s[i-2]*10000+s[i-1]*100+s[i]]++;
			}
			if(p==s[i+1]&&p!=s[i-1] && !(s[i]==s[i+1]&&s[i]!=s[i-1])) {
				sum[s[i-1]*10000+s[i]*100+s[i+1]]--;
			}else if(s[i]==s[i+1]&&s[i+1]!=s[i-1] && !(p==s[i+1]&&p!=s[i-1])) {
				sum[s[i-1]*10000+s[i]*100+s[i+1]]++;
			}
			if(s[i+1]==s[i+2]&&s[i+2]!=p && !(s[i+1]==s[i+2]&&s[i+2]!=s[i])) {
				sum[s[i]*10000+s[i+1]*100+s[i+2]]--;
			}else if(s[i+1]==s[i+2]&&s[i+2]!=s[i] && !(s[i+1]==s[i+2]&&s[i+2]!=p)) {
				sum[s[i]*10000+s[i+1]*100+s[i+2]]++;
			}
			if(sum[s[i-2]*10000+s[i-1]*100+s[i]]>=m)sk[s[i-2]*10000+s[i-1]*100+s[i]]=1;
			if(sum[s[i-1]*10000+s[i]*100+s[i+1]]>=m)sk[s[i-1]*10000+s[i]*100+s[i+1]]=1;
			if(sum[s[i]*10000+s[i+1]*100+s[i+2]]>=m)sk[s[i]*10000+s[i+1]*100+s[i+2]]=1;
			sum[s[i-2]*10000+s[i-1]*100+s[i]]=a;
			sum[s[i-1]*10000+s[i]*100+s[i+1]]=b;
			sum[s[i]*10000+s[i+1]*100+s[i+2]]=c;
		}
		s[i]=p;
	}
	for(int i=1; i<=400005; i++) {
		if(sk[i]==1) {
			ans++;
		}
	}
	cout<<ans<<"\n";
	for(int i=1; i<=400005; i++) {
		if(sk[i]==1) {
			cout<<char(i/10000+'a')<<char(i/100%100+'a')<<char(i%100+'a')<<"\n";
		}
	}
	return 0;
}

回复

共 0 条回复，欢迎继续交流。

正在加载回复...