前面的話

比賽連接：2021牛客寒假演算法基礎集訓營4
有些題目是自己思考做出來的，有些是看他人的思路自己做的，也有的是參考別人的代碼然后寫的，我決定這里以及以后都會寫出來，標記在思路右邊，
不同解法的時間復雜度也不同，會標記在代碼內，
如果是簡單題或者復雜度(做出來的或者沒做出來的)，我可能都會帶一些補充，放在每題的后面，

A ：九峰與簽到題 | 模擬 (簽到題)

【題意】
求出任何時刻，通過率都 ≥ 50 % \ge 50\% ≥50% 的題目，
【細節】
判斷通過率 ≥ 50 % \ge 50\% ≥50% 不建議這么寫： a c / a l l ≥ 0.5 ac/all\ge0.5 ac/all≥0.5
而是建議這么寫： 2 × a c ≥ a l l 2\times ac\ge all 2×ac≥all

B：武辰延的字串 | exKMP

【題意】
給你兩個字串 s 、 t s、t s、t
設 s i s_i si? 表示字串 s s s 的長度為 i i i 的前綴，
設 s i + s j s_i+s_j si?+sj? 表示 s i s_i si? 和 s j s_j sj? 的直接拼接，
問你有多少對不同的 i 、 j i、j i、j，滿足 s i + s j = t i + j s_i+s_j=t_{i+j} si?+sj?=ti+j?
【范圍】
1 ≤ ∣ s ∣ , ∣ t ∣ ≤ 1 0 5 1\le |s|,|t|\le 10^5 1≤∣s∣,∣t∣≤105
【思路】賽內
首先如果能滿足要求，一定要 s i = t i s_i=t_i si?=ti?
接下來就是對于每一個位置 i i i， s [ 1 , 2 , . . . ] s[1,2,...] s[1,2,...] 與 t [ i + 1 , i + 2 , . . . ] t[i+1,i+2,...] t[i+1,i+2,...] 的最長公共前綴是多少，
暴力計算肯定會超時的，不過我們有 e x K M P exKMP exKMP ，可以快速計算，
【代碼】
時間復雜度： O ( ∣ s ∣ + ∣ t ∣ ) O(|s|+|t|) O(∣s∣+∣t∣)
12 / 1000 M s 12/1000Ms 12/1000Ms

/* 求解 T 中 next[]，注釋參考 GetExtend() */
void GetNext(string & T, int & m, int next[])
{
    int a = 0, p = 0;
    next[0] = m;

    for (int i = 1; i < m; i++){
        if (i >= p || i + next[i - a] >= p){
            if (i >= p)
                p = i;
            while (p < m && T[p] == T[p - i])
                p++;
            next[i] = p - i;
            a = i;
        }
        else
            next[i] = next[i - a];
    }
}

/* 求解 extend[] */
void GetExtend(string & S, int & n, string & T, int & m, int extend[], int next[])
{
    int a = 0, p = 0;
    GetNext(T, m, next);

    for (int i = 0; i < n; i++){
        if (i >= p || i + next[i - a] >= p){
            if (i >= p)
                p = i;
            while (p < n && p - i < m && S[p] == T[p - i])
                p++;
            extend[i] = p - i;
            a = i;
        }
        else
            extend[i] = next[i - a];
    }
}

int nxt[100050];
int extend[100050];
int main()
{
    string S, T;
    int n, m;

    cin >> T >> S;
    n = S.size();
    m = T.size();
    GetExtend(S, n, T, m, extend, nxt);

    long long res = 0;
    for (int i = 0; i < n; i++){
        if(S[i] == T[i])res += (long long)extend[i+1];
        else break;
    }
    cout << res;
    return 0;
}

【補充】
其實這題推薦解應該是二分查找+字串哈希，不過 e x K M P exKMP exKMP 應該是時間最優解了，
不過后面有字串哈希的題…

D ：溫澈瀅的狗狗 | 二分

