--- 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]