Mirror的演算法筆記

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=c652 線段樹開根號,因開根號相加後不等於相加開根號 所以不能用lazy tag傳值快速更新 只能找到區間的葉節點開根號後push up 這裡可以做一個優化 因為開根號很快就會變成1 所以可以設一個tag往上傳遞 當葉節點的值為1時 將tag設為true 如果修改到tag值為true的點時 就不要理他 以下為code #include < bits/stdc++.h > using namespace std ; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); struct node { int l,r; ll sum; bool lazy; void update () { sum = sqrt (sum); } } st[ 300000 * 4 + 1 ]; void push_up ( int x ) { st[x].sum = st[x << 1 ].sum + st[x << 1 | 1 ].sum; st[x].lazy = st[x << 1 ].lazy & st[x << 1 | 1 ].lazy; } void build ( int x , int l , int r ) { st[x].l = l,st[x].r = r,st[x].sum = 0 ,st[x].lazy = 0 ; if (l == r) { cin >> st[x].sum; if (st[x].sum == 1 ) st[x].lazy = 1 ; } else { int mid = (l + r) >> 1 ; build (x << 1 ,l,mid); build (x << 1 | 1 ,mid + 1...

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=d799 維護兩個樹狀數組+前綴和就能達成區間更新和區間求和 以下為code #include < bits/stdc++.h > using namespace std ; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); #define lowbit ( x ) x & ( - x) int n; ll sum[ 500001 ]; struct bit { ll c[ 500001 ]; void update ( int p , int val ) { for (;p <= n;p += lowbit (p)) c[p] += val; } ll query ( int p ) { ll r = 0 ; for (;p > 0 ;p -= lowbit (p)) r += c[p]; return r; } } c1,c2; int main () { AC cin >> n; for (ll i = 1 ;i <= n;i ++ ) { int t; cin >> t; sum[i] = sum[i - 1 ] + t; } int q; cin >> q; while (q -- ) { int v,x,y,k; cin >> v; if (v == 1 ) cin >> x >> y >> k,c1. update (x,k),c1. update (y + 1 , - k),c2. update (x,k * x),c2. update (y + 1 , - k ...

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=d539 這題是求RMQ 可以用Sparse Table去做 不過因為我還不會 就線段樹跑下去 以下為code #include < bits/stdc++.h > using namespace std ; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); struct node { int l,r,max; } st[ 500001 * 4 ]; void push_up ( int x ) { st[x].max = max (st[x << 1 ].max,st[x << 1 | 1 ].max); } void build ( int x , int l , int r ) { st[x].l = l,st[x].r = r,st[x].max = 0 ; if (l == r) cin >> st[x].max; else { int mid = (l + r) >> 1 ; build (x << 1 ,l,mid); build (x << 1 | 1 ,mid + 1 ,r); push_up (x); } } int query ( int x , int l , int r ) { int L = st[x].l,R = st[x].r; if (L >= l && R <= r) return st[x].max; else { int mid = (L + R) >> 1 ,ans = 0 ; if (l <= mid) ans = query (x << 1 ,l,r); if (r > mid) ans = max (ans, query (x ...

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=d799 就線段樹模板 記得存值的變數要開大一點,例如long long 因為開太小吃WA 以下為code #include < bits/stdc++.h > using namespace std ; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); struct node { unsigned int l,r; unsigned long long sum,lazy; void update ( unsigned long long x ) { sum += (r - l + 1 ) * x; lazy += x; } } st[ 500001 * 4 ]; void push_up ( unsigned int x ) { st[x].sum = st[x << 1 ].sum + st[x << 1 | 1 ].sum; } void push_down ( unsigned int x ) { unsigned int lazy = st[x].lazy; st[x << 1 ]. update (lazy),st[x << 1 | 1 ]. update (lazy); st[x].lazy = 0 ; } void build ( unsigned int x , unsigned int l , unsigned int r ) { st[x].l = l,st[x].r = r,st[x].sum = st[x].lazy = 0 ; if (l == r) cin >> st[x].sum; else { unsigned int mid = (r + l) >> 1 ; build (x << 1 ,l,mid); ...

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=a565 這題雖然是stack題 不過只有p需要被丟進stack裡等q出現 所以開個變數模擬一下就好了 以下為code #include < bits/stdc++.h > using namespace std ; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC ll n; while (n -- ) { string s; cin >> s; ll p = 0 ,q = 0 ,l = s. size (); for (ll i = 0 ;i < l;i ++ ) { if (s[i] == ' p ' ) p ++ ; else if (s[i] == ' q ' && p > q) q ++ ; } cout << q << ' \n ' ; } }

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=c123 這題就開一個Stack依序把車廂push進去(1,2,3,........) 然後看輸入的值是否和當前stack的top一樣 一樣就pop 最後看stack是不是空的 以下為code #include < bits/stdc++.h > using namespace std ; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC ll n; while (cin >> n && n) { ll f; while (cin >> f && f) { queue < ll,list < ll >> q; q. push (f); stack < ll,list < ll >> s; for (ll i = 1 ;i < n;i ++ ) cin >> f,q. push (f); for (ll i = 1 ;i <= n;i ++ ) { s. push (i); while (s. size () && s. top () == q. front ()) s. pop (),q. pop (); } cout << (s. size () ? " No \n " : " Yes \n " ); } cout << ' \n ' ; ...

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=d016 Stack跑下去就對了 要注意的是數字可能不止一位 以下為code #include < bits/stdc++.h > using namespace std ; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC string str; ll n1,n2; while ( getline (cin,str)) { stack < ll,list < ll >> s; string t; istringstream iss (str); while (iss >> t) { if (t == " + " ) n2 = s. top (),s. pop (),n1 = s. top (),s. pop (),s. push (n1 + n2); else if (t == " - " ) n2 = s. top (),s. pop (),n1 = s. top (),s. pop (),s. push (n1 - n2); else if (t == " * " ) n2 = s. top (),s. pop (),n1 = s. top (),s. pop (),s. push (n1 * n2); else if (t == " / " ) n2 = s. top (),s. pop (),n1 = s. top (),s. pop (),s. push (n1 / n2); else if (t == " % " ) n2 = s. top (),s. pop (),n1 = s. top (),...

