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\)作为下一个技能进行状态转移

状态转移：

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)\)，有

可以发现只要分别记录\(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;
}

能力有限欢迎勘误