# TBC 002 Editorial ---- Rank.1 :place_of_worship: **[qq11123334](https://toj.tfcis.org/oj/acct/1749/)** Rank.2 :place_of_worship: **[Zaim](https://toj.tfcis.org/oj/acct/11789/)** Rank.3 :place_of_worship: **[sa072686](https://toj.tfcis.org/oj/acct/849/)** --- ## pA. 又帥又潮的男人 Author : DB0917 首殺 : madfarm0711 ---- 簡單的條件判斷，送分題 複雜度 : $O(n)$ ---- code: ```C++ #include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> a(n), b(n); int mxa=0, mxb=0, idxa, idxb; for(int i=0;i<n;i++) { cin >> a[i]; if(a[i]>mxa) { mxa=a[i]; idxa=i; } } for(int i=0;i<n;i++) { cin >> b[i]; if(b[i]>mxb) { mxb=b[i]; idxb=i; } } if(idxa==idxb) cout << idxa+1 << '\n'; else cout << -1 << '\n'; } ``` ---- ### Fun Fact: 這題本來要叫做 "又高又潮的人" 但想了一下覺得聽起來太怪了，就改了 --- ## pB. 帥潮寫數學 Author : DB0917 首殺 : ghostapplemonkey ---- 假設 $x+y=A_i$ 且 $y-x=A_j$ ($1\le i, j \le n$) 那麼你可以發現: 如果 $x$ 和 $y$ 要有解， $\frac{A_i + A_j}{2}$ 必須要是整數 因此答案為 : $\frac{oddcnt \times (oddcnt + 1)}{2} + \frac{evencnt \times (evencnt + 1)}{2}$ ##### \* $oddcnt$ 是奇數出現個數，$evencnt$ 是偶數出現個數 複雜度 : $O(n)$ ---- code: ```C++ #include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll signed main() { ios::sync_with_stdio(0); cin.tie(0); int oc=0, ec=0, n, tmp; cin >> n; while(n--) { cin >> tmp; if(tmp%2) oc++; else ec++; } cout << (oc+1LL)*oc/2LL + (ec+1LL)*ec/2LL << '\n'; } ``` ---- ### Fun Fact: 這題pdf少打了一個條件，就是$x$跟$y$要是整數 ~~但是我覺得這個大家都應該要知道吧~~ --- ## pC. PIZZA MOZZARELLA Author : DB0917 首殺 : sa072686 ---- 仔細觀察後可以發現，題目等同於在問你: 要怎麼排序才能盡可能的不要出現連續相同數字? 觀察到這個性質後 就可以利用貪心演算法解決這題了 複雜度 : $O(n+m)$ ---- code: ```C++ #include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll signed main() { cin.tie(0); ios::sync_with_stdio(0); int n, m, sum=0; cin >> n >> m; vector<int> cnt(m+1, 0); for(int i=0;i<n;i++) { int tmp; cin >> tmp; cnt[tmp]++; } for(int i=1;i<=m;i++) { int tmp; cin >> tmp; sum+=tmp*cnt[i]; } int mxo=(max_element(cnt.begin(), cnt.end())-cnt.begin()), val=cnt[mxo]; if(val<=n-val+1) cout << sum << '\n'; else { int basic=n-val+1, times=(val-basic)/basic, left=(val-basic)%basic; cout << sum+(1+times)*times/2*basic+(times+1)*left << '\n'; } } ``` ---- ### Fun Fact: 這題的題序 (自我介紹) 真的是我們庶務本人寫的 --- ## pD. 噴棋 Author : Blameazu. 首殺 : sa072686 ---- 觀察到，棋子一去不復返，一個點最多走一遍 根本就是DP水題 但是數學好難，我不會 看你要用外積還是畢氏定理硬幹都可以 複雜度 : $O(n^3)$ ---- code (by Blameazu.): ```C++ #include <bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast") #define ll long long #define int ll #define pii pair<int, int> int dp[505]; signed main() { ios::sync_with_stdio(false), cin.tie(0); int n; cin >> n; vector<pii> v(n+1); auto dis = [&](const auto &AA, const auto &BB) -> int { const auto A = v[AA]; const auto B = v[BB]; const auto &[a, b] = A; const auto &[c, d] = B; return (a-c)*(a-c) + (b-d)*(b-d); }; for(int i = 1; i <= n; i++) { cin >> v[i].first >> v[i].second; } for(int i = 1; i <= n; i++) dp[i] = INT_MIN; dp[1] = 0; int ans = 0; for(int i = 1; i <= n; i++) { for(int j = i+1; j <= n; j++) { for(int k = j+1; k <= n; k++) { if(dis(i, j) < dis(k,j) && dis(k, j) < dis(i, k)) { pii A = {v[j].first - v[i].first, v[j].second - v[i].second}; pii B = {v[j].first - v[k].first, v[j].second - v[k].second}; if(A.first * B.second - B.first * A.second == 0 && A.first * B.first + A.second * B.second < 0) { dp[k] = max(dp[k], dp[i] + 1); } } } } ans = max(ans, dp[i]); } cout << ans << '\n'; } ``` ---- code (by DB0917): ```C++ #include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll signed main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<pair<int, int>> vp(n); vector<int> dp(n, INT_MIN); dp[0] = 0; for(auto& [l, r] : vp) cin >> l >> r; for(int j=2;j<n;j++) { for(int i=0;i<j-1;i++) { for(int k=i+1;k<j;k++) { int dx1=vp[k].first-vp[i].first, dx2=vp[j].first-vp[k].first, dy1=vp[k].second-vp[i].second, dy2=vp[j].second-vp[k].second; int dx3=vp[j].first-vp[i].first, dy3=vp[j].second-vp[i].second; bool xs=((dx1>=0 && dx2>=0) || (dx1<=0 && dx2<=0)), ys=((dy1>=0 && dy2>=0) || (dy1<=0 && dy2<=0)); if(xs && ys && (dx1*dy2==dx2*dy1) && dx1*dx1+dy1*dy1<dx2*dx2+dy2*dy2 && dx2*dx2+dy2*dy2<dx3*dx3+dy3*dy3) { dp[j]=max(dp[j], dp[i]+1); } } } } cout << *max_element(dp.begin(), dp.end()); return 0; } ``` ---- ## Fun Fact: 這題為什麼要用賽中HACK制呢 ###### 因為測資生不完了QQ --- ## pE. 礙立斯和爆駁 Author : shorya1835 首殺 : ghostapplemonkey ---- 觀察一下，發現... 唉呦我的媽，Bob根本就是被霸凌 Bob試圖交換的數對Alice下回合必定能復原 而且還會額外加cost，太可憐了吧 ---- 因此對Bob來說最好的操作就是直接結束遊戲! 那麼對於Alice來說她只要選擇結束遊戲或交換即可 這邊暴力掃過去! 複雜度 : $O(n)$ ---- code: ```C++ #include <bits/stdc++.h> using namespace std; template<typename T> using vc = vector<T>; template<typename T> using vvc = vector<vector<T>>; template<typename T> using maxheap = priority_queue<T>; template<typename T> using minheap = priority_queue<T, vector<T>, greater<T>>; using ll = long long; #pragma GCC optimize("Ofast") int main() { ios::sync_with_stdio(0); cin.tie(0); int t; t=1; while(t--) { int n; cin >> n; vc<ll> v(n); ll as=0, bs=0; for(int i=0;i<n;i++) { cin >> v[i]; if(!(i%2)) as+=v[i]; else bs+=v[i]; } ll me = LLONG_MAX, best1 = LLONG_MIN, mo = LLONG_MAX, best2 = LLONG_MIN; for(int i=0;i<n;i++) { if(!(i%2)) { me = min(me, 2*v[i]+i); if(mo != LLONG_MAX) best2 = max(best2, (-2*v[i]+i)-mo); } else { mo = min(mo, -2*v[i]+i); if(me != LLONG_MAX) best1 = max(best1, (2*v[i]+i)-me); } } ll mx = (n%2?n:n-1)-1; mx=max(mx, best1); mx=max(mx, best2); cout << as-bs+mx << '\n'; } } ``` ---- ## Fun Fact: https://codeforces.com/contest/2140/problem/C --- ## pF. 樹上背包問題 Author : DB0917 ---- 大資結，經典的在線求區間最大和 + HLD 裸題，但是在合併區塊的時候要注意 複雜度 : $O(n+q \log ^2 n)$ ---- code: ```C++ #include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll const int MAXN=1000010; const ll NEG = LLONG_MIN/4; struct node { int dp[2][2]={}; bool empty; node() { empty = true; dp[0][0] = dp[0][1] = dp[1][0] = dp[1][1] = NEG; } node(int x) { empty=false; dp[0][0]=NEG; dp[1][0]=dp[0][1]=dp[1][1]=x; } int answer() const { if (empty) return NEG; return max({dp[0][0], dp[0][1], dp[1][0], dp[1][1]}); } node operator+(const node& other) const { if(other.empty) return *this; else if(empty) return other; node res; res.empty=false; res.dp[0][0]=max({answer(), other.answer(), dp[0][1]+other.dp[1][0]}); res.dp[0][1]=max(other.dp[0][1], dp[0][1]+other.dp[1][1]); res.dp[1][0]=max(dp[1][0], dp[1][1]+other.dp[1][0]); res.dp[1][1]=dp[1][1]+other.dp[1][1]; return res; } }; int parent[MAXN], depth[MAXN], heavy[MAXN], sz[MAXN], head[MAXN], pos[MAXN], tmp[MAXN], val[MAXN], cur_pos=0; node seg[MAXN*4]; vector<vector<int>> G(MAXN); int dfs(int now) { sz[now]=1; int mx=0; for(auto& next : G[now]) { if(next==parent[now]) continue; parent[next]=now; depth[next]=depth[now]+1; int s=dfs(next); sz[now]+=s; if(s>mx) { mx=s; heavy[now]=next; } } return sz[now]; } void decompose(int now, int top) { head[now]=top; pos[now]=++cur_pos; if(heavy[now]) decompose(heavy[now], top); for(auto& next : G[now]) { if(next==parent[now] || next==heavy[now]) continue; decompose(next, next); } } void build(int l, int r, int idx) { if(l==r) { seg[idx]=node(val[l]); return; } int mid=(l+r)>>1; build(l, mid, idx<<1); build(mid+1, r, idx<<1|1); seg[idx]=seg[idx<<1]+seg[idx<<1|1]; } void update(int l, int r, int p, int idx, int v) { if(l>p || r<p) return; if(l==r) { seg[idx]=node(v); return; } int mid=(l+r)>>1; if(mid>=p) update(l, mid, p, idx<<1, v); if(mid+1<=p) update(mid+1, r, p, idx<<1|1, v); seg[idx]=seg[idx<<1]+seg[idx<<1|1]; } node query(int nl, int nr, int gl, int gr, int idx) { if(nl>gr || nr<gl) return node(); if(nl>=gl && nr<=gr) return seg[idx]; int mid=(nl+nr)>>1; return query(nl, mid, gl, gr, idx<<1)+query(mid+1, nr, gl, gr, idx<<1|1); } node rev_node(const node &a) { if(a.empty) return a; node b; b.empty = false; b.dp[1][1] = a.dp[1][1]; b.dp[1][0] = a.dp[0][1]; b.dp[0][1] = a.dp[1][0]; b.dp[0][0] = a.dp[0][0]; return b; } int QueryPath(int u, int v, int n) { bool left_has = false, right_has = false; node left_node, right_node; while (head[u] != head[v]) { if (depth[head[u]] >= depth[head[v]]) { node cur = query(1, n, pos[head[u]], pos[u], 1); node cur_rev = rev_node(cur); if (!left_has) left_node=cur_rev, left_has=true; else left_node = left_node + cur_rev; u = parent[head[u]]; } else { node cur = query(1, n, pos[head[v]], pos[v], 1); if (!right_has) right_node = cur, right_has=true; else right_node = cur + right_node; v = parent[head[v]]; } } node mid; if (pos[u] <= pos[v]) mid = query(1, n, pos[u], pos[v], 1); else mid = rev_node(query(1, n, pos[v], pos[u], 1)); node res = mid; if (left_has) res = left_node+res; if (right_has) res = res+right_node; return res.answer(); } signed main() { cin.tie(0); ios::sync_with_stdio(0); int n, q; cin >> n >> q; for(int i=1;i<=n;i++) cin >> tmp[i]; for(int i=1;i<n;i++) { int a, b; cin >> a >> b; G[a].push_back(b); G[b].push_back(a); } dfs(1); decompose(1, 1); for(int i=1;i<=n;i++) val[pos[i]]=tmp[i]; build(1, n, 1); while(q--) { int cmd, u, v; cin >> cmd >> u >> v; if(cmd==1) { int ans=QueryPath(u, v, n); if(ans<0) cout << "BURST\n"; else cout << ans << '\n'; } else { update(1, n, pos[u], 1, v); } } } ``` ---- ## Fun Fact: 這題一點都不Fun --- ## 賽中 & 賽後 ----  為什麼沒有人要撈部分分? ----  貪心題用線段樹過了... orz ----  不要用AI阿... ---- [補題連結](https://toj.tfcis.org/oj/proset/?&order=None&show=all&proclass_id=198) [Feedback](https://forms.gle/koZETxySaTMsSQV98)