Solution - Codeforces Round 1005 (Div. 2)

Codeforces Round 1005 (Div. 2)

A Brogramming Contest

题意

给定01序列$s$和空序列$t$，你每次可以将$s$或$t$的一个后缀移动到另一个序列的后面，求最少几次操作可以使$s$全为$0$而$t$全为$1$。

思路

首先可以发现连续的$0$和$1$是可以整体操作的，所以可以简化$s$的形式为01交替序列。

其次，$s$的前缀$0$和$t$的前缀$1$是不需要操作的，于是我们可以直接删去它们。这样我们的任务变成了求最小次数使$s$和$t$都为空。

如果称简化01交替序列长度为复杂度的话，每次操作复杂度至多减1，也就是说最少要简化原序列的复杂度次才能消完。

构造一种消法：每次把$s$所有都放到$t$，或者$t$所有都放到$s$（前缀$0$和$1$不动），这样就可以每次减少一个复杂度。

故答案就是01交替的次数$+1$（去掉前缀$0$），时间复杂度$O(n)$。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 1;
inline int readint(){
    int x = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + (ch - '0'), ch = getchar();
    return x;
}
inline bool readbool(){
    char ch = getchar();
    while (ch != '0' && ch != '1') ch = getchar();
    return ch == '1';
}
signed main(){
    int t = readint();
    while (t--){
        int n = readint();
        bool pre = 0; int sum = 0;
        while (n--){
            bool x = readbool();
            if (x != pre) sum += 1, pre = x;
        }
        printf("%d\n", sum);
    }
    return 0;
}

B Variety is Discouraged

题意

删去最长的子串，使不同的数的数量最少。

思路

找到最长不重子串即可。时间复杂度$O(n)$。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 1;
int n, A[N], B[N];
signed main(){
    int t; cin >> t;
    while (t--){
        cin >> n;
        memset(B, 0, sizeof(B)); // initialize B
        for (int i = 1; i <= n; ++i){
            cin >> A[i]; // read A
            B[A[i]]++; // B[x] is the number of times x appears
        }
        int maxlen = 0, maxl = 0, curlen = 0, curl = 0;
        for (int i = 1; i <= n; ++i){
            if (B[A[i]] == 1){ // If A[i] appears only once
                if (!curlen){ // If we haven't found anything
                    curlen = 1, curl = i;
                }else{ // otherwise, update the length
                    curlen ++;
                }
            }else{ // If A[i] appears more than once
                curlen = 0;
            }
            if (curlen > maxlen){ // If curlen is longer, update the answer.
                // cout << "now: " << curlen << " " << curl << endl;
                maxlen = curlen;
                maxl = curl;
            }
        }
        // cout << "My answer is: ";
        if (maxlen == 0){
            cout << 0 << endl;
        }else{
            cout << maxl << " " << maxl + maxlen - 1 << endl;
        }
    }
    
    return 0;
}

C Remove the Ends

题意

给定一个序列，每次选择一个数，得分加上这个数的绝对值；如果这个数小于$0$，则删掉这个数和它右边的数；如果这个数大于$0$，则删掉这个数和它左边的数。求得分最大值。

思路

枚举最后取的数，那么这个数左边一定只能取正数，右边一定只能取负数。左边的正数从左往右取，右边的负数从右往左取，则可以取走左边所有正数和右边所有负数。这样得分就是最大化的，枚举所有数并取最大值即可。

时间复杂度$O(n)$

Code

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 2e5 + 2;
int n, A[N];
LL presum[N], sufsum[N];
signed main(){
    int t; cin >> t;
    while (t--){
        cin >> n;
        presum[0] = sufsum[n + 1] = 0;
        for (int i = 1; i <= n; ++i){
            cin >> A[i];
            presum[i] = presum[i - 1];
            if (A[i] > 0) presum[i] += A[i];
        }
        for (int i = n; i >= 1; --i){
            sufsum[i] = sufsum[i + 1];
            if (A[i] < 0) sufsum[i] -= A[i];
        }
        LL ans = 0;
        for (int i = 1; i <= n; ++i){
            // printf("pre = %lld, suf = %lld, i = %d\n", presum[i - 1], sufsum[i + 1], i);
            ans = max(ans, presum[i - 1] + sufsum[i + 1] + abs(A[i]));
        }
        cout << ans << endl;
    }
    return 0;
}

D Eating

题意

给定一个序列，每次询问假设有一个数$x$，从右往左和序列中的数比较，如果$x$大于等于当前数，则$x$和当前数作异或赋值给$x$，继续判断下一个数；如果$x$打败所有数或者$x$小于当前数，游戏结束，得分为$x$打败的数的数量。每次询问求得分。

思路

显然$x$被打败当且仅当在某一次比较中，当前数的最高若干位和$x$相等且某一位比$x$大（$x$在这一位为$0$，而那个数是$1$）。

