模拟

该题目的目标是通过模拟大雁的叫声来找出所需的最少大雁数量.$\\$观察到字符串的长度只有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