The 2024 Damascus University Collegiate Programming Contest
===
比賽鏈結
---
https://codeforces.com/gym/105242/

比賽影片
---
{%youtube JrUnYP879fE%}

記分板
---

題解
---
### A. Replace with MEX
---
#### 題目摘要
給一序列，可以將一個區間的值都改成那區間的mex(此操作最多一次)，問整個序列的最大mex

#### 想法

:::spoiler 實作

:::

### B. Powerful String
---
#### 題目摘要
設字串的power為$\prod\limits_{i=1}^{m}i^{f_t(t_i)}$，$f_t(t_i)是字元t_i在字串t的出現次數$。給定一個字串，每筆詢問給一個$l,\ r$，問範圍在$[l,\ r]$的子字串能不能交換兩數使power變大

#### 想法
注意到若$i<j,\ f(t_i)>f(t_j)$則power會上升，故對於每個字元，用$f_t$值去排序，並紀錄目前$f_t$值比我小的最右端的位置，看我目前字元的左端有無小於那個右端就好，複雜度$O(n+26q\log n)$

:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(a, b, c) for (int a = b; a < c; a++)
#define pii pair<int, int>
#define F first
#define S second

const int N=2e5+10;
vector<int> pos[30];
char s[N];
int pre[N][30];

void solve() {
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> s[i];
    for(int i=0;i<26;i++) pos[i].push_back(0);
    for(int i=1;i<=n;i++){
        for(int j=0;j<26;j++) pre[i][j]=pre[i-1][j];
        pre[i][s[i]-'a']++;
        pos[s[i]-'a'].push_back(i);
    }
    for(int i=0;i<26;i++) pos[i].push_back(n+1);
    int q;
    cin >> q;
    while(q--){
        int l, r;
        cin >> l >> r;
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        for(int j=0;j<26;j++){
            int ocur=pre[r][j]-pre[l-1][j];
            if (ocur) pq.push({ocur, j});
        }
        int R=0;
        int RR=0;
        int last=0;
        bool res=0;
        while(!pq.empty()){
            auto [trash, x]=pq.top();
            pq.pop();
            auto it1=lower_bound(pos[x].begin(), pos[x].end(), l);
            auto it2=upper_bound(pos[x].begin(), pos[x].end(), r);
            it2--;
            if (l<=(*it1)&&(*it1)<=(*it2)&&(*it2)<=r){
                if (last!=trash) R=max(R, RR);
                if (R>(*it1)) res=1;
                last=trash;
                RR=max(RR, (*it2));
            }
        }
        cout << (res?"YES":"NO") << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    solve();
}

:::

### C. Tree Tour
---
#### 題目摘要
給一顆樹，問有沒有一個路途經過所有點一或二次

#### 想法
注意到每點度數不能超過3，可以先把這個case判掉，再來標記所有度數3的點，會發現必須要是一條鍊才行，將這些case判掉就好了

:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(a, b, c) for (int a = b; a < b; a++)

const int N=2e5+10;
vector<int> v[N];
int in[N];

int rt;
void dfs1(int x, int p){
    if (in[x]==3) rt=x;
    for(auto e:v[x]) if (e!=p){
        dfs1(e, x);
    }
}

bool ans;
bool dfs2(int x, int p){
    bool res=(in[x]==3);
    int cnt=0;
    for(auto e:v[x]) if (e!=p){
        bool tmp=dfs2(e, x);
        cnt+=tmp;
        res|=tmp;
    }
    if (cnt>1) ans=0;
    return res;
}

void solve() {
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) in[i]=0;
    for(int i=1;i<n;i++){
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
        in[a]++, in[b]++;
    }
    int mx=0;
    for(int i=1;i<=n;i++) mx=max(mx, in[i]);
    if (mx>=4){
        cout << "NO\n";
        for(int i=1;i<=n;i++) v[i].clear();
        return;
    }
    dfs1(1, 0);
    ans=1;
    dfs2(rt, 0);
    cout << (ans?"YES":"NO") << '\n';
    for(int i=1;i<=n;i++) v[i].clear();
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t;
    while(t--) solve();
}

:::

### D. You Have Been Grid Squared
---
#### 題目摘要
有一個$n\times n$的格子，第$i$行的數從上到下依序是$i,\ i^2,\ i^4,\ i^8...$，問不同數字的個數

#### 想法
經過一番推理可以的到答案是$(非平方數個數\times n+平方數個數)$

:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(a, b, c) for (int a = b; a < b; a++)

const int N=1e5+10;
ll dp[N];
map<ll, bool> mp;

void solve() {
    int n;
    cin >> n;
    cout << (dp[n]*n+(n-dp[n])) << '\n';
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    dp[1]=0;
    for(int i=1;i<=100000;i++) mp[1LL*i*i]=1;
    for(int i=2;i<=100000;i++){
        dp[i]=dp[i-1];
        if (!mp[i]) dp[i]++;
    }
    int t;
    cin >> t;
    while(t--) solve();
}

:::

### E. Prefix GCD
---
#### 題目摘要
算將一數移除後的最大前綴gcd和

