前言
這套題中涉及到的知識點有 模擬、前綴和、貪心、快速排序、動態規劃、結構體、堆疊、佇列、dfs、bfs等,題目偏簡單,
在寫代碼時,可以用函式來實作單獨的功能,比如第二題實作一個判斷素數的函式,第三題實作一個將數字分解相加并乘以3加1的函式等,能使代碼變得簡潔明了, 方便后面的除錯和修改,
7-0 當日天數
昨天熱身賽的最后一題,但很多人沒寫出來,計算日期的這類問題,藍橋杯基本每年都會考,所以就寫一下思路和題解供參考,
編程計算某年某月某日當天,是當年的第幾天, 說明:1)當年1月1日是第1天;2)每月按月大,月小,閏年等情況,各月天數有不同(31,30,28,29);3)閏年按4年一閏,100年不閏,400年再閏計算,
輸入格式:
用空格分隔的三個正整數(表示年,月,日的整數),均是合法的資料,
輸出格式:
直接輸出年-月-日:整數,表示當日是第幾天,年號占4位,不足4位時補前導零,月和日各占2位,不足2位也補前導零,
輸入樣例:
2020 3 3
輸出樣例:
2020-03-03:63
首先是格式,使用printf(%02d, month); d前面加一個02的意思是 如果數字不夠2位數的話就在前面補0,scanf 與printf 還有許多用法,可以在網上或者自己試驗,多了解一下,
題目大致思路是:模擬每一天的增加,到達月底最后一天,月份加一,月份到達年底最后一個月,年份加一,注意每過一年還需要判斷一下是不是閏年,
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//用一個陣列存每個月有多少天
int arr[13] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
int main(){
int y, m, d, ans = 1;
cin >> y >> m >> d;
//閏年的話2月就是29天,注意如果題目是遍歷好多年的,每過一年就把arr[2]變為28,防止出錯,
if(y%4==0&&y%100!=0||y%400==0) arr[2] = 29;
int i = 1, j = 1; // 記錄月和天
while(1){
if(i == m && j==d) break;
j++; ans++;
// 如果天數大于當月的天數, 月數加一,天數變為0,
// 如果月數大于12,年數加一,月數變為0,本題不需要,
if(j > arr[i]){
i++, j = 1;
}
}
printf("%04d-%02d-%02d:%d",y,m,d,ans);
}
7-1 西安距離
小明來到了古都西安,想去參觀大唐西市!
西安的道路可以看做是與x軸或y軸垂直的直線,小明位于(a,b),而目的地位于(c,d),問最少幾步可以到達,
輸入格式:
一行中四個整數,a,b,c,d,表示坐標為(a,b)與(c,d),這里0<=a,b,c,d<=1000
輸出格式:
輸出這兩個點的西安距離,
輸入樣例:
0 0 3 4
輸出樣例:
7
題目中要求只能走與x軸或y軸水平的直線,因此不是求兩點之間的直線距離,而求|(x2-x1)|+|(y2-y1)|的值,注意求絕對值,代碼如下:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << abs(c-a)+abs(d-b);
}
7-2 判斷素數
本題的目標很簡單,就是判斷一個給定的正整數是否素數,
輸入格式:
輸入在第一行給出一個正整數N(≤ 10),隨后N行,每行給出一個小于2^31??的需要判斷的正整數,
輸出格式:
對每個需要判斷的正整數,如果它是素數,則在一行中輸出Yes,否則輸出No,
輸入樣例:
2
11
111
輸出樣例:
Yes
No
判斷一個數是否為素數只需遍歷到 n \sqrt{n} n ?即可,注意1不是素數,代碼如下:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int jud(int n){
if(n == 1) return 0;
for(int i = 2; i <= sqrt(n); i++){
if(n%i == 0) return 0;
}
return 1;
}
int main(){
int n, a;
cin >> n;
while(n--){
cin >> a;
if(jud(a)) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
7-3 掉入陷阱的數字
對任意一個自然數N0,先將其各位數字相加求和,再將其和乘以3后加上1,變成一個新自然數N1? ;然后對N1重復這種操作,可以產生新自然數N?2 ;……多次重復這種操作,運算結果最侄訓得到一個固定不變的數N?k,就像掉入一個數字“陷阱”,
本題要求對輸入的自然數,給出其掉入“陷阱”的程序,
輸入格式:
在一行內給出一個自然數N?0(N?0 < 30000),
輸出格式:
對于輸入的N?0,逐行輸出其掉入陷阱的步驟,第i行描述N掉入陷阱的第i步,格式為: i:N?i(i≥1),當某一步得到的自然數結果N?k(k≥1)與上一步N
?k?1?? 相同時,停止輸出,
輸入樣例:
5
輸出樣例:
1:16
2:22
3:13
4:13
用一個變數記錄上一次的數字是多少,如果這次跟上次相同就結束,
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//將n各位數字相加求和.再將其和乘以3后加上1
int resolve(int n){
int ans = 0;
while(n){
ans += n%10;
n /= 10;
}
return 3*ans+1;
}
int main(){
int n, f; // f用來記錄上一次的數字,
cin >> n;
for(int i = 1; ; i++){
f = n;
n = resolve(n);
cout << i << ":" << n << endl;
if(f == n) break;
}
return 0;
}
7-4 跳一跳
微信小程式中的跳一跳相信大家都玩過,emmm???只學習不玩游戲?那就吃虧了…好好讀題理解吧,
簡化后的跳一跳規則如下:玩家每次從當前方塊跳到下一個方塊,如果沒有跳到下一個方塊上則游戲結束,
如果跳到了方塊上,但沒有跳到方塊的中心則獲得1分;
跳到方塊中心時,若上一次的得分為1分或這是本局游戲的第一次跳躍則此次得分為2分,否則此次得分比上一次得分多兩分(即連續跳到方塊中心時,總得分將+2,+4,+6,+8…),
現在給出一個人跳一跳的全程序,請你求出他本局游戲的得分(按照題目描述的規則),
輸入格式:
輸入包含多個數字,用空格分隔,每個數字都是1,2,0之一,
1表示此次跳躍跳到了方塊上但是沒有跳到中心,
2表示此次跳躍跳到了方塊上并且跳到了方塊中心,
0表示此次跳躍沒有跳到方塊上(此時游戲結束),
對于所有評測用例,輸入的數字不超過30個
輸出格式:
輸出一個整數,為本局游戲的得分(在本題的規則下),
輸入樣例:
1 1 2 2 2 1 1 2 2 0
輸出樣例:
22
模擬即可,用一個變數標記連續幾次跳到中心,沒跳到中心就清0,
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
int n, ans = 0, f = 1;
while(cin >> n, n!=0){
if(n == 2) {
ans += f*2; f++;
}else{
ans++; f = 1;
}
}
cout << ans;
}
7-5 看電影
終于到周末了,明明是特別喜歡看電影,他想在一天內盡量多的看到完整的多部電影, 現在他把他喜歡的電影的播放時間表給你,希望你能幫他合理安排,
輸入格式:
輸入包含多組測驗資料,每組輸入的第一行是一個整數n(n<=100),表示明明喜歡的電影的總數, 接下來n行,每行輸入兩個整數si和ei(1<=i<=n),表示第i個電影的開始和結束時間,為了簡化問題,每個時間都用一個正整數表示, 當n=0時,輸入結束,
輸出格式:
對于每組輸入,輸出能完整看到的電影的個數,
輸入樣例:
在這里給出一組輸入,例如:
12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9
0
輸出樣例:
5
貪心演算法,根據電影的結束時間從小到大排序,用一個變數記錄當前時間,遍歷尋找滿足 電影開始時間>=當前時間的電影,尋找的第一個符合條件的電影就是最優的選擇,再將記錄時間的變數改為此電影的結束時間,直至遍歷結束,
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
struct node{
int begin, end;
}arr[N];
bool cmp(node a, node b){
if(a.end == b.end){
return a.begin < b.begin;
}
return a.end < b.end;
}
int main(){
int n;
while(cin >> n, n!=0){
int ans = 0, f = 0; // f用來記錄當前的時間
for(int i = 0; i<n; i++){
cin >> arr[i].begin >> arr[i].end;
}
sort(arr,arr+n,cmp);
//遍歷尋找
for(int i = 0; i < n; i++){
if(arr[i].begin >= f){
ans++;
f = arr[i].end;
}
}
cout << ans << endl;
}
}
7-6 求區間和
本題會給你一段長度為N的整數序列,并進行K次詢問,每次詢問要求你給出區間a到b的和(序列下標由1到N),由于區間和可能較大,請你輸出它對10000019取模的結果,
輸入格式:
首先一行整數N,代表序列長度,
接下來一行N個整數,為序列內容,
接下來一行整數K,代表對區間和的詢問次數,
接下來K行,每行兩個整數a和b,請你輸入序列的第a到b號元素(含)的和取模后的結果,
輸出格式:
一共K行,每行一個整數,代表詢問的區間和取模后的結果,
輸入樣例:
5
1 2 3 4 5
3
1 5
2 3
3 3
輸出樣例:
15
5
3
資料限制:
N<=1e?6,K<=1e5
??
使用前綴和陣列,經過預處理后,每次查詢只需要O(1)的時間復雜度,
(由于輸入的資料量過大,用cin,cout有時候會超時)
即對于一個數字序列,用arr[i]陣列儲存這串數的前 i 項的和,那么每次尋找序列第a到b號元素的和時就不需要遍歷a到b之前的所有數了,只需要計算arr[b] - arr[a-1]的值就行,
比如序列:3 2 4 1 5 6,
arr陣列(以1位陣列下標)對應的值是:3 5 9 10 15 21,
計算序列第3項到第5項的值就是 arr[5]-arr[2] = 15-5 = 10,
前綴和演算法實用性很高,此外還有差分演算法,建議不了解的同學在網上看看相關文章,
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
const int mod = 10000019;
int arr[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, a, b, m;
cin >> n;
for(int i = 1; i<=n; i++){
cin >> a;
arr[i] = (arr[i-1]+a)%mod;
}
cin >> m;
while(m--){
cin >> a >> b;
cout << (arr[b]+mod-arr[a-1])%mod << endl;
// +mod 是為了arr[b]<arr[a]的情況
}
}
7-7 最大子段和
給定n個整數(可能為負數)組成的序列a[1],a[2],a[3],…,a[n],求該序列如a[i]+a[i+1]+…+a[j]的子段和的最大值,當所給的整數均為負數時,定義子段和為0,
輸入格式:
輸入有兩行:
第一行是n值(1<=n<=10000);
第二行是n個整數,
輸出格式:
輸出最大子段和,
輸入樣例:
6
-2 11 -4 13 -5 -2
輸出樣例:
20
動態規劃的入門題,
設dp[i]為以第i個元素結尾且和最大的連續子陣列,
假設對于元素i,所有以它前面的元素結尾的子陣列的長度都已經求得,那么以第i個元素結尾且和最大的連續子陣列實際上,要么是以第i-1個元素結尾且和最大的連續子陣列加上這個元素,要么是只包含第i個元素,
即dp[i] = max(dp[i-1] + a[i], a[i]),可以通過判斷sum[i-1] + a[i]是否大于a[i]來做選擇,而這實際上等價于判斷sum[i-1]是否大于0,
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4+10;
int dp[N];
int main(){
int n, ans = 0, a;
cin >> n;
for(int i=1; i<=n; i++) {
cin >> a;
dp[i] = max(dp[i-1]+a, a);
ans = max(dp[i], ans);
}
cout << ans;
}
此外由于每次運算只需要前一次的結果,因此并不需要像普通的動態規劃那樣保留之前所有的計算結果,即不需要陣列儲存之前的結果,只需要保留上一次的即可,
7-8 逆波蘭運算式求值
逆波蘭表示法是一種將運算子(operator)寫在運算元(operand)后面的描述程式(算式)的方法,舉個例子,我們平常用中綴表示法描述的算式(1 + 2)*(5 + 4),改為逆波蘭表示法之后則是1 2 + 5 4 + *,相較于中綴表示法,逆波蘭表示法的優勢在于不需要括號,
請輸出以逆波蘭表示法輸入的算式的計算結果,
輸入格式:
在一行中輸入1個算式,相鄰的符號(運算元或運算子)用1個空格隔開,
輸出格式:
在一行中輸出計算結果,
限制:
2≤算式中運算元的總數≤100
1≤算式中運算子的總數≤99
運算子僅包括“+”、“-”、“*”,運算元、計算程序中的值以及最終的計算結果均在int范圍內,
輸入樣例1:
4 3 + 2 -
輸出樣例1:
5
輸入樣例2:
1 2 + 3 4 - *
輸出樣例2:
-3
考察資料結構中堆疊的應用,
對于每次輸入的元素,如果當前元素是整數,則壓入堆疊;如果是運算子,則將堆疊頂兩個元素彈出做相應運算,再將結果入堆疊,
最終運算式掃描完后,堆疊里的數就是結果,
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
stack<int> arr;
//將字串轉為數字
int to_int(string str){
int ans = 0, i = 0, f = 0;
if(str[0] == '-') {
f = 1; i = 1;
}
for(;i<str.size(); i++){
ans = ans*10+str[i]-'0';
}
if(f) ans = 0-ans;
return ans;
}
int main(){
string str;
while(cin >> str){
if(str[0] == '+'||str[0] == '-'||str[0] == '*'){
int n2 = arr.top(); arr.pop();
int n1 = arr.top(); arr.pop();
if(str[0] == '+') arr.push(n1+n2);
else if(str[0] == '-') arr.push(n1-n2);
else arr.push(n1*n2);
}else{
arr.push(to_int(str));
}
}
cout << arr.top();
}
7-9 排排排名
眾所周知,Keven所在的集訓隊經常舉辦比賽,然而每次比賽的排名統計是一個大麻煩,于是Keven找到了你并給了你這次比賽的分數,希望你能幫他統計一下這次比賽前K名隊員的排名,
輸入格式:
輸入在第一行給出 2 個整數,分別是 N(不超過 10 000 的正整數,為學生總數)、K(不超過 100 且不超過 N 的正整數),接下來 N 行,每行給出一位學生的賬號(長度不超過15位、不帶空格的字串)和比賽成績(區間 [0, 100] 內的整數),其間以空格分隔,題目保證沒有重復的賬號,
輸出格式:
然后按總評成績非升序輸出前K名學生的名次、賬號和成績,其間以 1 個空格分隔,需要注意的是:成績相同的學生享有并列的排名,排名并列時,按賬號的字母序升序輸出,
需要注意的是:
成績相同的學生享有并列的排名,排名并列時,按賬號的字母序升序輸出,詳見第二個樣例,
假設現在有三位同學,他們的成績分別是100、100、80,那么此時兩位100分的同學的排名應該都是 1 ,并且80分的同學的排名是 3 ,
輸入樣例1:
10 5
cy@zju.edu.cn 78
cy@pat-edu.com 87
1001@qq.com 65
uh-oh@163.com 96
test@126.com 39
anyone@qq.com 87
zoe@mit.edu 80
jack@ucla.edu 88
bob@cmu.edu 80
ken@163.com 70
輸出樣例1:
1 uh-oh@163.com 96
2 jack@ucla.edu 88
3 anyone@qq.com 87
3 cy@pat-edu.com 87
5 bob@cmu.edu 80
5 zoe@mit.edu 80
直接根據分數與賬號的字典序排序就行,輸出的時候注意名次可以相等,需要用變數記錄上一個人的分數和相等的名次數量,后面再加上,
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4+10;
struct node{
string str;
int n;
}arr[N];
bool cmp(node a, node b){
if(a.n == b.n){
return a.str < b.str;
}
return a.n > b.n;
}
int main(){
int n, m, f = 0, last = -1, lastn = 1;
cin >> n >> m;
for(int i = 0; i < n; i++) cin >> arr[i].str >> arr[i].n;
sort(arr,arr+n,cmp);
// f:是當前的名次, last:是上一個人的分數, lastn是有幾個擁有last分數的人
for(int i = 0; i < n; i++){
if(arr[i].n!=last){
last = arr[i].n;
f += lastn; lastn = 1;
}else lastn++;
if(f>m) break;
cout << f <<" "<< arr[i].str << " " << arr[i].n << endl;
}
}
7-10 白騎士的移動
小S第一次接觸國際象棋,他發現國際象棋中的Knight棋子的移動方式和中國象棋中的馬類似,
于是小S在棋盤上隨意擺上了一些棋子,其中包括一枚白騎士、一枚黑皇后、若干黑戰車和若干黑主教,
小S想知道,如何能在避開黑戰車和黑主教的攻擊范圍的前提下,花費更少的步數吃掉黑皇后,
注1:戰車的攻擊范圍呈直線,和中國象棋的車類似;主教的攻擊范圍呈斜線,無障礙物情況下可無限延伸,
注2:白騎士只能吃黑皇后,不可以吃掉黑戰車和黑主教,
輸入格式:
輸入僅包含一組樣例,
一組樣例包含8行(分別對應1-8行),每行包含8個字符,每個字符代表對應行對應列的棋盤格子狀況,
其中’ . ‘代表格子上沒有擺放任何棋子;’ K '代表格子上擺放的是白騎士; ’ Q '代表格子上擺放的是黑皇后; ’ R '代表格子上擺放的是黑戰車; ’ B '代表格子上擺放的是黑主教,
注:題目保證白騎士的初始位置不在黑戰車和黑主教的攻擊范圍內,
輸出格式:
如果白騎士可以在避開黑戰車和黑主教的攻擊的情況下吃掉黑皇后,則輸出花費步數的最小值;否則輸出"Checkmate",
輸入樣例1:
R.B.QB.R
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. K . . . . . .
輸出樣例1:
4
跟迷宮題類似,不過馬的路徑跟走迷宮的不太一樣,需要注意,尋找最小的步數,所以要用bfs(本題中dfs應該也不會超時),注意黑戰車與黑主教的攻擊,遇到障礙后就會停止,
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char arr[15][15];
int vis[15][15], ans = 0, bx, by;
// 馬的路徑
int d[8] = {2,2,1,1,-1,-1,-2,-2};
int f[8] = {1,-1,2,-2,2,-2,1,-1};
struct node{
int x, y, v;
};
//黑主教的攻擊范圍
void disB(int x, int y){
vis[x][y] = 1;
for(int i=x+1,j=y+1; i<=8&&j<=8; i++,j++){
if(arr[i][j] != '.') break;
vis[i][j] = 1;
}
for(int i = x-1, j = y-1; i>=1&&j>=1; i--,j--){
if(arr[i][j] != '.') break;
vis[i][j] = 1;
}
for(int i=x+1,j=y-1; i<=8&&j>=1; i++,j--){
if(arr[i][j] != '.') break;
vis[i][j] = 1;
}
for(int i=x-1,j=y+1; i>=1&&j<=8; i--,j++){
if(arr[i][j] != '.') break;
vis[i][j] = 1;
}
}
//黑戰車的攻擊范圍
void disR(int x, int y){
vis[x][y] = 1;
for(int i=x+1; i <= 8;i++){
if(arr[i][y] != '.') break;
vis[i][y] = 1;
}
for(int i=x-1; i >= 1;i--){
if(arr[i][y] != '.') break;
vis[i][y] = 1;
}
for(int i=y+1; i<= 8;i++){
if(arr[x][i] != '.') break;
vis[x][i] = 1;
}
for(int i=y-1; i >= 1;i--){
if(arr[x][i] != '.') break;
vis[x][i] = 1;
}
}
void bfs(){
queue<node> q;
node b; b.x=bx; b.y=by; b.v = 0;
q.push(b);
while(!q.empty()){
node p = q.front(); q.pop();
for(int i = 0; i<8; i++){
int x = p.x+d[i];
int y = p.y+f[i];
if(arr[x][y] == 'Q'){
ans = p.v+1; return;
}
if(x>=1 && x<=8 && y>=1 && y<=8 && vis[x][y]==0){
// cout << x <<" "<< y << endl;
vis[x][y] = 1;
node n; n.x = x; n.y = y; n.v =p.v+1;
q.push(n);
}
}
}
}
//對棋盤中的棋子進行處理
void check(){
for(int i = 1; i<=8; i++){
for(int j = 1; j<= 8; j++){
if(arr[i][j] == 'R'){
disR(i,j);
}else if(arr[i][j] == 'B'){
disB(i,j);
}else if(arr[i][j] == 'K'){
bx = i; by = j;
}
}
}
}
int main(){
for(int i = 1; i<=8; i++){
for(int j = 1; j<= 8; j++){
cin >> arr[i][j];
}
}
check();
bfs();
if(ans == 0) cout << "Checkmate";
else cout << ans;
}
轉載請註明出處,本文鏈接:https://www.uj5u.com/qita/272575.html
標籤:其他
上一篇:【雜記】01:王者榮耀,再見?
