Skip to content

2025-02-16 Codeforces Round 1005 (Div. 2)

Codeforces Round 1005 (Div. 2)

比赛链接: Codeforces Round 1005 (Div. 2)

很抽象的一集。算手速场吧，这C有点搞笑。。。

但是B我又突然感觉有点没想明白了。然后D感觉很难搞了，基本不用看了。。。

pEKXABj.png

A

要使得s里面只有0，t里面只有1。

所以我们有一种操作方式就是，把最前面的1之后的字符串总体移动到t里面，然后再找t里面最前面的一个0，再把这个开始的后缀整体移到s里面。

所以我们从1开始找，然后找0。实际上重复的00，11这种，我们就可以把它看做1个字符。

所以字符串最后大概是01010101...这种，我们实际上就是输出这玩意的长度，如果开头为0就-1。

C++
void solve()
{
    //10101 有多少个 就是多少
    int n;
    cin>>n;
    string s;
    cin>>s;
    int lst=1;
    s=" "+s;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(s[i]!=s[i-1]&&s[i]-'0'==lst){
            ans++;
            lst^=1;
        }
    }
    cout<<ans<<'\n';
}

B

当时写出来好慢啊，甚至还感觉有点难来着。。。现在看来有点唐。。。

数组的得分为数组的长度减去数组中不同元素的个数。这个的本质是什么呢？就是重复元素的个数。就差不多这个意思吧。

比如说有3个1，2个2，那么得分就是2+1，重复的元素的数量。

咱们需要删除中间的一段子段，使得得分最大。如果有多个，则输出使得数组长度最短的方案。

因为得分是重复元素的个数，所以一个元素都不删，得分一定也是最大的。所以咱们就是删除最长的仅由出现次数为1的元素组成的子段，这样不会使得分变小，且能删除尽量多的元素。

C++
void solve()
{
    int n;
    cin >> n;
    vi a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    vi cnt(n + 1);
    for (int i = 1; i <= n; i++)
        cnt[a[i]]++;
    int l = 0, mx = 0;
    for (int i = 1; i <= n; i++) {
        if (cnt[a[i]] == 1) {
            int j = i;
            while (j <= n && cnt[a[j]] == 1)
                j++;
            cmax(mx, j - i);
            if (j - i == mx)
                l = i;
            i = j;
        }
    }
    if (mx)
        cout << l << " " << l + mx - 1 << '\n';
    else
        cout << "0\n";
}

C

加了正数的话，那么只剩下后半部分了，加了负数的话只剩下前半部分了。

但是你全加正数或全加负数，显然都是可以的。

很容易想到就如果要加正数，那么只能是正数在负数前面。所以用两个前缀和就行了。

C++
void solve()
{
    int n;
    cin>>n;
    ll ans=0;
    vi a(n+1);
    vl p1(n+1),p2(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        p1[i]=p1[i-1],p2[i]=p2[i-1];
        if(a[i]<0)
            p1[i]-=a[i];
        else
            p2[i]+=a[i];
    }
    ans=p1[n];
    for(int i=1;i<=n;i++){
        cmax(ans,p2[i]+p1[n]-p1[i]);
    }
    cout<<ans<<'\n';
}

D

最高位比 \(x\) 低的数字必然不会使得 \(x\) 的最高位降低，所以它可以吃掉所有最高位比它低的。

咱们只需要找到它前面的离得最近的最高位大于等于它的，如果能继续吃，那么 \(x\) 的最高位必然会降低，所以操作次数最多只会有 \(\log x\) 次，直到不能进行操作。

用一个数组 \(lst_{i,j}\) 表示前 \(i\) 个数字里面最后面的最高位大于等于 \(j\) 的下标。然后每次跳转到 \(lst_{idx,\log x}\) ，再看能不能继续吃。

C++
void solve()
{
    int n, q;
    cin >> n >> q;
    vi w(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> w[i];
    // 找到下一个最高位大于等于x的
    vector<vi> lst(n + 1, vi(32, 0));
    for (int i = 1; i <= n; i++) {
        lst[i] = lst[i - 1];
        for (int j = __lg(w[i]); j >= 0; j--)
            lst[i][j] = i;
    }
    vi pre(n + 1);
    for (int i = 1; i <= n; i++)
        pre[i] = pre[i - 1] ^ w[i];
    // lst[i][j]指 [1,i]之间离i最近的最高位大于等于j的数字
    while (q--) {
        int x;
        cin >> x;
        int idx = n;
        while (idx > 0 && x) {
            int nxt = lst[idx][__lg(x)];
            x ^= pre[nxt] ^ pre[idx];
            // cerr<<x<<" "<<nxt<<" "<<idx<<"\n";
            idx = nxt;
            if (x < w[nxt] || idx == 0)
                break;
            x ^= w[nxt];
            idx--;
            // cerr<<nxt<<'\n';
        }
        cout << n - idx << ' ';
    }
    cout << '\n';
}

感觉对我来说还是很难想出来的。