【一】【算法分析與設計】基礎測試

排列式

題目描述

　　7254是一個不尋常的數，因為它可以表示為7254 = 39 x 186，這個式子中1~9每個數字正好出現一次

　　輸出所有這樣的不同的式子（乘數交換被認為是相同的式子）

　　結果小的先輸出；結果相同的，較小的乘數較小的先輸出。

輸入描述:

　　每一行輸出一個式子，式子中的等號前后空格、乘號（用字母x代表）前后空格

　　較小的乘數寫在前面

輸出描述:

示例1

輸入

輸出

4396 = 28 x 157

5346 = 18 x 297

5346 = 27 x 198

5796 = 12 x 483

5796 = 42 x 138

6952 = 4 x 1738

7254 = 39 x 186

7632 = 48 x 159

7852 = 4 x 1963

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;bool isValid(int a, int b, int c) {int count[10] = {0}; // 0-9的計數器，0位置不使用while (a > 0) { count[a % 10]++; a /= 10; }while (b > 0) { count[b % 10]++; b /= 10; }while (c > 0) { count[c % 10]++; c /= 10; }for (int i = 1; i <= 9; i++) {if (count[i] != 1) return false; // 檢查1-9是否每個恰好出現一次}return count[0] == 0; // 確保數字0沒有出現
}int main() {for (int i = 1234; i <= 9876; i++) {for (int j = 2; j <= sqrt(i); j++) {if (i % j == 0) {int k = i / j;if (isValid(i, j, k)) {cout << i << " = " << j << " x " << k << endl;}}}}return 0;
}

思路

首先我們要明確題目需要我們做的事情，我們需要輸出一個等式形如a=b*c，這一個等式有一定的要求，a、b、c三個數中，1-9的數字必須有且僅出現1次。

也就是我們需要做兩件事情，第一件事情，需要保證a=b*c等式成立，第二件事情，a、b、c三個數中，1-9的數字必須有且僅出現1次。

代碼解析

這段代碼的目標是找到所有的四位數i（從1234到9876），這些四位數可以分解為兩個因子j和k（i = j * k），并且在這個等式中，數字1到9每個恰好出現一次，而數字0不出現。

函數isValid

三個整數a、b和c，分別代表要檢查的四位數和它的兩個因子。

檢查這三個數組成的集合中，數字1到9是否每個恰好出現一次，而0不出現。

使用一個count數組來計數數字0到9的出現次數，數組的索引對應于數字本身。

遍歷a、b和c中的每個數字，將其分解為單個數字，并在count數組中相應位置增加計數。

遍歷count數組（從1到9），檢查每個數字是否恰好出現一次。如果任何一個數字出現次數不為1，返回false。

最后，確保數字0沒有出現，即count[0]應該為0。

主函數main

找到所有符合條件的四位數及其因子。

遍歷從1234到9876的所有四位數，對于每個數i，嘗試找到所有可能的因子j。

因子j的范圍是從2到sqrt(i)，因為超過sqrt(i)的因子將會產生重復的乘積組合。

對于每個j，如果j是i的因子（即i % j == 0），則計算另一個因子k = i / j。

調用isValid函數檢查i、j和k是否符合條件（即在這三個數中，數字1到9每個恰好出現一次，而0不出現）。

如果符合條件，輸出等式i = j x k。

乘法表

題目描述

輸出九九乘法表，輸出格式見樣例。

輸入描述:

此題沒有輸入

輸出描述:

輸出乘法表，對齊方式見樣例輸出

示例1

輸入

無

輸出

1*1= 1

1*2= 2 2*2= 4

1*3= 3 2*3= 6 3*3= 9

1*4= 4 2*4= 8 3*4=12 4*4=16

1*5= 5 2*5=10 3*5=15 4*5=20 5*5=25

1*6= 6 2*6=12 3*6=18 4*6=24 5*6=30 6*6=36

1*7= 7 2*7=14 3*7=21 4*7=28 5*7=35 6*7=42 7*7=49

1*8= 8 2*8=16 3*8=24 4*8=32 5*8=40 6*8=48 7*8=56 8*8=64

1*9= 9 2*9=18 3*9=27 4*9=36 5*9=45 6*9=54 7*9=63 8*9=72 9*9=81

