# APCS202206
注：不建議嘗試學習此處提供的Python解，那可能有礙身心 (?
## [1.數字遊戲](https://zerojudge.tw/ShowProblem?problemid=i399)
作法1:(C++做法)
紀錄各個數字出現次數同時維護眾數數量，由右往左掃描輸出有哪些數字
做法2:(Python做法)
用set排除重複數字後排序，眾數出現次數=4-不重複數字數量
$O(1)$
:::spoiler Example Code-C++ (Judged by ZeroJudge)

#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)

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)

#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)

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)

#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)

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)

#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)

:::