APCS 2021.09.05

tags: APCS

peienwu
thanksone
Wed, Sep 8, 2021 3:40 PM


原文網址:https://peienwu.com/apcs2109/


P1 七言對聯

題目連結

總共有ABC三種規則,就每一種都比對一次就可以了!

時間複雜度: 共有

n 組對聯,每一組都
O(1)
檢查,時間
O(n)
。(不過n最大也才50,不論什麼複雜度都可以吧)

#include <bits/stdc++.h> #define ll long long #define ld long double #define int long long #define N 50 #define Orz ios::sync_with_stdio(0),cin.tie(0) #define INF 2e18 #define rep(i,l,r) for(int i=l;i<=r;i++) #define all(x) x.begin(),x.end() #define pii pair<int,int> #define x first #define y second using namespace std; int n; bool a[N],b[N],f = 1; signed main(){ Orz; cin>>n; while(n--){ rep(i,1,7)cin>>a[i]; rep(i,1,7)cin>>b[i]; f = 1; if(a[2]==a[4]||a[2]!=a[6]){ cout<<"A";f = 0; } else if(b[2]==b[4]||b[2]!=b[6]){ cout<<"A";f = 0; } if(a[7]!=1 || b[7]!=0){ cout<<"B";f = 0; } if(a[2]==b[2]||a[4]==b[4]||a[6]==b[6]){ cout<<"C";f = 0; } if(f)cout<<"None"<<endl; else cout<<endl; } }

P2 魔王迷宮

題目連結

這一題是去模擬每一個魔王移動的狀況,要特別注意每一輪的國王是同時移動的,沒有先後順序,也就是說一顆炸彈可以炸掉不只一位魔王,如果有多個魔王移動到同一個格子,則他們會一起被炸掉。

時間複雜度: 有點難估計,因為很難確定每一個魔王的移動狀況次數,不過由於數字範圍不大,且

k 只有到500,因此直接做複雜度是可行的。

#include <bits/stdc++.h> #define ll long long #define ld long double #define int long long #define N 100 #define Orz ios::sync_with_stdio(0),cin.tie(0) #define INF 2e18 #define rep(i,l,r) for(int i=l;i<=r;i++) #define all(x) x.begin(),x.end() #define pii pair<int,int> #define x first #define y second using namespace std; int n,m,k; bool maze[N][N],bomb[N][N]; struct node{ int x,y,s,t; bool alive; }mp[505]; signed main(){ Orz; memset(maze,0,sizeof(maze)); cin>>n>>m>>k; rep(i,0,k-1){ cin>>mp[i].x>>mp[i].y; cin>>mp[i].s>>mp[i].t; mp[i].alive = 1; } int now_alive = k; while(now_alive){ memset(bomb,0,sizeof(bomb)); for(int p=0;p<k;p++){ if(mp[p].alive == 0)continue; int i = mp[p].x,j = mp[p].y; maze[i][j] = 1; } for(int p=0;p<k;p++){ if(mp[p].alive == 0)continue; int i = mp[p].x,j = mp[p].y; int nx = i + mp[p].s; int ny = j + mp[p].t; if(nx >= n || nx < 0 || ny >= m ||ny < 0){ now_alive--; mp[p].alive = 0; } else if(maze[nx][ny]){ now_alive--; mp[p].alive = 0; bomb[nx][ny] = 1; } else{ mp[p].x = nx; mp[p].y = ny; } } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(bomb[i][j] == 1) maze[i][j] = 0; } } } int ans = 0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(maze[i][j])ans++; } } cout<<ans<<endl; }

P3 幸運數字

題目連結

以區間最小值作為區分點將數列分成兩半,可以利用線段樹找區間最小值,利用迴圈模擬每一次範圍縮小的情況。

不過這一題比較特別,他的區間範圍一定會越來越小,且區間外的數字也就不需要使用到,因此可以將數列做一次排序,從頭開始找如果遇上區間外的數字則不理他,否則使用它當作區間的分隔點(這一定會是最小值,因為由小到大排序),將區間範圍縮小。

至於挑選左右區間的區間和,則可以透過前綴和

