Microsoft Word - ACL chapter00a-1ed.docx

Size: px

Start display at page:

Download "Microsoft Word - ACL044900-chapter00a-1ed.docx"

众链庄
7 years ago
Views:

1 +=

2 1) k k 2) 3) 4) RMQ 5) DP DP DP 6) k iv

3 7) Bash Wythoff Nim SG surreal number 49 序號解題策略和重要演算法所在章節 k Dinic DP 31 DP 32 DP 33 DP v

11 Dinic 12 13 14 15 16 17 18 19 20 21 22 23 24

4 序號解題策略和重要演算法所在章節 Bash game 44 Wythoff game 45 Nim game 46 k SG 49 surreal number vi

5 線上評測系統簡稱網址 POJ ZOJ UVA UVA Ural Ural SGU SGU HDOJ 1) 培養良好的認知結構 2) 提高解題能力 3) 注重解題策略的歸類分析 HDOJ vii

onlinejudge.org/ Ural Ural http://acm.timus.ru/ SGU SGU http://acm.sgu.

6 viii

7 1) k 2) ( k ) 3) 4) ( ) 5) 6) 7)

8 ( log 2 n ) [x, y] k (x k y) [x, y] x y y-x+1 k O(n) O(log 2 n) k [ ] [ ] 3 [ ] 1 [ ] 5 ( 1.1-1) n log 2 n +1 k 1) 2) k 1-2

0] [0 0 1 2 3 4 5 6 7] 3 [1 2 3 0 0] 1 [5 6

9 第 0 層 [ ] 第 3 層第 4 層第 2 層第 1 層 [ ] [ ] [ ] 0 0 [1] [2] [3] [ 4 3 ] [0] [0] [3] [4] [ ] [ 2 3 ] [ ] [ 6 7 ] [5] [6] [7] 離線建構整個查詢區間的劃分樹 [l, r] mid mid= l+r 2 [l, mid] [mid+1, r] i [l, i] [l, mid] [mid+1, r] sorted[] [l, r] soreted[mid] mid= l+r 2 [l, r] [l, mid] [mid+1, r] l i tree[p][i] p i tree[0][] sorted[] tree[0][] toleft[][] toleft[p][i] p i lpos rpos same 1-3

1-1 [ 5 6 4 7 3 ] [ 2 3 ] [ 5 4 3 ] [ 6 7 ] [5] [6] [7] 1.1.1 離線建構整個查詢區間的劃分樹 [l, r] mid mid= l+r 2

10 void build(int l,int r,int dep) if(l==r)return; int mid=(l+r)>>1; int same=mid-l+1; // dep [l,r] // // // [l,r] same for(int i=l;i<=r;i++) if(tree[dep][i]<sorted[mid])same--; int lpos=l; // int rpos=mid+1; for(int i=l;i<=r;i++) // [l,r] if(tree[dep][i]<sorted[mid]) // dep i // // -1 // tree[dep+1][lpos++]=tree[dep][i]; else if(tree[dep][i]==sorted[mid]&&same>0) tree[dep+1][lpos++]=tree[dep][i];same--; else tree[dep+1][rpos++]=tree[dep][i]; toleft[dep][i]=toleft[dep][l-1]+lpos-l; // dep 1 i // build(l,mid,dep+1); // build(mid+1,r,dep+1); // 在劃分樹上查詢子區間 [l, r] 中第 k 大的數 [L, R] [l, r] k (L l, r R) (l==r) (tree[dep][l]) [l, r] k [L, l-1] toleft[dep][l-1] [L, r] toleft[dep][r] [l, r] cnt=toleft[dep][r]-toleft[dep][l-1] cnt k ( [L, mid]) ( [mid+1, R]) [newl, newr] [L, l-1] toleft[dep][l-1]- toleft[dep][l-1] newl=l+toleft[dep][l-1]-toleft[dep][l-1] 1-4

11 [l, r] cnt newr=newl+cnt-1 ( -1 ) [L, mid] [newl, newr] k [l, r] r-l-cnt k- cnt newr [l, r] [r+1, R] [r+1, R] toleft[dep][r]-toleft[dep][r] () r toleft[dep][r]-toleft[dep][r] newr=r+toleft [dep][r]-toleft[dep][r] newl=newr-(r-l-cnt) int query(int L,int R,int l,int r,int dep,int k) // dep // [L,R] // [l,r] k if(l==r)return tree[dep][l]; // [l,r] // k int mid=(l+r)>>1; // int cnt=toleft[dep][r]-toleft[dep][l-1]; // [l,r] if(cnt>=k) // [L,mid] // [newl,newr] k int newl=l+toleft[dep][l-1]-toleft[dep][l-1]; int newr=newl+cnt-1; return query(l,mid,newl,newr,dep+1,k); else int newr=r+toleft[dep][r]-toleft[dep][r]; int newl=newr-(r-l-cnt); return query(mid+1,r,newl,newr,dep+1,k-cnt); // [mid+1,r] // [newl,newr] k-cnt 應用劃分樹解題 [l, r] k 1-5

mid=(l+r)>>1; // int cnt=toleft[dep][r]-toleft[dep][l-1]; // [l,r] if(cnt>=k) // [L,mid] // [newl,newr] k int newl=l+toleft[dep][l-1]-toleft[dep][l-1]; int newr=newl+cnt-1; return

12 1.1.1 K-th Number Macrohard k a[1..n] Q(i, j, k) a[i..j] k a=(1, 5, 2, 6, 3, 7, 4) Q(2, 5, 3) a[2..5] (5, 2, 6, 3) (2, 3, 5, 6) 輸入的第一行是列出陣列的大小 n 和要回答的問題數 m (1 n ,1 m 5000) 第二行列出回答問題的陣列, 即 n 個不同絕對值不超過 109 的整數後面的 m 行是列出的問題描述, 每個問題由 3 個整數組成 :i j 和 k (1 i j n,1 k j-i+1), 表示對應的問題 Q(i, j, k) 對每個問題輸出答案在已排好序的 a[i..j] 段輸出第 k 個數提示 : 本題大量輸入, 採用 C 風格輸入 - 輸出 (scanf, printf), 否則超時 ACM Northeastern Europe 2004 Northern Subregion POJ 2104 n k 1) ( build(1, n, 0)) 1-6