題目鏈接: https://tioj.ck.tp.edu.tw/problems/1221 寫超久........ 這題我用了unordered_set , queue , priority_queue去優化他 超扯...... 思維就是先洗下一個最久才會炒到的菜的鍋子 如範例測資中 3 2 7 1 2 3 1 3 1 2 2是最後才會炒到的菜 所以把2的鍋子先洗掉 以下為code #include < bits/stdc++.h > using namespace std ; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ); int main () { AC ll n,k,p,r = 0 ; cin >> n >> k >> p; vector < ll > v (p); vector < queue < ll,list < ll >>> vq (n + 1 ); for (ll i = 0 ;i < p;i ++ ) cin >> v[i],vq[v[i]]. push (i); for (ll i = 1 ;i <= n;i ++ ) vq[i]. push ( 1 e 9 ); unordered_set < ll > s; priority_queue < pair < ll,ll >> pq; for (ll i = 0 ;i < p;i ++ ) { if (s. find (v[i]) == s. end ()) s. insert (v[i]),r ++ ; if (s. size () > k) { s. erase (pq. top ().second); pq. pop (); } vq[...

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=d784 DP求最優解 dp[i]=max(dp[i-1]+input,input) 要特殊處理全部都是負數的情況 以下為code #include < bits/stdc++.h > using namespace std ; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ),cout. tie ( 0 ); int main () { AC ll num; cin >> num; while (num -- ) { ll n,temp =- 1 e 9 ; bool worst = true ; cin >> n; vector < ll > dp (n + 1 , 0 ); for (ll i = 1 ;i <= n;i ++ ) { ll t; cin >> t; if (t > 0 ) worst = false ; dp[i] = max (t,dp[i - 1 ] + t); temp = max (t,temp); } if (worst) cout << temp << ' \n ' ; else cout <<* max_element (dp. begin (),dp. end ()) << ' \n ' ; } }

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=b589 就DP 下一項是當前項+當前項值 下兩項是當前項+2*當前項 以下為code #include < bits/stdc++.h > using namespace std ; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ),cout. tie ( 0 ); int main () { AC ll n; while (cin >> n && n) { vector < ll > vec (n), dp (n + 2 ); for (ll i = 0 ;i < n;i ++ ) cin >> vec[i]; for (ll i = 0 ;i < n;i ++ ) { dp[i + 1 ] = max (dp[i + 1 ],dp[i] + vec[i]); dp[i + 2 ] = max (dp[i + 2 ],dp[i] + 2 * vec[i]); } cout << max (dp[n],dp[n + 1 ]) << ' \n ' ; } }

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=b855 可知最小值就是兩邊數字越平均越好 所以用0/1背包去湊出所有數字總和的一半 以下為code #include < bits/stdc++.h > using namespace std ; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ),cout. tie ( 0 ); int main () { AC ll t,n; cin >> t; while (t -- ) { cin >> n; vector < ll > vec (n); ll total = 0 ; for (ll i = 0 ;i < n;i ++ ) { cin >> vec[i]; total += vec[i]; } ll half = total / 2 ; vector < ll > dp (half + 1 , 0 ); for (ll i = 0 ;i < n;i ++ ) for (ll j = half;j >= vec[i];j -- ) dp[j] = max (dp[j - vec[i]] + vec[i],dp[j]); cout << dp[half] * dp[half] + (total - dp[half]) * (total - dp[half]) << ' \n ' ; } }

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=c264 想了好久終於想出答案 一眼就能看出是變形的0/1背包 但多了一個力矩要處理 首先要先對力矩做處理 把最重的sort到最前面(越重排在越前面一定越好) 再來寫一個0/1背包的模板上去並把它開成二維 用以存力矩的重量限制 而力矩的計算為每放j個物品就乘j 則轉移曲線為 dp[j][k]=max(dp[j][k],dp[j-1][k-weight[i]*j]+value[i]) 因為不一定能放滿L個 所以答案是 max(dp[i][j])    for i in l    for j in t 以下為code #include < bits/stdc++.h > using namespace std ; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ),cout. tie ( 0 ); int main () { AC ll n,t,l; cin >> n >> t >> l; vector < pair < ll,ll >> vec (n); for (ll i = 0 ;i < n;i ++ ) cin >> vec[i].first >> vec[i].second; sort (vec. begin (),vec. end (), greater <pair<ll , ll>> ()); vector < vector < ll >> dp (l + 1 , vector <ll> (t + 1 , 0 )); for (ll i = 0 ;i < n;i ++ ) for (ll j = l;j >= 1 ;j -- ) for (ll k = t;k >= vec[i].first * j;k --...

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=c264 變形LCS 也是用LCS的邏輯做下去啦 只是改成三個字串都要檢查一次 以下為code #include < bits/stdc++.h > using namespace std ; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ),cout. tie ( 0 ); int main () { AC string s1,s2,s3; cin >> s1 >> s2 >> s3; ll l1 = s1. size (),l2 = s2. size (),l3 = s3. size (); vector < vector < vector < ll >>> dp (l1 + 1 , vector <vector<ll>> (l2 + 1 , vector <ll> (l3 + 1 , 0 ))); for (ll i = 1 ;i <= l1;i ++ ) for (ll j = 1 ;j <= l2;j ++ ) for (ll k = 1 ;k <= l3;k ++ ) if (s1[i - 1 ] == s2[j - 1 ] && s2[j - 1 ] == s3[k - 1 ]) dp[i][j][k] = dp[i - 1 ][j - 1 ][k - 1 ] + 1 ; else dp[i][j][k] = max (dp[i - 1 ][j][k], max (dp[i][j - 1 ][k],dp[i][j][k - 1 ])); cout << dp[l1][l2][l3] << ' \n ' ; }

