110 選手班 - 暑期賽

tags: 宜中資訊 CP

pA 東北一中 (Title)

Tags: 字串、暴力搜索

子任務 1

限制：保證

$S$ 中不會出現蘭女或羅高的代號

暴力搜尋

$S$ 中出現過幾次 yl
時間複雜度：

$\mathcal{O}(|S|)$

子任務 2

限制：保證

$S$ 中不會出現宜中或羅高的代號

暴力搜尋

$S$ 中出現過幾次 lyg
時間複雜度：

$\mathcal{O}(|S|)$

子任務 3

限制：無額外限制

暴力搜尋

$S$ 中出現過幾次 yl、lyg、lt
可用 substr() 簡化實作
時間複雜度：

$\mathcal{O}(|S|)$

code

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

int main() {
    string s ;

    cin >> s ;

    int n = s.size() ;
    int a[3] = {} ;
    string t[3] = {"yl", "lt", "lyg"} ;

    for(int i=0; i<3; ++i) {
        for(int j=0; j+t[i].size()-1 < n; ++j) 
            if(s.substr(j, t[i].size()) == t[i])
                ++a[i] ; 
    }

    cout << a[0] << ' ' << a[1] << ' ' << a[2] << endl ;
}

pB 桌子拼接 (Tables)

Tags: 數論、質因數分解

子任務 1

限制：

$N\le {10}^3,a_i\le {10}^4$

題目要求選定的桌子必須用同樣長度的邊相連接，也就是選定的桌子皆要有相同的因數。若選定的因數為

$k$，則桌子

$a_i$ 所能貢獻的長度為

$\frac{a_i}{k}(k\mid a_i)$。
我們可以直接枚舉所有可能的因數

$k$，然後檢查

$N$ 個桌子各自能在這個因數下對答案貢獻多少，並對於所有的答案取最大值。
因為因數必然會小於桌子面積，所以只要枚舉到最大的

$a_i$ 即可。
時間複雜度：

$\mathcal{O}(Nmax(a_i))$

子任務 2

限制：

$a_i\le {10}^4$

透過枚舉所有可能的因數檢查各個桌子的速度太慢，因此我們可以換個方向。對於每個桌子直接找它有哪些因數，若桌子

$a_i$ 可以被分解為

$l\times s$，則代表因數

$l$ 的答案可以加上

$s$，而因數

$s$ 則是加上

$l$。
使用根號方法在

$\mathcal{O}({\sqrt{a}}_i)$的時間內枚舉

$a_i$ 的因數，並在最後對所有因數取答案最大值，即可以通過此子任務。
時間複雜度：

$\mathcal{O}(\sum {\sqrt{a}}_i+max(a_i))$

子任務 3

限制：無額外限制

觀察發現，能夠成為答案的因數必然為質數，因此我們只需枚舉每個桌子

$a_i$ 的質因數。若直接尋找質因數仍然要花根號的時間，因此這裡可以利用埃氏篩法預處理值域內所有數字的其中一個質因數，以在

$\mathcal{O}(\log a_i)$ 的時間內完成質因數分解。
令值域

$C=max(a_i)$
時間複雜度：

$\mathcal{O}(C\log \log C+\sum \log a_i+C)$

code

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

const int mxn = 1000010 ;
int prime[mxn] ;
long long len[mxn] ;

void init() {
    for(int i=1; i<mxn; ++i) prime[i] = 1 ;
    for(int i=2; i<mxn; ++i) {
        if(prime[i] > 1) continue ;
        prime[i] = i ;
        for(long long j=1LL*i*i; j<mxn; j += i) 
            prime[j] = i ;
    }
}

int main() {
    int n ;

    cin >> n ;
    vector<int> v(n) ;
    for(int i=0; i<n; ++i)
        cin >> v[i] ;

    init() ;
    for(auto i:v) {
        int k = i;
        if(prime[k] == k) continue ;
        while(prime[k] > 1) {
            len[prime[k]] += i / prime[k] ;
            int cur = prime[k] ;
            while(prime[k] % cur == 0) 
                k /= cur ;
        }
    }

    cout << *max_element(len, len+mxn) << endl ;
}