#### 想法
注意到會讓gcd減少的位置最多只會有$\log A_i$個，所以只要把那些點及第一個數抓出來刪掉後計算取max就好，複雜度$O(n\log A_i)$

:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(a, b, c) for (int a = b; a < c; a++)
#define all(x) (x).begin(), (x).end()
#define int ll

const int IINF = 1e9 + 7;
const int N=1e5+10;
ll a[N];

void solve() {
    int n;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    ll ans=0;
    int g=a[1];
    int g1=a[2];
    vector<int> p;
    for(int i=2;i<=n;i++){
        int tmp=__gcd(g, a[i]);
        g1=__gcd(g1, a[i]);
        if (tmp!=g) p.push_back(i);
        g=tmp;
        ans+=g1;
    }
    for(auto x:p){
        ll sum=a[1];
        g=a[1];
        for(int i=2;i<=n;i++) if (i!=x){
            g=__gcd(g, a[i]);
            sum+=g;
        }
        ans=max(ans, sum);
    }
    cout << ans << '\n';
}

main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int t = 1;
    // cin >> t; 
    while(t--) solve();
}

:::

### F. Queries on Distincts
---
#### 題目摘要
給一個只有小寫字母的字串
Q筆詢問問最小區間$s[i \dots j] \ (l \le i \le j \le r)$裡的distinct char等於 $s[l \dots r]$的distinct char
#### 想法
$對每個位置i去記錄從他出發找到j個不同字元的最小右界r$在哪，如此一來我們可以知道要找到j個不同字元從每個位置要延伸的大小，開26個資結(稀疏表、線段樹...)去維護區間最小值。

