Contestant~. Rank 596. Rating +153 (+653 - 500).

A. The Man who became a God

题意

给定数组 $a$，定义 $f(l,r) = |a_l - a_{l+1}| + |a_{l + 1} - a_{l + 2}| + \ldots + |a_{r-1} - a_r|$。

将数组 $a$ 划分为 $k$ 段，输出各段 $f$ 值之和的最小值。

思路

不难发现，划分等价于删除一个 $|a_i - a_{i + 1}|$。

那么，我们将所有 $|a_i - a_{i + 1}|$ 排个序，删去前 $k - 1$ 个大的，然后求和即可。

时间复杂度：$O(n \log n)$

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    vector<int> d(n - 1);
    int ans = 0;
    for(int i=1;i<n;i++) {
        d[i - 1] = abs(a[i] - a[i - 1]);
        ans += d[i - 1];
    }
    sort(all(d));
    for(int i=0;i<k-1;i++){
        ans -= d[n - i - 2];
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

尼玛，测评机卡这么久，我一开始还交错语言了

B. Hamon Odyssey

题意

给定一个数组 $a$，定义 $f(l,r) = a_l \& a_{l+1} \& a_{l+2} \& \ldots \& a_r$。

将数组 $a$ 划分为任意段，输出各段 $f$ 值之和的最小值，并最大化段数。

思路

我们直接贪心，按照段内所有数与运算后是否为 $0$ 划分即可。

此处不给出证明（因为我不会

时间复杂度：$O(n)$

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;
    int ans = 0;
    bool f = false;
    int now = 0;
    for(int i=0;i<n;i++) {
        int cur;
        cin >> cur;
        if(now == 0) now = cur;
        else now &= cur;
        if(now == 0){
            if(!f) f = true;
            else ans ++;
        }
    }
    cout << ans + 1 << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

这不就乱猜（（

C. Vampiric Powers, anyone?

题意

给定一个序列 $a$，定义添加元素操作如下：

设当前有 $m$ 个元素；
选择一个下标 $i$；
$a_{m+1} = a_i \oplus a_{i+1} \oplus \ldots \oplus a_m$

在可以添加任意数量的元素的条件下，输出序列中的元素的最大值。

思路

首先，因为我们处理的的是后缀，因而上一次加入的元素一定会在本次异或的范围内。

那么，我们不难发现，根据奇偶性以及异或的性质，我们无法取非连续子区间的异或值。

因而，我们考虑所有连续字符列中异或的最大值。

这可以通过枚举所有前缀和后缀的异或值，并和整个序列的异或值取异或，最后求出最大值。

时间复杂度：$O(n + 256 ^ 2)$

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int n;
    cin >> n;
    int ans = 0;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) {
        cin >> a[i];
        ans = max(ans, a[i]);
    }
    map<int, bool> pre, suf;
    pre[0] = suf[0] = true;
    int now = 0;
    for(int i=1;i<=n;i++){
        now ^= a[i];
        pre[now] = true;
    }
    now = 0;
    for(int i=n;i>=1;i--){
        now ^= a[i];
        suf[now] = true;
    }
    for(auto i : pre)
        for(auto j : suf)
            ans = max(ans, now ^ i.fs ^ j.fs); //连续
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while(t --) solve();
}

好像不可以 $dp$

D. Professor Higashikata

题意

给定一个长为 $n$ 的二进制字符串 $s$，以及 $m$ 个区间。

按照给定顺序将区间内的所有字符串 $s_i$ 取出并拼接成新的字符串 $t$。

定义一次操作为选定 $i, j$，交换 $s_i, s_j$。

给定 $q$ 个 非独立 查询，每次查询给定一个下标 $x$，并将 $s_x$ 对应的数字翻转。

翻转之后，输出让字符串 $t$ 字典序最大的操作数的最小值 (对于每个查询，操作是独立的)。

思路

首先，字典序具有贪心性，也就是说，每一位具有 "优先级"，如果优先级高的位置对应的值越高，那么不管后面是多少，字典序一定会更大。

那么，我们考虑给区间内的所有数赋上优先级。

显然，如果一个数在多个位置出现，我们肯定只考虑第一次出现的位置。因而，在遍历的时候，我们就可以跳过已经赋上优先级的数了。

基于上述操作，我们可以用 $set + $ 二分。

赋予优先级后，我们就可以将原来拼接得到的字符串 "离散化" 为一个按照优先级排序后的字符串 $s$。

我们接着考虑如何计算。

对于一个 $0, 1$ 序列，如果 $1$ 的个数为 $sum$，那么如果要将所有 $1$ 移动到前面，我们需要交换的次数就是 $(sum\ -\ $前 $sum$ 个数中 $1$ 的个数$)$。

自然，因为不在区间内的数我们无需考虑，那么设在区间内的数的个数为 $tot$，交换次数就是 $(\min(sum, tot)\ -\ $前 $sum$ 个数中 $1$ 的个数$)$。

对于 $q$ 个非独立查询，我们考虑用树状数组维护前缀和，在每次修改后更新即可。

时间复杂度：$O(n \log n)$

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

int a[N];
int lowbit(int x){return x&(-x);}
void Update(int n, int d,int x){for(int i=d;i<=n;i+=lowbit(i)) a[i]+=x;}
int Query(int d){int res=0;for(int i=d;i;i-=lowbit(i))res+=a[i];return res;}
int Query(int l,int r){return Query(r)-Query(l-1);}

void solve() {
    int n, m, q;
    string s;
    cin >> n >> m >> q >> s;
    s = "#" + s;
    vector<int> p;
    set<int> st;
    for(int i=1;i<=n;i++) st.insert(i);
    for(int i=1;i<=m;i++){
        int l, r;
        cin >> l >> r;
        auto it = st.lower_bound(l);
        while(it != st.end() && *it <= r){
            int now = *it;
            p.pb(now);
            it ++;
            st.erase(now);
        }
    }
    int sum = 0;
    for(auto e : s)
        if(e == '1') sum ++;
    vector<int> pri(n + 1, 0);
    for(int i=0;i<p.size();i++){
        pri[p[i]] = i + 1;
        if(s[p[i]] == '1') Update(n, i + 1, 1);
    }
    while(q --){
        int x;
        cin >> x;
        if(s[x] == '1'){
            s[x] = '0', sum --;
            if(pri[x] != 0) Update(n, pri[x], -1);
        }else{
            s[x] = '1', sum ++;
            if(pri[x] != 0) Update(n, pri[x], 1);
        }
        int ans = max(0ll, min(sum, (int) p.size()) - Query(1, sum));
        cout << ans << '\n';
    }
}

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

不会树状数组qaq