pC 哈蕾姆大師 (Harem)

Tags: 圖論、拓樸排序

子任務 1

限制：

$N\le 20$

要依照依賴關係去攻略角色，也就是要透過拓樸排序的順序依序攻略各個女角。若

$S$ 點無法拓樸排序，則代表無論如何皆無法攻略她。
暴力枚舉哪些點可能是要攻略的角色，再透過拓樸排序檢查這個組合是否合法。
時間複雜度：

$\mathcal{O}(2^N\times N)$

子任務 2

限制：對於所有

$a_i{b}_i$，保證

$a_i<b_i$

箭頭永遠是小的點指向大的點，也就是保證這張圖不會有環，是一個DAG。因此在這個子任務內必定有解，只要尋找哪些人是需要攻略的，哪些人不必。若

$a\to S$ 則代表

$a$ 也是需要被攻略的點，若此時

$b\to a$ 則代表

$b$ 也是需要被攻略的點。因此我們可以把箭頭轉向，從

$S$ 開始反向 DFS，途經的點必然會是指向

$S$ 的點，也就是我們必須要選的點。
時間複雜度：

$\mathcal{O}(N)$

子任務 3

限制：無額外限制

跟子任務 2 的差別是這次沒有保證整張圖是DAG，所以要先做一次拓樸排序，檢查哪些點在DAG上。再通過子任務 2 的方法尋找哪些點是必須要選的，檢查是否這些點皆在DAG上，若不是則代表無解，若是則加總各點的權重即是答案。
若使用 DFS 找拓樸排序的方法，則可以把兩件事放在一起做，因為 DAG 在反向圖中依然是 DAG。
時間複雜度：

$\mathcal{O}(N)$

code

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

const int N = 500010 ;

vector<int> g[N], rg[N] ;
int vis[N] ;

void dfs(int x) {
    vis[x] = true ;
    for(auto i:rg[x]) 
        if(!vis[i])
            dfs(i) ;
}

int main() {
    int n, m, s ;

    cin >> n >> m >> s ;
    vector<int> t(n + 1), deg(n + 1) ;
    for(int i=1; i<=n; ++i) 
        cin >> t[i] ;
    for(int i=0; i<m; ++i) {
        int a, b ;
        cin >> a >> b ;
        g[a].push_back(b) ;
        rg[b].push_back(a) ;
        deg[b]++ ; 
    }

    vector<bool> top(n + 1) ;
    queue<int> qu ;
    for(int i=1; i<=n; ++i) 
        if(deg[i] == 0)
            qu.push(i) ;
    
    while(qu.size()) {
        int u = qu.front() ;
        qu.pop() ;

        top[u] = true ;
        for(auto i:g[u])  {
            deg[i]-- ;
            if(deg[i] == 0)
                qu.push(i) ;
        }
    }

    dfs(s) ;
    long long ans = 0 ;
    for(int i=1; i<=n; ++i) {
        if(vis[i]) {
            if(!top[i]) {
                cout << -1 << endl ;
                return 0;
            }
            ans += t[i] ;
        }
    }

    cout << ans << endl ;
}

pD 老二哲學 (Second)

Tags: 資料結構、線段樹

子任務 1

限制：

$N\le {10}^3,Q\le {10}^3$

考慮暴力做法，對於每個詢問的區間

$[L,R]$：先直接跑過一遍尋找最大值並記錄下來，把最大值的位置拔掉（設為無限小），再跑過一遍尋找次大值。
時間複雜度：

$\mathcal{O}(NQ)$

子任務 2

限制：

$1\le a_i\le 2\times {10}^5$

如果你會區間第 K 大的話，就可以直接把模板丟上來了。
時間複雜度：

$\mathcal{O}((N+Q)\log C)$

子任務 3

限制：

$a_i\ne a_j,(i\ne j)$

