2022“杭电杯”中国大学生算法设计超级联赛（3）

大量参考官方题解

1002 Boss Rush

题意：给定/(n/)个技能，每个技能最多使用一次，释放第/(i/)个技能需要的回合数为/(t_i/)，伤害持续的回合为/(len_i/)，持续回合的伤害为/(d_{i,j}(1/le j/le len_i)/)。在一个技能释放时不能释放其他技能，问伤害达到/(H/)需要的回合数至少为多少。/((1 /le n /le18,1/le H /le 10^{18},1 /le t_i,len_i /le 10^5,1 /le d_{i,j} /le 10^9)/)

思路：发现/(H/)很大，考虑二分答案 。二分答案需要求出给定的回合内能造成的最大伤害，暴力算的复杂度是阶乘，肯定T。但是发现/(n/)很小，可以二进制枚举已经释放过的技能，设这个集合为/(S/)，定义/(F_S/)为当前集合在给定回合内能够造成的最大伤害，枚举不在当前集合的技能/(x/)作为下一个技能进行状态转移

状态转移：

/[设技能x在剩余的回合数能造成的最大伤害为w//
F_{S+x}=max(F_{S+x},F_S+w)
/]

AC代码：

时间复杂度 /(O(n2^nlogans)/)

#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = (int)(a); i <= (int)(b); i ++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

typedef long long LL;

const int N = 20, M = 1e5 + 10;

int n,dd[20];
LL H,f[1<<N];

struct WEAPON{
	int k,m;
	LL dmg[M];
}wp[N];

void init(){
	dd[0]=1;
	rep(i,1,20) dd[i]=dd[i-1]<<1;
}

bool check(int rd){
	rep(i,0,(1<<n)-1)  f[i]=-1;
	f[0]=0;
	for(int j=0;j < 1<<n;j++){
		if(f[j]==-1) continue;
		
		LL cur_w=0;
		
		rep(k,0,n-1) if(j>>k&1) cur_w+=wp[k].k;
			
		rep(k,0,n-1){
			if(j>>k&1) continue;
			if(rd-cur_w>0){
				int t=rd-cur_w;
				f[j+dd[k]]=max(f[j+dd[k]],f[j]+wp[k].dmg[min(wp[k].m,t)]);
				if(f[j+dd[k]]>=H) return true;
			}
		}
		
	}
	return false;
}

void work() {
	cin>>n>>H;
	int sum=0;
	rep(i,0,n-1) 
		rep(j,0,M-1) wp[i].dmg[j]=0;
	rep(i,0,n-1){
		cin>>wp[i].k>>wp[i].m;
		sum+=max(wp[i].k,wp[i].m);
		rep(j,1,wp[i].m){
			LL t;
			cin>>t;
			wp[i].dmg[j]=wp[i].dmg[j-1]+t;
		}
	}
	
	int l=1,r=sum+1;
	while(l<r){
		int mid=l+r>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
	
	cout<<(l==sum+1?-1:l-1)<<endl;
}

signed main() {
	IO
    init();
    
	int test=1;
	cin >> test;
    
	while (test--) 
		work();

	return 0;
}

1011 Taxi

题意：给定/(n/)个点，第/(i/)个点的坐标为/((x_i,y_i)/) ，权值为 /(w_i/)，有/(q/)个询问，每个询问给定一个点，坐标为/((x’,y’)/)，求/(min(|x^{‘}-x_i|+|y^{‘}-y_i|,w_i)(1 /le i /le n)/)

思路：如果没有/(w_i/)的限制，那么是经典问题。根据/(|x|=max(x,-x)/)，有

/[max/left/{|x^{‘}-x_i|+|y^{‘}-y_i| /right/} //=max/left/{max(x^{‘}-x_i,-x^{‘}+x_i)+max(y{‘}-y_i,-y^{‘}+y_i)/right/}//=max/left/{x^{‘}-x_i+y^{‘}-y_i,-x^{‘}+x_i+y^{‘}-y_i,x^{‘}-x_i-y^{‘}+y_i,-x^{‘}+x_i-y^{‘}+y_i/right/}//=max/left/{(x^{‘}+y^{‘})+(-x_i-y_i),(x^{‘}-y^{‘})+(-x_i+y_i),(-x^{‘}+y^{‘})+-x_i-y_i),(-x^{‘}-y^{‘})+(x_i+y_i)/right/}
/]

可以发现只要分别记录/(x_i+y_i,x_i-y_i,-x_i+y_i,-x_i-y_i/)的最大值就可以在/(O(1)/)时间内求出所有点到/((x^{‘},y^{‘})/)的曼哈顿距离的最大值。

接下来的步骤是把/(n/)个点以/(w_i/)从小到大排序，维护上述四个值的后缀最大值然后二分区间，推荐看官方题解十分详细

AC代码：

时间复杂度/(O((n+q)logn)/)

#include<bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = (int)(a); i <= (int)(b); i ++)
#define rrep(i, a, b) for(int i = (int)(a); i >= (int)(b); i --)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 1e5 + 10;

struct Point{
	int X,Y,W;
}p[N];

int a[N],b[N],c[N],d[N];

bool cmp(Point &x,Point &y){
	return x.W<y.W;
}

void work() {
	int n,q;
	cin>>n>>q;
	rep(i,1,n) cin>>p[i].X>>p[i].Y>>p[i].W;
	
	sort(p+1,p+n+1,cmp);
	a[n+1]=-INF,b[n+1]=-INF,c[n+1]=-INF,d[n+1]=-INF;
	rrep(i,n,1){
		a[i]=max(p[i].X+p[i].Y,a[i+1]);
		b[i]=max(p[i].X-p[i].Y,b[i+1]);
		c[i]=max(-p[i].X+p[i].Y,c[i+1]);
		d[i]=max(-p[i].X-p[i].Y,d[i+1]);
	}
	
	while(q--){
		int x,y;
		cin>>x>>y;
		
		int l=1,r=n,ans=0;
		while(l<=r){
			int mid=l+r>>1;
			int cur_w=p[mid].W;
			int cur_d=-x-y+a[mid];
			cur_d=max(cur_d,-x+y+b[mid]);
			cur_d=max(cur_d,x-y+c[mid]);
			cur_d=max(cur_d,x+y+d[mid]);
			if(cur_w<=cur_d){
				ans=max(ans,cur_w);
				l=mid+1;
			}
			else{
				ans=max(ans,cur_d);
				r=mid-1;
			} 
		}
		
		cout<<ans<<endl;
	}
}

signed main() {
	IO
	int test=1;
	cin >> test;
	
	while (test--) 
		work();
	
	return 0;
}

能力有限欢迎勘误