過 109 的整數後面的 m 行是列出的問題描述, 每個問題由 3 個整數組成 :i j 和 k (1 i j n,1 k j-i+1), 表示對應的問題 Q(i, j, k) 對每個問題輸出答案在已排好序的 a[i.

13 2) (a, b, c) query(1, n, a, b, 0, c) [a, b] c #include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> using namespace std; const int MAXN=100010; int tree[30][maxn]; int sorted[maxn]; int toleft[30][maxn]; // // tree[p][i] p i // // // toleft[p][i] p 1 i // build(l, r, deep) query(l, R, l, r, deep, k) static inline int Rint() // Rint() // inline // Rint() struct X int dig[256]; // X() for(int i='0';i<='9';++i) dig[i]=1; dig['-']=1; ; static X fuck; int s=1, v=0 c; // 0 for (;!fuck.dig[c=getchar()];); // if (c=='-') s=0; // else if (fuck.dig[c])v=c^48; // for(;fuck.dig[c=getchar()];v=v*10+(c^48)); // // v return s v :-v; // int main() // int n, m; while( scanf("%d %d" &n &m)) // for(int i=1;i<=n; i++) // scanf("%d" &tree[0][i]); sorted[i]=tree[0][i]; 1-7

deep) query(l, R, l, r, deep, k) static inline int Rint() // Rint() // inline // Rint() struct X int dig[256]; // X() for(int i='0';i<='9';++i) dig[i]=1; dig['-']=1; ; static X fuck; int s=1, v=0

14 return 0; sort(sorted+1 sorted+n+1); build(1 n 0); while(m--) int a b c; scanf("%d %d %d" &a &b &c); printf("%d\n" query(1 n a b 0 c)); // sorted[] // 0 1 // [1, n] // m // // [1, n] // [a, b] c Super Mario 1-8 Mario Mario ( n) i hi Mario h [L, R] Mario 第一行列出整數 T, 表示測試用例的數目對每個測試用例 : 第一行列出兩個整數 n m(1 n 10^5,1 m 10^5),n 是路的長度,m 是查詢次數下一行列出 n 個整數, 表示每塊磚的高度, 範圍是 [0, ] 接下來的 m 行, 每行列出 3 個整數 L R h (0 L R<n,0 h ) 對每個測試用例, 輸出 Case X: (X 是從 1 開始的測試用例的編號 ), 然後列出 m 行, 每行列出一個整數第 i 個整數是針對第 i 個查詢,Mario 可以踩踏上去的磚塊的個數 Case 1:

1.2 Super Mario 1-8 Mario Mario ( n) i hi Mario h [L, R] Mario 第一行列出整數 T, 表示測試用例的數目對每個測試用例 : 第一行列出兩個整數 n m(1 n 10^5,1 m 10^5),n 是路的長度,m 是查詢次數下一

15 ACM/ICPC Asia Regional Hangzhou Online HDOJ 4417 [L, R] H Mario H [L, R] + Mario x x [s, t] =[l, r]=[1, (t-s)+1] mid= l+r 2 [s, t] ( [s, t] mid ) Mario h Mario mid [mid+1, t] Mario mid [s, mid-1] #include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> using namespace std; const int MAXN=100010; int tree[30][maxn]; int sorted[maxn]; int toleft[30][maxn]; // // tree[p][i] p i // // toleft[p][i] p 1 i // build(l, r, deep) query(l, R, l, r, deep, k) int solve(int n,int s,int t,int h) // Mario h // [s,t] int ans=0; // 0 int l=1; // [s,t] [l,r] int r=(t-s)+1; int mid; 1-9

h> #include<algorithm> using namespace std; const int MAXN=100010; int tree[30][maxn]; int sorted[maxn]; int toleft[30][maxn]; // // tree[p][i] p i // //

16 while(l<=r) // Mario [s,t] mid=(l+r)>>1; // int temp=query(1,n,s,t,0,mid); // [s,t] mid if(temp<=h) // Mario h // Mario [s,t] mid // ans=mid; l=mid+1; else r=mid-1; // return ans; // int main() int T; int n,m; int s,t,h; scanf("%d",&t); // int icase=0; // while(t--) icase++; scanf("%d%d",&n,&m); // memset(tree,0,sizeof(tree)); for(int i=1;i<=n;i++) // scanf("%d",&tree[0][i]); sorted[i]=tree[0][i]; // sort(sorted+1,sorted+n+1); // build(1,n,0); // printf("case %d:\n",icase); // while(m--) scanf("%d%d%d",&s,&t,&h); // s++; // 1 t++; printf("%d\n",solve(n,s,t,h)); // Mario // h [s,t] return 0; 1-10

$printf("case %d:\n",icase); // while(m--) scanf("%d%d%d",&s,&t,&h); // s++; // 1 t++; printf("%d\n",solve(n,s,t,h)); // Mario // h [s,t] return 0;$

章節

試題阿財每年年初存入銀行 0000 元, 年利率 %, 每年計息一次, () 若依單利計息, 則第 0 年年底的本利和多少? () 若依複利計息, 則第 0 年年底的本利和約為多少?( 近似值 :0 0 計 ) 編碼 0044 難易中出處高雄中學段考題解答 ()000 元