記錄刷題的過程、感悟、題解。
希望能幫到，那些與我一同前行的，來自遠方的朋友😉
大綱：
?1、九進制轉十進制-（解析）-簡單的進制轉化問題😄
?2、順子日期-（解析）-考察日期
?3、刷題統計-（解析）-簡單的除法問題🥲，千萬別暴力，會超時
?4、修剪灌木-（解析）-真·貪心，主打一個觀察能力🥲or 想象力
?5、X 進制減法-（解析）-進階一點的進制轉化，需要對進制轉化，有更深層次的了解。
?6、統計子矩陣-（解析）-二維前綴和+滑動窗口，如果純前綴和打暴力（只能過70%）?
?7、積木畫-（解析）-太好了，我一直以為無解，原來能用線性dp做出來，太感動了(┬┬﹏┬┬)，原來還能讓人做。
?8、掃雷-（解析）-啊，這道題出乎意料的簡單，出在倒數第三題，簡直了😇，很多人都做不到吶。
?9、李白打酒加強版-（解析）-記憶化搜索+dfs，單純dfs定超時。|| dp也能解決。
?10、砍竹子-（解析）-這道題真是智者見智了，八仙過海、各顯神通。我用的優先隊列。😉
題目：
1、九進制轉十進制
問題描述
本題為填空題，只需要算出結果后，在代碼中使用輸出語句將所填結果輸出即可。
九進制正整數?(2022)9轉換成十進制等于多少？
運行限制
- 最大運行時間：1s
- 最大運行內存: 512M
本題就是一道，簡單的進制轉化題目
解析：(2022)9=2*9^0+2*9^1+0*9^2+2*9^3?
2是基數、9是進制數
#include <bits/stdc++.h>
using namespace std;
int main(){string str="2022";reverse(str.begin(),str.end());int sum=0;for(int i=0; i<str.size(); ++i){sum+=pow(9,i)*(str[i]-'0');}cout<<sum<<endl;return 0;
} 2、順子日期
問題描述
本題為填空題，只需要算出結果后，在代碼中使用輸出語句將所填結果輸出即可。
小明特別喜歡順子。順子指的就是連續的三個數字：123、456 等。順子日期指的就是在日期的?yyyymmdd?表示法中，存在任意連續的三位數是一個順子的日期。例如 20220123 就是一個順子日期，因為它出現了一個順子：123； 而 20221023 則不是一個順子日期，它一個順子也沒有。小明想知道在整個 2022 年份中，一共有多少個順子日期?
運行限制
- 最大運行時間：1s
- 最大運行內存: 512M
本題，就寫簡單一點吧:"2022" 已經不可能與任何數 形成順子了，可以直接排除掉
bool get_num(...)是用來判斷，月日是否合理
bool get_cnt(...)是用來判斷是否是順子
#include <bits/stdc++.h>
using namespace std;
bool get_num(int mm, int dd){if(mm==1||mm==3||mm==5||mm==7||mm==8||mm==10||mm==12){// 31 天if(dd>=1&&dd<=31) return true;}else if(mm==2){ // 28天if(dd>=1&&dd<=28) return true;}else if(mm==4||mm==6||mm==9||mm==11){ // 30天if(dd>=1&&dd<=30) return true;} return false;
}bool get_cnt(string str){str = "9"+str; // 前面后綴一個數 vector<int> arr(str.size(),0);for(int i=1; i<str.size(); ++i)if(str[i]==str[i-1]+1) arr[i]=arr[i-1]+1; for(int i=1; i<arr.size(); ++i) if(arr[i]==2) return true;return false;
}int main()
{int sum=0;// 暴力。0100-1299 // 這些的嗎？其實也能用遞歸深搜 for(int i=0; i<10; ++i){for(int j=0; j<10; ++j){for(int k=0; k<10; ++k){for(int z=0; z<10; ++z){ // 一共10層循環int mm = i*10+j;int dd = k*10+z;if(get_num(mm,dd)){string str = to_string(i)+to_string(j)+to_string(k)+to_string(z);if(get_cnt(str)) sum++;}}}}}cout<<sum<<endl;return 0;
}3、刷題統計
問題描述
小明決定從下周一開始努力刷題準備藍橋杯競賽。他計劃周一至周五每天 做?a?道題目, 周六和周日每天做?b?道題目。請你幫小明計算, 按照計劃他將在 第幾天實現做題數大于等于?n?題?
輸入格式
輸入一行包含三個整數?a,b 和?n.
輸出格式
輸出一個整數代表天數。
樣例輸入
10 20 99樣例輸出
8評測用例規模與約定
對于?50%?的評測用例,?1≤a,b,n≤10^6.
對于?100%?的評測用例,?1≤a,b,n≤10^18.
// 哦草！本題大意了，沒有看數據10^18次方吶，直接就開始暴力了。
// 本題沒有必要開一個循環，一個一個加
// 能直接進行除法運算
#include <bits/stdc++.h>
#define int long long
using namespace std;signed main(){int a,b,n;cin>>a>>b>>n;int cnt = 0;int sum = n/(a*5+b*2);int temp = n%(a*5+b*2);if(temp<=a*5){cnt+=ceil((double)temp/a); }else{temp-=5*a;cnt+=5;cnt+=ceil((double)temp/b);} cnt+=sum*7;cout<<cnt<<endl;return 0;
} 4、修剪灌木
問題描述
愛麗絲要完成一項修剪灌木的工作。
有?N?棵灌木整齊的從左到右排成一排。愛麗絲在每天傍晩會修剪一棵灌 木, 讓灌木的高度變為 0 厘米。愛麗絲修剪灌木的順序是從最左側的灌木開始, 每天向右修剪一棵灌木。當修剪了最右側的灌木后, 她會調轉方向, 下一天開 始向左修剪灌木。直到修剪了最左的灌木后再次調轉方向。然后如此循環往復。
灌木每天從早上到傍晩會長高 1 厘米, 而其余時間不會長高。在第一天的 早晨, 所有灌木的高度都是 0 厘米。愛麗絲想知道每棵灌木最高長到多高。
輸入格式
一個正整數?N, 含義如題面所述。
輸出格式
輸出?N?行, 每行一個整數, 第?i?行表示從左到右第?i?棵樹最高能長到多高。
樣例輸入
3樣例輸出
4 2 4評測用例規模與約定
對于?30%?的數據,?N≤10.
對于?100% 的數據,?1<N≤10000.
// 本題大意了，其實挺好解決的。
// 最開始，我傻傻的，造了三個循環去解決本題，好愚蠢的呢，簡單題，做麻煩?
// 其實腦子里面模擬一下，前面割著草，后面長著草，是不是有畫面感了
// 一共n顆灌木，到第i顆灌木時：(n-i-1)*2 or i*2 顆 --取最大?
// 只是兩個方向，從左向右時：i*2
// ? ? ? ? ? ? ?從右向左時：(n-i-1)*2
#include <bits/stdc++.h>
using namespace std;int main(){int n;cin>>n;vector<int> res(n,0);for(int i=0; i<n; ++i){res[i]=max(i*2,(n-i-1)*2);}for(int i:res) cout<<i<<endl;return 0;
}5、X 進制減法
問題描述
進制規定了數字在數位上逢幾進一。
X?進制是一種很神奇的進制, 因為其每一數位的進制并不固定！例如說某 種?X?進制數, 最低數位為二進制, 第二數位為十進制, 第三數位為八進制, 則?X?進制數 321 轉換為十進制數為 65 。
現在有兩個X?進制表示的整數?A?和?B, 但是其具體每一數位的進制還不確 定, 只知道?A?和?B?是同一進制規則, 且每一數位最高為?N?進制, 最低為二進 制。請你算出 A?B?的結果最小可能是多少。
請注意, 你需要保證?A?和?B?在?X?進制下都是合法的, 即每一數位上的數 字要小于其進制。
輸入格式
第一行一個正整數?N, 含義如題面所述。
第二行一個正整數?Ma, 表示?X?進制數?A?的位數。
第三行?Ma??個用空格分開的整數, 表示?X?進制數?A?按從高位到低位順序各 個數位上的數字在十進制下的表示。
第四行一個正整數?Mb?, 表示?X?進制數?B?的位數。
第五行?Mb??個用空格分開的整數, 表示?X?進制數?B?按從高位到低位順序各 個數位上的數字在十進制下的表示。
請注意, 輸入中的所有數字都是十進制的。
輸出格式
輸出一行一個整數, 表示?X?進制數?A?B?的結果的最小可能值轉換為十進 制后再模 1000000007 的結果。
樣例輸入
11 3 10 4 0 3 1 2 0樣例輸出
94樣例說明
當進制為: 最低位 2 進制, 第二數位 5 進制, 第三數位 11 進制時, 減法 得到的差最小。此時?A?在十進制下是?108, B 在十進制下是 14 , 差值是 94。
評測用例規模與約定
對于?30%?的數據,?N≤10; Ma,Mb≤8.
對于?100% 的數據,?2≤N≤1000;1≤Ma?,Mb?≤100000;A≥B.
// 這是一道貪心題，讀清楚題目之后，本題思路就會異常清晰。
// “兩個數，共用一套X進制的規則”
// 質保保證兩個數，盡可能的小就行
// 本題最重要的就是，進制轉換的計算，
//（本位，前方所有進制相乘，就是此位置該乘的數）--> 舉例：10*(2*5)+4*(2)+0*(0)=108?
#include <bits/stdc++.h>
#define int long long
const int CNT = 1000000007;
using namespace std;signed main(){int N;cin>>N;int an,bn;cin>>an;vector<int> A(an,0);for(int i=an-1; i>=0; --i) cin>>A[i];cin>>bn;vector<int> B(bn,0);for(int j=bn-1; j>=0; --j) cin>>B[j];int sum = 0;int X = 1;for(int i=0; i<an; ++i){sum=(sum+(A[i]-B[i])*X)%CNT;X *= max(A[i],B[i])<=1?2:max(A[i],B[i])+1;X%=CNT;}cout<<sum<<endl;return 0;
} 6、統計子矩陣
問題描述
給定一個?N×M 的矩陣?A, 請你統計有多少個子矩陣 (最小?1×1, 最大?N×M) 滿足子矩陣中所有數的和不超過給定的整數?K??
輸入格式
第一行包含三個整數?N,M?和?K.
之后?N?行每行包含?M?個整數, 代表矩陣?A.
輸出格式
一個整數代表答案。
樣例輸入
3 4 10 1 2 3 4 5 6 7 8 9 10 11 12樣例輸出
19樣例說明
滿足條件的子矩陣一共有 19 , 包含:
大小為?1×1?的有 10 個。
大小為?1×2?的有 3 個。
大小為?1×3?的有 2 個。
大小為?1×4?的有 1 個。
大小為?2×1?的有 3 個。
評測用例規模與約定
對于?30%?的數據,?N,M≤20.
對于?70% 的數據,?N,M≤100.
對于?100%的數據,?1≤N,M≤500;0≤Aij≤1000;1≤K≤250000000
運行限制
- 最大運行時間：1s
- 最大運行內存: 256M
本質上就是一道二維前綴和+滑動窗口的集合，如果只用二維前綴和的話只能過70%
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e2 + 5;
int arr[N][N];
int n, m, K;signed main() {// 輸入矩陣的行數、列數和閾值 Kcin >> n >> m >> K;// 輸入矩陣元素for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j)cin >> arr[i][j];// 計算每行的前綴和for (int i = 1; i <= n; ++i)for (int j = 1; j <= m; ++j)arr[i][j] += arr[i][j - 1];// 計算每列的前綴和，得到二維前綴和for (int j = 1; j <= m; ++j)for (int i = 1; i <= n; ++i)arr[i][j] += arr[i - 1][j];int cnt=0;// 上邊界 for(int top=0; top<=n; ++top){// 下邊界 for(int bott=top+1; bott<=n; ++bott){// 左上邊界 int l=0; // 右上邊界 for(int r=1; r<=m; ++r){int sum= arr[bott][r]-arr[bott][l]-arr[top][r]+arr[top][l]; while(sum>K&&l<r){l++;sum= arr[bott][r]-arr[bott][l]-arr[top][r]+arr[top][l];}cnt+=r-l;}} }// 輸出結果cout << cnt << endl;return 0;
} 7、積木畫
問題描述
小明最近迷上了積木畫, 有這么兩種類型的積木, 分別為?I?型（大小為 2 個單位面積) 和?L?型 (大小為 3 個單位面積):
同時, 小明有一塊面積大小為?2×N?的畫布, 畫布由?2×N?個?1×1?區域構成。小明需要用以上兩種積木將畫布拼滿, 他想知道總共有多少種不同的方式? 積木可以任意旋轉, 且畫布的方向固定。
輸入格式
輸入一個整數?N，表示畫布大小。
輸出格式
輸出一個整數表示答案。由于答案可能很大，所以輸出其對 1000000007 取模后的值。
樣例輸入
3樣例輸出
5樣例說明
五種情況如下圖所示，顏色只是為了標識不同的積木：
評測用例規模與約定
對于所有測試用例，1≤N≤10000000.
運行限制
- 最大運行時間：3s
- 最大運行內存: 512M
注：其實很久很久之前，我是很恐懼這種題型的，因為我覺得無解
? ? ? ? 現在發現，竟然能用動態規劃解決，那實在太幸福了。畢竟難總比無解好
// 很多人說，本題是狀態壓縮，其實按照線性dp的思路就能解決。
// 說到動態規劃，大家都清楚，是由前方狀態推出后方狀態
// 當然啦，還有每個狀態的意義，狀態推導公式、初始化，遍歷順序
/*
?? ?每個狀態的意義：！！一定要看清楚?
?? ?dp[i][0] ,第i列，只有第一行被填滿
?? ?dp[i][2] ,第i列，只有第二行被填滿
?? ?dp[i][1] ,第i列，兩整行都被填滿?
*/?
/*
?? ?狀態推導公式：
?? ?dp[i][0]
?? ?如果要使第一行能被填滿，有兩種可能，上一列為dp[i-1][2]，于是可以橫放一個I型
??? ?還有一種可能是，上上一列 為dp[i-2][1]，這種情況下，可以放置一個L型 ??
??? ?于是推導出 dp[i][0]= dp[i-1][2]+dp[i-2][1];
??? ?
??? ?dp[i][2]
??? ?上一列為dp[i-1][0],上一列，第一行有東西，此刻，就能橫向放置I型
?? ?上上一列為dp[i-2][1]，這種情況下，可以放置一個L型?
?? ?于是推導出 dp[i][2]=dp[i-1][0]+dp[i-2][1];
?? ?
?? ?dp[i][1]
?? ?本列想要填滿，只有可能為dp[i-1][0] or dp[i-1][2]，本列可以放置L型
?? ?dp[i-1][1]（上一列被填滿），本列可以放置I型
?? ?dp[i-2][1]（上上一列被填滿），那可以置換成兩個L型?
?? ?dp[i][1]=dp[i-1][0] + dp[i-1][2] + dp[i-1][1] + dp[i-2][1];
*/?
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1000000007;
const int N = 1e7+5;
// vector<vector<int>> dp(N,vector<int>(3,0));
int dp[N][3];signed main(){int n;cin>>n; dp[0][1]=1; // 只能豎放一個I dp[1][1]=1; // 只能豎放一個I ，這個才是真正的第一列。for(int i=2; i<=n; ++i){dp[i][0]=(dp[i-1][2]+dp[i-2][1])%MOD;dp[i][2]=(dp[i-1][0]+dp[i-2][1])%MOD;dp[i][1]=((dp[i-1][0] + dp[i-1][2])%MOD + (dp[i-1][1] + dp[i-2][1])%MOD)%MOD;} cout<<dp[n][1]<<endl;return 0;
}
8、掃雷
題目描述
在一個?n?行?m?列的方格圖上有一些位置有地雷，另外一些位置為空。
請為每個空位置標一個整數，表示周圍八個相鄰的方格中有多少個地雷。
輸入描述
輸入的第一行包含兩個整數?n,m。
第?2?行到第?n+1?行每行包含?m?個整數，相鄰整數之間用一個空格分隔。如果對應的整數為?0，表示這一格沒有地雷。如果對應的整數為?1，表示這一格有地雷。
其中，1≤n,m≤100 分鐘后還是在當天。
輸出描述
輸出?n?行，每行?m?個整數，相鄰整數之間用空格分隔。
對于沒有地雷的方格，輸出這格周圍的地雷數量。對于有地雷的方格，輸出?9。
輸入輸出樣例
示例 1
輸入
3 4 0 1 0 0 1 0 1 0 0 0 1 0輸出
2 9 2 1 9 4 9 2 1 3 9 2運行限制
- 最大運行時間：1s
- 最大運行內存: 128M
本題意想不到的簡單，我人傻了。?
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e2+5;
vector<vector<int>> arr(N,vector<int>(N,0));
// 看到這道題目，我有點炸了，這道題目，咋這么簡答😥，不是哥們，這可是倒數第三題呢。
//int arr[N][N];
//int res[N][N];
vector<vector<int>> res(N,vector<int>(N,0));
int n,m;
int fa1[]={1,1,0,0,-1,1,-1,-1};
int fa2[]={-1,1,1,-1,0,0,1,-1};signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1; i<=n; ++i)for(int j=1; j<=m; ++j) cin>>arr[i][j];// 真嘟假嘟for(int i=1; i<=n; ++i){for(int j=1; j<=m; ++j){if(arr[i][j]!=0) res[i][j]=9;else{int sum=0;for(int k=0; k<8; ++k){if(arr[i+fa1[k]][j+fa2[k]]!=0) sum++;}res[i][j]=sum;}}}for(int i=1; i<=n; ++i){for(int j=1; j<=m; ++j) cout<<res[i][j]<<" ";cout<<endl;}return 0;
}9、李白打酒加強版
問題描述
話說大詩人李白, 一生好飲。幸好他從不開車。
一天, 他提著酒顯, 從家里出來, 酒顯中有酒 2 斗。他邊走邊唱:
無事街上走，提顯去打酒。 逢店加一倍, 遇花喝一斗。
這一路上, 他一共遇到店?N?次, 遇到花?M?次。已知最后一次遇到的是花, 他正好把酒喝光了。
請你計算李白這一路遇到店和花的順序, 有多少種不同的可能?
注意: 顯里沒酒 ( 0 斗) 時遇店是合法的, 加倍后還是沒酒; 但是沒酒時遇 花是不合法的。
輸入格式
第一行包含兩個整數?N?和?M.
輸出格式
輸出一個整數表示答案。由于答案可能很大，輸出模 1000000007 的結果.
樣例輸入
5 10樣例輸出
14樣例說明
如果我們用 0 代表遇到花，1 代表遇到店，14 種順序如下：
010101101000000
010110010010000
011000110010000
100010110010000
011001000110000
100011000110000
100100010110000
010110100000100
011001001000100
100011001000100
100100011000100
011010000010100
100100100010100
101000001010100
評測用例規模與約定
對于?40%?的評測用例:?1≤N,M≤10。
對于?100%?的評測用例:?1≤N,M≤100 。
運行限制
- 最大運行時間：1s
- 最大運行內存: 256M
記憶化搜索+遞歸
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007;
int used[105][105][105];
int n,m,drink;
// 不論是遞歸，還是動規，都是推到至，上一種狀態
int dfs(int n,int m,int drink){if(n<0||m<0||drink<0) return 0;if(drink>m) return 0;if(n==0&&m==1&&drink==1) return 1; // 一切剛剛好 // 記憶化搜索 if(used[n][m][drink]!=-1) return used[n][m][drink]; // 記憶化搜索，代表遍歷過 else {return used[n][m][drink]=(dfs(n-1,m,drink*2)+dfs(n,m-1,drink-1))%MOD; }}
signed main(){cin>>n>>m;memset(used,-1,sizeof used); // 統一初始化，助力記憶化搜索 drink = 2;cout<<dfs(n,m,drink); return 0;
}動態規劃
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007;
int n,m;
int dp[105][105][105];signed main(){cin>>n>>m;// 初始狀態是：經過了0家店、0家花、有2壺酒。// 其實，就是由兩個狀態推導出來的/** dp[n][m][k]: 酒店 dp[n-1][m][drink/2] 他的上一種狀態，可能已經經過n-1店、m家花、擁有drink/2個酒* dp[n][m][k]：花店 dp[n][m-1][drink+1] 他的上一種狀態，可能經過n家店、m-1家花、擁有drink+1杯酒*/dp[0][0][2]=1; // 這是一種可能for(int i=0; i<=n; ++i){for(int j=0; j<=m; ++j){ for(int k=0; k<=m; ++k){if(j>0 && k>0) dp[i][j][k]=dp[i][j-1][k+1];if(i>0 && k%2==0) dp[i][j][k]=(dp[i][j][k]+dp[i-1][j][k/2])%MOD;}}}cout<<dp[n][m-1][1]<<endl;return 0;
}10、砍竹子
問題描述
這天, 小明在砍竹子, 他面前有?n?棵竹子排成一排, 一開始第?i?棵竹子的 高度為?hi?.
他覺得一棵一棵砍太慢了, 決定使用魔法來砍竹子。魔法可以對連續的一 段相同高度的竹子使用, 假設這一段竹子的高度為?H, 那么
用一次魔法可以 把這一段竹子的高度都變為???H2?+1?, 其中??x??表示對?x?向下取整。小明想 知道他最少使用多少次魔法可
讓所有的竹子的高度都變為 1 。
輸入格式
第一行為一個正整數?n, 表示竹子的棵數。
第二行共?n?個空格分開的正整數?hi?, 表示每棵竹子的高度。
輸出格式
一個整數表示答案。
樣例輸入
6 2 1 4 2 6 7樣例輸出
5樣例說明
// 靈感：暴力解法，去最大，找連續，并及時刪除?
// 我忘記了，向上取整，是個啥玩意？？?
// 哪我就斗膽，用一次優先隊列,在具體看一下，優先隊列的用法
/*
? 本題，其實最抽象的就是sqrtl---應用，因為本題最大特色就是，數字有10^18次方這么大，而double只用10^16~17這么大。
? 為啥本題我選擇了優先隊列！畢竟本題是一道貪心題，找規則唄，下方樣例說明中，提示，竹子，是從最高處開始砍的。
? 優先隊列不就是這么玩的嗎😄？
? 然后，又因為能使用魔法（本質就是，坐標相鄰，大小相同的數組....
? 所以一看就要引入pair<int,int>，當然struct也行。兩者構造的時間與占用的空間都差不多。
? 本來我還以為本題，需要用到雙向隊列（模擬）呢，不過，沒想到這是一道中等題，沒考的那么深
? 此外，本題你需要重載一下priority_queue;
? 好了，說正題
? 本題在插入獲取數據的時候，會遇到兩種情況
? 1、一連串相同的，共需用一次魔法
? 2、遇到最大的，砍一次，需用一次魔法
? 3、還有在遇到1時，直接彈出隊列。不需要用到魔法。
? 具體實現方式，在下方的😉
*/
#include <bits/stdc++.h>
#define int long long
#define x first
#define y secondusing namespace std;struct cmp{bool operator()(const pair<int,int>& p1,const pair<int,int>& p2){if(p1.x==p2.x) return p1.y>p2.y; // 小頂堆return p1.x<p2.x; // 不改變符號時，默認為大頂堆 }
};int get_res(int cnt){ // 本題的公式，化簡 return floor(sqrtl(floor(double(cnt)/2)+1));
}signed main(){priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> pq;int n;cin>>n;for(int i=0; i<n; ++i){int num;cin>>num;pq.emplace(num,i); }int cnt=0;int temp_id=-2,temp_cnt=-2;while(!pq.empty()){ // 優先隊列不為空auto cur = pq.top();pq.pop(); // 直接刪除 if(cur.x==1) continue;if(temp_id==cur.y-1&&temp_cnt==cur.x){// 當是下一個相同的值的時候temp_id=cur.y; int val = get_res(cur.x); if(val!=1) pq.emplace(val,temp_id);}else{// 這是一個新的不同的數值cnt++;temp_cnt=cur.x;temp_id =cur.y;int val = get_res(cur.x);if(val!=1) pq.emplace(val,temp_id);}} cout<<cnt;return 0;
} 知識點
一、double 與?long double
double?
- 大小：通常占用 8字節（64位）
- 十進制取值范圍：有效位數 約為15~17位
long double
- 大小：有編譯器決定，標準規定不少于double
但是，在某些編輯器，與double占用的字節（8字節）是相同的
? ? ? ? 在GCC編輯器的x86_64架構下，可能占12字節（96位）；
? ? ? ? 甚至在部分平臺占用16字節（128位）（拓展進度） - 十進制取值范圍：通常比double更大，通常有效位數18-19位
二、揭開 C++ 數學函數后綴的神秘面紗：f、l?與精度戰爭
1、絕對值函數
- fabs(double x) 計算double類型的絕對值
- fabsf(float x) 計算float類型的絕對值
- fabsl(long double x) 計算long double 類型的絕對值
2、取整函數
向上取整
- ceil(double x) ：對double向上取整
- ceilf(float x)：對float向上取整
- ceill(long double x)：對long double向上取整
向下取整
floor(double x)、floor(float x)、floor(long double x)。
四舍五入
round、roundf、roundl
3、開方
sqrt(double x)、sqrtf(float x)、sqrtl(long double x)
4、指數對數函數
三、不用+號的，加法
給出兩個整數 a 和 b , 求他們的和并以整數（int）的形式返回。不能使用 + 等數學運算符。
樣例
輸入：
a = 1
b = 2
輸出：3
其實，這個是根據位運算^(存不進位的結果)與&(存進位的結果)
#include <iostream>
using namespace std;
int main(){int a=5;int b=3;int temp_a,temp_b;while(b!=0){temp_a = a^b; // 存放 不進位數 temp_b = a&b; // 僅存放 進位數 temp_b<<=1; // 將 進位的結果 右移 a=temp_a;b=temp_b; }cout<<a;return 0;
} 四、狀態壓縮動態規劃
五、為什么二維 vector 在 C++ 中慢如蝸牛？—— 數組與 vector 的性能對決
1、內存分配方式
vector<vector<int>>?
- 這是一個二維動態數組，每個內部的vector單獨分配內存。內存的分布是非連續的。
- 訪問代價大，不同vector之間非連續，內存命中率低，會降低訪問速度。
int arr[n][m]
- 內存是連續的，直接分配一個n*m大小的內存，訪問元素時緩存利用率高，性能更優。
- 查找內存也非常方便，(i,j)--base+i*m+j，無序跳躍式訪問。
2、初始化開銷
vector<vector<int>>?
- 在初始化時，需要多次調用構造器，去構造vector。?
int arr[n][m]
- 全局或靜態聲明的數組，在程序剛啟動時直接就能初始化，無需運行時開銷。
3、擴容代價
vector
- 當容量不夠時，會擴容，然后復制拷貝。
- 內存碎片化增加，影響后續分配效率。
靜態數組
- 大小固定，無擴容問題
4、內存占用
vector中，有各種額外元素（size、capacity、allocator等），占用內存更高。
靜態數組，只是存儲容量。
六、memset與sizeof
memset
C 庫函數?void *memset(void *str, int c, size_t n)?用于將一段內存區域設置為指定的值。
memset() 函數將指定的值 c 復制到 str 所指向的內存區域的前 n 個字節中，這可以用于將內存塊清零或設置為特定值。
在一些情況下，需要快速初始化大塊內存為零或者特定值，memset() 可以提供高效的實現。
在清空內存區域或者為內存區域賦值時，memset() 是一個常用的工具函數。
重點！！通常memset是對每一個字節賦值，所以分配時，只能分配0 or -1（負一的補碼為：1111）。-1用來賦值，0一般是用來清空。
void *memset(void *str, int c, size_t n)- str?-- 指向要填充的內存區域的指針。
- c?-- 要設置的值，通常是一個無符號字符。
- n?-- 要被設置為該值的字節數。
#include <bits/stdc++.h>
using namespace std;
int main(){int arr[2][4];cout<<sizeof(arr)<<endl;cout<<sizeof(arr[0])<<endl;cout<<sizeof(arr[0])/sizeof(arr[0][0])<<endl;memset(arr,-1,sizeof(arr));cout<<arr[1][1];return 0;
}
--------------------------------
32
16
4
-1
--------------------------------sizeof
通過上述的例子，應該就能看出，sizeof求的是字節數。
如果更好的建議、請留言，我會 一 一查看。( ?? ω ?? )?