我们从高位往低位枚举每一个二进制位，并维护两个指针：$left$和$right$，表示$x$在$left$这一点必败，在$right$以及右边必胜。

一开始$left = 0, right = n + 1$，枚举到每一位的时候，我们尝试缩小这个区间：如果$x$在这一位是$1$，则在$[left + 1, right - 1]$这个区间内，对于从右往左数第一个$1$右边的数，$x$都是必胜的，而对于从右往左数第二个$1$，$x$就必败了；如果$x$在这一位是$0$，则在区间内，对于从右往左数第一个$1$，$x$就必败了。这样可以缩小这个区间，最后答案就是$n - left$。复杂度可以通过预处理达到$O(q\log n)$，代码中展现的做法是$O(q\log^2 n)$的。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 2, M = 30;
int n, q, A[N], rxor[N];
set<int, greater<int> > st[M];
signed main(){
    int t; cin >> t;
    while (t--){
        cin >> n >> q;
        for (int i = 1; i <= n; ++i){
            cin >> A[i];
        }
        for (int j = 0; j < M; ++j) st[j].clear();
        rxor[n + 1] = 0;
        for (int i = n; i >= 1; --i){
            rxor[i] = rxor[i + 1] ^ A[i];
            for (int j = 0; j < M; ++j){
                if ((1 << j) & A[i]){
                    st[j].insert(i);
                }
            }
        }
        while (q--){
            int x; cin >> x;
            int defeat = 0, win = n + 1;
            for (int j = M - 1; j >= 0; --j){
                auto it = st[j].upper_bound(win);
                int fi = 0, se = 0;
                if (it != st[j].end()){
                    fi = *it;
                    ++it;
                    if (it != st[j].end()){
                        se = *it;
                    }
                }
                // if (j <= 4) printf("n = %d, j = %d, x = %d, fi = %d, se = %d, win = %d, defeat = %d\n", n, j, x, fi, se, win, defeat);
                if ((x ^ rxor[win]) & (1 << j)){
                    if (se){
                        defeat = max(defeat, se);
                    }
                    win = max(defeat + 1, fi + 1);
                }else{
                    if (fi){
                        defeat = max(defeat, fi);
                    }
                }
            }
            // printf("n = %d, x = %d, win = %d, defeat = %d\n", n, x, win, defeat);
            cout << n - defeat << ' ';
        }
        cout << endl;
    }
    return 0;
}

E Mycraft Sand Sort

题意

见原题，不好描述。

思路

初始答案为$1$，从左往右逐次删去最短的一条，我们可以发现，每次删去一条之后，记这条周围与它颜色相同的所有条的个数为$x$，则答案会乘$C_x^{x - 1} = x$。所以把相邻条缩成一条丢到链表里面，支持删除和合并的操作，就可以得到正确答案。复杂度$O(n)$。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 1, MOD = 998244353;
int pre[N], nxt[N], col[N], num[N], idx;
int n, p[N], c[N], bl[N];
int fa[N];
int find(int x){
    return (fa[x] == x ? x : (fa[x] = find(fa[x])));
}
signed main(){
    int t; cin >> t;
    while (t--){
        cin >> n;
        for (int i = 1; i <= n; ++i){
            cin >> p[i];
            fa[i] = i;
        }
        int prec = -1;
        idx = 0;
        for (int i = 1; i <= n; ++i){
            cin >> c[i];
            if (c[i] != prec){
                col[++idx] = c[i];
                num[idx] = 1;
                pre[idx] = idx - 1;
                nxt[idx] = 0;
                if (idx != 1) nxt[idx - 1] = idx;
                prec = c[i];
            }else{
                num[idx]++;
            }
            bl[p[i]] = idx;
        }
        // for (int i = 1; i <= idx; ++i){
        //     printf("i = %d, col = %d, num = %d, nxt = %d, pre = %d\n",i,col[i],num[i],nxt[i],pre[i]);
        // }
        // for (int i = 1; i <= n; ++i){
        //     printf("bl[%d] = %d\n",i, bl[i]);
        // }
        int ans = 1;
        for (int i = 1; i <= n; ++i){
            int now = find(bl[i]);
            if (num[now] != 1){
                ans = (LL)ans * num[now] % MOD;
                num[now]--;
            }else{
                nxt[pre[now]] = nxt[now];
                pre[nxt[now]] = pre[now];
                num[now]--;
                now = pre[now];
                // printf("now = %d\n", now);
                while (now && nxt[now] && col[now] == col[nxt[now]]){
                    fa[find(nxt[now])] = find(now);
                    now = nxt[now];
                    nxt[pre[now]] = nxt[now];
                    pre[nxt[now]] = pre[now];
                    num[pre[now]] += num[now];
                    num[now] = 0;
                    now = pre[now];
                }
            }
        //     printf("i = %d ----------------------\n",i);
        //     for (int i = 1; i <= idx; ++i){
        //     printf("i = %d, col = %d, num = %d, nxt = %d, pre = %d\n",i,col[i],num[i],nxt[i],pre[i]);
        // }
        }
        // cout << "The answer is: ";
        cout << ans << endl;
    }
    return 0;
}/*
3
5
3 2 4 1 5
1 1 2 2 3

5
1 4 5 2 3
1 2 2 2 1

5
3 1 4 2 5
1 3 3 3 1



10
10
9 1 2 3 6 7 5 8 4 10
1 1 2 2 1 1 1 3 1 1
*/

