CF1969

flower1 · 2025-09-01 13:44:55 · 个人记录

CF1969

D

Description

有 n 个商品，Alice 以 a_i 的价格选择若干个物品进货，然后卖给 Bob。Bob 可以选择其中的 k 个免费拿走，剩下的付款 b_i 元。

Alice 希望自己的利润最大化，而 Bob 希望 Alice 的利润最小化，求 Alice 能获得的最大利润。

Solution

首先忽略所有 a_i >b_i 的物品，选择这些物品无论如何都是亏钱的。

考虑 Bob 会如何行动，为了使 Alice 收益最小，Bob 一定会免费拿走 b_i 前 k 大的物品。

考虑 Alice 会如何行动，设 Bob 拿走的物品 b_i 最小值为 w，那么 Alice 一定会进货所有 b_i \le w 的物品。

因此我们按照 b_i 排序，枚举 w，预处理所有 b_i \le w 的物品的贡献，对于 b_i > w 的物品，选择其中 a_i 前 k 小的物品一定是最优的，这容易用堆动态维护。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
struct node{
    int a,b;
}d[N];
int T,n,k,num,sum[N],ans;
priority_queue<int>q;
bool cmp(node x,node y){
    return x.b<y.b;
}
int read(){
    int k=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9')
        k=k*10+ch-'0',ch=getchar();
    return k;
}
signed main(){
    T=read();
    while(T--){
        n=read(),k=read();
        ans=0;
        for(int i=1;i<=n;i++)
            d[i].a=read();
        for(int i=1;i<=n;i++)
            d[i].b=read();
        sort(d+1,d+1+n,cmp);
        for(int i=1;i<=n;i++){
            sum[i]=sum[i-1];
            if(d[i].a<d[i].b)
                sum[i]+=d[i].b-d[i].a;
        }
        num=0;
        for(int i=n;i>=1;i--){
            if(i<=n-k){
                ans=max(ans,sum[i]-num);
                q.push(d[i].a);
                num+=d[i].a-q.top();
                q.pop();
            }
            else{
                num+=d[i].a;
                q.push(d[i].a);
            }
        }
        printf("%lld\n",ans);
        while(!q.empty())
            q.pop();
    }
    return 0;
}

E

Description

定义一个子段是独特子段，当且仅当存在一个整数在这个子段中出现恰好一次。

给定序列 a ，求至少替换多少个元素，才能使得 a 的所有子段为独特子段。

Solution

考虑扫描线，定义一个二维平面，横轴代表左端点，纵轴代表右端点，点 (l,r) 代表子段 [l,r]。

依次考虑每一个点，设 pre_i 为 a_i 前面第一个与其相同的数， suf_i 为 a_i 后面第一个与其相同的数。

则对于所有 l \in [pre_i+1,i]，r \in [i,suf_i-1]，[l,r] 为独特子段，这在二维平面上可以转化为一个矩形，可以用扫描线维护矩形面积并，这样未被矩形覆盖的点就不是独特子段。

我们从右到左扫描线，设当前扫描到左端点 x，若有对应右端点未被覆盖。此时有结论，直接将 a_x 替换为序列中未出现过的数一定是最优的。

感性证明一下，将 a_x 替换后，对于所有 l \in [1,x]，r \in [x,n]，[l,r] 都为独特子段。

由于是从右到左的扫描线，当扫描到 x 时，所有左端点 > x 的子段都被处理完成了，因此我们只关心修改后左端点 \le x 的子段，即扫描线左侧的影响。而修改 x 所影响的矩形可以完全覆盖修改其他点的矩形，从而得证。

Code

#include <bits/stdc++.h>
#define ls k<<1
#define rs k<<1|1
using namespace std;
const int N=3e5+5;
struct node{
    int l,r,k;
};
int T,n,a[N],b[N],pr[N],sf[N],ans;
int mi[N<<2],tag[N<<2];
vector<node>e[N];
int read(){
    int k=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9')
        k=k*10+ch-'0',ch=getchar();
    return k;
}
void pushup(int k){
    mi[k]=min(mi[ls],mi[rs]);
}
void pushdown(int k){
    if(tag[k]){
        mi[ls]+=tag[k],tag[ls]+=tag[k];
        mi[rs]+=tag[k],tag[rs]+=tag[k];
        tag[k]=0;
    }
}
void build(int k,int l,int r){
    tag[k]=0;
    if(l==r){
        mi[k]=0;
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(k);
}
void modify(int k,int l,int r,int x,int y,int v){
    if(x>y) return;
    if(x<=l&&r<=y){
        mi[k]+=v,tag[k]+=v;
        return;
    }
    pushdown(k);
    int mid=(l+r)>>1;
    if(x<=mid) modify(ls,l,mid,x,y,v);
    if(mid+1<=y) modify(rs,mid+1,r,x,y,v);
    pushup(k);
}
int main(){
    T=read();
    while(T--){
        ans=0;
        n=read();
        for(int i=1;i<=n;i++)
            a[i]=read();
        for(int i=1;i<=n;i++){
            pr[i]=b[a[i]];
            b[a[i]]=i;
        }
        for(int i=1;i<=n;i++) b[i]=n+1;
        for(int i=n;i>=1;i--){
            sf[i]=b[a[i]];
            b[a[i]]=i;
        }
        for(int i=1;i<=n;i++) b[i]=0;
        for(int i=1;i<=n;i++){
            e[pr[i]].push_back((node){i,sf[i]-1,-1});
            e[i].push_back((node){i,sf[i]-1,1});
        }
        build(1,1,n);
        for(int i=n;i>=1;i--){
            for(node j:e[i])
                modify(1,1,n,j.l,j.r,j.k);
            modify(1,1,n,1,i-1,1);
            if(mi[1]==0){
                modify(1,1,n,i,n,1);
                ans++;
            }
            modify(1,1,n,1,i-1,-1);
        }
        printf("%d\n",ans);
        for(int i=0;i<=n;i++)
            e[i].clear();
    }
    return 0;
}

F

Description

给定一个大小为 n 的牌堆 a，每张牌是 k 种类型的一个。

初始摸 k 张牌，每次打出两张牌，再摸两张牌，若打出的两张牌一样则的一分，最大化分数。

Solution

首先有结论，若手中有两张一样的牌，则打出这两张牌一定是不劣的。

因为若将两张 x 拆成 (x,y)，(x,z) 打出，一定不如打出 (x,x)，(y,z)。

考虑当前手牌中没有两张一样的牌是什么情况，一定是所有 k 种手牌各有一张，记这样的情况为非平凡局面。

尝试 dp，设 f_i 表示当是第 i 回合，现在是非平凡局面，所能获得的最多硬币数。

每次转移枚举打出的手牌，再暴力判断是或否合法，时间复杂度 O(n^2 k^2)。

我们发现枚举打出的手牌非常劣，因为只有较少的情况是合法的。

准确来说，从 i 转移到 j，出牌方式是唯一的。

进一步，若在 i 回合打出 (x,y)，则在 i \sim j 手牌中，x，y 一定会出现奇数次，剩下的牌一定会出现偶数次。

因此每次转移的时候，我们枚举转移点并且维护后续手牌的奇偶性，仅在有两个类型的手牌个数为奇数时转移。

还有一种情况，若自 i 回合后，转移不到非平凡局面。

剩下的牌中第 x 张牌有 cnt_x 张，则贡献为 \sum \left\lfloor\frac{cnt_x}{2}\right\rfloor。

由于是向下取整，因此我们优先出 cnt_x 为奇数的牌即可。

时间复杂度 O(n^2)。

Code

(待续)