編程筆記|藍橋杯模擬賽收獲（5-7題）
本文非原創(chuàng)侍芝，僅為個人的學(xué)習(xí)筆記研铆，借鑒了一些文章鏈接如下。
2020年藍橋杯模擬賽解題報告（CPP版本)
C++ 中string.find() 函數(shù)的用法總結(jié)
C++ getline函數(shù)用法詳解
C++ 定義數(shù)組 傳遞數(shù)組
此外還有一本書《c++語言程序設(shè)計(第四版)》（鄭莉州叠，董淵）
第五題
一個正整數(shù)如果任何一個數(shù)位不大于右邊相鄰的數(shù)位蚜印，則稱為一個數(shù)位遞增的數(shù)，例如1135是一個數(shù)位遞增的數(shù)留量，而1024不是一個數(shù)位遞增的數(shù)窄赋。
給定正整數(shù) n，請問在整數(shù) 1 至 n 中有多少個數(shù)位遞增的數(shù)楼熄？
代碼：
#include <iostream>
#include <cstring>
void work();
using namespace std;
int main() {
while (1)//死循環(huán)為測試用
work();
return 0;
}
void work() {
int n;
cin >> n;
int ans = 0;
for (int i = 1; i <= n; ++i) {
char s[8];
sprintf(s, "%d", i);
bool flag = 1;
for (int j = 1; j < strlen(s); ++j) {
if (s[j - 1] > s[j]) {
flag = 0;
break;
}
}
if (flag)
ans++;
}
cout << ans << endl;
}
分析：
這道題我應(yīng)該寫出來了忆绰，但是老師的代碼肯定好一些，畢竟用了我不會用的sprintf函數(shù)可岂。
第六題
在數(shù)列 a[1], a[2], …, a[n] 中错敢，如果對于下標(biāo) i, j, k 滿足 0<i<j<k<n+1 且 a[i]<a[j]<a[k]，則稱 a[i], a[j], a[k] 為一組遞增三元組缕粹，a[j]為遞增三元組的中心稚茅。
給定一個數(shù)列，請問數(shù)列中有多少個元素可能是遞增三元組的中心平斩。
分析:
這題我應(yīng)該也做對了亚享，我是用c語言編寫的，因為我連c++的數(shù)組都沒怎么學(xué)過绘面。欺税。侈沪。老師這里用c++，我可以學(xué)習(xí)晚凿。
具體思路：
就是向前遍歷找到一個比此數(shù)小的一個數(shù)亭罪，向后遍歷，找到一個比他大的歼秽。通過分析復(fù)雜度應(yīng)為应役，因為測試數(shù)據(jù)最大是1000，所以能在一秒之內(nèi)解決戰(zhàn)斗燥筷。箩祥。。
照抄老師原話荆责，我比賽的時候從沒想過滥比，會不會時間不夠
代碼：
#include <iostream>
void work();
using namespace std;
int main() {
while(1)//死循環(huán)為測試用
work();
return 0;
}
void work() {
int n, ans = 0;
cin >> n;
int *data = new int[n];
for (int i = 0; i < n; ++i) {
cin>>data[i];
}
for (int j = 1; j < n-1; ++j) {
int hasSmall=0;
for (int i = 0; i <j ; ++i) {
if(data[i]<data[j]){
hasSmall=1;
break;
}
}
int hasBig=0;
for (int k = j+1; k < n; ++k) {
if(data[j]<data[k]){
hasBig = 1;
break;
}
}
if(hasSmall&&hasBig)
ans++;
}
cout << ans << endl;
delete[] data;
}
數(shù)組定義
1.靜態(tài)分配
int array[10];
2.動態(tài)分配
- c語言
//定義
int arraysize;//元素個數(shù)
printf("請輸入數(shù)組的大小：");
scanf("%d",&arraysize);
int *array;//指針指向數(shù)組
array=(int *)malloc(arraysize *sizeof(int));//動態(tài)內(nèi)存分配
//釋放
free(array);
- c++
一維：
//定義
int arraysize;//元素個數(shù)
cout<<"請輸入數(shù)組的大凶鲈骸：";
cin>>arraysize;
int *array;//指針指向數(shù)組
array=new int[arraysize]; //動態(tài)內(nèi)存分配
//釋放
delete []array;
最好釋放盲泛，但是不釋放也沒什么關(guān)系，他在結(jié)束之后不會占用內(nèi)存键耕，網(wǎng)上是這么說的寺滚。
二維：
//定義
cin>>row >>col ;
int **p2 ;
p2 = new int*[row] ;
for( i = 0 ; i < row ; i ++ )
p2[i] = new int[col] ;
//釋放二維數(shù)組
for( i = 0 ; i < row ; i ++ )
delete []p2[i] ;
delete []p2 ;
三維：
參考二維，而且你暫時也用不到啊屈雄。
第七題
小明對類似于 hello 這種單詞非常感興趣村视，這種單詞可以正好分為四段，第一段由一個或多個輔音字母組成酒奶，第二段由一個或多個元音字母組成蚁孔，第三段由一個或多個輔音字母組成，第四段由一個或多個元音字母組成惋嚎。
給定一個單詞杠氢，請判斷這個單詞是否也是這種單詞，如果是請輸出yes另伍，否則請輸出no鼻百。
元音字母包括 a, e, i, o, u，共五個摆尝，其他均為輔音字母温艇。
分析：
找到第一個元音的下標(biāo)index1，必須大于0堕汞，且能找到
沿著index1繼續(xù)找下一個非元音得到index2勺爱，必須能找到
沿著index2繼續(xù)找下一個元音得到index3，必須能找到
最后判斷index3-1位置的字符應(yīng)該是從后往前第一個非元音（因為index3及以后的字符都必須是元音了）
拿hello舉例子
第一個元音為e臼朗，如果e的index為零邻寿，說明前面沒有輔音串蝎土，所以退出
如果不為零视哑，繼續(xù)找找到下一個非元音位置绣否，這個index應(yīng)該是這個字
符串的第三段位置了，再找下一個元音挡毅，得到的index蒜撮，應(yīng)該是逆序找
的第一個輔音，因為如果滿足的話“輔元輔元”倒過來是“元輔元輔”跪呈。
到這里我只能說一句妙啊段磨。
代碼：
#include <iostream>
int work();
using namespace std;
int main() {
while (1) { //死循環(huán)是為了測試
if (work())
cout << "yes" << endl;
else
cout << "no" << endl;
}
return 0;
}
int work() {
string word;
const string yuan = "aeiou";
getline(cin, word);
if (word.size() < 4)
return 0;
//第一個元音字符的pos
int index1 = word.find_first_of(yuan, 0);
if (index1 == 0 || index1 == string::npos) {
return 0;
}
//之后第一個非元音
int index2 = word.find_first_not_of(yuan, index1 + 1);
if (index2 == word.size() - 1 || index2 == string::npos) {
return 0;
}
//之后第一個元音
int index3 = word.find_first_of(yuan, index2 + 1);
if (index3 == string::npos) {
return 0;
}
if (index3 - 1 != word.find_last_not_of(yuan)) {
return 0;
}
return 1;
}
- getline()
c++中的cin雖然有其簡潔的優(yōu)點，但也不能用的時候：
當(dāng) cin 讀取數(shù)據(jù)時耗绿，它會傳遞并忽略任何前導(dǎo)白色空格字符（空格苹支、制表符或換行符）。一旦它接觸到第一個非空格字符即開始閱讀误阻，當(dāng)它讀取到下一個空白字符時债蜜，它將停止讀取。
下面的語句將為你的理解帶來幫助究反。
// This program illustrates a problem that can occur if
// cin is used to read character data into a string object.
#include <iostream>
#include <string> // Header file needed to use string objects
using namespace std;
int main()
{
string name;
string city;
cout << "Please enter your name: ";
cin >> name;
cout << "Enter the city you live in: ";
cin >> city;
cout << "Hello, " << name << endl;
cout << "You live in " << city << endl;
return 0;
}
運行結(jié)果是這樣的：
Please enter your name： John Doe
Enter the city you live in: Hello, John
You live in Doe
為什么在Enter the city you live in的時候你輸入都沒輸入就已經(jīng)跳到下一行語句了呢寻定？
因為上次cin讀入的終點在你的John的后面，在cin第二次出現(xiàn)時精耐，他就從那個地方再開始讀后面的Doe\n狼速。這是我根據(jù)結(jié)果進行的猜測，不知道對不對卦停，
為了解決這個問題向胡，可以使用一個叫做 getline 的 C++ 函數(shù)。此函數(shù)可讀取整行惊完，包括前導(dǎo)和嵌入的空格僵芹，并將其存儲在字符串對象中。
getline 函數(shù)如下所示：
getline(cin,inputline)
inputline是你想輸入的string型的變量名
這個函數(shù)可以完美的解決之前的問題专执。
其次參考程序用到的函數(shù)有
| 函數(shù)名 |
|---|
| string.size() |
| string.find_first_of() |
| string.find_first_not_of() |
| string.find_last_of() |
| string.find_last_not_of() |
此外還有string.rfind()函數(shù)返回的是從右向左查找的序數(shù)淮捆。
注意
string.find 和以上函數(shù)表中的函數(shù)有一點本質(zhì)區(qū)別：
下面舉一例說明：
-
如果string sub = ”abc“；
string s = ”cdeabcigld“本股；s.find(sub) , s.rfind(sub) 這兩個函數(shù)攀痊，如果完全匹配，才返回匹配的索引,即：當(dāng)s中含有abc三個連續(xù)的字母時拄显，才返回當(dāng)前索引苟径。
s.find_first_of(sub), s.find_first_not_of(sub), s.find_last_of(sub), s.find_last_not_of(sub) 這四個函數(shù)，查找s中含有sub中任意字母的索引躬审。
如果沒有查詢到棘街，則返回string：：npos蟆盐，這是一個很大的數(shù)，其值不需要知道遭殉。
下面是另一種關(guān)于此題的解法（非常有意思）
就是把找到的元音換成1石挂，非元音換成零。
舉個符合序列的例子：
hhhaaaakkkkiii
這個序列將被轉(zhuǎn)化為：
00011110000111
此種序列一定符合的規(guī)律：
- 以0開頭1結(jié)尾
- 其中變換次數(shù)為三次(不能多不能少)
但是怎樣將第二條轉(zhuǎn)化為數(shù)學(xué)語言呢险污？
對于任意i>=0&s[i]與s[i+1]相加的結(jié)果為1痹愚，這樣的i有三個。
代碼如下：
#include <iostream>
int work();
using namespace std;
int main() {
while (1) { //死循環(huán)是為了測試
if (work())
cout << "yes" << endl;
else
cout << "no" << endl;
}
return 0;
}
inline bool isYuan(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
int work() {
string word;
getline(cin, word);
unsigned long size = word.size();
if (size < 4)
return 0;
if (isYuan(word[0]) || !isYuan(word[size - 1]))
return 0;
int *h = new int[size];
for (int i = 0; i < size; ++i) {
if (isYuan(word[i]))
h[i]=1;
else
h[i]=0;
}
int cnt=0;
for (int i = 1; i < size; ++i) {
if (h[i-1]+h[i]==1)cnt++;
}
delete[]h;
return cnt==3;
}
需要注意蛔糯，這里又有一個c++的知識點：
內(nèi)聯(lián)函數(shù)：
函數(shù)的運用可以提高程序的運行效率拯腮，但是某些函數(shù)反復(fù)調(diào)用也會影響運行效率，對于某些函數(shù)本身很簡單蚁飒，規(guī)模小有使用頻繁的可以使用內(nèi)聯(lián)函數(shù)动壤。內(nèi)聯(lián)函數(shù)不是在調(diào)用時發(fā)生控制轉(zhuǎn)移而是在編譯時將函數(shù)體嵌入每一個掉用處，所以不浪費運行時間淮逻。特別對藍橋杯這種限制了時間的競賽來講琼懊。但是對于復(fù)雜的函數(shù)使用內(nèi)聯(lián)函數(shù)，則會使函數(shù)膨脹弦蹂，怎大開銷肩碟。