考慮子任務 1 的做法，透過線段樹加速尋找最大值的過程，但是線段樹只能記錄最大值為和，無法得知該拔哪個點。然而此子題限制每個值都不一樣，所以可以直接開一個 map 紀錄每個值對應到的位置。對於每筆詢問：第一次查詢區間最大值，透過 map 把該點拔掉，再次查詢一次最大值即可找到答案。
時間複雜度：

$\mathcal{O}(N+Q\log N)$

子任務 4

限制：無額外限制

做法一
考慮子任務 3 的做法，既然原本的線段是無法紀錄最大值的位置，那乾脆直接把線段樹內存的東西改成位置，每次 query 或 pull 的時候比較該位置的值。如此一來便可以在第一次查詢找到最大值的位置，拔掉該點，再查詢第二次以找到答案。
時間複雜度：

$\mathcal{O}(N+Q\log N)$

code

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

const int N = 1000010 ;
const int INF = 0x3f3f3f3f ;

int mxn = 1;
int v[N], seg[4*N] ;

int pull(int l, int r) {
    return v[l] > v[r] ? l : r ;
}

void build(int lb, int rb, int idx) {
    if(lb == rb) {
        seg[idx] = idx - mxn + 1;
        return ;
    }

    int mid = lb + rb >> 1 ;
    build(lb, mid, idx*2) ;
    build(mid+1, rb, idx*2+1) ;
    seg[idx] = pull(seg[idx*2], seg[idx*2+1]) ;
}

void modify(int idx) {
    idx += mxn - 1;
    while(idx > 1) {
        idx >>= 1 ;
        seg[idx] = pull(seg[idx*2], seg[idx*2+1]) ;
    }
}

int query(int l, int r, int lb, int rb, int idx) {
    if(l <= lb && rb <= r) return seg[idx] ;

    int mid = lb + rb >> 1;
    int lch = 0, rch = 0 ;
    if(l <= mid) lch = query(l, r, lb, mid, idx*2) ;
    if(mid <  r) rch = query(l, r, mid+1, rb, idx*2+1) ;
    return pull(lch, rch) ;
}

int main() {
    int n, q ;

    cin >> n >> q ;
    for(int i=1; i<=n; ++i)
        cin >> v[i] ;
    
    v[0] = -INF ;
    while(mxn < n) 
        mxn <<= 1;
    build(1, mxn, 1) ;

    while(q--) {
        int l, r ;
        cin >> l >> r ;
        int tmp = -INF, top = query(l, r, 1, mxn, 1) ;
        swap(v[top], tmp) ;
        modify(top) ;

        cout << v[query(l, r, 1, mxn, 1)] << endl ;
        swap(v[top], tmp) ;
        modify(top) ;
    }
}

做法二
既然要找次大值，那就把線段樹內每個節點儲存兩個資料：該區間最大值與次大值。而 query 與 pull 也可以依照此定義稍作修改，即可找到答案。
時間複雜度：

$\mathcal{O}(N+Q\log N)$

pE 瘋搶口罩 (Mask)

Tags: 動態規劃、背包問題

子任務 1

限制：

$K=0$

0-1背包問題

$\text{dp}[i][j]=$ 選前

$i$ 個物品，且預算為

$j$

• 選擇：
  $\text{dp}[i][j]=\text{dp}[i-1][j-p_i]+s_i$
• 不選：
  $\text{dp}[i][j]=\text{dp}[i-1][j]$

時間複雜度：

$\mathcal{O}(NM)$

子任務 2

限制：

$M\le 500,r_i=0,K=1$

作法一
先以0-1背包作為初始的結果，接著對於每個物品，枚舉如果他是無限背包的狀況。對所有的可能性取最大值即是答案。
時間複雜度：

$\mathcal{O}(NM)$

code

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

const long long INF = 0x3f3f3f3f3f3f3f3f ;

