演算法
Big O 時間複雜度
int Binary_Search () {
int L=0, M, R=INF;
while (R-L >1) {
M=(L+R)/2;
if (check(M)) {
L=M;
} else {
R=M;
}
}
return L;
}
競賽會評估時間複雜度,簡單解法比較好
輸入輸出 C-style input/output
格式化 scanf fscanf sscanf
格式化輸出 printf fprintf sprintf
非格式化輸出gets(remove from C++14 fgets
非格式化輸出 puts, fputs
直接輸入輸出 getchar, putchar
Formatted i/o
%% 一個%
%c一個字元或一堆資院
%s一個沒有空白的字串
%[set] 一個只包含set的字元的字串 ,若要寫成不包含 :%[1]
Ex %[^0-9] 存一個沒有0-9的字串
%[][] 右括弧先
%d %i %u(無符號) %o %x 一個整數
%0d可以輸出binary
%a %e(十進位科學記號) %f %lf(倍準) %g 一個符點數
scanf吃進的東西是pointer
%-3d靠左-3格
%f.1 小數點後一位
ex %010.3f 補0補到10格
stream-base i/o
std::cin, std::cout
std::getline std::iostream::getline
<iomanip>:std::setw std::setfill std::setprecision
常見題性
輸入t筆測資,輸出到底幾位
輸出直到eof
EOF:檔案結尾 EOF=-1 是一個巨集
二分搜
要有單調性
輸入整行字串
fgets(word, 128, stdin); 包含空白
c++
getline(cin, name);
輸入以空白分隔的數列
sscanf
string stream (c++)
檔案輸入輸出
freopen
fopen
c++
fstream
&a對a這個變數取位置
while(t–) {
xxxx
}
scanf return 1 2 -1(EOF)
while (~(scanf())) 等同於 while (scanf()!=-1)
EOF ctrl D linux/ ctrl Z windows
using namespace std;
c++ cin cout
cin >> n;
cin >> n >> m;
cout << n
cout << sum << '\n' << flush
cout << sum << endl
gets puts
fgets(buffer, 128, stdin)
getchar putchar
stdin stdout stderr
c++
string s;
getline(cin,s);
會自己分配記憶體
cin.getline() ???好像很類似scanf ,會跳過space
換行
getchar
windows \r\n
linux \n
sscanf(str, "%d", )
c++
#include <iostream>
stringstream ss;
ss << input ;
while (ss>>num) {}
cout << num << endl
Ex
stringstream ss(s)
while (ss >> a)
c++
auto 型別
ex
auto f = fopen("in.txt", "r");
ifstream fin("in.txt")
fin.close()
cin cout VS printf scanf
cin cout 速度其實差不多,但有時比較慢
字串會差不多,
時間會有差是差在endl
因為中間會跑很多層,會累積到一定數量再輸出
c++ 裡,加上endl 會清掉
cout << n << endl 代表清空,丟到螢幕上
ios_base::sync_with_std(false);
只能用c或c++
cin.tie(NULL); 不要和endl同時用
加上面兩行可以加快速度
遞迴 迴圈
考慮一個int x,算 x^n mod m
觀察規律
n&1
inline int f(x) { return x*x; }
inline 會使後面的展開
暴力演算法
快速冪(較難)
剪枝
八后問題
雙向BFS
快速冪
合併排序
最近點對
1<n<10^5
or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Syncing