【題意】
從左到右有 n n n 個點，每個點有顏色 c i c_i ci?
如果 c i ≠ c j c_i\ne c_j ci??=cj?，那么點對 ( i , j ) (i,j) (i,j) 之間有親密度 ∣ i ? j ∣ |i-j| ∣i?j∣
我們把所有有親密度的點對取出來，優先級按照親密度從高到低， i i i 從高到低， j j j 從高到低排序，
問你親密度排序后第 k k k 對點對是哪兩個點，或者告訴她不存在親密度第 k k k 的點對，
【范圍】
1 ≤ n ≤ 1 0 5 1\le n\le 10^5 1≤n≤105
1 ≤ k ≤ n ( n ? 1 ) 2 1\le k\le \frac{n(n-1)}{2} 1≤k≤2n(n?1)?
1 ≤ c i ≤ n 1\le c_i\le n 1≤ci?≤n
【思路：第一步】參考題解
因為親密度排序的最高優先級是親密度大小，容易想到我們可能可以二分找出親密度 ≤ d \le d ≤d 的異色點對個數，然后確定最終第 k k k 對點對的親密度的值是多少，
假設我們知道了最終親密度為 d d d，且親密度 ≤ d ? 1 \le d-1 ≤d?1 的點對數量 m m m，我們只要 O ( n ) O(n) O(n)，從左到右掃一遍距離為 d d d 的點對，如果顏色不同那么 m m m 自增 1 1 1 ，直到 m = k m=k m=k 即可，
那么我們想知道怎么去二分找親密度 ≤ d \le d ≤d 的異色點對的個數，
【思路：第二步】
首先，直接求很難求，我們根據容斥得到：異色點對的個數 = = = 所有點對個數 ? - ? 同色點對個數，
有 n n n 個數，距離 ≤ d \le d ≤d 的所有點對個數是多少呢？假設距離為 i i i，我們得到這個式子：
a l l = ∑ i = 1 d ( n ? i ) = n d ? ( 1 + d ) d 2 all=\sum_{i=1}^d (n-i)=nd-\frac{(1+d)d}{2} all=i=1∑d?(n?i)=nd?2(1+d)d?
有 n n n 個數，距離 ≤ d \le d ≤d 的同色個數是多少呢？
我們肯定列舉每一種顏色 c c c ，然后用 滑動視窗 去計算 距離 ≤ d \le d ≤d 的點對個數，
我們會事先把顏色為 c c c 的點按照下標升序丟到 V e c t o r [ c ] Vector[c] Vector[c] 中預處理，
假設視窗左端、右端下標分別為 s t 、 e d ? 1 st、ed-1 st、ed?1，我們新加進來下標為 e d ed ed 的同色點，
如果新的視窗長度 ≤ d \le d ≤d，那么新的點產生的點對個數為 e d ? s t ed-st ed?st，
如果新的視窗長度 > d >d >d，那么我們把視窗向右移動，直到距離合法，回傳上一步，
【代碼】
時間復雜度： O ( n log ? n ) O(n\log n) O(nlogn)
49 / 1000 M s 49/1000Ms 49/1000Ms

const int MAX = 2e5+50;

int n;
ll k;
vector<int>V[MAX];

ll solve(int x,int d){
    int st = 0;
    ll res = 0;
    for(int ed = 1;ed < V[x].size();++st){
        while(ed < V[x].size() && V[x][ed] - V[x][st] <= d){
            res += ed - st;
            ed++;
        }
    }
    return res;
}

bool check(ll d){
    ll sum = (ll)n * d - (1+d)*d/2;
    for(int i = 1;i <= n;++i){
        if(V[i].size() >= 2)sum -= solve(i,d);
    }
    return sum >= k;
}
int aa[MAX];
int main()
{
    scanf("%d%lld",&n,&k);
    for(int i = 1;i <= n;++i){
        int t;scanf("%d",&t);
        aa[i] = t;
        V[t].push_back(i);
    }
    ll L = 1,R = n - 1;
    while(L < R){
        ll M = (L + R) >> 1;
        if(check(M))R = M;
        else L = M + 1;
    }
    ll tmp = (L-1) * n - (1+L-1)*(L-1)/2;
    for(int i = 1;i <= n;++i){
        if(V[i].size() >= 2)tmp -= solve(i,L-1);
    }
    for(int i = 1;i + L<= n;++i){
        if(aa[i] != aa[i+L])tmp++;
        if(tmp == k){
            printf("%d %d",i,i+L);
            return 0;
        }
    }
    printf("-1");
    return 0;
}