#include<iostream>
using namespace std;
int main(){for(int i=1;i<=9;i++){for(int j=1;j<=i;j++){if(j!=1) cout<<" ";cout<<j<<"*"<<i<<"=";printf("%2d",i*j);}cout<<endl;}
}

送分題

題目描述

數據結構之神ccz又在出毒瘤數據結構了

神出了這樣一個題：

給你三個數，在這三個數中間任意加*或者是+，然后可以隨便打括號，只要這個表達式合法

比如說1 2 3可以得到：

1+2*3=7

1*(2+3)=5

1*2*3=6

(1+2)*3=9

不能改變這三個數的原順序

最大化表達式的值

輸入描述:

輸入三行，每行一個數

分別表示a，b，c

輸出描述:

輸出一行一個數表示答案

示例1

輸入

1

2

3

輸出

9

示例2

輸入

2

10

3

輸出

60

備注:

1 <= a , b , c <= 10

#include<iostream>
using namespace std;int main() {int a,b,c;cin>>a>>b>>c;int ret1,ret3;int x12=max(a+b,a*b);int x23=max(b+c,b*c);ret1=max(x12+c,x12*c);ret3=max(x23+a,x23*a);cout<<max(ret1,ret3);return 0;
}

思路

首先我們有三個數字a，b，c，我們不可以改變這三個數字的相對位置，可以任意添加+或者*以及括號。整個過程相當于需要進行兩次運算，第一次運算，要么是a和b運算，要么是b和c運算，因為無法改變相對位置，所以沒辦法讓a和c運算，如果a和b運算，我們需要得到較大的值，只需要在+和*兩種情況中選出最大的即可，max(a+b,a*b);。如果b和c運算，我們需要得到較大的值，只需要在+和*兩種情況中選出最大的即可，max(b+c,b*c);。最后對于這兩種情況，可以得到相應的答案，ret1=max(x12+c,x12*c); ret3=max(x23+a,x23*a);。最后選出最大值輸出即可。

對于不同的情況，計算出結果。貪心的思想，每次都做最優的選擇，得到的結果就是最優的。

代碼解析

這段代碼的目的是接收三個整數a、b、c作為輸入，然后通過在這三個數之間插入加法或乘法運算符，嘗試找出能夠得到的最大結果。這個過程沒有改變數字的原始順序，即只考慮在給定順序下的運算。

通過cin從標準輸入讀取三個整數a、b、c。

x12=max(a+b,a*b);：計算a和b這兩個數通過加法或乘法能得到的最大值，并將結果存儲在x12中。

x23=max(b+c,b*c);：計算b和c這兩個數通過加法或乘法能得到的最大值，并將結果存儲在x23中。

ret1=max(x12+c,x12*c);：以x12為基礎，考慮將c加到x12的結果上或將c與x12相乘，從這兩個操作中選擇能得到的最大值，結果存儲在ret1中。

ret3=max(x23+a,x23*a);：以x23為基礎，考慮將a加到x23的結果上或將a與x23相乘，從這兩個操作中選擇能得到的最大值，結果存儲在ret3中。

通過cout輸出ret1和ret3之間的最大值，即所有考慮過的運算組合中可能得到的最大結果。

[NOIP2008]ISBN號碼

題目描述

每一本正式出版的圖書都有一個ISBN號碼與之對應，ISBN碼包括9位數字、1位識別碼和3位分隔符，其規定格式如“x-xxx-xxxxx-x”，其中符號“-”是分隔符（鍵盤上的減號），最后一位是識別碼，例如0-670-82162-4就是一個標準的ISBN碼。ISBN碼的首位數字表示書籍的出版語言，例如0代表英語；第一個分隔符“-”之后的三位數字代表出版社，例如670代表維京出版社；第二個分隔之后的五位數字代表該書在出版社的編號；最后一位為識別碼。

識別碼的計算方法如下：

首位數字乘以1加上次位數字乘以2……以此類推，用所得的結果mod 11，所得的余數即為識別碼，如果余數為10，則識別碼為大寫字母X。例如ISBN號碼0-670-82162-4中的識別碼4是這樣得到的：對067082162這9個數字，從左至右，分別乘以1，2，…，9，再求和，即0×1+6×2+……+2×9=158，然后取158 mod 11的結果4作為識別碼。