題目鏈接: https://tioj.ck.tp.edu.tw/problems/1175 LIS+二分搜優化 以下為code #include < bits/stdc++.h > using namespace std; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ),cout. tie ( 0 ); int main () { AC ll n; cin >> n; vector < ll > vec (n); vector < ll > dp; for (ll i = 0 ;i < n;i ++ ) cin >> vec[i]; dp. push_back (vec[ 0 ]); for (ll i = 1 ;i < n;i ++ ) { if (vec[i] > dp. back ()) dp. push_back (vec[i]); else * lower_bound (dp. begin (),dp. end (),vec[i]) = vec[i]; } cout << dp. size () << ' \n ' ; }

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=b184 0/1背包問題 一開始傻傻的把所有都存下來跑 其實可以每次輸入跑一次就好 以下為code #include < bits/stdc++.h > using namespace std; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ),cout. tie ( 0 ); int main () { AC ll n; while (cin >> n) { vector < ll > dp ( 101 , 0 ); while (n -- ) { ll v,c; cin >> v >> c; for (ll j = 100 ;j >= v;j -- ) dp[j] = max (dp[j],dp[j - v] + c); } cout << dp[ 100 ] << ' \n ' ; } }

題目鏈接: https://tioj.ck.tp.edu.tw/problems/2009 先用還原後減掉還原前,得到要用幾步去還原 範例輸入 9 2 1 2 3 4 5 6 7 8 9 1 2 3 4 6 7 7 9 1 如上範例輸出 得到幾步還原之陣列如下 0 0 0 0 1 1 0 1 1 迴圈跑到有值的地方就減掉,並加進答案 注意不要忘記把負數+9(因為可能可以多調整好幾圈) 以下為code #include < bits/stdc++.h > using namespace std; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ),cout. tie ( 0 ); int main () { AC int n,k,r = 0 ; cin >> n >> k; vector <int> dis (n); for ( int i = 0 ;i < n;i ++ ) cin >> dis[i]; for ( int i = 0 ;i < n;i ++ ) { int t; cin >> t; dis[i] = t - dis[i]; if (dis[i] < 0 ) dis[i] += 9 ; } for ( int i = 0 ;i <= n - k;i ++ ) { if (dis[i]) { int t = dis[i]; for ( int j = 0 ;j < k;j ++ ) { dis[i + j] -= t; if (dis[i + j] < 0 ) dis[i + j] += 9 ; } ...

