问题 L: 鸭子唱歌
Contest2816 - 2021個人訓練賽第10場
問題 L: 鴨子唱歌
題目描述
小明的樓下出現了許多鴨子，一開始只有一只鴨子在唱歌，“quack……quack……quack……”，小明覺得還挺好聽的。緊接著，所有鴨子都一起唱了起來。小明開始厭煩了，他想要知道到底有多少只鴨子在他家樓下。
由于鴨子們邊唱邊跳，小明數著數著就數不清楚了。因此他想到了一個辦法，把鴨子的聲音錄下來，用計算機來進行分析。一只鴨子發出的聲音，只能是“quack”唱完整的一遍或者連續多遍，但是不同鴨子的聲音會疊加，同一個微小的時刻就只有1只鴨子發出一個聲音。例如：“ququaackck”就是由兩只鴨子的聲音疊加而成的，第一只是“qu___ack”,第二只是“qua___ck”；又例如，“quackquack”這段聲音，可能是1只鴨子，也可能是2只鴨子發出的。如果小明獲取的聲音是類似“quakc”不是由“quack”重復構成，或者只是其中一部分，這樣的聲音就是不規則，無效的。
現在，小明記錄下了一段時間內鴨子的聲音，問，這段聲音中最少包含多少只鴨子？
輸入
輸入只有一行，一個字符串表示鴨子的聲音。字符串中只包含“q”，“u”，“a”，“c”，“k”這5種小寫字母。
輸出
輸出最少包含鴨子數量。若小明的聲音錄制無效，輸出-1。
樣例輸入 Copy
【樣例1】
quqacukqauackck
【樣例2】
quackquakc
【樣例3】
qqqqqqqqqquuuuuuuuuuaaaaaaaaaacccccccccckkkkkkkkkk
樣例輸出 Copy
【樣例1】
2
【樣例2】
-1
【樣例3】
10
提示
樣例1解釋
鴨子1：qu_ac_kq_uack
鴨子2：__q__u__a____ck
聲音最少由2只鴨子構成，第一只鴨子唱了2遍，第二只鴨子唱了一遍。
樣例2解釋
不規則序列，不能由“quack”構成
【數據范圍】
30%的數據，鴨子的聲音長度不超過200
70%的數據，鴨子的聲音長度不超過1000
100%的數據，鴨子的聲音長度不超過2500
題目解析：一只鴨子叫它必然是按順序的排列，當出現第二只鴨子時就會有字母穿插在之中間。
解法：找出連續的quack，當中間出現不同的字母開新的空間存儲，如果出現的不能成為新的鴨子叫就不能組成輸出-1，同時不能組完全的也不行輸出-1，最后結果輸出新開空間數就是鴨子個數。
#include<iostream> using namespace std; char a[10000],c[10000]; int main() {int i,t=0,f,j;cin>>a;for(i=0;a[i];i++)//按順序判斷每一個字母{f=0;//用來判斷是否被放入數組中for(j=0;j<t;j++){if(a[i]=='q'&&c[j]=='k'){f=1;c[j]='q';break;}else if(a[i]=='u'&&c[j]=='q'){f=1;c[j]='u';break;}else if(a[i]=='a'&&c[j]=='u'){f=1;c[j]='a';break;}else if(a[i]=='c'&&c[j]=='a'){f=1;c[j]='c';break;}else if(a[i]=='k'&&c[j]=='c'){f=1;c[j]='k';break;}}if(f==0&&a[i]=='q')//只有位q時才能開新的空間{c[t++]='q';}else if(f==0)//需要開空間但是不是q就不成立{cout<<-1;return 0;}}for(i=0;i<t;i++)//判斷每一個是否都能完整組成quack{if(c[i]!='k'){cout<<-1;return 0;}}cout<<t;return 0;}總結
以上是生活随笔為你收集整理的问题 L: 鸭子唱歌的全部內容，希望文章能夠幫你解決所遇到的問題。