O(1) 算出答案。

時間複雜度: 如果是一個遞增或遞減的序列,則每一次區間大小只會縮減1,此時複雜度為

O(n),加上最一開始的排序是
O(nlogn)
,總共為
O(nlogn)

排序作法

#include <bits/stdc++.h> #define ll long long #define ld long double #define int long long #define N 300005 #define Orz ios::sync_with_stdio(0),cin.tie(0) #define INF 2e18 #define rep(i,l,r) for(int i=l;i<=r;i++) #define all(x) x.begin(),x.end() #define pii pair<int,int> #define x first #define y second using namespace std; int n,arr[N],pref[N]; pii sorted[N]; signed main(){ Orz; cin>>n; rep(i,1,n){ cin>>sorted[i-1].x; arr[i] = sorted[i-1].x; sorted[i-1].y = i; pref[i] = pref[i-1]+arr[i]; } sort(sorted,sorted+n); int ind = 0,l = 1,r = n; while(r>l){ while(sorted[ind].y > r || sorted[ind].y < l)ind++; int left = pref[sorted[ind].y-1]-pref[l-1]; int right = pref[r]-pref[sorted[ind].y]; if(left > right){ r = sorted[ind].y-1; } else{ l = sorted[ind].y+1; } } cout<<arr[l]<<endl; }

線段樹作法

如果用線段樹實作,尋找區間最小值,可以在

O(logn) 的時間內詢問。在最差的情況下,一共會詢問
n
次,因此總時間複雜度一樣是
O(nlogn)
。實作上也不複雜,建立線段樹以及區間詢問,區間修改和懶標之類的東西。可以比較一下時間:

線段樹的表現稍微好一點,不過其實是相當接近的!

#include <bits/stdc++.h> #define ll long long #define ld long double #define int long long #define N 300005 #define Orz ios::sync_with_stdio(0),cin.tie(0) #define INF 2e18 #define rep(i,l,r) for(int i=l;i<=r;i++) #define all(x) x.begin(),x.end() #define pii pair<int,int> #define x first #define y second using namespace std; int n,arr[N],pref[N]; pii seg[4*N]; //建立線段樹[l,r) void build(int cur,int l,int r){ if(r <= l)return; if(r - l <= 1){ seg[cur] = {arr[l],l}; return; } int mid = (l+r)/2; build(2*cur,l,mid); build(2*cur+1,mid,r); if(seg[2*cur].x < seg[2*cur+1].x) seg[cur] = seg[2*cur]; else seg[cur] = seg[2*cur+1]; } //詢問區間最小值,回傳pair pii query(int cur,int l,int r,int ql,int qr){ if(r <= l || ql >= r || qr <= l)return {INT_MAX,INT_MAX}; if(ql <= l && qr >= r)return seg[cur]; int mid = (l+r)/2; pii lft = query(2*cur,l,mid,ql,qr); pii rgt = query(2*cur+1,mid,r,ql,qr); if(lft.x < rgt.x)return lft; return rgt; } signed main(){ Orz; cin>>n; rep(i,1,n){ cin>>arr[i]; pref[i] = pref[i-1]+arr[i]; } build(1,1,n+1); int l = 1,r = n+1; while(r - l > 1){ int ind = query(1,1,n+1,l,r).y; int left = pref[ind-1] - pref[l-1]; int right = pref[r-1] - pref[ind]; if(left > right)r = ind; else l = ind + 1; } cout<<arr[l]<<"\n"; }

歐恩作法

有一種二元樹,我也不知道叫啥,根為全序列最小值,左節點為左邊序列最小值,右節點為右邊序列最小值。

thanksone

建法

紀錄每個位置左、右邊離自己最近、比自己小的,爸爸就是兩個之中比較大的那一個。

thanksone

時間複雜度: 種樹加跑答案總共

O(n)

