何大王

@hush

Joined on Jan 19, 2024

  • by: 何煦(hush) 基本模板 Start template :::spoiler template #include<bits/stdc++.h> //#pragma GCC optimize("O2,unroll-loops") //#pragma GCC target("sse,sse2,ssse3,sse4,avx,avx2") #define int long long
     Like  Bookmark
  • 題目的發想 大致上有兩種出發點: 把生活中常見的問題、數學考卷遇到的問題、其他OJ看到的問題當靈感 先設定某個(或某些)考點,再去想題目 寫題敘 最最最重要的部分: :::danger務必清楚表達題意::: 要以解題者的角度思考過題序是否會出現難以判斷或是有歧義的敘述或是狀況
     Like 2 Bookmark
  • by: hush 內容 這堂課主要會教各種dp的優化,通常會去優化轉移的效率,或是優化儲存空間 前綴和優化 例題: csdc412 題意:
     Like  Bookmark
  • by: hush LIS 求一段長度為$n$的序列$a$的最長遞增子序列(Longest Increase Subsequence)的長度,這裡的子序列不一定要是連續的 定義狀態: 定義$dp[n+1]$,$dp[i]$代表以$a[i]$結尾的LIS長度 轉移式:$dp[i]=\max(dp[j])+1,\ j<i,\ a[j]<a[i]$ 邊界條件(2選1): 1.$\not\exists j<i,\ a[j]<a[i]$ 時 $dp[i]=1$
     Like  Bookmark
  • by: hush 介紹 電腦儲存資料的方法 可以想成是容器 以下將介紹實用的幾種資料結構 以及如何用STL召喚它們 陣列(Array)
     Like  Bookmark
  • by: hush 先偷教一個小技巧「快速冪」 計算$a^n=\overbrace{a\times a\times ...\times a}^\text{n項}$,時間複雜度$O(n)$ 太慢了! 若將$n$換成二進制表示也就是$n_{(10)}=k_0k_1...k_{c(2)}=k_02^c+k_12^{c-1}+...+k_c2^0$ 例如:
     Like  Bookmark
  • by: hush 函式(function)是什麼? 不是韓式炸雞腿 把一段程式碼包裝以便重複使用的工具 優點:使同樣的程式碼容易被重複使用 使整體程式的可讀性提升 拿來遞迴這才是主因
     Like  Bookmark
  • by: hush 概念 貪心演算法(Greedy algorithm) 透過每次都選當下最優解,達到全局最優解 不是所有問題都可以用貪心法解決 常用在最優解問題 遇到類似問題就大膽地猜 要寫greedy證明很重要,通常會利用反證法或是歸納法,不過比賽中的證明不需要太嚴謹
     Like  Bookmark
  • by: hush 概念 合併排序法(Merge sort)的概念是先分割再合併 分割: 就是一直對半分割下去(使用遞迴) 直到序列只剩一個元素就回傳 合併: 將左右兩邊排好的序列合併成一個排好的序列
     Like  Bookmark
  • 1. 理解函式 函式就是你丟問題給它,它就會幫你解決問題。 一般的函式你就是很直觀的寫下去就好,例如: int max(int a,int b) { if (a>b) return a; return b; } 2. 理解遞迴函式
     Like  Bookmark
  • by: hush 概念 先隨機選擇一個基準點(pivot) 把比它小的元素放在它的左邊,大的放右邊 對左右兩邊做重複步驟1, 2,直到剩一個元素 實作上會利用雙指標來進行步驟2 (白板解釋)
     Like  Bookmark
  • by:hush 排序? 排序就是把物品照順序排好 排序演算法是非常重要且基本的工具,很多題目都需要使用到它,也很適合拿來練習實作 各種排序演算法 氣泡排序法(Bubble sort) 方法:
     Like  Bookmark
  • by:hush 枚舉子集(subset) 什麼是子集? 從一個母集合裡挑若干個元素,可以全挑也可以不挑 (集合沒有順序也不重複) 舉例: 定義一個集合$S={1,3,4,6}$ 則 ${4,1}或{1,3,4,6}或{ }$ 為$S$的子集
     Like  Bookmark
  • by:hush 枚舉? 很直觀的做法 就是把所有的可能性都檢查一遍,確保萬無一失 一般的枚舉 舉例:檢查一個數$n$($2\le n\le 10^6$)是否為質數
     Like  Bookmark
  • by : hush 如何判斷一個程式碼的效率呢? 看它的執行的時間和使用的記憶體量多寡 也就是時間複雜度和空間複雜度 時間複雜度 我們先當作所有簡單運算的執行時間都一樣
     Like  Bookmark
  • by:何煦 大綱 演算法 複雜度 枚舉法 二分搜 貪心法 結語
     Like  Bookmark
  • Online Judge(簡稱OJ)是啥? 常見的OJ CSDC OJ (竹中軟研的,歡迎來刷排名) CSDCOJ ZeroJudge (很多高中生在用) ZJ
     Like  Bookmark