int main() {
    int n, m, k ;
    
    cin >> n >> m >> k ;
    vector<long long> p(n), s(n), r(n) ;
    for(int i=0; i<n; ++i) 
        cin >> p[i] >> s[i] >> r[i] ;
    
    long long dp[5010] = {};
    for(int i=0; i<n; ++i) 
        for(int j=m; j >= p[i]; --j) 
            dp[j] = max(dp[j], dp[j - p[i]] + s[i]) ;
    
    long long ans = dp[m] ;
    for(int i=0; i<n && k == 1; ++i) {
        for(int j=1; m >= p[i] * j; ++j)
            ans = max(ans, dp[m - p[i] * j] + s[i] * j) ;
    }

    cout << ans << endl ;
}

作法二
考慮在

$\text{dp}$ 上多新增一個維度

$[0/1]$，紀錄是否已使用過無限背包。

$\text{dp}[i][j][0/1]=$ 選前

$i$ 個物品，且預算為

$j$，

$0/1$ 是否使用過無限背包

• 不選：
  $\text{dp}[i][j][0]=\text{dp}[i-1][j][0]$
• 01：
  $\text{dp}[i][j][0]=\text{dp}[i-1][j-p_i][0]+s_i$
• 首次無限：
  $\text{dp}[i][j][1]=\text{dp}[i][j-p_i][0]+s_i$
• 之後無限：
  $\text{dp}[i][j][1]=\text{dp}[i][j-p_i][1]+s_i$

此時發現當我們要選無限的時候，還要知道是否已經選擇為無限了，所以我們可以把

$[0/1]$ 改成三種狀態

$[0/1/2]$，分別代表 沒選過 / 正在選 / 已選過。

• 不選：
  • $\text{dp}[i][j][0]=\text{dp}[i-1][j][0]$
  • $\text{dp}[i][j][2]=max(\text{dp}[i-1][j][1],\text{dp}[i-1][j][2])$
• 01：
  • $\text{dp}[i][j][0]=\text{dp}[i-1][j-p_i][0]+s_i$
  • $\text{dp}[i][j][2]=max(\text{dp}[i-1][j-p_i][1],\text{dp}[i-1][j-p_i][2])+s_i$
• 無限：
  $\text{dp}[i][j][1]=max(\text{dp}[i][j-p_i][0],\text{dp}[i][j-p_i][1])+s_i$

時間複雜度：

$\mathcal{O}(NM)$

code

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

int main() {
    int n, m, k ;

    cin >> n >> m >> k ;
    vector<int> p(n+1), s(n+1), r(n+1) ;
    for(int i=1; i<=n; ++i) 
        cin >> p[i] >> s[i] >> r[i] ;
    
    long long dp[110][510][3] = {} ;
    
    for(int i=1; i<=n; ++i) {
        for(int j=0; j<=m; ++j) {
            dp[i][j][0] = dp[i-1][j][0] ;
            dp[i][j][2] = max(dp[i-1][j][1], dp[i-1][j][2]) ;

            if(j >= p[i]) {
                dp[i][j][0] = max(dp[i][j][0], dp[i-1][j-p[i]][0] + s[i]) ;
                dp[i][j][2] = max(dp[i][j][2], max(dp[i-1][j-p[i]][1], dp[i-1][j-p[i]][2]) + s[i]) ;
                dp[i][j][1] = max(dp[i][j][1], max(dp[i][j-p[i]][0], dp[i][j-p[i]][1]) + s[i]) ;
            }
        }
    }

    cout << max({dp[n][m][0], dp[n][m][1], dp[n][m][2]}) << endl ;
}

子任務 3

限制：

$M\le 500,r_i=0$

子任務 3 與子任務 2 的差別在於

$K$ 沒有限制了。因此我們可以單純的把第三個維度的

$[0/1/2]$ 改成

$[0\sim 2k]$ 代表選了幾個與每個使否正在選擇中。然而這樣不好實作，因此我們可以把是否正在選擇中再拉出來變成第四個維度。

$\text{dp}[i][j][k][0/1]=$ 選前

$i$ 個物品，且預算為

$j$，且已有

$k$ 個無限背包，

$0/1$ 第

$i$ 個物品是否為無限背包

