专栏文章

CF1969

fflower1
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio1l7zt
此快照首次捕获于
2025/12/02 11:52
3 个月前
此快照最后确认于
2025/12/02 11:52
3 个月前
查看原文

CF1969

D

Description

有 nn 个商品，Alice 以 aia_i 的价格选择若干个物品进货，然后卖给 Bob。Bob 可以选择其中的 kk 个免费拿走，剩下的付款 bib_i 元。
Alice 希望自己的利润最大化，而 Bob 希望 Alice 的利润最小化，求 Alice 能获得的最大利润。

Solution

首先忽略所有 ai>bia_i >b_i 的物品，选择这些物品无论如何都是亏钱的。
考虑 Bob 会如何行动，为了使 Alice 收益最小，Bob 一定会免费拿走 bib_i 前 kk 大的物品。
考虑 Alice 会如何行动，设 Bob 拿走的物品 bib_i 最小值为 ww，那么 Alice 一定会进货所有 bi≤wb_i \le w 的物品。
因此我们按照 bib_i 排序，枚举 ww，预处理所有 bi≤wb_i \le w 的物品的贡献，对于 bi>wb_i > w 的物品，选择其中 aia_i 前 kk 小的物品一定是最优的，这容易用堆动态维护。

Code

CPP
#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

定义一个子段是独特子段，当且仅当存在一个整数在这个子段中出现恰好一次。
给定序列 aa ，求至少替换多少个元素，才能使得 aa 的所有子段为独特子段。

Solution

考虑扫描线，定义一个二维平面，横轴代表左端点，纵轴代表右端点，点 (l,r)(l,r) 代表子段 [l,r][l,r]。
依次考虑每一个点，设 preipre_i 为 aia_i 前面第一个与其相同的数， sufisuf_i 为 aia_i 后面第一个与其相同的数。
则对于所有 l∈[prei+1,i]l \in [pre_i+1,i]，r∈[i,sufi−1]r \in [i,suf_i-1]，[l,r][l,r] 为独特子段，这在二维平面上可以转化为一个矩形，可以用扫描线维护矩形面积并，这样未被矩形覆盖的点就不是独特子段。
我们从右到左扫描线，设当前扫描到左端点 xx，若有对应右端点未被覆盖。此时有结论，直接将 axa_x 替换为序列中未出现过的数一定是最优的。
感性证明一下，将 axa_x 替换后，对于所有 l∈[1,x]l \in [1,x]，r∈[x,n]r \in [x,n]，[l,r][l,r] 都为独特子段。
由于是从右到左的扫描线，当扫描到 xx 时，所有左端点 >x> x 的子段都被处理完成了，因此我们只关心修改后左端点 ≤x\le x 的子段，即扫描线左侧的影响。而修改 xx 所影响的矩形可以完全覆盖修改其他点的矩形，从而得证。

Code

CPP
#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

给定一个大小为 nn 的牌堆 aa，每张牌是 kk 种类型的一个。
初始摸 kk 张牌，每次打出两张牌，再摸两张牌，若打出的两张牌一样则的一分，最大化分数。

Solution

首先有结论，若手中有两张一样的牌，则打出这两张牌一定是不劣的。
因为若将两张 xx 拆成 (x,y)(x,y)，(x,z)(x,z) 打出，一定不如打出 (x,x)(x,x)，(y,z)(y,z)。
考虑当前手牌中没有两张一样的牌是什么情况，一定是所有 kk 种手牌各有一张，记这样的情况为非平凡局面。
尝试 dp，设 fif_i 表示当是第 ii 回合，现在是非平凡局面，所能获得的最多硬币数。
每次转移枚举打出的手牌，再暴力判断是或否合法，时间复杂度 O(n2k2)O(n^2 k^2)。
我们发现枚举打出的手牌非常劣，因为只有较少的情况是合法的。
准确来说，从 ii 转移到 jj，出牌方式是唯一的。
进一步，若在 ii 回合打出 (x,y)(x,y)，则在 i∼ji \sim j 手牌中，xx，yy 一定会出现奇数次，剩下的牌一定会出现偶数次。
因此每次转移的时候，我们枚举转移点并且维护后续手牌的奇偶性，仅在有两个类型的手牌个数为奇数时转移。
还有一种情况，若自 ii 回合后，转移不到非平凡局面。
剩下的牌中第 xx 张牌有 cntxcnt_x 张，则贡献为 ∑⌊cntx2⌋\sum \left\lfloor\frac{cnt_x}{2}\right\rfloor。
由于是向下取整，因此我们优先出 cntxcnt_x 为奇数的牌即可。
时间复杂度 O(n2)O(n^2)。

Code

(待续)

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...