F We Be Summing

题意

给定一个序列和整数$k$，求有多少个这个序列的连续子序列，满足可以被劈成非空的两部分，使左半部分的最小值加右半部分的最大值刚好为$k$。

思路

首先观察到$min(b_1, b_2, \cdots, b_i)$和$max(b_{i + 1}, b_{i + 2}, \cdots, b_m)$随着$i$增大都是单调不升的，说明只有唯一的整数对$(x, y)$满足$x + y = k$，且使$x = min(b_1, b_2, \cdots, b_i)$且$y = max(b_{i + 1}, b_{i + 2}, \cdots, b_m)$。所以一个子序列对应一个$(x, y)$，或者不对应。这说明通过不同的$(x, y)$得到的合法子序列总是不同的（关键性质）。

对于$a_i + a_j = k(i < j)$，我们定义它的左右端点的掌管区间分别为$[\text{上一个小于等于}a_i\text{的数的下标} + 1, i]$和$[j, \text{下一个大于等于}a_j\text{的数的下标}]$。这样可以做到不重不漏。如果可行，那么这对$(i, j)$的贡献就是这两个区间长度的乘积。

考虑何时会不可行：如果$\text{下一个小于}a_i\text{的数的下标}$比$\text{上一个大于}a_j\text{的数的下标}$要大的话，那$(i, j)$就无法产生贡献。所以这种情况不可行。

具体实现可以用单调栈预处理所有的“上一个小于等于”，“下一个大于等于”，“下一个小于”和“上一个大于”，然后枚举$i$，发现$j$的可行域是一个区间，所以可以用双指针动态维护。最后复杂度为$O(n)$。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 1;
int n, k, A[N], prel[N], preh[N], sufl[N], sufh[N], st[N], top;
vector<int> G[N]; int head[N], tail[N], len[N];
signed main(){
    int t; cin >> t;
    while (t--){
        // puts("---------------------------");
        cin >> n >> k;
        for (int i = 1; i <= n; ++i){
            G[i].clear(), head[i] = 0, tail[i] = -1, len[i] = 0;
        }
        for (int i = 1; i <= n; ++i){
            cin >> A[i];
            G[A[i]].push_back(i);
            prel[i] = preh[i] = 0;
            sufl[i] = sufh[i] = n + 1;
        }
        for (int i = 1; i <= n; ++i){
            while (top && A[st[top]] > A[i]){
                sufl[st[top--]] = i;
            }
            st[++top] = i;
        } top = 0;
        for (int i = 1; i <= n; ++i){
            while (top && A[st[top]] <= A[i]){
                sufh[st[top--]] = i;
            }
            st[++top] = i;
        } top = 0;
        for (int i = n; i >= 1; --i){
            while (top && A[st[top]] >= A[i]){
                prel[st[top--]] = i;
            }
            st[++top] = i;
        } top = 0;
        for (int i = n; i >= 1; --i){
            while (top && A[st[top]] < A[i]){
                preh[st[top--]] = i;
            }
            st[++top] = i;
        } top = 0;
        LL ans = 0;
        // for (int i = 1; i <= n; ++i){
        //     printf("i = %d, prel = %d, preh = %d, sufl = %d, sufh = %d\n",i, prel[i], preh[i], sufl[i], sufh[i]);
        // }
        for (int i = 1; i <= n; ++i){
            int b = k - A[i];
            if (b > n) continue;
            while (head[b] < G[b].size() && G[b][head[b]] <= i){
                int now = G[b][head[b]];
                if (head[b] <= tail[b]){
                    len[b] -= sufh[now] - now;
                }
                ++head[b];
            }
            tail[b] = max(tail[b], head[b] - 1);
            if (head[b] >= G[b].size()) continue;
            while (tail[b] + 1 < G[b].size()){
                int j = tail[b] + 1, now = G[b][j];
                if (preh[now] >= sufl[i]) break;
                // printf("i = %d, now = %d, l1 = %d, r1 = %d, l2 = %d, r2 = %d\n", i, now, prel[i] + 1, i, now, sufh[now] - 1);
                // Modifymin(1, 1, n, prel[i] + 1, i, now);
                // Modifymax(1, 1, n, prel[i] + 1, i, sufh[now] - 1);    
                len[b] += sufh[now] - now;
                ++tail[b];
            }
            ans += (LL) (i - prel[i]) * len[b];
        }
        cout << ans << endl;
        
    }
    return 0;
}/*
1
5 6
4 5 2 1 1

*/