论如何 AK ABC346

__vector__ · 2024-03-24 12:07:37 · 题解

赛时过 ABCDEF，同时想出了 G 题正解但没时间写了。

A

模拟。

B

注意 W,B 很小，所以实际合法区间的 l,r 也不会很大。
把 S 设置为暴力重复 500 次 wbwbwwbwbwbw 差不多肯定可以了。

然后暴力枚举合法区间。

C

先算出 1 到 K 的和，然后依次减去里面出现过的就可以了。

D

我是比较麻烦的分类讨论做法。
先思考下 dp 有哪些需要关注哪些状态？

• 目前枚举到了第 i 个字符，计算前 i 个字符组成的字符串的答案。
• 另外，转移的时候发现，我们似乎不知道第 i-1 个字符是什么，没法转移。所以加入状态：第 i 个字符是什么？
• 另外还要注意一点：正好有一对相邻值相等，那么我们还需要考虑另一个状态：前 i 个字符是否已经存在一对相临值相等？
• 我们还需要求出最小代价，这个加入 dp 值就可以了。

综上，设置 dp_{1 \le i \le n,a \in (0,1),b \in (0,1)} ，注意 a 代表真，b 代表假，那么这个 dp 代表前 i 个字符，且第 i 个字符发生变化的真假为 a，前 i 个字符存在一对相邻值相等的真假为 b，此时最小操作代价。

转移：

#define FOR(i,a,b) for(int i=a;i<=b;i++)
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
dp[1][0][0] = 0;
dp[1][1][0] = c[1];
FOR(i, 2, n)
{
    // case1: 上一个不变
    if (s[i - 1] == s[i])
    { // 和上一个相同
        // ca1: 这次变，不会影响相同数量变化
        ckmn(dp[i][1][1], dp[i - 1][0][1] + c[i]);
        ckmn(dp[i][1][0], dp[i - 1][0][0] + c[i]);
        // ca2 这次不变
        ckmn(dp[i][0][1], dp[i - 1][0][0]);
    }
    else
    {
        // ca1：这次不变，不影响相同数量变化
        ckmn(dp[i][0][1], dp[i - 1][0][1]);
        ckmn(dp[i][0][0], dp[i - 1][0][0]);
        // ca2: 这次便
        ckmn(dp[i][1][1], dp[i - 1][0][0] + c[i]);
    }

    // case2：上一个变
    if (s[i - 1] == s[i])
    {
        // ca1：这次不变，不会影响相同数量变化
        ckmn(dp[i][0][1], dp[i - 1][1][1]);
        ckmn(dp[i][0][0], dp[i - 1][1][0]);
        // ca2: changed now
        ckmn(dp[i][1][1], dp[i - 1][1][0] + c[i]);
    }
    else
    {
        // ca1: 这次变，不会影响相同数量
        ckmn(dp[i][1][1], dp[i - 1][1][1] + c[i]);
        ckmn(dp[i][1][0], dp[i - 1][1][0] + c[i]);
        // ca2:  not change
        ckmn(dp[i][0][1], dp[i - 1][1][0]);
    }
}
printf("%lld\n", min(dp[n][1][1], dp[n][0][1]));

E

以下，可能会用括号代表一个整体。

考虑每次操作实际会有多少影响。

