Codeforces Round 882 (Div. 2) A–D

A. The Man who became a God

题意

给定 $n$ 个正整数，$a_1,a_2,\ldots,a_n$，把它们分成 $k$ 连续的段，每段的值为相邻两数的差绝对值的和。求每段和的最小值。

$1\le k \le n \le 100$。

解法 1 （动态规划）

设 $f_{i,j}$ 代表前 $i$ 个数分成 $j$ 段的最小值 $(i\ge j > 0)$。

$$f_{i,j}=\min_{j-1 \le k < i} \left( f_{k,j-1}+ \sum_{p=k+1}^{j-1} |a_p-a_{p+1}| \right)$$

边界条件 $f_{1,1}=0$。复杂度 $O(n^2)$。

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

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 105;

int a[N];
int sm[N]; // 相邻绝对值的前缀和
int dp[N][N];

void solve(){
    int n=read(),k=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(i!=1)sm[i]=sm[i-1]+abs(a[i]-a[i-1]);
    }
    dp[1][1]=0;
    for(int i=2;i<=n;i++){
        dp[i][1] = sm[i];
        
        for(int j=2;j<=i;j++){
            dp[i][j] = 1e9;
            for(int k=j-1;k<i;k++){
                dp[i][j] = min(dp[i][j],dp[k][j-1]+(sm[i]-sm[k+1]));
            }
        }
    }
    printf("%d\n",dp[n][k]);
}

int main(){
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}

解法 2（贪心）

观察最终答案和 $|a_1-a_2|+|a_2-a_3|+\ldots+|a_{n-1}-a_n|$ 的差别。不难发现，分成 $k$ 段之后，答案就少了 $k-1$ 个相邻两数的绝对值。则直接贪心减去前 $k$ 大的相邻绝对值即可。

先预处理出相邻绝对值，然后排序求和。复杂度 $O(n\log n)$。（所以这题 $n$ 完全可以放到 $2\times 10^5$）

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

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 105;

int a[N];
int cha[N]; // 相邻绝对值的前缀和

void solve(){
    int n=read(),k=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }

    for(int i=1;i<n;i++){
        cha[i]=abs(a[i]-a[i+1]);
    }
    sort(cha,cha+n);
    
    int ans = 0;
    for(int i=1;i<=n-k;i++){
        ans+=cha[i]; // 选前 n-k 个小的
    }
    printf("%d\n",ans);
}

int main(){
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}

B. Hamon Odyssey

题意

给定 $n$ 个正整数，$a_1,a_2,\ldots,a_n$，把它们分成 $k$ 连续的段，每段的值为区间内所有数的位运算与，求在保证每一段的值和最小的前提下，最多能分成几段。

$1\le n \le 2 \cdot 10^5$。

解法 1 （动态规划）

首先，一个重要的性质是：若 $a_1 \,\&\, a_2 \,\&\ \ldots \,\&\ a_n \neq 0$，则最多只能分一段。因为分一段以上一定会让每段的值的和增加。

我们考虑 $a_1 \,\&\, a_2 \,\&\ \ldots \,\&\ a_n = 0$ 的情况。问题转化为：分成最多段，使每一段的位运算与为 $0$。

设 $f_i$ 代表前 $i$ 个数最多能分成几段。

$$f_i=\max_{0\le k<i}{\left\{f_k+1 \ |\ a_{k+1} \,\&\, \ldots \,\&\ a_i=0 \right\}}$$

这个转移方程是 $O(n^2)$ 的。我们注意到 $k$ 的取值是一段单调区间。我们预处理每个 $i$ 最早能取到的 $k$ 的值，然后维护 $f$ 的前缀最大值，就可以优化到 $O(n)$。

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

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 2e5+5;

char a[N][31];
int up[N][31]; // 从 (i,j) 找到第一个 0
int dp[N];
int dpmx[N]; // max(dp[1..i])

void solve(){
    int n=read();

    int val = -1;
    for(int i=1;i<=n;i++){
        int x=read();
        if(val==-1)val=x;
        else val&=x;

        for(int j=0;j<31;j++){
            a[i][j] = (x&(1<<j))>0?1:0; // 转化为二进制

            if(a[i][j]==0)up[i][j]=i;
            else up[i][j]=up[i-1][j]; // 这一位最早能到多少
        }
    }

    if(val!=0){
        puts("1");
        return;
    }

    for(int i=1;i<=n;i++){
        dpmx[i]=dpmx[i-1];
        
        int upto = 1e9;
        for(int j=0;j<31;j++){
            upto = min(upto, up[i][j]);
        }

        if(upto==0)continue;
        upto--;
        dp[i]=dpmx[upto]+1;
        dpmx[i]=max(dpmx[i-1],dp[i]);
    }

    printf("%d\n",dp[n]);
}