題目鏈接: https://zerojudge.tw/ShowProblem?problemid=d418 同UVA 993: https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=934 這題就從9開始暴力跑下去 都除不盡就-1 直到跑到1就是答案 以下為code #include < bits/stdc++.h > using namespace std; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ),cout. tie ( 0 ); int main () { AC ll num; cin >> num; while (num -- ) { ll n,r = 0 ,p = 1 ; cin >> n; if (n == 1 ) cout << " 1 \n " ; else { bool b = 1 ; while (n != 1 && b) { for (ll i = 9 ;i >= 1 ;i -- ) { if (i == 1 ) b = 0 ; else if ( ! (n % i)) { n /= i; r += p * i; p *= 10 ; break ; } } ...

題目鏈接: https://tioj.ck.tp.edu.tw/problems/1441 這題寫了超久...卡在幾個情況沒想到,這次把他記錄下來 最一開始我寫出的code大概是如下這樣 #include < bits/stdc++.h > using namespace std; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ),cout. tie ( 0 ); int main () { AC ll n,t; bool b = 0 ; cin >> n; stack < ll,list < ll >> s; cin >> t; s. push (t); while ( -- n) { cin >> t; if (t < s. top () ^ b) { b ^= 1 ; s. push (t); } } cout << s. size () + b << ' \n ' ; } 最一開始我用的版本還是沒有把stack修改為list當容器的,直接吃了一個MLE 上面的code還有一個很重要的問題 就是沒注意到XOR的運算優先順序和前後兩個石頭數字相等時應另外處理而不是讓他(t<s.top())=false 此外 應前後兩者的關係不會被其他石頭所影響,則空間可優化 用變數t表示 t=h[i-1] 再者,應取大時若沒取,則h[i+1] ≥h[i] 同理可得取小時若沒取,則h[i+1]≤h[i] 所以每次循環結束都更新t=h[i]必為最優解 code如下 #include < bits/stdc++.h > using namespace std; typedef long long ll; #define AC ios :: sync_with_stdio ( 0 ),cin. tie ( 0 ),cou...