2022 Hangzhou Electric Cup Super League 3

Boss Rush

题目链接：[Boss Rush](Problem - 7163 (hdu.edu.cn))

题意：Characters have multiple skills,Skill needs to be cast first,Then it will cause damage,You can only use new skills after the damage is done.,Damage is dealt second by second,The damage may be different every second,However, the sequence of skills cannot be changed,You can choose to put or not put each skill,Ask at least need how many seconds to kill the monster.

题解：二分答案,According to the time to determine whether the time can kill the monster.

从前往后依次发动若干个技能,Then the time when the next skill can be activated is equal to the sum of the time required to activate the skills in between.,因此只和之前发动过哪些技能有关.

时间复杂度：$O(n^{n}lo{g}^{ans})$

//二分答案 
#include <iostream>
#include <cstring>
using namespace std;
typedef long long int ll;
ll hp;
int n;
long long dp[20][100005];//存储第ibefore skillslenframe damage --前缀和 
int t[100005],d[100005];//存储第iThe cast time and damage dealt time of each skill 
int sum[(1<<18)+1];//s二进制 中1representativei个技能, 0Represents not letting goi个技能 sum存储当前sThe time it takes for the skill to be released 
ll f[(1<<18)+1];//记录sAll skills represented by binary numbers The total amount of damage that can be caused 
bool check(int x){
	for(int s=0;s<(1<<n);s++){
		f[s]=-1; //For the initial damage-1; 
	}
	f[0]=0;
	for(int s=0;s<(1<<n);s++){
		ll w=f[s];//通过f[s]获取当前sCorresponding total damage --fArrays are computed later 
		if(w<0)continue;//If the damage is negative ,definitely not 
		if(w>=hp)return 1;//If the damage is greater thanhp... 
		int cur=sum[s];//当前s所花费的时间 
		if(cur>x)continue;//If the time taken is greater than the required time 不行了 
		for(int i=0;i<n;i++){
			if(!((s>>i)&1)){//如果s never let goi个技能 
				if(cur+d[i]-1<=x){//如果加上第iThe time of a skill still does not time out ,then the damage can be added to all 
					f[s|(1<<i)]=max(f[s|(1<<i)],w+dp[i][d[i]-1]);
				}
				else{//如果超时,Then the damage can only be added to the frame that does not time out.,Also make sure to update Damage increases 
					f[s|(1<<i)]=max(w+dp[i][x-cur],f[s|(1<<i)]);
				}
			}
		}
	}
	return 0;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int tt;
	cin>>tt;
	while(tt--){
		cin>>n>>hp;
		int l=0,r=0;
		for(int i=0;i<n;i++){
			cin>>t[i]>>d[i];//输入第iCasting time and damage time of each skill 
			r+=t[i]+d[i]-1;//r存储前iA skill always take time Solve the upper bound of the dichotomous answer 
			for(int j=0;j<d[i];j++){
				cin>>dp[i][j];//输入第i个技能的第jThe damage a frame can do 
			}
			for(int j=1;j<d[i];j++){
				dp[i][j]+=dp[i][j-1];//计算第i个技能前jThe sum of the damage the frame can do 
			}
		}
		memset(sum,0,sizeof(sum));
		for(int s=1;s<(1<<n);s++){
			sum[s]=sum[s-(s&-s)]+t[__builtin_ctz(s&-s)];//Fast calculations with bit operations sHow long does it take to complete the corresponding skills?
			//smeans just one more1,Then other skills must have been let go before,So just add on the previous basis 最新的那个1the corresponding time. 
		}
		int ans=-1;//Initially means can't kill monsters 
		while(l<=r){//二分答案 
			int mid=(l+r)/2;
			if(check(mid)){//Check when the time ismidWhen can you kill the monster 
				ans=mid;
				r=mid-1;
			}else{
				l=mid+1;
			}
		}
		cout<<ans<<'\n';
	}
}

Package Delivery

题目链接：[Package Delivery](Problem - 7170 (hdu.edu.cn))

题意：总共有n件货物,Every time a pickup take at mostk件,Each item can only be picked up at one time period,问,It takes at least a few times to pick up all the goods.

题解：先按照结束时间排序,Sort by start time,Pick up sooner by end time,At the same time, check whether the goods can also be picked up according to the start time（When such goods are taken away, they need to be sorted by the end time,The later the end time, the sooner it will be picked up）.

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int,int> P;
P no[100005];
int ql[100005],qr[100005];
bool del[100005];
priority_queue<P,vector<P>,greater<P> >que;
inline col(int i,int j){ 
    return no[i].first<no[j].first;
}
inline cor(int i,int j){
    return no[i].second<no[j].second;
}
void solve(){
    memset(no,0,sizeof(no));
    memset(ql,0,sizeof ql);
    memset(qr,0,sizeof qr);
    memset(del,0,sizeof(del));
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>no[i].first>>no[i].second;
        ql[i]=qr[i]=i;
    }
    sort(ql+1,ql+n+1,col);//按照结束时间排序
    sort(qr+1,qr+n+1,cor);//按照开始时间排序
    
    int j=1;
    int ans=0;
    for(int i=1;i<=n;i++){
        if(del[qr[i]])continue;
        ans++;
        while(j<=n&&no[ql[j]].first<=no[qr[i]].second){//Anything with a start time earlier than or equal to the end time of the current shipment can be taken away
            que.push(P(no[ql[j]].second,ql[j]));//Priority queue sorted by end time
            j++;
        }
        for(int w=1;w<=k;w++){//Take away the mostk件货物
            if(que.empty())break;
            pair<int,int>pa;
            pa=que.top();//Priority to take away goods with an early end time
            que.pop();
            del[pa.second]=1;
        }
    }
    cout<<ans<<'\n';
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}