The 2020 ICPC Asia Yinchuan Regional Programming Contest M. Tower of the Sorcerer(数论分块+单点更新ST表优化dp)

小衣同学

已于 2023-11-05 19:21:41 修改

阅读量177

点赞数 1

分类专栏： # 分块/定期重构/莫队 # dp优化乱搞AC 文章标签：数论分块 ST表 dp优化

于 2023-11-05 19:21:25 首次发布

本文链接：https://blog.csdn.net/Code92007/article/details/134233208

版权

乱搞AC 同时被 3 个专栏收录

34 篇文章

订阅专栏

dp优化

15 篇文章

订阅专栏

分块/定期重构/莫队

7 篇文章

订阅专栏

题目

你有一个初始攻击值strw(1<=strw<=1e5)和无穷的血量，

以下有n(n<=1e5)个怪物，

第i个怪物有stri(1<=stri<=1e5)的攻击值和hpi(1<=hpi<=1e5)的血量

每打一个怪时，你先攻击，怪物受到你的攻击值的伤害，

如果怪物血量<=0，就认为怪物死亡

否则，怪物对你造成怪物的攻击值的伤害，

然后再你攻击，重复这个过程，直至怪物的血量<=0

打死一只怪后，你会更新你的攻击值为 $a=max(a,b)$ ，

其中a为你之前的攻击值，b为打死的这只怪的攻击值

求最优打怪顺序下，打死n只怪物时，

受到的最小伤害的总和是多少，输出这个值

思路来源

乱搞ac

题解

首先，最优的打怪顺序，

肯定是先利用若干只怪，不断提升攻击值，把攻击值升到最大，再把剩下的怪都打死

换言之，攻击值从初始攻击值上升到最大攻击值，

是需要按怪物的攻击值增序取一个子序列，不在子序列的怪都最后打

所以，按怪物的攻击值排增序，

1. 已经小于等于初始攻击值(不能提升攻击值)的怪物，肯定是留到最后打

2. 对于攻击值大于当前人物攻击值的怪物，有两种决策，

一种是最后打，一种是打死，然后获得对应的攻击值提升，

线段树做法

很自然想到线段树维护，

线段树上i的位置的值，表示当前攻击值为i时，打赢之前的所有怪的最小受到伤害的值

当前打死的怪的攻击值是st时，无需考虑大于st的位置的值

①最后打，[1,st]对应用最大攻击值去打当前怪，是一个区间加

②用当前攻击值打死，对怪物的血量hp数论分块，

数论分块内的一段区间对怪物造成的伤害是相同的，

打死的次数是血量除以伤害向上取整 $\left \lceil \frac{hp}{str} \right \rceil$ ，

所以受到的伤害也是固定的，即 $(\left \lceil \frac{hp}{str} \right \rceil -1)*str_{monster}$

数论分块后，更新st单点，是一个单点取min的操作

线段树这样做的复杂度是 $O(n\sqrt{n}log(n))$ ，会TLE

ST表做法

线段树的操作是一个区间加和一个单点更新，

如果将区间加的值当做偏移量，就只有st一个位置的单点更新

而且，st表示可以按增序更新单点的，

具体来说，dp[j][i]表示以i为右端点长度为 $2^j$ 的一段的区间的最小值

就把复杂度降到了 $O(n\sqrt{n}+n*logn)$ ，可以通过

注意怪物的攻击值是离散的，

但是，为了更新 $dp[j][i]$ 值时，需要用到 $dp[j-1][i-(1<<(j-1))]$ 的值

所以，每一个位置的dp值都需要单点更新，不存在怪物的点，更新成默认最大值INF即可

向上取整版数论分块

不是很懂 $\left \lceil \frac{n}{l} \right \rceil$ 的数论分块怎么写，

但是通过手玩，发现常用的向下版的数论分块，

最多只有l、r两个端点的值会变，所以手动if判断一下

AC代码（ST表单点更新）

// Problem: M. Tower of the Sorcerer
// Contest: Codeforces - The 2020 ICPC Asia Yinchuan Regional Programming Contest
// URL: https://codeforces.com/gym/104022/problem/M
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e5+10,M=1e5,K=18;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int n,str,lg[N];
ll mn[K][N];
//ll sum;
void upd(int p,ll v){
	mn[0][p]=min(mn[0][p],v);
	rep(i,1,K-1){
		mn[i][p]=mn[i-1][p];
		if(p>=(1<<(i-1)))mn[i][p]=min(mn[i][p],mn[i-1][p-(1<<(i-1))]);
	}
}
ll amn(int l,int r){
	int k=lg[r-l+1];
	ll v=min(mn[k][l+(1<<k)-1],mn[k][r]);
	//printf("l:%d r:%d v:%lld\n",l,r,v);
	return v;
}
P a[N];
int cal(int hp,int x){
	//printf("hp:%d x:%d\n",hp,x);
	return (hp+x-1)/x;
}
void sol(){
	rep(i,2,M)lg[i]=lg[i>>1]+1;
	sci(n),sci(str);
	int mx=str;
	rep(i,1,n){
		sci(a[i].fi),sci(a[i].se);
		mx=max(mx,a[i].fi);
	}
	if(str>1){
		a[++n]=P(str,1);
		str=1;
	}
	sort(a+1,a+n+1);
	memset(mn,INF,sizeof mn);
	upd(str,0);
	ll sum=0;
	int las=1;
	rep(i,1,n){
		int st=a[i].fi,hp=a[i].se;
		int w=cal(hp,mx);
		ll planb=1ll*(w-1)*st;
		sum+=planb;
		ll now=INF;
		rep(j,las,st)upd(j,INF);
		las=st+1;
		for(int l=1,r;l<=hp;l=r+1){
			r=hp/(hp/l);
			int v=cal(hp,l),L=l,R=r;
			if(L>1 && cal(hp,L-1)==v)L--;
			if(cal(hp,R)!=v)R--;
			if(L>=st)break;
			R=min(R,st-1);
			ll plana=1ll*(v-1)*st;
			now=min(now,amn(L,R)+plana);
		}
		if(hp<st)now=min(now,amn(hp,st));
		//seg.add(1,1,st,planb);
		upd(st,now-planb);
		//printf("st:%d now:%lld planb:%lld now-planb:%lld\n",st,now,planb,now-planb);
	}
	//printf("sum:%lld amn:%lld\n",sum,amn(mx,mx));
	printf("%lld\n",sum+amn(mx,mx));
}
int main(){
	sol();
	return 0;
}