E：九峰與子序列 | d p dp dp + 字串哈希

【題意】
有一個目標字串 k k k
有 n n n 個字串序列，分別為 c 1 ? c n c_1\cdots c_n c1??cn?
問你有多少種方案，選出一些子序列使其拼接起來形成 k k k 串
【范圍】
∣ k ∣ ≤ 5 × 1 0 6 |k|\le 5\times10^6 ∣k∣≤5×106
n ≤ 40 n\le 40 n≤40
∑ ∣ c i ∣ ≤ 5 × 1 0 6 \sum|c_i|\le 5\times10^6 ∑∣ci?∣≤5×106
【思路】賽內一些 + 參考題解
首先要讀懂題意，是求子序列，即 [ a 1 , a 2 ] [a_1,a_2] [a1?,a2?] 和 [ a 2 , a 1 ] [a_2,a_1] [a2?,a1?] 是相同的一種，
把一些字串拼成目標串？很有 d p dp dp 的感覺了，
我們設 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示前 i i i 個字串序列拼成目標串到第 j j j 位的方案數
容易得到狀態轉移方程：
d p [ i ] [ j ] = d p [ i ? 1 ] [ j ] + d p [ i ? 1 ] [ j ? l e n ( a i ) ] × C o m p a r e ( a i [ 1 , l e n ( a i ) ] , k [ j ? l e n ( a i ) + 1 , j ] ) dp[i][j]=dp[i-1][j]+dp[i-1][j-len(a_i)]\times Compare\Big( a_i[1,len(a_i)],k[j-len(a_i)+1,j] \Big) dp[i][j]=dp[i?1][j]+dp[i?1][j?len(ai?)]×Compare(ai?[1,len(ai?)],k[j?len(ai?)+1,j])
但是關鍵是這個比較特別花時間，那就用字串哈希 ，然后比較哈希值吧，
然后注意到，空間復雜度 O ( n ∣ k ∣ ) O(n|k|) O(n∣k∣) 是不大允許的，像背包演算法一樣，我們可以逆序滾動，把第一個維度給省略掉，
【代碼】
時間復雜度： O ( n ∣ k ∣ + ∑ ∣ c i ∣ ) O(n|k|+\sum|c_i|) O(n∣k∣+∑∣ci?∣)
空間復雜度： O ( ∣ k ∣ + max ? ∣ c i ∣ ) O(|k|+\max|c_i|) O(∣k∣+max∣ci?∣)
390 / 1000 M s 390/1000Ms 390/1000Ms

const int MAX = 5e6+50;

const ll pri = 233;

char aim[MAX];
char aa[MAX];
unsigned long long hsh[MAX];
unsigned long long shs[MAX];
unsigned long long base[MAX];
ll dp[MAX];
int main()
{
    int n,k;scanf("%d%s",&n,aim+1);
    k = strlen(aim+1);
    base[0] = 1;
    for(int i = 1;i <= k;++i){
        hsh[i] = hsh[i-1] * pri + aim[i];
        base[i] = base[i-1] * pri;
    }
    dp[0] = 1;
    for(int i = 1;i <= n;++i){
        scanf("%s",aa+1);
        int ed = strlen(aa+1);
        shs[0] = 0;
        for(int j = 1;j <= ed;++j){
            shs[j] = shs[j-1] * pri + aa[j];
        }

        for(int j = k - ed + 1;j >= 1;--j){
            ll hash1 = hsh[j+ed-1] - hsh[j-1] * base[ed];
            if(hash1 == shs[ed]){
                dp[j+ed-1] += dp[j-1];
            }
        }
    }
    printf("%lld",dp[k]);
    return 0;
}

