省流：唐了但没完全唐。

牛客挑战赛74

A

简单DP。用第二维状态0表示没拿的多一，1表示拿和没拿的相等，2表示拿了的多一。

挂了一发的原因是起始状态忘记初始化了。

int n,a[100005]; 
long long f[100005][3];//状态0表示没拿多一，1表示拿和没拿相等，2表示拿了的多一 
int main(){
	R(n);
	for(int i=1;i<=n;i++){
		R(a[i]);
	}
	f[0][1]=0;	//初始时拿和没拿相等
	f[0][0]=f[0][2]=-1e18;	//唐：忘记初始化了 
	for(int i=1;i<=n;i++){
		f[i][1]=max(f[i-1][0]+a[i],f[i-1][2]);
		f[i][0]=f[i-1][1];
		f[i][2]=f[i-1][1]+a[i];
	}
	cout<<max(max(f[n][0],f[n][1]),f[n][2])<<endl;
	return 0;
}

B

贪心，将每个手斧的破坏程度从小到大排序，分别在树高的集合中二分，与能砍的树中树高最大的匹配。

int n,m,a[100005],b[100005];
multiset<int> s;
int main(){
	R(n);R(m);
	for(int i=1;i<=n;i++){
		R(a[i]);
		s.insert(a[i]);
	}
	for(int i=1;i<=m;i++)
		R(b[i]);
	sort(b+1,b+1+m);
	int cnt=0;
	for(int i=1;i<=m;i++){
		if(s.empty()) break;
		auto p=s.upper_bound(b[i]);
		if(p!=s.begin()){
			s.erase(--p);
			cnt++;
		}
	}
	cout<<cnt<<endl;
	return 0;
}

C

分类讨论题。详情见代码。

int T;
long long a1,b1,a2,b2;
int main(){
	R(T);
	while(T--){
		R(a1);R(b1);R(a2);R(b2);
		long long ans=max(a1+b1,a2+b2);
		//A 写数学 B 写语文
		ans=min(ans,max(a1+b1,max(a1,b2)+a2/2));		//B抄A不抄
		ans=min(ans,max(max(a1,b2)+b1/2,max(a1,b2)+a2/2));		//都抄
		ans=min(ans,max(max(a1,b2)+b1/2,b2+a2));			//A抄B不抄
		//B 写数学 A 写语文
		ans=min(ans,max(a1+b1,max(b1,a2)+b2/2));		//B抄A不抄
		ans=min(ans,max(max(a2,b1)+a1/2,max(b1,a2)+b2/2));		//都抄
		ans=min(ans,max(max(b1,a2)+a1/2,b2+a2));			//A抄B不抄
		
		//唐：忘记可以一个人写两份作业了给另一个人抄了。
		//A 写数学语文
		ans=min(ans,max(a1+b1,a1+max(b1,a2/2)+b2/2));
		ans=min(ans,max(a1+b1,b1+max(a1,b2/2)+a2/2));
		//B 写数学语文
		ans=min(ans,max(a2+b2,a2+max(b2,a1/2)+b1/2));
		ans=min(ans,max(a2+b2,b2+max(a2,b1/2)+a1/2));
		
		printf("%lld\n",ans);
	}
	return 0;
}

D

数据结构题（大概）

一个想法是把每次操作3扣除的血量累加起来考虑，就可以实现对整体血量进行一个计算。

假设扣除的总血量为$dlt$，那么我们维护的血量为$hp_i=realhp_i+dlt$。具体表现为编号$x$加入战斗时血量设为$b_x+dlt$，撤出战斗时血量设为0（或者负数），为编号$x$恢复血量$h$时血量等于$\min\{hp_x+h,b_x+dlt\}$。

以上操作1，2，4可以用一个数组维护血量。

对于操作3，我们注意到每个人死亡后不会再参与战斗，那么我们可以同时用一个set去维护血量，每次操作3时暴力从小到大判断set中各元素血量是否小于$dlt$进而进行删除。这样对于操作3，每个元素最多被遍历一次。

操作1，2，4在维护数组时同时维护set即可。

总复杂度$O((n+k) \log_2 n)$

int n,k;
long long m;
int a[100005],b[100005];
typedef pair<ll,int> P;
set<P> hp;
long long hp2[100005];
int main(){
	R(n);R(m);R(k);
	long long atk=0;
	for(int i=1;i<=n;i++){
		R(a[i]);
		atk+=a[i];
	}
	for(int i=1;i<=n;i++){
		R(b[i]);
		hp.insert(P(b[i],i));
		hp2[i]=b[i];
	}
	ll dlt=0;
	int excnt=0;
	while(k--){
		int opt,x,h;
		R(opt);R(x);
		if(opt==1){
			hp.insert(P(b[x]+dlt,x));
			hp2[x]=b[x]+dlt;
			atk+=a[x];
			excnt--;
		}
		else if(opt==2){
			hp.erase(P(hp2[x],x));
			hp2[x]=0;
			atk-=a[x];
			excnt++;
		}
		else if(opt==3){
			dlt+=x;
			for(auto i=hp.begin();i!=hp.end()&&i->first<=dlt;i=hp.begin()){
				atk-=a[i->second];
				hp2[i->second]=0;
				hp.erase(i);
			}
		}
		else{
			R(h);
			if(hp2[x]>0){
				hp.erase(P(hp2[x],x));
				hp2[x]=min(hp2[x]+h,b[x]+dlt);
				hp.insert(P(hp2[x],x));
			}
		}
		if(hp.size()+excnt<=0){
			puts("NO");
			return 0;	
		}
		m-=atk;
		if(m<=0){
			puts("YES");
			printf("%llu\n",hp.size()+excnt);
			return 0;
		}
	}
	puts("NO");
	return 0;
}

其余咕。