Try   HackMD

競程觀念(技巧)

前言

在打比賽的時候,以下小技巧可以讓你的成績更好喔!


組隊比賽的成員

通常都是三人一隊,你需要:

  1. 一個程式設計師

    很明顯吧,各位打的是程式比賽欸,他必須要有以下能力:

    不管他的隊友用人類語言講了甚麼,他都必須把它轉成程式。

    e.g. 我要三層迴圈,而且有時候要從第一層然後直接跳到第三層,

    第二層不能執行

    類似這種無理的要求,程式設計師都要寫出來。

  2. 一個數學家

    舉凡時間複雜度、數論都必須用到數學家,

    通常一場比賽都會有一題數論題,

    而數學家就把所有比賽時間砸去那題就對了!

    砸出來,他就是這場比賽的 MVP!

  3. 一個靈媒

    講得「道地」一點,就是一個乩童

    他必須去解動態規劃的題目,

    想出來,把方法告訴程式設計師,

    他就是這場比賽的 MVP!


如果數學家或靈媒沒解出任何題目,沒關係,這很正常

而程式設計師就要聽著隊友無理的要求寫程式就對了,還要去解各類演算法題

當然,如果程式設計師解出了很多演算法題,他也可以成為這場比賽的 MVP。


水題的特別策略

通常一場比賽會有一題水題,

所有隊員應該賽前先分配好誰要「看」哪幾題的題敘,

看到水題的那一刻,請隊中解水題最快的人來解

(如果因為全場都只會一題,這時候比 penalty,你們這隊就會贏)

實用技巧:尾刀

在高強度的程式比賽中,通常你是沒辦法搶首殺的,

而且題目都不是裸題,因此有時候很難判斷哪題很水。

這時可以跟著計分板前排的人解題,因為通常他們解出的第一題都比較水,甚至是全場最水。

這個技巧不只用在第一題,到第二題、第三題通常都有用

但如果真的卡太久或是沒想法,那還是先挖別題試解吧。


時間複雜度

當你看到一個題目,除了算法寫對,你必須計算會不會 TLE

像是 sort 的題目用 bubble sort 通常都不會過。(時間複雜度為

O(N2))

通常需要

O(NlgN) 的算法,例如內建 sort

怎麼算時間複雜度???

  1. 迴圈

    多層迴圈,把你每個迴圈跑的次數乘起來就對了

  2. 很奇怪的遞迴法

    試著想:它比較接近哪一種跑法?

    二分法

    O(lgN)

    線性

    O(N)

    費式數列

    O(ϕN) (
    ϕ=1+52
    ,黃金比例)

  3. 其他

    通常只會出現

    O(n),O(lnn),想想看比較像哪種


太難算的就不勉強了,請估算

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →
(e.g. 建質數表的複雜度),不然就背起來!!!


在算完這些複雜度後,請把變數全都帶進去,計算程式最多大約要跑幾次,

通常時限一秒大約可以換算成

3×108 次運算


p.s. 有時基於常數,運算速度可能比你想像中還慢,因此以

108 以內當作一個好標準

各位自己在解題網站出題的時候,拜託,時限請盡量壓超過:標程時間 +

max(0.3s, 標程時間
×0.5)
,避免被卡常數的問題


IO優化

很多種,記以下這種就好

cin.tie(nullptr), ios_base::sync_with_stdio(false);


寫更簡潔的程式

define

#define all(x) x.begin(), x.end(); sort(all(vec)); // sort all the vector

using

using LL = long long; LL n; //n is the long long type

template

namespace abb { using LL = long long; template<class T> using V = vector<T>; template<class T> using P = pair<T, T>; template<class T> using V2d = vector<vector<T>>; }; using namespace abb; V<int> v; //vector<int> v; V<string> str; //vector<string> str; V2d<LL> vec; //vector<vector<long long>> vec;

黃色鴨鴨法

這是一種 debug 的方法

很簡單,想像你面前有一隻黃色小鴨,現在,請你一行一行地向鴨鴨解釋你的程式碼在做甚麼

聽起來很基本,但這方法可以找出大量的邏輯錯誤,

練久了很有用處喔!

例題 (求第

n 項的費式數列):

code
int main() { int n; int arr[n]; while(cin >> n){ arr[0] = 1, arr[1] = 1; for(int i = 2; i < n; i++) arr[i] = arr[i - 1] + arr[i - 2]; cout << arr[n - 1] << '\n'; } return 0; }

當你很歡樂地講解給黃色鴨鴨聽,到第

3 行:

欸?我的

n 沒設初始值欸
第一個錯誤

到第

5 行時,你會發現:若
n=1
,那 arr[1] 不就 RE 了嗎?
第二個問題

總結:黃色鴨鴨法用的熟悉可以解決很多問題,要學習跳脫主觀思考,客觀地面對你的 code

學習資料&刷題網站

https://hackmd.io/@yjk930805/share