# APCS202206 注：不建議嘗試學習此處提供的Python解，那可能有礙身心 (? ## [1.數字遊戲](https://zerojudge.tw/ShowProblem?problemid=i399) 作法1:(C++做法) 紀錄各個數字出現次數同時維護眾數數量，由右往左掃描輸出有哪些數字 做法2:(Python做法) 用set排除重複數字後排序，眾數出現次數=4-不重複數字數量 \$O(1)\$ :::spoiler Example Code-C++ (Judged by ZeroJudge) ```cpp= #include<bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(0);cin.tie(0); vector<ll> a(3); vector<ll> c(9,0); for(ll &i : a) cin>>i; vector<ll> ans(1,0); for(ll i : a){ c[i-1]++; ans[0] = max(ans[0],c[i-1]); } for (ll i = 8;i>=0;i--) if(c[i]) ans.push_back(i+1); for (ll i = 0;i<ans.size();i++)cout << ans[i] << " \n"[i+1==ans.size()]; } ``` ::: :::spoiler Example Code-Python (Judged by ZeroJudge) ```python= print(" ".join((lambda o:[str(4-len(o))]+o)(sorted(set(input().split()),reverse=True)))) ``` ::: ## [2.字串解碼](https://zerojudge.tw/ShowProblem?problemid=i400) 反過來做 做法一：(C++做法) 用deque，由右往左掃描，遇到0則放前面，遇到1放後面 做法二：(Python做法) 把對應到0的取出，後面接上對應到1的反過來 \$O(mn)\$ :::spoiler Example Code-C++ (Judged by ZeroJudge) ```cpp= #include<bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(0);cin.tie(0); ll m,n; cin >> m >> n; vector<string> e(m); string s; for (string &o : e) cin >> o; cin >> s; deque<char> dat(s.begin(),s.end()); for (ll i = m-1;i>=0;i--){ ll r = 0; deque<char> nw; for (ll j = n-1;j>=0;j--){ r^=e[i][j]-'0'; if (e[i][j]-'0') nw.push_back(dat[j]); else nw.push_front(dat[j]); } if (r) for (ll j = 0;j<(n>>1);j++) swap(nw[j],nw[n-(n>>1)+j]); dat = nw; } for(char c : dat) cout << c; cout << "\n"; } ``` ::: :::spoiler Example Code-Python (Judged by ZeroJudge) ```python= print((lambda m,n: (lambda e,s,f:sum(bool(s.__setitem__(0,f(s[0],o))) for o in reversed(e))*""+s[0])([input() for _ in range(m)],[input()],(lambda s,e:(lambda ss:ss[n-(n>>1):]+(ss[n>>1] if n&1 else "")+ss[:n>>1] if sum(int(ch) for ch in e)&1 else ss)("".join([s[i] for i in range(n) if e[i]=="0"]+list(reversed([s[i] for i in range(n) if e[i]=="1"])))))))(*map(int,input().split()))) ``` ::: ## [3.雷射模擬](https://zerojudge.tw/ShowProblem?problemid=i401) 紀錄各行列上有哪些點有鏡子，並排序 再直接模擬，查詢的時候用二分搜 \$O(n\log n)\$ :::spoiler Example Code-C++ (Judged by ZeroJudge) ```cpp= #include<bits/stdc++.h> using namespace std; using ll = long long; const ll sz = 30000; int main(){ ios::sync_with_stdio(0);cin.tie(0); ll n; cin >> n; vector<vector<pair<ll,ll>>> rows(sz*3),cols(sz*2); while (n--){ ll x,y,c; cin >> x >> y >> c; y+=sz; rows[y].push_back({x,c}); cols[x].push_back({y,c}); } for (vector<pair<ll,ll>> &v : rows) if (v.size()>1) sort(v.begin(),v.end()); for (vector<pair<ll,ll>> &v : cols) if (v.size()>1) sort(v.begin(),v.end()); bool sus = true; ll facing = 1; // 1=positive 0=negative ll hv = 1; // 1=horizontal 0=vertical ll x = 0; ll y = sz; function<void(vector<pair<ll,ll>>&,ll&)> query = [&](vector<pair<ll,ll>>& line, ll& p){ if (facing){ vector<pair<ll,ll>>::iterator it = upper_bound(line.begin(),line.end(),make_pair(p,1LL)); if (it!=line.end()){ p = (*it).first; facing ^= (*it).second; sus = true; } }else{ vector<pair<ll,ll>>::iterator it = lower_bound(line.begin(),line.end(),make_pair(p,0LL)); if (it!=line.begin()){ it--; p = (*it).first; facing ^= (*it).second; sus = true; } } }; ll ans = 0; while (sus){ sus = false; if (hv) query(rows[y],x); else query(cols[x],y); hv^=1; ans += sus; } cout << ans << "\n"; } ``` ::: :::spoiler Example Code-Python (not completed) ```python= print((lambda l:(lambda s,v:(lambda d:sum(bool(v.__setitem__(5,d[v[2]][v[0]]+v[3]))+bool(bool(v.__setitem__(4,s[v[2]][v[5]][v[2]]==v[0][v[2]]))+bool(v.__setitem__(3,-v[3] if s[v[2]][v[5]][2] else v[3])) if len(l)>v[5]>=0 else v.__setitem__(4,False))+bool(v.__setitem__(1,v[1]+v[4])) for __ in range(1000000) if v[4])*0+v[1])([{v[:2]:k for k,v in enumerate(s[i])} for i in range(2)]))([sorted(l,key=lambda o:o[i^1]*1000000+o[i]) for i in range(2)],[(0,0),0,0,1,True,0]))([(0,0,0)]+[tuple(map(int,input().split())) for _ in range(int(input()))])) ``` ::: ## [4.內積](https://zerojudge.tw/ShowProblem?problemid=i402) 用各種排列方式對齊後，直接兩兩相乘，做最大連續區間和 即掃描一次序列 求 目前前綴和 - 最小前綴和 之最大值 \$O(mn)\$ :::spoiler Example Code-C++ (Judged by ZeroJudge) ```cpp= #include<bits/stdc++.h> using namespace std; using ll = long long; ll solve(vector<ll> &a, vector<ll> &b){ ll la = a.size(); ll lb = b.size(); ll ans = -1e18; for (ll d = -la+1;d<=lb-1;d++){ ll s = 0; ll p = 0; for (ll i = max(0LL,-d); i<min(la,lb-d);i++){ s += a[i]*b[i+d]; ans = max(ans,s-p); p = min(p,s); } } return ans; } int main(){ ios::sync_with_stdio(0);cin.tie(0); ll m,n; cin >> m >> n; vector<ll> x(m),y(n); for (ll &i : x) cin >> i; for (ll &i : y) cin >> i; ll ans = solve(x,y); reverse(y.begin(),y.end()); ans = max(ans,solve(x,y)); cout << ans << "\n"; } ``` ::: :::spoiler Example Code-Python (not completed) ```python= ``` :::