【補充】
特地去復習(預習)了一下字串哈希，用雙哈希直接 T L E + M L E TLE+MLE TLE+MLE，用單哈希還是 T L E TLE TLE
結果只能用 u l l ull ull 自然溢位了…
本題也可以用折半搜索去做，不過會比較麻煩，

F：魏遲燕的自走棋 | 并查集

【題意】
有 n n n 個人， m m m 個裝備，每個人只能有一個裝備，一個裝備只能分配給一個人，
其中第 i i i 件裝備可以給 k i k_i ki? 個人，分別為 p 1 , ? ? , p k i p_1,\cdots,p_{k_i} p1?,?,pki??，裝備了能總體增加 w i w_i wi? 戰斗力，
問你總體戰斗力最大值能為多少？
【范圍】
1 ≤ n , m ≤ 1 0 5 1\le n,m\le 10^5 1≤n,m≤105
1 ≤ k i ≤ 2 1\le k_i\le 2 1≤ki?≤2
1 ≤ w i ≤ 1 0 9 1\le w_i\le 10^9 1≤wi?≤109
【思路】參考題解
我們把人當做點，裝備當做邊，就有了一個圖，
我們如果不要某個裝備，相當于把這條邊給刪掉，
我們最后的合法情況是什么情況？就是對于每一個連通圖來說，要么：
n n n 個點連接 n ? 1 n-1 n?1 條邊，為一棵樹(或者一個有自環的點)
n n n 個點連接 n n n 條邊，為一個基環樹
~~按照出題人的結論~~ 按照貪心的思路，每次拿權值最大的邊，如果是一個點，那么相當于刪掉這個點，如果是兩個不同的點，那么相當于把這兩個點縮為一個點，可以通過并查集來實作，
為什么貪心可以呢？考慮一個合法方案，假設是一個基環樹，
我們在樹的任意地方添上一條權值大于樹的所有邊的新邊，容易得到，我們都可以通過斷掉一條小邊，加上這條大邊，使得最后得到的解合法且更大，
【代碼】
時間復雜度： O ( m log ? m ) O(m\log m) O(mlogm)
49 / 1000 M s 49/1000Ms 49/1000Ms

const int MAX = 2e5+50;

int fa[MAX];
bool used[MAX];
int find_fa(int x){
    if(x == fa[x])return x;
    return fa[x] = find_fa(fa[x]);
}

void add(int x,int y){
    int fx = find_fa(x);
    int fy = find_fa(y);
    if(fx != fy){
        fa[fx] = fy;
    }
}
bool sam(int x,int y){
    int fx = find_fa(x);
    int fy = find_fa(y);
    return fx == fy;
}

struct node{
    int ta,tb;
    ll w;
    bool operator <(const node &ND)const{
        return w > ND.w;
    }
}aa[MAX];

int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++i)fa[i] = i;

    for(int i = 1;i <= m;++i){
        int shu;scanf("%d",&shu);
        if(shu == 1){
            scanf("%d%lld",&aa[i].ta,&aa[i].w);
            aa[i].tb = aa[i].ta;
        }else{
            scanf("%d%d%lld",&aa[i].ta,&aa[i].tb,&aa[i].w);
        }
    }
    sort(aa+1,aa+1+m);
    ll res = 0;
    for(int i = 1;i <= m;++i){
        int x = find_fa(aa[i].ta);
        int y = find_fa(aa[i].tb);
        if(x != y){
            if(!used[x]){
                res += aa[i].w;
                used[x] = 1;
            }else if(!used[y]){
                res += aa[i].w;
                used[y] = 1;
            }
            fa[x] = y;
        }else{
            if(!used[x])
                res += aa[i].w;
            used[x] = 1;
        }
    }
    printf("%lld",res);
    return 0;
}

G：九峰與蛇形填數 | 差分 + 優先佇列

