Educational Codeforces Round 155 (Rated for Div. 2) F. Last Man Standing(ST表/dp的松弛思想)

最新推荐文章于 2025-03-25 06:15:00 发布

小衣同学

最新推荐文章于 2025-03-25 06:15:00 发布

阅读量231

点赞数

分类专栏：思维题 # 倍增/RMQ((ST/二维ST/二维线段树/KD树) 文章标签： st表松弛 dp

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

版权

思维题同时被 2 个专栏收录

112 篇文章

订阅专栏

倍增/RMQ((ST/二维ST/二维线段树/KD树)

10 篇文章

订阅专栏

题目

t(t<=10)组样例，每次给出n(n<=2e5)个人，

第i个人有hi(hi<=2e5)条命，每条命有ai(ai<=2e5)点血

当对人造成x点伤害时，如果x<当前血量，血量减少x，否则，扣掉一条命，令血量回满

游戏开始时，你可以设置一个正整数x，

然后每一轮，对所有玩家都造成x点伤害，

当所有玩家阵亡时，游戏结束，游戏结束时结算得分

最后阵亡的玩家，假设在第a轮阵亡，而倒数第二个阵亡的玩家，假设在第b轮阵亡，

则最后阵亡的玩家的分数为a-b（a=b时，得分为0），其他玩家的分数为0

对于每个玩家i，独立地求，正整数x任意设置时，玩家i能获得的最大得分

思路来源

jiangly代码/nanami代码

题解

题解1（ST表）

简单手玩后发现，每个人能坚持的轮数是 $h_{i}*\left \lceil \frac{a_{i}}{x}\right \rceil$ ，

所以，可以枚举每个x，对于x倍数枚举y，

对于[1,y]内的值v来说， $\left \lceil \frac{v}{y} \right \rceil$ 是相同的，区间求一下h的最大值（需要值对应的所在位置）

区间求最大值，st表O(nlogn)预处理一下，然后O(1)求，总复杂度O(nlogn)

题解2（后缀+松弛思想）

仔细思考后发现，ST表的过程是没有必要的，

实际只需要从大到小扫一遍，维护后缀最大值即可

因为一个值(hi,ai)，

在小于ai的地方被枚举到的话，只会不超过答案

而在ai的地方被枚举到的时候，等于答案的值可以取到，

也就意味着可以取到最大值，

所以，扫两遍，第一遍求最大值，第二遍求次大值

代码1（ST表）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=4e5+5;
const int lim=2e5;
ll a[MAXN],h[MAXN],n,lg[MAXN];
ll ans[MAXN];
struct node{int x,y;}s[20][MAXN];
node operator +(node x,node y){
	for(int i:{y.x,y.y})if(i&&i!=x.x&&i!=x.y){
		if(h[x.x]<h[i]){
			x.y=x.x;x.x=i;
		}else if(h[x.y]<h[i]) x.y=i;
	}
	return x;
}
node ask(int l,int r){
	int k=lg[r-l+1];
	return s[k][l]+s[k][r-(1<<k)+1];
}
void solve(){
	cin>>n;
	memset(ans,0,sizeof(ans));
	for(int i=1;i<=n;i++) cin>>h[i];
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<MAXN;i++) s[0][i]={0,0};
	for(int i=1;i<=n;i++) s[0][a[i]]=s[0][a[i]]+(node){i,0};
	for(int i=1;i<20;i++){
		for(int j=1;j+(1<<i)-1<MAXN;j++)
			s[i][j]=s[i-1][j]+s[i-1][j+(1<<i-1)];
	}
	for(int i=1;i<=lim;i++){
		auto val=[&](int x){return h[x]*((a[x]+i-1)/i);}; 
		int mx1=0,mx2=0;
		for(int l=1,r=i;l<=lim;l+=i,r+=i){
			auto it=ask(l,r);
//			cout<<"gp "<<it.x<<' '<<it.y<<endl;
			for(int j:{it.x,it.y}) if(j){
				if(val(j)>val(mx1)) mx2=mx1,mx1=j;
				else if(val(j)>val(mx2)) mx2=j;
			}
		}
//		cout<<i<<' '<<mx1<<' '<<mx2<<endl;
		ans[mx1]=max(ans[mx1],val(mx1)-val(mx2));
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<' ';cout<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	for(int i=2;i<MAXN;i++) lg[i]=lg[i>>1]+1;
	int _;cin>>_;
	while(_--) solve();
}

代码2（后缀+松弛思想）

#include<bits/stdc++.h>
//#include<iostream>
//#include<map>
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 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 pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define pb push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
//std::mt19937_64 gen(std::chrono::system_clock::now().time_since_epoch().count());
//ll get(ll l, ll r) { std::uniform_int_distribution<ll> dist(l, r); return dist(gen); }
const int N=2e5+10,M=2e5;
int t,n,h[N],a[N];
ll ans[N];
array<P,2>mx[N];
map<P,int>id;
void init(){
    rep(i,1,M){
        mx[i][0]=mx[i][1]=P(0,0);
        ans[i]=0;
    }
    id.clear();
}
int main(){
	sci(t);
	while(t--){
        sci(n);
        init();
        rep(i,1,n)sci(h[i]);
        rep(i,1,n){
            sci(a[i]);
            P x=P(h[i],a[i]);
            id[x]=i;
            rep(j,0,1){
                if(x>mx[a[i]][j]){
                    swap(x,mx[a[i]][j]);
                }
            }
        }
        per(i,M-1,1){
            rep(k,0,1){
                P x=mx[i+1][k];
                rep(j,0,1){
                    if(x>mx[i][j]){
                        swap(x,mx[i][j]);
                    }
                }
            }
        }
        rep(x,1,M){
            ll v1=-1,v2=-1,fir=-1,sec=-1;
            int p=-1;
            for(int i=1;i<=M;i+=x){
                ll w=1ll*mx[i][0].fi*(i+x-1)/x;
                if(w>v1)v1=w,p=i;
            }
            fir=v1;
            for(int i=1;i<=M;i+=x){
                ll w=1ll*mx[i][i<=p && mx[i][0]==mx[p][0]].fi*(i+x-1)/x;
                if(w>v2)v2=w;
            }
            sec=v2;
            if(fir>sec){
                p=id[mx[p][0]];
                ans[p]=max(ans[p],fir-sec);
            }
        }
        rep(i,1,n){
            printf("%lld%c",ans[i]," \n"[i==n]);
        }
    }
    return 0;
}