{%hackmd @themes/orangeheart %}

# Coding skills


[不知道區賽題目多爛得請看這裡](https://mysh212.github.io/2022/11/15/%E5%AD%B8%E7%A7%91%E5%8D%80%E8%B3%BD%E7%B6%93%E9%A9%97/)


:::spoiler 簡報
<iframe src="https://slides.com/ysh-1/palette/embed" width="576" height="420" title="Coding skills" scrolling="no" frameborder="0" webkitallowfullscreen mozallowfullscreen allowfullscreen></iframe>
:::

## 資源

### 新手

[Zerojudge 前50題](https://zerojudge.tw/)

### 會語法

[AP325 (尤其是 ***DP*** 編得很好)](https://judge.tcirc.tw/Problems?tabid=AP325#tab03)
[這是講義](https://drive.google.com/drive/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m?fbclid=IwAR1XEtjJGZVk_VU1Wzm4gu2uVruFVRco9eDzjgOvIqUeQTkggKlayRMKiz8)

### DP以上 圖論未滿

[cses problemset(各種經典題目)](https://cses.fi/)

### 老手

[Codeforces](https://codeforces.com/)

### 太閒的

[TIOJ(一堆怪題目)](https://tioj.ck.tp.edu.tw/)

### 衝區賽 全國賽

[TIOJ(請寫全國賽、北市賽)](https://tioj.ck.tp.edu.tw/)

### 教材

[不用說](https://hackmd.io/@mysh212/HARC)

## 拿到題目

==讀題敘== -> ==看輸入== -> **確認範圍，是否能暴力解**-> ==二分搜?== -> ==猜演算法== -> ==有信心?==

==有== -> 直接實作
==沒有== -> 寫個暴力解，看能不能撈分 or 悟出什麼東西

> 尤其是區賽 請先看看範圍，因為常常沒出到理論最佳解
> 千萬不要和 ***Mingyee*** 一樣燒

## 善用 `assert`

~~因為區賽常常出錯題目~~ 所以先驗證題目有沒有問題(用 ***RE*** 判斷)

當然也可以用這招作假解

> 回頭譴責某 TOI

int main() {
    int n;cin>>n;
    assert(n <= 2e5);
    return 0;
}

## 時間剪枝

邪教，但有試有機會

舉例來說，時限為一秒

#include<bits/stdc++.h>
using namespace std;
int main() {
    auto t = clock();
    int ans_for_now = INT_MAX;
    
    int n;cin>>n;
    vector<int>f(n);
    
    srand(time(NULL));
    for(int &i : f) {
        cin>>i;
    }
    
    while(clock() - t < 900) {
        int l = rand() % n;
        int r = rand() % n;
        ans_for_now = max(ans_for_now,abs(f.at(l) - f.at(r)));
    }
    
    cout<<ans;
    return 0;
}

如上，題目是給個陣列，找出最大差距。
我們開了個變數 `ans_for_now` 表示 **目前找到最大的答案** ，並且在時間快到的時候再輸出答案。

~~雖然可以用 ***greedy*** 在 $O(1)$ 時間裡完成~~

> cms 建議使用 mt19937

## `#define int long long`

不知道哪邊要改 `long long` ?
那就全改ouob

#include<bits/stdc++.h>
using namespace std;
int main() {
    int a;cin>>a;
    cout<<a;
}

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    int a;cin>>a;
    cout<<a;
}

## segment fault?

遇到這種狀況:

Program received signal SIGSEGV, Segmentation fault.

或是:

terminate called after throwing an instance of 'std::bad_alloc'

  what():  std::bad_alloc

恭喜你獲得了傳說中的 ==RE==
有可能...

- 陣列戳出去
- 遞迴過深
- 陣列開太大
- 記憶體不足
- `while` 沒有中止
- 程式心情不好 不想工作

但錯誤訊息只有這樣是要怎麼 ***debug*** ??

### STL `.at()`

如果你使用的是 `vector` 或 `deque` 可以將 `f[i]` 改成 `f.at(i)`

這樣程式在呼叫時會先確認你是不是有戳出去，有的話會直接將程式中止，並輸出以下訊息:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 3) >= this->size() (which is 3)

`__n` 是你呼叫的數字，上面的意思是說你呼叫了 `f.at(3)` 但 `f` 只有 $3$ 項。

注意:

如果你呼叫 `f.at(-1)` 你會獲得:

terminate called after throwing an instance of 'std::out_of_range'
  what():  vector::_M_range_check: __n (which is 4294967295) >= this->size() (which is 3)

> 偷吃步
> <kbd>Ctrl</kbd> + <kbd>H</kbd> 將 `[` 取代為 `.at(` ； 將 `]` 取代為 `)`

但如果今天不是這問題呢?
遞迴過深? 條件沒寫好?

## gdb

究極黑魔法

首先，編譯你的 ***code***

g++ t.cpp -o t.exe -O2 -std=c++17 -g

gdb t.exe

你會獲得:

GNU gdb (GDB) 7.6.1
Copyright (C) 2013 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show copying"
and "show warranty" for details.
This GDB was configured as "mingw32".
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>...
Reading symbols from .\t.exe...done.

然後提示輸入命令

### 命令

- `l` `list` 列出程式碼
- `b` `breakpoint` 後面接行數，程式執行到這裡會停下來
- `p` `print` 後面接變數名稱，輸出該變數現在的值
- `i b` `info breakpoint` 顯示目前建立了哪些中斷點
- `i s` `info stack` 顯示函式呼叫狀況

大概長這樣

#0  check (x=0) at C:\Users\ysh00\Coding\t.cpp:6
#1  0x0040148d in check (x=2)
    at C:\Users\ysh00\Coding\t.cpp:7
#2  0x0040148d in check (x=4)
    at C:\Users\ysh00\Coding\t.cpp:7
#3  0x0040148d in check (x=6)
    at C:\Users\ysh00\Coding\t.cpp:7
#4  0x0040148d in check (x=8)
    at C:\Users\ysh00\Coding\t.cpp:7
#5  0x004079b8 in check (x=<optimized out>)
    at C:\Users\ysh00\Coding\t.cpp:7
#6  _fu0___ZSt3cin () at C:\Users\ysh00\Coding\t.cpp:14

- `r` `run` 開始執行程式
- `c` `continue` 停下來後，繼續執行程式
- `n` `next` 停下來後，繼續執行完一行
- `s` `step` 停下來後，繼續執行一步

而剛剛講到，正常執行時錯誤訊息有等於沒有，現在使用 `gdb` 執行一次看看:

Program received signal SIGSEGV, Segmentation fault.
0x00407b8c in construct<int, int const&> (this=0xcf1864, 
    __p=0xabababab)
    at c:/mingw/lib/gcc/mingw32/6.3.0/include/c++/ext/new_allocator.h:120
120             { ::new((void *)__p) _Up(std::forward<_Args>(__args)...); }

獲得這咚咚，是 ***STL*** 內部函式出錯，我們使用 `i s` 追蹤問題出現在主程式第幾行

#0  0x00407b8c in construct<int, int const&> (
    this=0xcf1864, __p=0xabababab)
    at c:/mingw/lib/gcc/mingw32/6.3.0/include/c++/ext/new_allocator.h:120
#1  construct<int, int const&> (__a=..., __p=0xabababab)
    at c:/mingw/lib/gcc/mingw32/6.3.0/include/c++/bits/alloc_traits.h:455
#2  push_back (__x=<optimized out>, this=0xcf1864)
    at c:/mingw/lib/gcc/mingw32/6.3.0/include/c++/bits/stl_vector.h:918
#3  _fu2___ZSt3cin () at C:\Users\ysh00\Coding\t.cpp:32

可以看到在 `#3` 這邊行數停留在 $32$ 行，因此問題出現在這裡。