#P3090. 数大雁(100分)
-
1000ms
Tried: 258
Accepted: 52
Difficulty: 3
所属公司 :
华为od
数大雁(100分)
模拟
该题目的目标是通过模拟大雁的叫声来找出所需的最少大雁数量.观察到字符串的长度只有1000(最多200*'quack'),考虑暴力模拟,枚举第几只大雁,用指针遍历叫声顺带vis数组标记(一只大雁可能循环的quackquack....)已经被使用过,所以尽可能的打上凑更多的完整叫声直到无法完整的凑出'quack'输出答案即可
代码如下
cpp
#include <bits/stdc++.h>
using namespace std;
#define N 100005
char dx[5]={'q','u','a','c','k'};
int vis[N];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
string s;
cin>>s;
int n=s.length();
s=' '+s;
int ans=0;
for(int i=1;i<=n;i++){
int boo=0;
int now=0;
for(int j=1;j<=n;j++){
if(dx[now]==s[j]&&vis[j]==0){
vis[j]=1;
if(now==4) boo=1;
now++;
now%=5;
}
}
if(boo==0) break;
ans++;
}
cout<<ans<<'\n';
return 0;
}
python
dx = ['q', 'u', 'a', 'c', 'k']
s = input().strip()
n = len(s)
vis = [0] * (n + 1)
ans = 0
while True:
boo = 0
now = 0
for j in range(n):
if dx[now] == s[j] and vis[j] == 0:
vis[j] = 1
if now == 4:
boo = 1
now += 1
now %= 5
if boo == 0:
break
ans += 1
# 如果没有匹配到任何一个完整的 "quack",返回 -1,否则返回找到的 "quack" 的数量
if ans == 0:
print(-1)
else:
print(ans)
java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
char[] dx = {'q', 'u', 'a', 'c', 'k'};
String s = sc.nextLine();
int n = s.length();
int[] vis = new int[n];
int ans = 0;
while (true) {
int boo = 0;
int now = 0;
for (int j = 0; j < n; j++) {
if (dx[now] == s.charAt(j) && vis[j] == 0) {
vis[j] = 1;
if (now == 4) {
boo = 1;
}
now++;
now %= 5;
}
}
if (boo == 0) {
break;
}
ans++;
}
// 如果没有找到任何 "quack",输出 -1,否则输出找到的 "quack" 数量
if (ans == 0) {
System.out.println(-1);
} else {
System.out.println(ans);
}
sc.close();
}
}
题目描述
一群大雁往南飞,给定一个字符串记录地面上的游客听到的大雁叫声,请给出叫声最少由几只大雁发出。
具体的:
1.大雁发出的完整叫声为”quack“,因为有多只大雁同一时间嘎嘎作响,所以字符串中可能会混合多个”quack”。
2.大雁会依次完整发出”quack”,即字符串中’q’ ,‘u’, ‘a’, ‘c’, ‘k’ 这5个字母按顺序完整存在才能计数为一只大雁。如果不完整或者没有按顺序则不予计数。
3.如果字符串不是由’q’, ‘u’, ‘a’, ‘c’, ‘k’ 字符组合而成,或者没有找到一只大雁,请返回−1。
输入描述
一个字符串,包含大雁quack的叫声。1≤字符串长度≤1000,字符串中的字符只有’q’, ‘u’, ‘a’, ‘c’, ‘k’。
输出描述
大雁的数量
样例1
输入
qucakquack
输出
1
样例2
输入
qaauucqckk
输出
-1
样例3
输入
quacqkuac
输出
1
样例4
输入
qququaauqccauqkkcauqqkcauuqkcaaukccakkck
输出
5