【題意】
給定一個 n × n n\times n n×n 的初始全 0 0 0 的矩陣，
進行填數 m m m 次，每次選擇左上角為 x i , y i x_i,y_i xi?,yi?，填邊長為 k k k 的蛇形矩陣，
蛇形矩陣類似下圖：
[ 1 2 3 6 5 4 7 8 9 ] \begin{bmatrix} 1&2&3\\ 6&5&4\\ 7&8&9 \end{bmatrix} ???167?258?349????
最后輸出最終的矩陣，
【范圍】
n < 2000 n<2000 n<2000
m < 3000 m<3000 m<3000
1 ≤ x i , y i ≤ n 1\le x_i,y_i\le n 1≤xi?,yi?≤n
max ? ( x i + k ? 1 , y i + k ? 1 ) ≤ n \max(x_i+k-1,y_i+k-1)\le n max(xi?+k?1,yi?+k?1)≤n
【思路】賽內想 + 來不及寫了吃了個飯的時候想出來了
我們希望快速算出每一個位置 ( i , j ) (i,j) (i,j) 最終是被哪一個矩形所覆寫的，
找了很久的二維線段樹的區間置數+單點查詢的板子，但是找不到…
我們二維區間差分可以做到給某一個矩形增加 c c c ，但是也很難做到區間數字置為 c c c 呀，
但是如果是一維的話，就好辦了：
假設有多次操作，第 i i i 次讓編號為 i i i 的矩形覆寫位置 [ x i , y i ] [x_i,y_i] [xi?,yi?] 如果是這樣的話我們怎么做呢？
因為編號依次增大，我們可以搞一個優先佇列，每次最優先考慮編號最大的矩形，然后我們要獲得每個位置分別是哪些矩形的開始位置 記錄在 v e c t o r [ i ] vector[i] vector[i] 中，以及每個矩形的最右范圍 M P [ i ] MP[i] MP[i] ，
這樣，我們每次遇到 v e c t o r [ p o s ] vector[pos] vector[pos] 非空，就把矩形編號放進優先佇列中去，還要判斷佇列中最大編號是否超過 M P [ i ] MP[i] MP[i] 了，是的話直接把該矩形編號 p o p pop pop 掉，
二維怎么做呢？其實一樣的！二維就是多個一維相加即可做，不要想復雜了，
然后得到每個位置的最終矩形編號，我們容易直接計算出該位置的數字，
【代碼】
時間復雜度： O ( n 2 log ? m ) O(n^2\log m) O(n2logm)
1107 / 2000 M s 1107/2000Ms 1107/2000Ms

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 3e3+50;

struct node{
    int z,y;
    int bh;
};
struct node2{
    int a,b,k;
}bb[MAX];
vector<node>V[MAX];
vector<int> de[MAX];
int aa[MAX][MAX];
unordered_map<int,int>MP;
priority_queue<int>Q;
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;++i){
        int x,y,k;scanf("%d%d%d",&x,&y,&k);
        bb[i].a = x;
        bb[i].b = y;
        bb[i].k = k;

        for(int j = x;j <= x + k - 1;++j)
            V[j].push_back({y,y+k-1,i});
    }
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= n;++j)de[j].clear();
        MP.clear();
        while(!Q.empty())Q.pop();
        MP[0] = INF;
        for(int j = 0;j < V[i].size();++j){
            de[V[i][j].z].push_back(V[i][j].bh);
            MP[V[i][j].bh] = V[i][j].y;
        }

        Q.push(0);
        for(int j = 1;j <= n;++j){
            for(int k = 0;k < de[j].size();++k)
                Q.push(de[j][k]);
            while(MP[Q.top()] < j)Q.pop();

            aa[i][j] = Q.top();
        }
    }

    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= n;++j){
            int shu = aa[i][j];
            if(shu == 0)printf("0 ");
            else{
                int hang = i - bb[shu].a + 1;
                int lie  = j - bb[shu].b + 1;
                int res = (hang-1)*(bb[shu].k);
                if(hang&1){
                    res+=lie;
                }else{
                    res+=bb[shu].k-lie + 1;
                }
                printf("%d ",res);
            }
        }
        puts("");
    }
    return 0;
}

H：吳楚月的運算式 | 樹形 d p dp dp