#include <bits/stdc++.h> #define int long long #define pii pair<int, int> #define ff first #define ss second using namespace std; array<int, 300004> A, S, L, R; array<pii, 300004> tree; void plant(int n){ for(int i = 1; i <= n; i++){ if(A[L[i]] > A[R[i]]) tree[L[i]].ss = i; else tree[R[i]].ff = i; } } int solve(int l, int r, int m){ if(l == r) return A[l]; if(S[m - 1] - S[l - 1] > S[r] - S[m]) return solve(l, m - 1, tree[m].ff); else return solve(m + 1, r, tree[m].ss); } signed main(){ int n; cin >> n; stack<pii> s; pii m = {1e9, 0}; s.push({0, 0}); for(int i = 1; i <= n; i++){ cin >> A[i]; if(A[i] < m.ff) m = {A[i], i}; S[i] = A[i] + S[i - 1]; while(A[i] < s.top().ff){ R[s.top().ss] = i; s.pop(); } L[i] = s.top().ss; s.push({A[i], i}); } plant(n); cout << solve(1, n, m.ss); return 0; }

thanksone

如果把範測的笛卡爾樹具象化,大概長這樣:

8
3 9 4 5 1 6 2 8

大致步驟就是:

  1. 單調隊列建立函數
    L
    以及
    R
    ,表示往左往右看第一個小於自己的數
  2. 建立笛卡爾樹(
    L[i],R[i]
    挑大的作為父節點)
  3. 從根節點開始走訪,左右節點就會分別是左右區間的最小值
  4. 利用前綴和計算區間大小,決定要走左還是右子樹
  5. 走訪到區間長度為
    1
    時即答案!

總共有三個不同的作法,使用到排序、線段樹、笛卡兒樹的作法。其中,他們的間複雜度分別是

O(nlogn)
O(nlogn)
O(n)

  1. 排序作法:AC (0.1s, 9.5MB)
  2. 線段樹作法:AC (84ms, 20.9MB)
  3. 歐恩作法:AC (82ms, 15.6MB)

在笛卡兒樹的作法中,對每一個數字尋找兩側第一個小於它的數字(這可以用單調隊列完成),之後把每一個數字的父親節點設為找到的兩端數字中較大的那一個。

此作法的概念是,假設序列中第

i 個數字找到兩側數字分別是
li
以及
ri
,當他如果是區間最小時,區間必須在
[li+1:ri1]
之中,否則它就不會是最小值了。

至於為何是選擇

max(A[li],A[ri]) 當做父節點?則是因為如果選擇較小的那一個,在縮小區間範圍後,無法確定另外一個是否在區間外,如果包含區間內,則
A[i]
便不會是最小值,違反了定義。換言之,選擇了較大的那一個當作父節點,按照定義當走到這個父節點時,它是區間的最小值,將它排除之後,
A[i]
就會是下一個區間的最小值!

P4 美食博覽會

題目連結

NORMAL 版本

對於序列中k個連續的區間,每一個區間滿足區間內的元素皆不重複,區間範圍可以重疊(不過重疊部分只會算一次),找出這k個連續區間所能覆蓋到的最大長度。

感覺跟背包問題的概念有點像,n個物品可以對應到k個區間,重量則對應到這裡的序列中的數字。這題用DP解。

定義

定義

dp[i][j]
i
個試吃員,看了前
j
個攤位,最多可以吃到幾個攤位。

轉移式

維護一個函數

f[i] 表示如果試吃員吃了第
i
個攤位的美食,他所能吃到最左端的攤位的索引值。也就是說,試吃員可以吃
f[i]
i
攤位的美食。

dp[i][j]=max(dp[i][j1],dp[i1][f[j]1]+jf[j]+1)

轉移式代表了要使用第

i 的攤位作為右端點,或是不要使用(直接用前一個),取兩者的最大值。後面一串加減是計算區間大小

邊界

dp[i][j]=0,for all 0≤i≤k,0≤j≤n

從轉移式可以看到他空間可以用滾動DP優化!

GREEDY的作法?
如果每一次都選擇最大的區間,並將這個區間的值都改成0,做7次,得到答案,是正確的做法嗎?

反例

最大的區間不一定會被完全選到。以下測資:

12 2
5 4 3 2 1 3 4 5 6 4 3 2

如果是Greedy會選擇

213456 ,然後從兩邊挑一邊。答案是
9

但是用DP做會是
54321
加上
56432
,答案是
10