• 不選：
  $\text{dp}[i][j][k][0]=max(\text{dp}[i-1][j][k][1],\text{dp}[i-1][j][k][0])$
• 01：
  $\text{dp}[i][j][k][0]=max(\text{dp}[i-1][j-p_i][k][0],\text{dp}[i-1][j-p_i][k][1])+s_i$
• 無限：
  $\text{dp}[i][j][k][1]=max(\text{dp}[i][j-p_i][k-1][0],\text{dp}[i][j-p_i][k][1])+s_i$

時間複雜度：

$\mathcal{O}(NMK)$

子任務 4

限制：

$M\le 500$

子任務 4 只是多加上每個物品要變成無限時，要額外增加一筆費。所以只要在每個物品第一次選擇無限背包時（

$k-1\to k$）把費用加上

$r_i$ 即可。

$\text{dp}[i][j][k][0/1]=$ 選前

$i$ 個物品，且預算為

$j$，且已有

$k$ 個無限背包，且第

$i$ 個物品是否為無限背包

• 不選：
  $\text{dp}[i][j][k][0]=max(\text{dp}[i-1][j][k][0],\text{dp}[i-1][j][k][1])$
• 01：
  $\text{dp}[i][j][k][0]=max(\text{dp}[i-1][j-p_i][k][0],\text{dp}[i-1][j-p_i][k][1])+s_i$
• 無限：
  $\text{dp}[i][j][k][1]=max(\text{dp}[i][j-p_i-r_i][k-1][0],\text{dp}[i][j-p_i][k][1])+s_i$

不過要特別注意的是，我們要預設所有

$\text{dp}[i][j][k][1]$ 為負無限大。因為這代表第

$i$ 個物品是無限背包且我們已經付出

$r_i$ 的代價了，然而我們有可能在這個狀況無法付出此代價。透過預設為負無限大，即可避免誤選這格做為轉移點的狀況。
時間複雜度：

$\mathcal{O}(NMK)$

子任務 5

限制：無額外限制

子任務 5 與子任務 4 本質上無差別，但是若直接把範圍修改丟上去會得到 MLE。所以這裡要對其中一個維度使用滾動陣列以降低空間複雜度，如同一般的01背包，直接把第一個維度（選了前

$i$ 個物品）壓掉即可。

時間複雜度：

$\mathcal{O}(NMK)$
空間複雜度：

$\mathcal{O}(MK)$

code

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

const long long INF = 0x3f3f3f3f3f3f3f3f ;
long long dp[2][5010][110][2] ;

int main() {
    int n, m, k ;
    
    cin >> n >> m >> k ;
    vector<int> p(n), s(n), r(n) ;
    for(int i=0; i<n; ++i) 
        cin >> p[i] >> s[i] >> r[i] ;
    
    for(int i=0; i<n; ++i) {
        // 0-1 knapsack
        for(int j=1; j<=m; ++j) {
            for(int u=0; u<=k; ++u) {
                dp[i&1][j][u][0] = max(dp[i&1^1][j][u][0], dp[i&1^1][j][u][1]) ;
                if(j >= p[i]) {
                    dp[i&1][j][u][0] = max({
                        dp[i&1][j][u][0], 
                        dp[i&1^1][j - p[i]][u][0] + s[i],
                        dp[i&1^1][j - p[i]][u][1] + s[i]
                    }) ;
                }
            }
        }

        //unbounded
        for(int j=0; j<=m; ++j) {
            for(int u=1; u<=k; ++u) {
                dp[i&1][j][u][1] = -INF ;
                if(j >= p[i] + r[i]) {
                    dp[i&1][j][u][1] = max({
                        dp[i&1][j][u][1],
                        dp[i&1][j - p[i]][u][1] + s[i],
                        dp[i&1][j - p[i] - r[i]][u - 1][0] + s[i]
                    }) ;
                }
            }
        }
    }

    long long ans = 0 ;
    for(int i=0; i<=k; ++i)
        ans = max({ans, dp[n-1&1][m][i][0], dp[n-1&1][m][i][1]}) ;
    cout << ans << endl ;
}