int main(){
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}

解法 2（贪心）

还是考虑 $a_1 \,\&\, a_2 \,\&\ \ldots \,\&\ a_n = 0$ 的情况。我们对于每一段，不停取数，只要位运算与的结果为 $0$ 就开始取下一段。如果最后一段的结果不是 $0$，那么就把最后一段并到前一段上。

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

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 2e5+5;

int a[N];

void solve(){
    int n=read();

    int val = -1;
    for(int i=1;i<=n;i++){
        a[i]=read();
        if(val==-1)val=a[i];
        else val&=a[i];
    }

    if(val!=0){
        puts("1");
        return;
    }

    int ans = 0;
    int now = -1;
    for(int i=1;i<=n;i++){
        if(now==-1){
            now=a[i];
        }else{
            now &= a[i];
        }

        if(now==0){
            ans++;
            now=-1;
        }
    }
    
    printf("%d\n",ans);
}

int main(){
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}

C. Vampiric Powers, anyone?

题意

给定 $n$ 个正整数，$a_1,a_2,\ldots,a_n$。每次可以选取一段后缀的异或，加入到序列的后面。求在进行了任意次操作后，最大能在序列中得到多少。

$1 \le n \le 10^5, 0 \le a_i < 2^8$。

解法 1 （0-1 Trie）

最后答案就是原序列的一段区间异或最大值。（证明有点烦，我就懒得写了）

求区间异或最大值可以转化成求前缀异或中两个任意的最大值。对于这个问题，可以用 0-1 Trie 在 $O(n \log n)$ 复杂度内解决。

注意每次 Trie 要清空。自己想办法随便清空就行了，注意不要全部清空，应该会超时，每次只清空用了的部分。

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

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 2e5+5;
int a[N],b[N];

int* dellist[N<<5], delcnt; // 保存要删除的节点
int ch[N << 5][2], tot, ans;
void insert(int x) {
    for (int i = 30, u = 1; i >= 0; --i) {
        int c = ((x >> i) & 1);  // 二进制一位一位向下取
        if (!ch[u][c]){
            ch[u][c] = ++tot;
            dellist[delcnt++]=&ch[u][c];
        }
        u = ch[u][c]; 
    }
}
void get(int x) {
    int res = 0;
    for (int i = 30, u = 1; i >= 0; --i) {
        int c = ((x >> i) & 1);
        if (ch[u][c^1]) {  // 如果能向和当前位不同的子树走，就向那边走
            u = ch[u][c^1];
            res |= (1<<i);
        }
        else u = ch[u][c];
    }
    ans = max(ans, res);  // 更新答案
}


void solve(){
    // memset(ch,0,sizeof(ch));
    ans=0; delcnt = 0;
    tot=1;

    int n=read();
    insert(0);
    for(int i=1;i<=n;i++){
        a[i]=read();
        b[i]=b[i-1]^a[i]; // 前缀异或
        insert(b[i]);
    }

    for(int i=1;i<=n;i++)get(b[i]);

    for(int i=0;i<delcnt;i++){
        *dellist[i] = 0; // 清空 Trie
    }

    printf("%d\n",ans);
}

int main(){
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}

解法 2（利用值域）

还是看求前缀异或中两个任意的最大值的问题。注意到本题的值域极小 $(0 \le a_i < 2^8)$，不妨直接将所有前缀异或排序，然后去重，最多只需要进行 $(2^8)^2$ 次比较。复杂度 $O(n\log n+(2^8)^2)$。

这个方法时间上没有很大区别，好处是空间占用极大降低。

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

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 2e5+5;
int a[N],b[N];

void solve(){

    int n=read();
    vector<int> x;

    x.push_back(0);
    for(int i=1;i<=n;i++){
        a[i]=read();
        b[i]=b[i-1]^a[i]; // 前缀异或
        x.push_back(b[i]);
    }

    sort(begend(x));
    auto p = unique(begend(x));

    int ans = 0;
    for(auto it1=x.begin();it1<p;it1++){
        for(auto it2=it1+1;it2<p;it2++){
            ans = max(ans,(*it1)^(*it2));
        }
    }

    printf("%d\n",ans);
}

int main(){
    int T=read();
    while(T--){
        solve();
    }
    return 0;
}

D. Professor Higashikata

题意

给定长度为 $n$ 的 $0-1$ 字符串 $s$，以及 $m$ 个区间 $l_i,r_i$。
问题：现在可以交换两个字符，求为了使 $s[l_1..r_1]s[l_2..r_2]\ldots s[l_m..r_m]$ 字典序最大，最少需要交换几次？
现在有 $q$ 次询问，每次询问反转 $s$ 的某一位，对于每次询问输出问题的答案。

