實中資研7th

@nehs-iced-7th

Public team

Joined on Aug 16, 2021

  • 並查集 Disjoint set union 試想一個情境 今天是開學第一天 而你完全不認識其他的同學 其他的同學也是 他們也完全不認識其他的人 隨著你們越混越熟 這樣你勢必會認識一些人 只要你認識一個同學 你也會跟他的朋友們混在一起 只要你跟一個人有關係 那怕是$(朋友的)^n$都算跟你混一起的 總共有$N$個同學 有$Q$次操作 ($1\le N,Q\le 10^5$)
     Like  Bookmark
  • 基礎圖論 Author:H1de_on_bruH 概要 圖的構成 怎麼存圖? 圖的遍歷:DFS與BFS 甚麼是圖論? 維基百科:
     Like  Bookmark
  • 分治 Author: PixelCat 概要 分治的架構 分治複雜度分析 2.1. 遞迴樹 2.2. 主定理 分治與排序 3.1. 暴力作法 (Bubble Sort, Insertion Sort) 3.2. 歸併排序 Merge Sort
     Like 3 Bookmark
  • 複雜度 Author: PixelCat 概要 什麼是複雜度 如何計算複雜度 複雜度的記號 為何複雜度重要 什麼是複雜度 競程中的複雜度可以指:
     Like  Bookmark
  • 關於 關於競賽組 學習資源 一般主題 基礎語法 進階語法 常用函式庫 標準模板庫STL
     Like  Bookmark
  • 標準模板庫 STL 概要 STL常用容器與用法整理 搭配基礎資結、複雜度服用,風味更佳 STL是什麼 S tandard T emplate L ibrary
     Like  Bookmark
  • C++基礎語法 Author: H1de_on_bruH 概要 一些剛入門C++你需要知道的事 推薦的編輯(譯)環境 Code::blocks Code::blocks是非常好用的IDE,對於新手來說非常好上手,顏色字體設定那些的調起來也很方便
     Like 1 Bookmark
  • 二分搜尋 Author: PixelCat 問題敘述 給你一個只有01的序列,0只會出現在1前面 序列長度是 $N$,第 $i$ 格是 $f(i)$ 像是
     Like  Bookmark
  • 學習資源 競賽程式很大部分依靠自學,很少能找到一個老師或一個網站就教給你所有知識,必須到處自己找資源,思考統整,才會慢慢進步。這裡列出一些我有用過、值得閱讀參考學習資源。 基本功 在開始之前,有最最基本的兩個技能不能不學習。 Google 假如看到不會的、想學的主題,Google絕對是找資料最迅速直接的方式。然而下關鍵字也是有技巧的,一開始可能要花很久找資料,不過經過練習絕對可以進步的。 英文 目前關於演算法的相關資源多數還是英文,各大題庫中英文也占多數,絕對不能排斥讀英文。同樣的,一開始可能會一邊查字典讀很久,但久而久之閱讀也會變快,程式能力和英文能力是可以一起進步的。
     Like 5 Bookmark
  • 輕重鍊剖分 Author:H1de_on_bruH 路徑問題: 假設有個節點為$N$個的樹 每個節點上都有一個點權 有$Q$次詢問 每次詢問$u$跟$v$路徑上所有點的權和 且$N,Q\le 10^5$,我們該怎麼在一秒內執行完? LCA 我們可以用倍增法先$O(N\log N)$預處理 每次詢問花$O(\log N)$查詢 這樣總體的複雜度是$O((N+Q)\log N)$ 在這樣的資料範圍下可以很漂亮的解決這個問題
     Like  Bookmark
  • 最小生成樹MST Author:H1de_on_bruH A市是一個繁榮的城市 有一天市長想要再蓋一個快速道路路網 然而有些路段的花費勢必會因為地價、技術、地形等因素而有所差異 市長想要找到一個能夠聯通所有點的最小花費 而市長聽說你是全實驗最電的競程選手 於是想請你幫他用程式來解決他的煩惱 題目連結 想法1:貪心
     Like  Bookmark
  • 二分圖最大匹配與匈牙利演算法 Author:H1de_on_bruH 何謂二分圖? 試想一個情境 學校裡有很多男生跟女生,他們各自有一些喜歡的對象 而到了歲末舞會,這些男女們就會開始湊成一對一對的 當然這些人中不乏一些渣男渣女,表面上跟你很好,實際上有很多對象 但你是校長,你才不管有哪些人沒有伴,你只在乎最多可以湊出多少對 那調查完所有人喜歡的對象後,我們可以畫出像上方的一張圖,學術上稱之為二分圖
     Like  Bookmark
  • 最短路徑 為甚麼需要最短路徑 要怎麼找到最短路徑? 以下有三種演算法 各有各自的優缺點 需要靠自己多寫題目用心體會 floyd warshall全點對最短路徑 想法非常的直覺 我們枚舉一個$k$當作中繼站 再枚舉一對$(i,j)$當作起訖點
     Like  Bookmark
  • C++與編譯器 Author: PixelCat 章節目錄 [TOC] C++ 是一個編譯式的程式語言。也就是說,給人看的程式碼會先經過「編譯」,成為給機器看的執行檔才被執行;相對於 python 之類直譯式語言。本篇概略介紹 C++ 的編譯器如何運作、以及在競賽中如何利用強大的編譯器為自己所用。 本篇所有指令使用 g++ (GCC) 12.1.0 編譯器。多數 linux 發行版有內建; windows 使用者可以安裝 MinGW (使用 Dev-c++ 或 Code::blocks 自帶的 MinGW 也可以);而 MacOS 因為我沒用過所以請自行解決 QQ
     Like 3 Bookmark
  • LCA 最低共同祖先 Author:H1de_on_bruH 概要 基本知識 作法們 例題們 基本知識
     Like  Bookmark
  • 進階語法-指標與參考 Author: PixelCat 概要 前言 指標 指標與const關鍵字 函數指標 參考 有獎徵答
     Like 3 Bookmark
  • 根號分塊 Author:H1de_on_bruH 概要 根號RMQ 根號分塊 淺談分塊:RMQ(Range Maxium Query) 給你一個長為$N$的數列 詢問$Q$次$[L,R]$區間的最大值 $(1\le N,Q\le 10^5)$
     Like  Bookmark
  • 遞迴 Author: PixelCat 概要 遞迴的架構 遞迴問題複雜度分析 例題們 3.1. 河內塔 3.2. 費氏數列 3.3. 快速冪
     Like  Bookmark
  • 強連通分量 Author:H1de_on_bruH 概要 定義 Tarjan演算法 Kosaraju's演算法 給定一個有向圖 求有幾個強連通分量 強連通分量(簡稱SCC:Strongly Connected Components)的意思是:
     Like  Bookmark
  • STL練習賽題解 A. Bit++ 來源: CF 282A 想法: 直接判斷第二個字元是什麼就好。 :::spoiler 為什麼? 你會發現指令只有四種:
     Like 1 Bookmark