【題意】
給定一顆有根樹，根編號為 1 1 1
有 n n n 個節點，每個節點有權值 v i v_i vi?，每條邊有一個運算子 { + ? ? / } \{+-*/\} {+??/} 中的一種，
問你從根出發到各個節點，運算式按照正常的優先級去計算，到各個節點的權值分別為多少，
對答案取模 1 e 9 + 7 1e9+7 1e9+7
【范圍】
1 ≤ n ≤ 1 0 5 1\le n\le 10^5 1≤n≤105
1 ≤ v i ≤ 1 0 9 1\le v_i\le 10^9 1≤vi?≤109
【思路】賽內
考慮到沒有 ( ( ( 和 ) ) ) 的括號的優先級干擾，我們把每個點的權值記錄成 a + b a+b a+b 的形式，
如果是乘法與除法，根據優先級，我們只對 b b b 進行計算，
如果是加法與減法，根據優先級，我們把 a a a 替換成 a + b a+b a+b，然后把 b b b 替換該節點的權值，正負號表示加或者減，
【代碼】
時間復雜度： O ( n ) O(n) O(n)
55 / 1000 M s 55/1000Ms 55/1000Ms

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 1e5+50;

ll q1[MAX],q2[MAX];
vector<int>V[MAX];
char op[MAX];
ll aa[MAX];
void dfs(int x){
    for(auto it : V[x]){
        if(op[it] == '+'){
            q1[it] = (q1[x] + q2[x]) % MOD;
            q2[it] = aa[it];
        }else if(op[it] == '-'){
            q1[it] = (q1[x] + q2[x]) % MOD;
            q2[it] = -aa[it] + MOD;
        }else if(op[it] == '*'){
            q1[it] = q1[x];
            q2[it] = q2[x] * aa[it] % MOD;
        }else if(op[it] == '/'){
            q1[it] = q1[x];
            q2[it] = q2[x] * inv(aa[it]) % MOD;
        }

        dfs(it);
    }
}
int main()
{
    int n;scanf("%d",&n);
    for(int i = 1;i <= n;++i)scanf("%lld",&aa[i]);
    for(int i = 2;i <= n;++i){
        int t;scanf("%d",&t);
        V[t].push_back(i);
    }
    scanf("%s",op+2);
    q1[1] = 0;q2[1] = aa[1];
    dfs(1);
    for(int i = 1;i <= n;++i){
        printf("%lld ",((q1[i] + q2[i]) % MOD + MOD) % MOD);
    }
    return 0;
}

I：九峰與分割序列 | d p dp dp + 單調佇列優化