解法

不难发现要使字典序最大就是要前面的位先满足是 $1$。于是，我们可以给每一位设定一个优先级。这个优先级可以用线段树，对于每个区间，我们进行区间赋值设定优先级，然后对于每一位我们做一个单点查询就可以得到每一位的优先级。

然后再用一颗线段树维护当前的 $s$。反转操作就是一个单点修改。
而问题的答案就是：$x-\text{前 } x \text{ 位 1 的个数}$。其中 $x=min(\text{1 的数量},\text{包含在新字符串中的位个数})$。$x$ 代表能使前 $x$ 个都是 $1$，所以只需要进行这么多次操作。进行一次区间查询就可以得到答案。

复杂度 $O((n+q)\log n)$。

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

using ll=long long;
using ull=unsigned long long;
using pii=pair<int,int>;
#define begend(x) x.begin(),x.end()
#define mem0(x) memset(x,0,sizeof(x))
#define YES puts("Yes")
#define NO puts("No")

int read(){
    int f=1,x=0;char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}

const int N = 2e5+5;
int pos[N],now=0;

char s[N];

struct SegmentTree{ // 线段树
    ll t[N<<2], tag[N<<2];
    SegmentTree(){
        mem0(t); memset(tag,-1,sizeof(tag));
    }
    void pushdown(int o,int l,int r){
        if(l==r)return;

        int lch = o<<1,rch=o<<1|1;
        int mid=(l+r)>>1;
        if(tag[o]!=-1){
            t[lch]=tag[o]*(mid-l+1);
            t[rch]=tag[o]*(r-mid);
            tag[lch]=tag[rch]=tag[o];
            tag[o]=-1;
        }
    }
    void modify(int o,int l,int r,int ql,int qr,ll qk){ // 赋值操作
        if(ql<=l && r<=qr){
            t[o]=(r-l+1)*qk;
            tag[o]=qk;
            return;
        }
        pushdown(o,l,r);
        int lch = o<<1,rch=o<<1|1;
        int mid=(l+r)>>1;
        if(ql<=mid)modify(lch,l,mid,ql,qr,qk);
        if(qr>mid)modify(rch,mid+1,r,ql,qr,qk);
        t[o]=t[lch]+t[rch];
    }
    ll query(int o,int l,int r,int ql,int qr){
        if(ql<=l && r<=qr){
            return t[o];
        }
        int lch = o<<1,rch=o<<1|1;
        int mid=(l+r)>>1;
        pushdown(o,l,r);
        int res = 0;
        if(ql<=mid)res+=query(lch,l,mid,ql,qr);
        if(qr>mid)res+=query(rch,mid+1,r,ql,qr);
        return res;
    }
}t1,t2;

// t1 维护每个位置的优先级，预处理用
// t2 维护按照优先级之后，每个位置到底是多少

bool cmp(const pii& a,const pii& b){
    return a.first>b.first || (a.first==b.first && a.second<b.second);
}

int main(){
    int n=read(),m=read(),q=read();
    scanf("%s",s+1);

    vector<pii> rang; // 所有的区间
    for(int i=0;i<m;i++){
        int l=read(),r=read();
        rang.push_back({l,r});
    }
    reverse(begend(rang)); // 倒序处理，因为前面的优先级更高，覆盖后面的
    for(int i=0;i<m;i++){
        int l = rang[i].first, r = rang[i].second;
        t1.modify(1,1,n,l,r,i+1); // 优先级为 i（越大越优先）,0 代表不存在
    }

    vector<pii> v;
    int realCnt = 0;
    for(int i=1;i<=n;i++){
        int priority = t1.query(1,1,n,i,i);
        if(priority!=0)realCnt++; // 有几位真正出现了
        v.push_back({priority, i});
    }
    sort(begend(v),cmp);
    int cnt=0;
    for(auto item:v){
        pos[item.second]=++cnt; // 保存原来的位映射到了哪里
        t2.modify(1,1,n,cnt,cnt,s[item.second]-'0'); // 设置这一位的初始值
    }

    for(int i=0;i<q;i++){
        int x=pos[read()];
        int valx = t2.query(1,1,n,x,x);
        t2.modify(1,1,n,x,x,valx^1); // 反转 x 上的值

        int pos = min(realCnt,(int)t2.t[1]); // 需要保证的是 1~pos 都是 1
        if(!pos){ // 没有 1，不需要动
            puts("0");continue;
        }

        int have1 = t2.query(1,1,n,1,pos); // 1~pos 中有几个 1
        printf("%d\n",pos-have1); // 需要把差的这些 1 从后面换到前面来
    }

    return 0;
}