---
# System prepended metadata

title: C++OJ技巧
tags: [C++Book]

---

# C++OJ技巧
###### tags: `C++Book`

## cout 優化
```cpp=
#include <iostream>
using namespace std;

int main() 
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	// 你真正的 code
	return 0;
}
```
```cpp
cout<<endl;//會flush
cout<<'\n';//效率較佳
```

## 讀測資
直到EOF

```cpp=
int a;
while (cin)
{
	// ...
}
```

==確保存在第一個整數 n== 之後，再輸入 n 個整數。

```cpp=
int n;
int ary[128];
while (cin >> n)
{
	for (int i=0; i<n; i++)
	{
		cin >> ary[i];
	}
	// ...
}
```

如果你使用 scanf() 則可看==回傳值得知正確輸入的東西個數==：
```cpp=
int a, b;
while (scanf("%d%d", &a, &b) == 2)
{
	// ...
}
```

## int 的範圍

### int 
* 2^31-1
* 2147483647
* 2*10^9
### long long
* 2^63-1
* 9*10^18
* printf()使用%lld
### 

## [iomanip](http://www.cplusplus.com/reference/iomanip/)
cout格式化

## 窺探測資
在某筆測資的程式裡面加上while(1) 如果跑到某筆測資就會TLE

## 陣列
* 建議宣告為全域變數
* 宣告在全域的陣列元素會自動初始化為零
:::info
主因是解題過程，時常需要開相當大的陣列，
可能是數百、甚至上千萬個 int。

能夠宣告在區域變數中的大小，
遠較全域來得小，而且每台電腦未必一致。

由於函數呼叫的特性，他會佔用系統 stack 的空間，
會更容易發生遞迴過深等 stack overflow 相關的問題。

這些屬於潛在的、不一定發生但難以預測和判斷的問題。
為了規避不必要的風險，最安穩的方法就是將陣列一律宣告於全域。

更多細節可以參考 Lys0829 所寫的 [這篇文章](https://hackmd.io/tTAs-GXpQIqGLfIrEkfLRA) 或者 google 相關的關鍵字。

:::

---
:::info
初始化時==未指定==（長度不足）的部份，會==自動填入 0==，例如以下：
:::

```cpp=
int dx[4] = {0};
for (int i=0; i<4; i++)
{
	cout << dx[i] << '\n';
}
```

:::warning
一個常見的誤會是將上述寫法誤解成把每一格都填成 0，這是==錯==的；
但真正的意思是：==把第一格填成 0，剩下沒填到的補 0==。
:::

---
`sizeof() //(keyword)` 可以計算變數所佔用的空間大小，單位是位元組（byte）。
藉由除掉每個元素的大小，可以得出元素個數。

---
```cpp=
for (int i=0; i<n; i++)
{
	for (int j=0; j<m; j++)
	{
		cin >> ary[i][j];
	}
}
for(int y=0;x<n;y++){
    for(int x=0;x<n;x++){
        cin>>arr[y][x];
    }
}
```

可知 i 在第一維、j 在第二維，剛好按照英文書寫的順序。
這個順序基於 C++ 的一些優化，會是最快速的。

## esp 誤差

為了避免上述問題，通常我們會為它加上一個極小的值，
再將其轉為整數，以避免因為誤差而死得不明不白。

```cpp=
const double EPS = 1e-7;
```

如此在 287.03 實際被近似為 287.02XXXXXXXXXXX 時，
透過補上 EPS 可以拉回 287.03YYYYYYYY：

![](https://i.imgur.com/g5MKftG.png)

這個誤差修正通常稱其為 eps，
由於只是補上誤差，通常至少要開到 ==1e-5 或者更小==，
以免影響結果。

1e-7 是 C++ 中，常數的科學記號的表示方式，
代表 1 * 10^-7^。
同理，8e7 代表的是 8 * 10^7^。

EPS 除了用常數宣告，也可以用 define 來替代：

```cpp=
#define EPS 1e-7
```

### 千萬不要拿浮點數進行 == 的比較！！

正確的方式是：如果他們的差非常非常的小，就應該判斷它們相等。
也就是說，應該判斷 p-q 的絕對值是否比 EPS 小：

```cpp=
const double EPS = 1e-7;
double p = 1.213;
double q = 3.639 / 3;
cout << (fabs(p-q) < EPS) << '\n';
```
:::info
盡量以不用浮點數的方式計算
:::


## 優化
#### 記憶體體操作的速度遠慢於運算, 尤其是字串的複製速度更慢
*toj
>https://hackmd.io/@ruoXi4chTC2rB4_BWoCYVQ/SJwYvu2-r/%2FIB9_SKGvSBegeYSL48fbMw# C++ OJ 技巧