# 競程介紹 ---- ## 講師自介 - handle: owoovo_shih - 全國賽一等 - 選訓二階 - 在APIO被逆( ~~版本更新受害者~~ ) --- # 競程是啥 可以吃嗎 ---- ## 演算法 一連串明確的步驟跟指令，操作完可以得到特定的結果 ---- ## 競技程式 - 在題目的條件下設計演算法在一定的限制下解決問題 - 不要求code好不好看 會動就好 - 通常好好寫不會多於250行 - 即時評測 ---- ## 題目 - 題序 - 記憶體限制、時間限制 - 數據範圍 - 範例測資 ---- ## 題型 - batch - interactive - two steps - output only ---- ## [verdict](https://tioj.ck.tp.edu.tw/about/verdicts) --- # 學習資源 ---- ## 實體的 - 建中讀書會 - 資訊之芽 - IOIC - IONC,APCSC(講師沒去過) ---- ## 學習網站 - 從零開始的演算法競賽入門教學 - 建中校培講義(大部分人首推2016) - OI Wiki - USACO Guide - CP-Algorithms - topic-list([Shahjalal Shohag](https://blog.shahjalalshohag.com/topic-list/), [YouKn0wWho](https://youkn0wwho.academy/topic-list)) - 各個選手自己的blog ---- ## 線上比賽 - codeforces(通常打到大概12點或1點) - atcoder(開心日本時區) - meta hacker cup(每年一次,作息破壞者) - 補題很重要 ---- ## 刷題網站 - CSES - codeforces (list [1](https://cftracker.netlify.app/contests),[2](https://cf.kira924age.com/#/table/) ,[random mashup](https://randommashupgenerator.netlify.app/)) - atcoder ([list](https://kenkoooo.com/atcoder/#/table/), typical 90, dp contest) - cs academy - TIOJ, OJDL - [NTUCPC judge](https://oj.ntucpc.org/) - zerojudge(不推) - luogu - oj.uz, OI checklist --- # 比賽們 ---- ## 團體賽 - ytp(8月)：前十可以做專題 - 成大賽(8月)：要去台南 - HP codewar(10月)：聽說有抽獎 - ISSC：聽說很怪 - NPSC(12月)：非常好，但每校決賽只取三隊 pccorz ---- ## 怎麼進選訓/當國手 有兩種方法進選訓 - 學科能競：校內->北市->全國 - 初選 選訓1J->2J(and APIO)->去玻利維亞/烏茲別克斯坦/? ---- ## 教練 我想打能競 - 校內初選：取大約25人和一些高一的保障名額 - 複選：取11(應該)個和去年全國賽一二等當校隊 - 也因為這樣所以高二以下的全國一二等會拿到TIOJ管理員然後他們要負責隔年的校內賽 - 北市賽(11月)：取10個去打全國賽 - 全國賽(12月)：3個一等獎和7個二等獎能進選訓 pacybworzah ---- ## 能競輸了QQ - 初選資格：海選或apcs實作3或有當年度全國賽 - 初選(3月)： > 初選錄取 18 至 20 名為原則，先依年級分別錄取，高一（含 9 年級以下）、高二、高三 各年級最多先取前四名，其餘人數再依全體考生初選成績高低擇優錄取。 ---- ## 選訓 - 有兩階段(3,4月)，每一階段有兩周 - 取12個人進二階，4個人當國手 - 每周一場模考 - 用模考分數(占最多)、平時成績、APIO算成績 ---- ## 選訓生活 - 捷絲旅 - 做題、vir OI - 聽課 - 體育課 - 怪話集 - 邪惡表格  ----  ----  ----  --- # 其他事 - 關於公假 - 關於段考免考 --- # 閒聊時間結束！ 真的要開始講課了 (簡報是隨意趕快打好的，想看更細節的去資讀看pooh講義) ---- # C++語法 ---- 講師真的不會語法 所以我們來看[從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/10/21/0-index/) --- # 複雜度 ---- 如果$\exists M,f(x)\leq g(x)\times M,\forall x$ 那我們說$f(x)=O(g(x))$ ---- ```=cpp int a[maxn]; for(int i=1;i<=n;i++){ for(int j=i;j<=n;j+=i){ a[i]++; } } ``` ---- ```=cpp for(int i=0;i<(1<<n);i++){ for(int j=0;j<n;j++){ if(i&(1<<j)){ //do something O(1) } } } ``` ---- 一秒可以跑$10^8\sim 10^9$次操作 | 範圍 | 對應的複雜度 | |----------------|--------------| | $n \leq 10$ | $O(n!)$ | | $n \leq 20$ | $O(2^n)$ | | $n \leq 500$ | $O(n^3)$ | | $n \leq 5000$ | $O(n^2)$ | | $n \leq 10^5$ | $O(n\log n)$ | | $n \leq 10^6$ | $O(n)$ | | $n \leq 10^{18}$ | $O(\log n)$ | pacybwoah寫的 ---- 什麼時候要看常數 --- # [遞迴](https://www.google.com/search?q=%E9%81%9E%E8%BF%B4) ---- 記得看終止條件 ---- ```=cpp int fib(int n){ if(n<=1)return 1; return fib(n-1)+fib(n-2); } ``` ```=cpp int gcd(int a,int b){ if(a%b==0)return b; return gcd(b,a%b); } ``` ```=cpp ll inv(ll a){ return a==1?1:(p-p/a)*(inv(p%a))%p; } ``` ```=cpp int tem[maxn]; void c(int pos,int use){ //if(n-use<k-pos)return; if(pos==k){ //do something return; } for(int i=use+1;i<=n;i++){ tem[pos]=i; c(pos+1,i); } } ``` --- # 二分搜 ---- ## 終極密碼 ---- ## 為什麼可以戳一半 000000000111111111111 ---- ## 實作 左閉右開：我們想要找到1,0的分界 ```=cpp int l=minn,r=maxn; while(l<r-1){ int m=(l+r)>>1; if(check(m)){ r=m; }else{ l=m; } } ``` (我們想要開心的保證l永遠是0，r永遠是1，那最後$[l,r]$就會是01分界) ---- 左閉右閉：在我們想找第一個1 ```=cpp int l=minn,r=maxn; while(l!=r){ int m=(l+r)>>1; if(check(m)){ r=m; }else{ l=m+1; } } ``` 推薦在不知道要不要加一時去想$[l,l+1]$的case ---- ## 一些些題目 [typical90_a](https://atcoder.jp/contests/typical90/tasks/typical90_a) [tioj 1337](https://tioj.ck.tp.edu.tw/problems/1337) [tioj 2194](https://tioj.ck.tp.edu.tw/problems/2194) ---- ## 三分搜 ---- 有一個先遞減再遞增(嚴格)的函數$f(x)$ 怎麼找(靠近)最低點？ ---- 戳戳戳 我們戳兩個點然後來看一下會怎樣 在$[a,b]$裡戳到$a<x<y<b$ 三個case看看看，就發現都超好 ---- 在大多數的時間我們通常在凸(凹)函數上三分搜 因為凸(凹)函數可以互相加之後還是凸(凹)函數 ---- ## [che](https://dmoj.ca/problem/cco18p4) --- # 雙指針/單調 ---- 沒時間打了== 我們來看神神pooh --- # 前綴和/差分 ---- 有個數列$a_i$，問$\displaystyle\min_{j\leq i} a_j$ for all i 有個數列$a_i$，問$\displaystyle\sum_{j\leq i} a_j$ for all i 有個數列$a_i$，問一些$(i,j)$的$\displaystyle\sum_{i\leq k\leq j} a_k$ ---- 為什麼+可以 ---- 有關前綴的詢問->前綴和 有關區間的詢問(有反元素的運算($+,\oplus,\times,\cdots$))->前綴和 ---- 多一些些維度？ 好好數數 --- # 分治 ---- 再次來看神神pooh --- # greedy ---- 偷自己的[簡報](https://slides.com/owoovo/greedy) --- # dp ---- [偷偷偷](https://slides.com/becaido/gdp#/3) ---- 觀察題 [agc062b](https://atcoder.jp/contests/agc062/tasks/agc062_b) [oi暴雷](https://oj.uz/problem/view/JOI22_copypaste3)