你的任務是編寫程序判斷輸入的ISBN號碼中識別碼是否正確，如果正確，則僅輸出“Right”；如果錯誤，則輸出你認為是正確的ISBN號碼。

輸入描述:

只有一行，是一個字符序列，表示一本書的ISBN號碼（保證輸入符合ISBN號碼的格式要求）。

輸出描述:

共一行，假如輸入的ISBN號碼的識別碼正確，那么輸出“Right”，否則，按照規定的格式，輸出正確的ISBN號碼（包括分隔符“-”）。

示例1

輸入

0-670-82162-4

輸出

Right

示例2

輸入

0-670-82162-0

輸出

0-670-82162-4

#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main(){vector<int> d;string str;cin>>str;for(auto x:str){if(x-'0'>=0&&x-'0'<=9){d.push_back(x-'0');}}int sum=0;for(size_t i=0;i<d.size()-1;i++){sum+=d[i]*(i+1);}sum=sum%11;if(sum==10&&str[str.length()-1]=='X') cout<<"Right";else if(sum==(str[str.length()-1]-'0')) cout<<"Right";else{if(sum==10){str[str.length()-1]='X';}else{str[str.length()-1]=sum+'0';}cout<<str;}return 0;
}

這段代碼的目的是驗證并糾正一個包含ISBN（國際標準書號）的字符串。ISBN的最后一位是一個校驗碼，可以是0到9之間的任何數字，或者是字符'X'來代表10。這個校驗碼是通過前面的數字按照一定的規則計算得出的，以確保ISBN的正確性。具體來說，這段代碼執行以下步驟：

用戶輸入一個字符串str，代表一個可能的ISBN號。

遍歷字符串str，將其中的數字字符轉換為整數，并存儲在向量d中。

通過遍歷d向量，計算前面所有數字（除了最后一個數字，它是待驗證的校驗碼）的加權和。加權規則是：每個數字乘以它的位置索引（從1開始計數），然后將這些乘積相加。

將加權和對11取模，得到的結果就是計算出的校驗碼sum。

如果sum為10，并且字符串的最后一個字符是'X'，則輸出"Right"，表示校驗碼正確。

如果sum與字符串最后一個字符代表的數字相等，也輸出"Right"。

如果兩個條件都不滿足，則說明校驗碼錯誤，需要糾正：

如果sum為10，則將字符串最后一個字符替換為'X'。

否則，將其替換為sum對應的數字字符。

然后輸出糾正后的完整ISBN字符串。

代碼中的邏輯基于ISBN的校驗碼計算規則，即通過特定的加權和模11得到的結果。這種校驗機制用于檢測ISBN號中的輸入錯誤或偶然的錯誤。

前天是哪天

題目描述

給定公元2000年到公元3000年之間的某一天，請你給出該天的前天是哪一天.

輸入描述:

輸入在一個日期，格式如"yyyy-mm-dd"，題目保證所有輸入日期為合法日期。

輸出描述:

在一行中輸出日期，格式如"yyyy-mm-dd"。

示例1

輸入

2020-11-15

輸出

2020-11-13

備注:

注意日期格式，月份或者天數不足2位要補零。