显然，第 i 次操作的影响为：第 i 次覆盖的点数 - （(\cup_{j=i+1}^M 第 j 次操作覆盖的点集）\cap (第 i 次覆盖的点集)）的大小

而这个怎么处理呢？

• 如果存在 j \gt i，使得第 i,j 次操作相同，那么第 i 次操作可以忽略。

• 否则，第 i 次操作实际贡献为第 i 次覆盖点数 - 第 j \gt i 次操作中与第 i 次覆盖方向不同的操作数量。
  倒着算就可以了。

  F

  单调性是显然的，可以二分 k。

然后，其实没啥技术含量的，判定是否合法，只需要枚举每一位模拟就行。

细节不少，但是没啥记录的意义，唯一要注意的是 check 过程可能会爆 long long。

G

直接做不好做，那么反过来考虑每个元素对哪些 [l,r] 有贡献。

假设目前是第 i 个元素，p 是最小的 p 满足区间 [p,i] 只存在一个 a_i，q 是最大的 q 满足区间 [i,q] 只存在一个 a_i。那么显然，对于所有的 p \le l \le i,i \le r \le q，区间 [l,r] 合法。

注意到这里的贡献对 l 和 r 各进行了一个区间范围的限制，而上面实际上可以抽象成一个二维平面，所有满足 p \le l \le i,i \le r \le q 的点 (p,q) 都可以计入最终贡献，也就是说它实际上将一个矩形内的所有整点加入了最终贡献。

最终答案可以转换成，有多少点 (p,q) 满足 1 \le p \le q \le n，且被任意一个矩阵覆盖过。

这个东西扫描线搞定。

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define REP(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back()
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int maxn=2e5+5;
int n;
int a[maxn];
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
/*
对于每个 i，设有效区间 [a,b]

那么对于区域 [a<=l<=i][i<=r<=b] 所有点都有解
加入矩阵即可。
然后扫描线求出矩阵面积并，然后就是答案。
*/
vector<int> pos[maxn];
struct Matrix{
    int x_l,x_r,y_l,y_r;
}matrix[maxn];
Matrix mkmt(int a,int b,int c,int d){
    Matrix res;
    res.x_l=a,res.x_r=b,res.y_l=c,res.y_r=d;
    return res;
}
int cntmat;
struct Seg_Tree{
    int cov[maxn<<2];
    int len[maxn<<2];
    int L[maxn<<2],R[maxn<<2];
    void build(int pos,int l,int r){
        L[pos]=l,R[pos]=r;
        if(l==r){
            return;
        }
        int mid=(l+r)/2;
        build(pos*2,l,mid);
        build(pos*2+1,mid+1,r);
    }
    void pushup(int pos){
        if(cov[pos]){
            len[pos]=(R[pos]-L[pos]+1);
        }else{
            if(pos*2<maxn*4){
                len[pos]=len[pos*2]+len[pos*2+1];
            }else{
                len[pos]=0;
            }
        }
    }
    void chg(int pos,int l,int r,int add){
        if(L[pos]>=l&&R[pos]<=r){
            cov[pos]+=add;
            pushup(pos);
            return;
        }
        if(R[pos]<l||L[pos]>r)return;
        int mid=(L[pos]+R[pos])/2;
        if(mid>=l)chg(pos*2,l,r,add);
        if(mid<r)chg(pos*2+1,l,r,add);
        pushup(pos);
    }
    int getsum(){
        return len[1];
    }
}sgt;
struct Line{
    int y_up,y_dw,x;
    int add;
}line[maxn*2];
void solve(){
    scanf("%d",&n);
    FOR(i,1,n){
        scanf("%d",&a[i]);
        pos[a[i]].emplace_back(i);
    }
    FOR(i,1,n){
        for(int j=0;j<pos[i].size();j++){
            int l=1,r=n;
            if(j!=0){
                l=pos[i][j-1]+1;
            }
            if(j+1!=pos[i].size()){
                r=pos[i][j+1]-1;
            }
            matrix[++cntmat]=mkmt(l,pos[i][j],pos[i][j],r);
    //      printf("add  = %d %d %d %d\n",l,i,i,r);
        }
    }
    assert(cntmat==n);
    FOR(i,1,cntmat){
        line[(i-1)*2+1].y_up=matrix[i].y_r;
        line[(i-1)*2+1].y_dw=matrix[i].y_l;
        line[(i-1)*2+1].x=matrix[i].x_l;
        line[(i-1)*2+1].add=1;

        line[(i-1)*2+2].y_up=matrix[i].y_r;
        line[(i-1)*2+2].y_dw=matrix[i].y_l;
        line[(i-1)*2+2].x=matrix[i].x_r+1;
        line[(i-1)*2+2].add=-1;
    }
    sort(line+1,line+cntmat*2+1,[&](Line& a,Line& b){
        return a.x<b.x;
    });
    sgt.build(1,1,n);
    ll s1=0;
    line[cntmat*2+1].x=n+1;//占位
    // 注意到，有些线段可能会到达 x=n 位置，此时贡献
    FOR(i,1,cntmat*2){
        ll len=line[i+1].x-1-line[i].x+1;// 当前纵线的有效长度
        sgt.chg(1,line[i].y_dw,line[i].y_up,line[i].add);
        s1+=(ll)sgt.getsum()*len;
    }
    printf("%lld\n",s1);
}
int main()
{
    int T=1;
    while(T--){
        solve();
    }
    return 0;
}