【題意】嗯嗯題目挺言簡意賅的就謄過來了
給定一個長度為 n n n 的序列，將其分割成若干個子區間.
子區間的貢獻為：若前一個子區間的長度 > k >k >k 且該區間長度 ≤ k \le k ≤k，則貢獻為區間和的兩倍，否則貢獻為區間和，
第一個子區間的的前一個子區間長度視為 0 0 0，
求一種分割方法，使得所有子區間貢獻之和最大，輸出最大貢獻，
【范圍】
k ≤ n ≤ 1 0 5 k\le n\le 10^5 k≤n≤105
a i ≤ 1 0 9 a_i\le 10^9 ai?≤109
【思路】題解 + 代碼
這題貌似是除了魔方模擬外最難的題目了…我也理解了很久，
容易想到，我們設一個 d p [ i ] [ j ] dp[i][j] dp[i][j]，表示：
d p [ i ] [ 0 ] dp[i][0] dp[i][0] 表示到 i i i 位置為止，且最后一個區間長 ≤ k \le k ≤k 的最大貢獻
d p [ i ] [ 1 ] dp[i][1] dp[i][1] 表示到 i i i 位置為止，且最后一個區間長 > k > k >k 的最大貢獻
更新也很好想到：
d p [ i ] [ 0 ] = max ? { s u m [ j ～ i ] + d p [ j ? 1 ] [ 0 ] 2 ? s u m [ j ～ i ] + d p [ j ? 1 ] [ 1 ] i ? j + 1 ≤ k d p [ i ] [ 1 ] = max ? { s u m [ j ～ i ] + d p [ j ? 1 ] [ 0 ] s u m [ j ～ i ] + d p [ j ? 1 ] [ 1 ] i ? j + 1 > k \begin{aligned} dp[i][0]&=\max \begin{cases} sum[j\sim i] + dp[j-1][0]\\ 2*sum[j\sim i]+dp[j-1][1] \end{cases}&i-j+1\le k\\ dp[i][1]&=\max \begin{cases} sum[j\sim i] + dp[j-1][0]\\ sum[j\sim i]+dp[j-1][1] \end{cases}&i-j+1> k\\ \end{aligned} dp[i][0]dp[i][1]?=max{sum[j～i]+dp[j?1][0]2?sum[j～i]+dp[j?1][1]?=max{sum[j～i]+dp[j?1][0]sum[j～i]+dp[j?1][1]??i?j+1≤ki?j+1>k?
最終答案為 max ? ( d p [ n ] [ 0 ] , d p [ n ] [ 1 ] ) \max(dp[n][0],dp[n][1]) max(dp[n][0],dp[n][1])
這樣子貌似要用好多個線段樹去維護，挺麻煩的，我們換一種設法：
設 a n s [ i ] = max ? ( d p [ i ] [ 0 ] , d p [ i ] [ 1 ] ) ans[i]=\max(dp[i][0],dp[i][1]) ans[i]=max(dp[i][0],dp[i][1])，設 f [ i ] = d p [ i ] [ 1 ] f[i]=dp[i][1] f[i]=dp[i][1]
這樣轉移就變成了：
a n s [ i ] = max ? { a n s [ i ? 1 ] + n u m [ i ] 2 ? s u m [ j ～ i ] + f [ j ? 1 ] i ? j + 1 ≤ k f [ i ] = a n s [ i ? k ? 1 ] + s u m [ i ? k ～ i ] \begin{aligned} ans[i]&=\max \begin{cases} ans[i-1]+num[i]\\ 2*sum[j\sim i]+f[j-1]&i-j+1\le k \end{cases}\\ f[i]&=ans[i-k-1]+sum[i-k\sim i] \end{aligned} ans[i]f[i]?=max{ans[i?1]+num[i]2?sum[j～i]+f[j?1]?i?j+1≤k?=ans[i?k?1]+sum[i?k～i]?
唔呼，每行都巧妙地別有深意 ~~???~~
這個時候，我們發現唯一的麻煩就是去轉移那個 a n s [ i ] ans[i] ans[i] 的第二行了，
我們直接用單調佇列 去維護那個最大的 2 ? s u m [ j ～ i ] + f [ j ? 1 ] 2*sum[j\sim i]+f[j-1] 2?sum[j～i]+f[j?1]就可以了，
為什么是單調佇列呢？因為我們有 i ? j + 1 ≤ k i-j+1\le k i?j+1≤k 且需要求那個運算式的最大值，
【代碼】
時間復雜度： O ( n ) O(n) O(n)
21 / 1000 M s 21/1000Ms 21/1000Ms

const int MAX = 5e6+50;

int num[MAX];
ll pre[MAX];
int L,R;
int deq[MAX];
ll ans[MAX],f[MAX];
int main()
{
    int n,k;scanf("%d%d",&n,&k);
    for(int i = 1;i <= n;++i){
        scanf("%d",&num[i]);
        ans[i] = f[i] = pre[i] = pre[i-1] + num[i];
    }
    L = 0;R = 0;
    deq[R++] = k + 1;
    for(int i = k + 2;i <= n;++i){
        while(L < R && i - deq[L] > k)L++;
        ans[i] = max(f[deq[L]] + 2 * (pre[i] - pre[deq[L]]),ans[i-1] + num[i]);
        f[i] = ans[i - k - 1] + pre[i] - pre[i - k - 1];
        while(L < R && f[deq[R-1]] + 2 * (pre[i] - pre[deq[R-1]]) < f[i])R--;
        deq[R++] = i;
    }
    printf("%lld",ans[n]);
    return 0;
}

J：鄔澄瑤的公約數 | 數論

【題意】
求
gcd ? ( x 1 a 1 , x 2 a 2 , ? ? , x n a n ) \gcd(x_1^{a_1},x_2^{a_2},\cdots,x_n^{a_n}) gcd(x1a1??,x2a2??,?,xnan??)
答案取模 1 e 9 + 7 1e9+7 1e9+7
【范圍】
1 ≤ n , x i , a i ≤ 1 0 4 1\le n,x_i,a_i\le 10^4 1≤n,xi?,ai?≤104
【思路】賽內
考慮到 g c d gcd gcd 的本質就是求出 ∏ { p 1 min ? s 1 , p 2 min ? s 2 , ? ? , p t min ? s t } \prod\{p_1^{\min s_1},p_2^{\min s_2},\cdots,p_t^{\min s_t}\} ∏{p1mins1??,p2mins2??,?,ptminst??}，求出每個質數的最小冪次，
我們算出每個質數的最小冪次，乘起來即可，
其實細想只要 O ( n n ) O(n\sqrt n) O(nn ?) 的暴力判斷代碼即可，我這個由于是第二題，直接瞎敲敲就隨意了ww
【代碼】
時間復雜度： O ( n 2 log ? n ) O(\frac{n^2}{\log n}) O(lognn2?) 帶優化，卡不卡估計都能過
7 / 1000 M s 7/1000Ms 7/1000Ms 雖然過的飛快

/*
 _            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
        __/ |
       |___/
*/
const int MAX = 2e4+50;

int cnt;
bool vis[MAX];
int prime[MAX];
int shu[MAX];
int xx[MAX],pp[MAX];

void shai(int n){
    for(int i = 2;i <= n;++i){
        if(!vis[i]){
            prime[++cnt] = i;
        }
        for(int j = 1;j <= cnt && i * prime[j] <= n;++j){
            vis[i * prime[j]] = 1;
            if(i % prime[j] == 0)break;
        }
    }
}

int main()
{
    int n;scanf("%d",&n);
    shai(10000);
    for(int i = 1;i <= cnt;++i)shu[i] = INF;
    int mn = INF;
    for(int i = 1;i <= n;++i)scanf("%d",&xx[i]);
    for(int i = 1;i <= n;++i)scanf("%d",&pp[i]);

    for(int i = 1;i <= n;++i){
        int t = xx[i];
        int p = pp[i];
        for(int j = 1;j <= cnt;++j){
            if(prime[j] > t){
                mn = min(mn,j-1);
                break;
            }
            int ci = 0;
            while(t % prime[j] == 0){
                ci++;
                t /= prime[j];
            }
            ci *= p;
            shu[j] = min(shu[j],ci);
        }
    }
    ll res = 1;
    for(int i = 1;i <= mn;++i){
        res = res * qpow(prime[i],shu[i]) % MOD;
    }
    printf("%lld",res);
    return 0;
}

參考

【題解】2021年牛客寒假集訓營第四場題解

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/262115.html

標籤：其他

上一篇：這竟然是一篇年度總結

下一篇：PAT (Basic Level) Practice1018 錘子剪刀布

【解題報告】2021牛客寒假演算法基礎集訓營4

【解題報告】2021牛客寒假演算法基礎集訓營4

前面的話

A ：九峰與簽到題 | 模擬 (簽到題)

B： 武辰延的字串 | exKMP

D ：溫澈瀅的狗狗 | 二分

E： 九峰與子序列 | d p dp dp + 字串哈希

F： 魏遲燕的自走棋 | 并查集

G：九峰與蛇形填數 | 差分 + 優先佇列

H：吳楚月的運算式 | 樹形 d p dp dp

I：九峰與分割序列 | d p dp dp + 單調佇列優化

J：鄔澄瑤的公約數 | 數論

參考

B：武辰延的字串 | exKMP

E：九峰與子序列 | d p dp dp + 字串哈希

F：魏遲燕的自走棋 | 并查集