/*日期類代碼實現*/
#include <iostream>
using namespace std;
#include<string>
class Date {
public:int GetMonthDay(int year, int month) {static int monthDays[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};if (month == 2 && ( (year % 4 == 0 && year % 100 != 0) || year % 400 == 0)) {return 29;}return monthDays[month];}Date(int year = 0, int month = 1, int day = 1) {if (year >= 0&& month >= 1 && month <= 12&& day >= 1 && day <= GetMonthDay(year, month)) {_year = year;_month = month;_day = day;} else {cout << "非法日期" << endl;}}bool operator<(const Date& d) {if (_year < d._year)return true;else if (_year == d._year && _month < d._month)return true;else if (_year == d._year && _month == d._month && _day < d._day)return true;elsereturn false;}bool operator==(const Date& d) {return _year == d._year && _month == d._month && _day == d._day;}bool operator<=(const Date& d) {return (*this) < d || (*this) == d;}bool operator>(const Date& d) {return !((*this) <= d);}bool operator>=(const Date& d) {return !((*this) < d);}bool operator!=(const Date& d) {return !((*this) == d);}Date& operator+=(int day) {if (day < 0) {return (*this) -= -day;}_day += day;while (_day > GetMonthDay(_year, _month)) {_day -= GetMonthDay(_year, _month);_month++;if (_month == 13) {_year++;_month = 1;}}return *this;}Date operator+(int day) {if (day < 0) {return (*this) - (-day);}Date ret(*this);ret += day;return ret;}Date& operator-=(int day) {if (day < 0) {return (*this) += -day;}_day -= day;while (_day <= 0) {_month--;if (_month == 0) {_year--;_month = 12;}_day += GetMonthDay(_year, _month);}return *this;}Date operator-(int day) {if (day < 0) {return (*this) + (-day);}Date ret(*this);ret -= day;return ret;}Date& operator++() {(*this) += 1;return *this;}Date operator++(int) {Date ret(*this);(*this) += 1;return ret;}Date& operator--() {(*this) -= 1;return *this;}Date operator--(int) {Date ret(*this);(*this) -= 1;return ret;}void Show() {printf("%d-%02d-%02d",_year,_month,_day);}
private:int _year;int _month;int _day;
};int main() {string str;cin>>str;int year,month,day;int pos1=str.find("-");int pos2=str.rfind("-");year=stoi(str.substr(0,pos1));month=stoi(str.substr(pos1+1,pos2-(pos1+1)));day=stoi(str.substr(pos2+1));Date d(year,month,day);d-=2;d.Show();return 0;
}

小名的回答

題目描述

總算到暑假了，小姐姐是非常的閑，所以想去找梅溪湖的小名玩，可是她從沒去過梅溪湖，所以只能憑小名告訴她的地方走，每次只能向上下左右四個方向走1步。小姐姐的坐標為(0,0)，小名在(a,b)，小姐姐有點近視，小名也有點近視。所以到了(a,b)也不一定能和小名會面，不過還好，小姐姐最后找到了小名。小姐姐想要小名知道自己來一趟是多么不容易，所以在聊天的過程中小姐姐說自己為了到這里走了n步。小名，你覺得她說的可能是真話么。有可能就輸出YES,否則輸出NO(如果用random的話,小姐姐覺得你好像不在意她，明年暑假就不來了)

輸入描述:

a,b,n(-1000<=a,b<=1000,a*b>0,1<=n<=2000)

輸出描述:

"YES" or "NO"

示例1

輸入

2 2 4

輸出

YES

示例2

輸入

1 9 2

輸出

NO

#include<iostream>
using namespace std;
int main(){int a,b,n;cin>>a>>b>>n;int c=abs(a)+abs(b);if(n>=c&&(n-c)%2==0) cout<<"YES";else cout<<"NO";
}

if(n>=c&&(n-c)%2==0)這個if語句檢查是否可以在n步內到達(a, b)。首先，n必須大于或等于c，即有足夠的步數到達目標。其次，(n-c)%2==0確保在到達目標后，剩余的步數是偶數。因為每多出一步，都需要再多一步才能回到目標點，所以剩余步數必須是偶數。

如果姐姐可以到目標位置，那么她走的路線一定含有必須行走的最短路徑，其他走的路都是多余的，多出來的步數是否合理，只需要看是否可以走出目標地點再走回目標地點，也就是偶數即可。

[NOIP2004]不高興的津津

題目描述

津津上初中了。媽媽認為津津應該更加用功學習，所以津津除了上學之外，還要參加媽媽為她報名的各科復習班。另外每周媽媽還會送她去學習朗誦、舞蹈和鋼琴。但是津津如果一天上課超過八個小時就會不高興，而且上得越久就會越不高興。假設津津不會因為其它事不高興，并且她的不高興不會持續到第二天。請你幫忙檢查一下津津下周的日程安排，看看下周她會不會不高興；如果會的話，哪天最不高興。

輸入描述:

包括七行數據，分別表示周一到周日的日程安排。每行包括兩個小于10的非負整數，用空格隔開，分別表示津津在學校上課的時間和媽媽安排她上課的時間。

