专栏文章

S2T1 youyou 的垃圾桶

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

文章操作

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

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

P11217 youyou 的垃圾桶 题解

题目传送门

分析

youyou 死亡时，必定时被垃圾桶打了几轮，再在最后被前几个垃圾桶干掉
所以可以枚举前面的轮数，再枚举最后的垃圾桶数，一定要记得答案-1
时间复杂度 O(qnlog⁡2W)O(qn\log_2W)
预计 20pts

优化

小结论
对于每一个垃圾桶来说，它打满 nn 轮，造成的总伤害为
ai×20+ai×21+...+ai×2n−1a_i \times 2^0 + a_i \times 2^1+...+a_i \times 2^{n-1}
提公因数
ai×(20+21+...+2n−1)a_i \times (2^0+2^1+...+2^{n-1})
可得
ai×(2n−1)a_i \times (2^n-1)
所以，我们要找到的是第一个 ⩾W\geqslant W 的总伤害
即 ∑i=1nai×(2x−1)⩽W\sum\limits_{i=1}^n a_i \times (2^{x}-1) \leqslant W 的最大 xx
设 ∑i−1nai=sum\sum\limits_{i-1}^{n} a_i = sum
则 sum×(2x−1)⩽Wsum \times (2^x-1) \leqslant W
得 2x−1⩽Wsum2^x-1 \leqslant \frac{W}{sum}
即 2x⩽Wsum+12^x \leqslant \frac{W}{sum} + 1
就是 x⩽log⁡2(Wsum+1)x \leqslant \log_2{(\frac{W}{sum}+1)}
因为 xx 是正整数，所以用向下取整，剩下的留给最后一轮
x=⌊log⁡2(Wsum+1)⌋x = \lfloor \log_2{(\frac{W}{sum}+1)} \rfloor
可证明 ⌊log⁡2(Wsum+1)⌋=⌊log⁡2(⌊Wsum+1⌋)⌋\lfloor \log_2{(\frac{W}{sum}+1)} \rfloor = \lfloor \log_2{( \lfloor \frac{W}{sum}+1 \rfloor ) } \rfloor
实现为
CPP
int x=floor(log2(1.0*(w+sum)/sum));
更新 O(n)O(n) ，查询 O(n)O(n)
总时间复杂度为 O(qn)O(qn)
预计得分 35pts

大优化

  • 从更新优化：快速对一段区间更新，可用差分、线段树，差分查询 O(n)O(n)，不合适，所以用线段树
  • 查询：既然是线段树，最后一行就不用从1累加了，由于答案满足单调性，可用二分
CPP
bool check(int x,int y){
	int sum=query(1,1,x);
	return sum*((1ll<<y))>=now;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q>>w;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];//累加和
	}
	build(1,1,n);
	while(q--){
		ans=0;
		int l,r,d;
		cin>>l>>r>>d;
		sum+=(r-l+1)*d;//和更新
		upd(1,l,r,d);
		int x=floor(log2(1.0*(w+sum)/sum));//算轮数
		ans+=n*x;
		now=w-sum*((1ll<<x)-1);//剩下的血量
		int anss=0;
		int ll=0,rr=n+1;
		while(ll<=rr){
			int mid=ll+rr>>1;//mid为最后一行的垃圾桶数
			if(check(mid,x)){
				rr=mid-1;
				anss=mid;
			}else{
				ll=mid+1;
			}
		}
		cout<<ans+anss-1<<endl;
	}
	return 0;
}
时间复杂度 O(qlog⁡22n)O(q\log_2^2n)
大概 60-70pts

小优化

根据题目，O(qlog⁡2n)O(q\log_2 n) 可以过
主要瓶颈在二分+线段树
能否把两个log并在一起呢？
把二分塞进线段树，因为只需要1-x，所以在线段树中向左或右儿子递归，最终返回受致命一击的垃圾桶下标再加上 n×x−1 n \times x - 1即可
实现
CPP
int query(int x,int a/*血量*/,int b/*轮数*/){
	if(t[x].v*(pw2[b-1])<=a || t[x].l==t[x].r){//这些垃圾桶打完才死或没死
		return t[x].r-t[x].l+1;
	}
	push_down(x);
	if(a<=t[ls].v*(pw2[b-1])){//在左儿子打死
		return query(ls,a,b);
	}else{//在右儿子打死
		return t[ls].r-t[ls].l+1+query(rs,a-t[ls].v*(pw2[b-1]),b);
	}
	return 0;
}
时间复杂度 O(qlog⁡2n)O(q\log_2n)
100pts

AC code

AC
记录
CPP
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define ls x<<1
#define rs x<<1|1
using namespace std;
const int N=2e5+10;
int n,q,w,sum;
int a[N],pw2[110];
int ans;
int now;
struct node{
	int l,r,v,tag;
}t[N<<2];
void push_up(int x){
	t[x].v=t[ls].v+t[rs].v;
	return;
} 
void push_down(int x){
	t[ls].v+=(t[ls].r-t[ls].l+1)*t[x].tag;
	t[rs].v+=(t[rs].r-t[rs].l+1)*t[x].tag;
	t[ls].tag+=t[x].tag;
	t[rs].tag+=t[x].tag;
	t[x].tag=0;
	return;
}
void build(int x,int l,int r){
	t[x].l=l;
	t[x].r=r;
	t[x].tag=0;
	if(l==r){
		t[x].v=a[l];
		return;
	}
	int mid=l+r>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	push_up(x);
	return;
}
void upd(int x,int l,int r,int k){
	if(l<=t[x].l && t[x].r<=r){
		t[x].v+=(t[x].r-t[x].l+1)*k;
		t[x].tag+=k;
		return;
	}
	push_down(x);
	int mid=t[x].l+t[x].r>>1;
	if(l<=mid){
		upd(ls,l,r,k);
	}
	if(r>mid){
		upd(rs,l,r,k);
	}
	push_up(x);
	return;
}
int query(int x,int a/*血量*/,int b/*轮数*/){
//	cout<<t[x].l<<' '<<t[x].r<<' '<<t[x].v*(pw2[b-1])<<' '<<a<<' '<<b<<endl;
	if(t[x].v*(pw2[b-1])<=a || t[x].l==t[x].r){
		return t[x].r-t[x].l+1;
	}
	push_down(x);
	if(a<=t[ls].v*(pw2[b-1])){
		return query(ls,a,b);
	}else{
		return t[ls].r-t[ls].l+1+query(rs,a-t[ls].v*(pw2[b-1]),b);
	}
	return 0;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q>>w;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	pw2[0]=1;
	for(int i=1;i<=62;i++){
		pw2[i]=pw2[i-1]*2;
	}
	build(1,1,n);
	while(q--){
		ans=0;
		int l,r,d;
		cin>>l>>r>>d;
		sum+=(r-l+1)*d;
		upd(1,l,r,d);
		int x=floor(log2(1.0*(w+sum)/sum));
		ans+=n*x;
		now=w-sum*(pw2[x]-1);
		int anss=0;
		int ll=0,rr=n+1;
		cout<<ans+(now==0?0:query(1,now,x+1))-1<<endl;
	}
	return 0;
}
散花！！！

评论

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

正在加载评论...