競程介紹
講師自介
- handle: owoovo_shih
- 全國賽一等
- 選訓二階
- 在APIO被逆(
版本更新受害者)
競程是啥
可以吃嗎
演算法
一連串明確的步驟跟指令，操作完可以得到特定的結果
競技程式
- 在題目的條件下設計演算法在一定的限制下解決問題
- 不要求code好不好看 會動就好
- 通常好好寫不會多於250行
- 即時評測
題目
- 題序
- 記憶體限制、時間限制
- 數據範圍
- 範例測資
題型
- batch
- interactive
- two steps
- output only
學習資源
實體的
- 建中讀書會
- 資訊之芽
- IOIC
- IONC,APCSC(講師沒去過)
學習網站
- 從零開始的演算法競賽入門教學
- 建中校培講義(大部分人首推2016)
- OI Wiki
- USACO Guide
- CP-Algorithms
- topic-list(Shahjalal Shohag, YouKn0wWho)
- 各個選手自己的blog
線上比賽
- codeforces(通常打到大概12點或1點)
- atcoder(開心日本時區)
- meta hacker cup(每年一次,作息破壞者)
- 補題很重要
刷題網站
- CSES
- codeforces (list 1,2 ,random mashup)
- atcoder (list, typical 90, dp contest)
- cs academy
- TIOJ, OJDL
- NTUCPC judge
- 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++語法
講師真的不會語法
所以我們來看從零開始的演算法競賽入門教學
複雜度
如果\(\exists M,f(x)\leq g(x)\times M,\forall x\)
那我們說\(f(x)=O(g(x))\)
int a[maxn];
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j+=i){
a[i]++;
}
}
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寫的 |
什麼時候要看常數
記得看終止條件
int fib(int n){
if(n<=1)return 1;
return fib(n-1)+fib(n-2);
}
int gcd(int a,int b){
if(a%b==0)return b;
return gcd(b,a%b);
}
ll inv(ll a){
return a==1?1:(p-p/a)*(inv(p%a))%p;
}
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的分界
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
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
一些些題目
三分搜
有一個先遞減再遞增(嚴格)的函數\(f(x)\)
怎麼找(靠近)最低點？
戳戳戳
我們戳兩個點然後來看一下會怎樣
在\([a,b]\)裡戳到\(a<x<y<b\)
三個case看看看，就發現都超好
在大多數的時間我們通常在凸(凹)函數上三分搜
因為凸(凹)函數可以互相加之後還是凸(凹)函數
雙指針/單調
沒時間打了==
我們來看神神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
偷自己的簡報