輸出描述:

包括一行，這一行只包含一個數字。如果不會不高興則輸出0，如果會則輸出最不高興的是周幾（用1, 2, 3, 4, 5, 6, 7分別表示周一，周二，周三，周四，周五，周六，周日）。如果有兩天或兩天以上不高興的程度相當，則輸出時間最靠前的一天。

示例1

輸入

5 3

6 2

7 2

5 3

5 4

0 4

0 6

輸出

3

#include<iostream>
#include<vector>
using namespace std;
int main(){vector<vector<int>> vv(7, vector<int>(2, 0));for(int i=0;i<7;i++){cin>>vv[i][0]>>vv[i][1];if(vv[i][0]+vv[i][1]>8) {cout<<i+1;return 0;}}cout<<0;
}

代碼解析

這行代碼使我們可以直接使用std命名空間中的所有成員，而不需要在每個標準庫類或函數前加std::前綴。

vector<vector<intvv(7, vector<int(2, 0));

這行代碼聲明了一個名為vv的二維向量（向量的向量），并初始化為7行2列，所有元素初始值為0。這意味著vv可以存儲7天的數據，每天有兩個整數。 for(int i=0;i<7;i++){

這個循環從0迭代到6，用于逐天讀取輸入數據。 cin>>vv[i][0]>>vv[i][1];

這行代碼從標準輸入讀取兩個整數，并將它們存儲在vv的第i行中。vv[i][0]和vv[i][1]分別代表第i天的兩個整數。 if(vv[i][0]+vv[i][1]>8) {

這個if語句檢查第i天的兩個整數之和是否大于8。

cout<<i+1;

如果某天的整數之和首次超過8，則輸出那天的編號（因為編號從1開始，所以輸出i+1），然后： cout<<0;

如果循環結束后沒有找到任何一天的整數之和超過8，則輸出0。

C++格式化的探究

在C++中，cout確實可以用于格式化輸出，但它的方式與傳統的C語言中的printf函數略有不同。C++中的cout是基于流的輸出，使用<<操作符來連續地將數據發送到輸出。為了實現格式化輸出，可以在cout語句中使用一些特殊的控制符號來修改輸出的格式，如設置寬度、填充字符和小數點精度等。

設置寬度和填充

你可以使用setw()和setfill()來設置下一個輸出字段的寬度和填充字符。設置寬度僅僅對下一個數據有效。設置填充依舊是持續的效果。

#include <iostream>
#include <iomanip> // 需要包含這個頭文件來使用setw和setfillusing namespace std;int main() {cout << setw(10) << setfill('*') << 123 << endl;cout << setw(10) << 123 << endl;// 輸出: //*******123//*******123return 0;}

控制浮點數精度

使用setprecision()來控制浮點數的輸出精度。設置精度是持續的效果。

#include <iostream>
#include <iomanip> // 需要包含這個頭文件來使用setprecisionusing namespace std;int main() {double pi = 3.14159265358979;cout << setprecision(5) << pi <<  endl << pi << endl; // 顯示5位有效數字cout << setprecision(9) << pi << endl; // 顯示9位有效數字cout << fixed << setprecision(3) << pi << endl; // 固定小數點顯示3位小數// 輸出://3.1416//3.1416//3.14159265//3.142return 0;}

設置左對齊或右對齊

使用left和right控制符來設置對齊方式。setw設置寬度只對下一個輸出的數據有效，而設置左右對齊一直都有效。

#include <iostream>
#include <iomanip>using namespace std;int main() {cout << setw(10) << left << 123 << "end" << setw(5) << 234 << right <<"end"<< setw(5) << 123 << "end" << endl; // 左對齊cout << setw(10) << right << 123 << "end" << endl; // 右對齊// 輸出://123       end234  end  123end//123endreturn 0;}

十六進制、八進制和十進制輸出

可以使用hex、oct和dec來控制整數的輸出格式。設置進制也是持續的效果。

#include <iostream>
using namespace std;int main() {int num = 255;cout << hex << num << endl; // 十六進制cout << 255 << endl;cout << oct << num << endl; // 八進制cout << dec << num << endl; // 十進制// 輸出://ff//ff//377//255return 0;}