---
# System prepended metadata

title: Data Stuctures and Thought Method
tags: [高階競技程式設計]

---

---
tags: 高階競技程式設計
---
# Data Stuctures and Thought Method

- 讓cin加速的方法
```C++
ios::sync_with_stdio(0);
cin.tie(0);
```

- 陣列初始化
```C++=
/* memset example */
#include <stdio.h>
#include <string.h>

int main ()
{
  char str[] = "almost every programmer should know memset!";
  memset (str,'-',6);
  puts (str);
  return 0;
}
```
output:
```
------ every programmer should know memset!
```

:::info
陣列size建議用題目的max value
要動態的化建議用**vector**
:::

STL: 內建的東西
---
### vector
- `vector::size()` and `vector::resize()`
- `vector::assign()` 
  - *[vector::assign - C++ Reference](http://www.cplusplus.com/reference/vector/vector/assign/)*
- `vector::push_back()`

### string
- `string`是`vector`的一種，`vector`有的他都有
- `string::substr()`
  - *[string::substr - C++ Reference](http://www.cplusplus.com/reference/string/string/substr/)*

### 自學清單
- [ ] pair
- [ ] set
- [ ] map

### sort
- 排序通常都是用**字典序(lexicographical)**
- `std::sort()`
  - 可以自己定義`compare function`
  - *[sort - C++ Reference](http://www.cplusplus.com/reference/algorithm/sort/)*

### 題目賞析
- codeforces 1130B
- codeforces 1107A
---

## 演算法設計思維
### 範例問題:最大連續和

### 枚舉
- 暴力解?
### 動態規劃
- dynamic programming?
- 每次遞迴可以用上次遞迴的解
### 分治法
- divide n conquer
- 把一個大問題分成幾個獨立的子問題
  - 把子問題分成子子問題
    - ...
    - 遇到邊界回傳
- recursive???
### greedy
- 每次都做當下看起來最佳的選擇
- O(N)???
```C++
int best = A[1], sum = 0;
for (int R = 1; R <= N; R++) {
sum = max(A[R], sum + A[R]);
best = max(best, sum);
}
```
- 感覺答案不對???
>[time=Wed, Feb 27, 2019 8:48 PM]