一椎木、一維數(shù)組轉(zhuǎn)二維下標(biāo)小技巧
“1234x4567“， x在一維數(shù)組中的下標(biāo)為4(i=4);
轉(zhuǎn)化成3*3的二維數(shù)組
1 2 3
4 x 4
5 6 7
x的坐標(biāo)為 (1,1);(x=1,y=1);
x=i/3主到；y=i%3慰技；
當(dāng)將二維數(shù)組中的坐標(biāo)轉(zhuǎn)換成一維數(shù)組下標(biāo)時
k=x*3+y
二构诚、scanf與cin
在算法競賽中只有輸入輸出數(shù)據(jù)規(guī)模在100萬或以上的時候才必須用scanf
否則cin不會影響是否AC贵少，不會使得因為數(shù)據(jù)的輸入和輸出而超時呵俏。
三、注意pow和sqrt函數(shù)的類型
cout << sqrt(45) << endl;
cout << (int)(sqrt(45) + 1) << endl;
pow函數(shù)和sqrt函數(shù)返回的都是double 類型滔灶，需要注意使用數(shù)據(jù)的時候最好用int進(jìn)行強(qiáng)制轉(zhuǎn)換
否則特別容易出錯普碎。（int）強(qiáng)制轉(zhuǎn)換的過程中會直接舍棄掉浮點數(shù)的小數(shù)部分，不進(jìn)行四舍五入
所以如果判斷距離是不是在某一范圍內(nèi)（經(jīng)常使用的是用勾股定理判斷距離問題）录平，這時候直接將結(jié)果加1或減1麻车；
然后再做強(qiáng)制轉(zhuǎn)換。
四斗这、判斷奇偶性
if(i&1)
//i為奇數(shù)
else
i為偶數(shù)
不要使用%了动猬，效率低
五、C++處理小數(shù)常用的三個函數(shù)
1.floor函數(shù)（有小數(shù)則去掉）
功能：把一個小數(shù)向下取整
即就是如果數(shù)是2.2 涝影，那向下取整的結(jié)果就為2.000000
如果是-2.2枣察，向下取整為-3争占；
原型：double floor(doube x);
返回值：
成功：返回一個double類型的數(shù)燃逻，此數(shù)默認(rèn)有6位小數(shù)
無失敗的返回值
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main()
{
double i = floor(2.2);
double j = floor(-2.2);
printf("The floor of 2.2 is %f\n", i);
printf("The floor of 2.2 is %f\n", j);
system("pause");
return 0;
}
2.ceil函數(shù)（有小數(shù)則進(jìn)位）
功能：把一個小數(shù)向上取整
即就是如果數(shù)是2.2 ，那向上取整的結(jié)果就為3.000000
原型：double ceil(doube x);
參數(shù)解釋：
x:是需要計算的數(shù)
返回值：
成功：返回一個double類型的數(shù)臂痕，此數(shù)默認(rèn)有6位小數(shù)
無失敗的返回值
頭文件：#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main()
{
int i = ceil(2.2);
int j = ceil(2.7);
printf("i=%d,j=%d\n", i, j);
system("pause");
return 0;
}
在最短路勁判斷距離的時候 經(jīng)常用根號sqrt（）伯襟；和平方和power等，因為其返回值都是小數(shù) 握童，這時候可以使用ceil處理
例題：競碼編程 畫圓
3.round函數(shù) （四舍五入）
功能：把一個小數(shù)四舍五入
即就是如果數(shù)是2.2 姆怪，那四舍五入的結(jié)果就為2
如果數(shù)是2.5,那結(jié)果就是3
原型：double round(doube x);
參數(shù)解釋：
x:是需要計算的數(shù)
頭文件：#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main()
{
double i = round(2.2);
double x = round(2.7);
double j = round (-2.2);
double y = round(-2.7);
printf("The round of 2.2 is %f\n", i);
printf("The round of 2.7 is %f\n", x);
printf("The round of -2.2 is %f\n", j);
printf("The round of -2.7 is %f\n", y);
system("pause");
return 0;
}
以上三個函數(shù)都可以用一個int類型的變量來接受其返回值，這樣可以同時完成浮點型向整型的強(qiáng)制轉(zhuǎn)換澡绩。也可以定義double型變量接受返回值
int k=ceil(2.3);
輸出3稽揭；
六、 DFS何時返回
這個通過一些練習(xí)發(fā)現(xiàn)了一個規(guī)律
當(dāng)dfs遍歷一個數(shù)組的時候
1.數(shù)組下標(biāo)是從0~n-1的
if(cnt==n)
{
ans=min(ans,sum);
}
2.數(shù)組下標(biāo)是從1~n的
if(cnt>n){
ans=min(ans,sum);
}
七肥卡、※C++含多成員結(jié)構(gòu)體插入結(jié)構(gòu)體隊列問題
這個問題是個棘手的問題
C++11的寫法十分簡單
struct node {
int cnt;
int x;
int y;
}
queue<node> q;
q.push({cnt,x,y});
使用以上的{} 賦值結(jié)構(gòu)體的方式屬于C++11 溪掀，{}中的成員個數(shù)可以任意
但是藍(lán)橋杯不支持C++11的寫法，如果有兩個成員步鉴，可以用pair揪胃，
pair<int,int> p;
queue<p> q;
q.push(make_pair(x,y));
如果有多個成員則需要寫構(gòu)造函數(shù)
struct node {
int cnt;
int x;
int y;
node(int a, int b, int c)
{
cnt = a;
x = b; //有參構(gòu)造函數(shù)
y = c;
}
node() {
cnt = 0;
x = 0; //無參構(gòu)造函數(shù)
y = 0;
}
};
bool in(int x,int y)
{
return x >= 1 && x <= n && y >= 1 && y <= m;
}
void bfs(int x,int y) {
queue<node> q;
q.push(node(a[x][y],x,y));//插入時璃哟，直接使用構(gòu)造函數(shù)對結(jié)構(gòu)體構(gòu)造，然后插入
while (q.size()) {
}
}
八喊递、輸入地圖下標(biāo)1開始問題
char a[N][N];
for (int i = 1; i <= n; i++)
{
cin >> a[i]+1; //這樣寫地圖才能從(1,1)到（n,m）;
}
九随闪、模擬豎式計算
當(dāng)算法題目中出現(xiàn)豎式計算時候，一般根據(jù)人的計算思路骚勘，從最低位到高位進(jìn)行模擬
需要注意的就是進(jìn)位問題
a——被加數(shù)
b——加數(shù)
c——和
t——進(jìn)位
n——n進(jìn)制
1.根據(jù)a b 和t 求c
(a+b+t) mod n=c
2.已知 當(dāng)前位的 a b t 求下一位的進(jìn)位t
t = (a + b + t) / n;
十铐伴、DFS做最短路問題（維護(hù)字典序最小問題）
在DFS過程中維護(hù)當(dāng)前序列和最優(yōu)序列的大小關(guān)系，如果發(fā)現(xiàn)當(dāng)前序列的字典序一定大于最優(yōu)序列俏讹，則可以直接退出盛杰。
具體做法如下：
如果維護(hù)路徑的字典序最小，可以先將答案的vector置成N
每次DFS一遍之后vector都會改變 沒變的位置還是N
if (!state)
{
if (u > ans[cnt]) return true;
//如果大于了當(dāng)前的藐石，則答案一定不如之前的好即供，一定不是最小字典序 直接返回。
if (u < ans[cnt]) state = -1;
}