thanksone

時間複雜度: 兩層迴圈總共是

O(kn)

#include <bits/stdc++.h> #define ll long long #define ld long double #define int long long #define N 1000005 #define Orz ios::sync_with_stdio(0),cin.tie(0) #define INF 2e18 #define rep(i,l,r) for(int i=l;i<=r;i++) #define all(x) x.begin(),x.end() #define pii pair<int,int> #define x first #define y second using namespace std; int n,k,dp[2][N],lft[N],arr[N]; int mp[N]; signed main(){ Orz; cin>>n>>k; memset(dp,0,sizeof(dp)); memset(lft,0,sizeof(lft)); memset(mp,0,sizeof(mp)); rep(i,1,n)cin>>arr[i]; int maxn = 0; for(int i=1;i<=n;i++){ if(mp[arr[i]]!=0){ lft[i] = mp[arr[i]]+1; mp[arr[i]] = i; } else{ lft[i] = 1; mp[arr[i]] = i; } lft[i] = max(maxn,lft[i]); maxn = max(maxn,lft[i]); } for(int i=0;i<k;i++){ for(int j=1;j<=n;j++){ dp[1][j] = max(dp[1][j-1],dp[0][lft[j]-1]+j-lft[j]+1); } for(int j=1;j<=n;j++){ dp[0][j] = dp[1][j]; } } cout<<dp[1][n]<<endl; } // 1 1 2 1 4 1 7 1 3 8 // 1 1 2 2 4 4 7 7 7 8

EXTRA 版本

熟悉的題目,大的感人的k。如果依照上面

O(nk)的做法肯定TLE。
俗話說得好 : "好的DP定義是AC的一半"
因此經過一系列通靈,我們得到了一個非常漂亮的定義

thanksone

定義

dp[i]= 必須選第
i
家,
(
能吃最多的攤販數量,需要的人數
)(dp[i]
是一個
pair)

thanksone

轉移式

維護一個函數

L[i] ,其實就是樓上的
f[i]
,但是我比較想要叫他
L

dp[i]=maxj<L[i](dp[j])+iL[i]+1

max(a,b)=a,if(a.first>b.first or (a.first==b.first and a.second>b.second))

thanksone

優化

Aliens優化 : 利用penalty限制人數
每當有一個人加入,便扣除

p 個攤販的業績
當總人數超過
k
,表示
p
不夠大,仍然有太多人利大於弊
反之,當總人數小於
k
,表示
p
太大,有太多人弊大於利
看出來了嗎?
p
可以二分搜喔!

thanksone

時間複雜度: 二分搜加每次DP

O(nlogn)

#include <bits/stdc++.h> #define int long long #define pii pair<int, int> #define ff first #define ss second using namespace std; int n, k; array<int, 100004> A/*num of stands*/, L/*leftest stand can eat to*/, cnt/*count of each num*/; array<pii, 100004> dp; pii add(pii p, int v){ p.ff += v; p.ss++; return p; } pii max(pii a, pii b){ if(a.ff == b.ff) return a.ss > b.ss? a : b; return a.ff > b.ff ? a : b; } pii DP(int p){ //ff = stands visited, ss = people needed pii ans = {0, 0}; int l = 0; for(int i = 0; i < n; i++){ while(l < L[i]) ans = max(ans, dp[l++]); dp[i] = add(ans, i - L[i] + 1 + p); } while(l < n) ans = max(ans, dp[l++]); return ans; } int BIS(){ int l = -n, r = n, mid, ans = 0; pii tmp; while(l != r){ //binary search penalty mid = (l + r) >> 1; tmp = DP(mid); if(tmp.ss < k){ l = mid + 1; ans = max(ans, tmp.ff - mid * tmp.ss); }else r = mid; } return max(ans, DP(l).ff - l * k); } signed main(){ cin >> n >> k; int l = 0; for(int i = 0; i < n; i++){ cin >> A[i]; cnt[A[i]]++; while(cnt[A[i]] > 1) cnt[A[l++]]--; L[i] = l; } cout << BIS(); return 0; }

感謝 東霖 幫忙抓bug

thanksone