在回答每筆詢問前，先找到區間不同的字元有幾個，再將qr的範圍做限制，因為有可能找到的答案右界會是超出qr的，然後就直接輸出。
:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(a, b, c) for (int a = b; a < c; a++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define lpos pos << 1
#define rpos pos << 1 | 1

const int IINF = 1e9 + 7;

struct SparseTable{
    vector<vector<int>> sp;
    SparseTable(vector<int> &a) {
        int n = a.size();
        sp.resize(n, vector<int>(__lg(n) + 1));
        for (int i = n - 1; i >= 0; i--) {
            sp[i][0] = a[i];
            for (int j = 1; i + (1 << j) <= n; j++) {
                sp[i][j] = min(sp[i][j - 1], sp[i + (1 << j - 1)][j - 1]);
            }
        }
    }
    auto query(int l, int r) { // [l, r)
        int k = __lg(r - l);
        return min(sp[l][k], sp[r - (1 << k)][k]);
    }
};

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    vector<queue<int>> c(26);
    vector pre(n, vector<int>(26, 0));
    rep (i, 0, n) {
        c[s[i] - 'a'].push(i);
        if (i) rep (j, 0, 26) pre[i][j] = pre[i - 1][j];
        pre[i][s[i] - 'a']++;
    }
    set<int> st;
    rep (i, 0, 26) if (!c[i].empty()) st.insert(c[i].front());
    vector to(n, vector<int>(26, n));
    rep (i, 0, n) {
        st.erase(c[s[i] - 'a'].front());
        c[s[i] - 'a'].pop();
        to[i][0] = i;
        int id = 0;
        for (int pos : st) {
            id++;
            to[i][id] = pos;
        }
        if (!c[s[i] - 'a'].empty()) st.insert(c[s[i] - 'a'].front());
    }
    // rep (i, 0, n) rep (j, 0, 26) {
    //     cout << to[i][j] << " \n" [j == 25];
    // }
    vector<SparseTable> distinct; // 0-base
    rep (i, 0, 26) {
        vector<int> tmp;
        rep (j, 0, n) {
            if (to[j][i] == n) tmp.pb(n);
            else tmp.pb(to[j][i] - j + 1);
        }
        SparseTable sp(tmp);
        distinct.pb(sp);
    }
    int q; cin >> q;
    while (q--) {
        int l, r; cin >> l >> r;
        l--, r--;
        int d = -1;
        rep (i, 0, 26) {
            d += ((pre[r][i] - (l ? pre[l - 1][i] : 0)) > 0);
        }
        int L = l, R = r + 1;
        while (R - L > 1) {
            int mid = L + R >> 1;
            if (to[mid][d] <= r) L = mid;
            else R = mid;
        }
        r = L + 1;
        // cout << d << ' ' << l << ' ' << r << '\n';
        cout << distinct[d].query(l, r) << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int t = 1;
    // cin >> t; 
    while(t--) solve();
}

:::

### G. Lexicographically Maximum
---
#### 題目摘要

#### 想法
判case+greedy
:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(a, b, c) for (int a = b; a < c; a++)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define lpos pos << 1
#define rpos pos << 1 | 1

const int IINF = 1e9 + 7, MAXN = 1e6 + 5;

void solve() {
    string s; cin >> s;
    int n = s.size();
    vector<queue<int>> q(26);
    rep (i, 0, n) {
        q[s[i] - 'a'].push(i);
    }
    set<int> st;
    rep (i, 0, 26) if (!q[i].empty()) st.insert(q[i].front());
    string t = "";
    rep (i, 0, n) {
        if (st.size() > s[i] - 'a' + 1) {
            int id = *st.rbegin();
            id++;
            while (id < n && s[id] - 'a' + 1 <= st.size()) id++;
            int cur = i;
            int sz = st.size();
            while (cur < id) {
                t.pb('a' + sz - 1);
                st.erase(q[s[cur] - 'a'].front());
                q[s[cur] - 'a'].pop();
                if (!q[s[cur] - 'a'].empty()) st.insert(q[s[cur] - 'a'].front());
                cur++;
            }
            i = id - 1;
        } else {
            auto it = st.begin();
            if (st.size() == s[i] - 'a' + 1 && next(it) != st.end() && s[*next(it)] < s[i]) {
                int id = *st.rbegin();
                id++;
                while (id < n && s[id] - 'a' + 1 <= st.size()) id++;
                int cur = i;
                int sz = st.size();
                while (cur < id) {
                    t.pb('a' + sz - 1);
                    st.erase(q[s[cur] - 'a'].front());
                    q[s[cur] - 'a'].pop();
                    if (!q[s[cur] - 'a'].empty()) st.insert(q[s[cur] - 'a'].front());
                    cur++;
                }
                i = id - 1;
            } else {
                t.pb(s[i]);
                st.erase(q[s[i] - 'a'].front());
                q[s[i] - 'a'].pop();
                if (!q[s[i] - 'a'].empty()) st.insert(q[s[i] - 'a'].front());
            }
        }
    }
    cout << t << '\n';
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int t = 1;
    // cin >> t; 
    while(t--) solve();
}

:::

### H. Banis Hotel
---
#### 題目摘要

#### 想法

:::spoiler 實作

:::

### I. Minimum XOR
---
#### 題目摘要

#### 想法

:::spoiler 實作

:::

### J. The Square Game
---
#### 題目摘要
Ahmad和Ahmad玩遊戲，問誰贏
#### 想法
Ahmad
:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(a, b, c) for (int a = b; a < b; a++)

void solve() {
    cout << "Ahmad\n";
}

int main() {
    solve();
}

:::

### K. 2.. 3.. 4.. Colorful! Colorful! Colorful!
---
#### 題目摘要

#### 想法

:::spoiler 實作

:::

### L. Median of the Array
---
#### 題目摘要
定義中位數是$a$排序完後的$a_{\lfloor \frac{n+1}{2}\rfloor}$，給定數列$a$問能不能拆出兩個數列$b,c$使得$b,c$數列的中位數相等
#### 想法
不難發現，如果$b,c$中位數相等，那一定也是$a$的中位數。
所以只要想好怎麼分就好，如果$n$是奇數，那必定會拆出一個奇數一個偶數大小的數列，奇數大小的就選中位數就好，那麼剩下兩種情況，原數列中間部分是$\{a,b,b\}$或是$\{a,a,b\}$，左邊的case必定是爛的。
如果$n$是偶數，中間部分會是$\{a,b,b,c\}$或$\{a,a,b,c\}$，兩個都能拆出答案，所以只要檢查是不是其中一個就好。
:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(a, b, c) for (int a = b; a < c; a++)

const int N=2e5+10;
ll a[N];

void solve() {
    int n;
    cin >> n;
    rep(i,0,n) cin >> a[i];
    // rep(i,0,n) cout << a[i];
    sort(a,a+n);
    if(n==2) {(a[0]==a[1]) ? cout <<"YES\n":cout<<"NO\n";}
    else{
        int idx = (n-1)/2;
        if(n&1){
            a[idx]==a[idx-1] ? cout <<"YES\n":cout<<"NO\n";;
        }else{
            (a[idx]==a[idx+1] || a[idx]==a[idx-1]) ? cout <<"YES\n":cout<<"NO\n";;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int t;
    cin >> t; 
    while(t--) solve();
}

:::

### M Taim and Zingers.
---
#### 題目摘要
給$n$，你可以偷走最多$k$個東西使$n=n-k$，接著如果$n$是三的倍數，那你會拿到$\frac{n}{3}$，否則如果$n$是二的倍數，那你會拿到$\frac{n}{2}$，否則你會拿到$n$，問你能拿到的$n+k$ 的最大值。
#### 想法
發現做$7$次後對$2,3$的餘數關係就會有一次循環，所以只要做$\min(k,7)$次，對答案取$\max$就好
:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(a, b, c) for (int a = b; a < b; a++)
ll s(ll a){
    if(a%3==0) return a/3;
    else if(a%2==0) return a/2;
    else return a;
}
void solve() {
    ll n,k; cin >> n >> k;
    ll ans = 0, sum=s(n);
    k = min(k,7LL);
    k = min(k,n);
    for(int i = 1; i <= k ;i++){
        sum = max(sum,s(n-i)+i);
    }
    cout << sum << '\n';
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    int t; cin >> t;
    while(t--)solve();
}

:::