TLE代码（线段树）

// Problem: M. Tower of the Sorcerer
// Contest: Codeforces - The 2020 ICPC Asia Yinchuan Regional Programming Contest
// URL: https://codeforces.com/gym/104022/problem/M
// Memory Limit: 512 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=1e5+10,M=1e5;
const ll INF=1e16;
int n,str;
//ll sum;
P a[N];
struct segtree{
	int n;
	struct node{int l,r;ll v,c;}e[N<<2];
	#define l(p) e[p].l
	#define r(p) e[p].r
	#define v(p) e[p].v
	#define c(p) e[p].c
	void up(int p){v(p)=min(v(p<<1),v(p<<1|1));}
	void bld(int p,int l,int r){
		l(p)=l;r(p)=r;
		if(l==r){v(p)=INF;c(p)=0;return;}
		int mid=l+r>>1;
		bld(p<<1,l,mid);bld(p<<1|1,mid+1,r);
		up(p);
	}
	void psd(int p){
		if(c(p)){
			v(p<<1)+=c(p);
			c(p<<1)+=c(p);
			v(p<<1|1)+=c(p);		
			c(p<<1|1)+=c(p);
			c(p)=0; 
		}
	}
	void init(int _n){n=_n;bld(1,1,n);}
	void chg(int p,int x,ll v){
		if(l(p)==r(p)){v(p)=min(v(p),v);return;}
		int mid=l(p)+r(p)>>1;
		psd(p);
		chg(p<<1|(x>mid),x,v);
		up(p);
	}
	void add(int p,int ql,int qr,ll v){
		if(ql<=l(p)&&r(p)<=qr){
			v(p)+=v;
			c(p)+=v;
			return;
		}
		psd(p);
		int mid=l(p)+r(p)>>1;
		if(ql<=mid)add(p<<1,ql,qr,v);
		if(qr>mid)add(p<<1|1,ql,qr,v);
		up(p);
	}
	ll amn(int p,int ql,int qr){
		if(ql<=l(p)&&r(p)<=qr)return v(p);
		int mid=l(p)+r(p)>>1;
		ll res=INF;
		psd(p);
		if(ql<=mid)res=min(res,amn(p<<1,ql,qr));
		if(qr>mid)res=min(res,amn(p<<1|1,ql,qr));
		return res;
	}
}seg;
int cal(int hp,int x){
	//printf("hp:%d x:%d\n",hp,x);
	return (hp+x-1)/x;
}
void sol(){
	sci(n),sci(str);
	int mx=str;
	rep(i,1,n){
		sci(a[i].fi),sci(a[i].se);
		mx=max(mx,a[i].fi);
	}
	if(str>1){
		a[++n]=P(str,1);
		str=1;
	}
	sort(a+1,a+n+1);
	seg.init(M);
	seg.chg(1,str,0);
	rep(i,1,n){
		int st=a[i].fi,hp=a[i].se;
		int w=cal(hp,mx);
		ll planb=1ll*(w-1)*st;
		//sum+=planb;
		ll now=INF;
		//printf("i:%d mx:%d hp:%d w:%d planb:%lld\n",i,mx,hp,w,planb);
		// if(st<=str){
			// seg.add(1,st,st,planb);
			// continue;
		// }
		for(int l=1,r;l<=hp;l=r+1){
			r=hp/(hp/l);
			//printf("l:%d r:%d hp:%d\n",l,r,hp);
			int v=cal(hp,l),L=l,R=r;
			while(L>1 && cal(hp,L-1)==v)L--;
			while(cal(hp,R)!=v)R--;
			if(L>=st)break;
			R=min(R,st-1);
			ll plana=1ll*(v-1)*st;
			//printf("L:%d R:%d v:%d st:%d plana:%lld\n",L,R,v,st,plana);
			now=min(now,seg.amn(1,L,R)+plana);
		}
		if(hp<st)now=min(now,seg.amn(1,hp,st));
		seg.add(1,1,st,planb);
		seg.chg(1,st,now);
	}
	printf("%lld\n",seg.amn(1,mx,mx));
}
int main(){
	sol();
	return 0;
}