Living-Dream 系列笔记 第24期

Problem

T1

/*
思路：
暴力枚举所有的和，用桶标记每个和出现的次数，找最大值且编号最小即可。
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;

int s1,s2,s3;
int sum=-1e9,ans;
int mp[131];

signed main(){
	ios::sync_with_stdio(0);
	cin>>s1>>s2>>s3;
	for(int i=1;i<=s1;i++)
		for(int j=1;j<=s2;j++)
			for(int k=1;k<=s3;k++)
				mp[i+j+k]++;
	for(int i=1;i<=131;i++)
		if(sum<mp[i])
			sum=mp[i],ans=i;
	cout<<ans;
	return 0;
}

T2

/*
思路：
对于每一个关键点，循环判断其是否在某个轰炸范围内，记录次数和最后一次轰炸即可。
注意输出格式。
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;

int m,n; 
struct point{
	int x,y,xx,yy;
}a[2031];

signed main(){
	ios::sync_with_stdio(0);
	cin>>m>>n;
	for(int i=1;i<=m;i++)
		cin>>a[i].x>>a[i].y>>a[i].xx>>a[i].yy;
	for(int i=1,xxx,yyy;i<=n;i++){
		cin>>xxx>>yyy;
		string pd="NO"; int last=0,cnt=0;
		for(int j=1;j<=m;j++)
			if(xxx>=a[j].x&&xxx<=a[j].xx&&yyy>=a[j].y&&yyy<=a[j].yy)
				pd="YES",last=j,cnt++;
		if(pd=="NO") cout<<pd<<'\n';
		if(pd=="YES") cout<<pd<<' '<<cnt<<' '<<last<<'\n';
	}
	return 0;
}

T3

/*
思路：
因为k有着十分明显的单调性，所以我们考虑二分答案。
最naive的check方式：
对于每个位置，每次取台上表演时间最小的牛，
将此位置的时间累加上它的跳舞时间，
最后在每个位置上的时间取max和tmax比较即可。
然后我们发现这样每次循环每个位置找最小值很慢，
所以我们考虑使用优先队列优化这一过程，
具体来说：
首先将前k头牛的跳舞时间加入队列，
并且记录z，表示上一头牛的结束时间；
再循环k+1~n头牛，不断将总时间累加上当前牛所需要的时间（即pq.top()-z)。
然后记录z=队首，并弹出队首；
最后舞台上还剩k头牛，再循环k次不断弹出队首，
并向上面一样更新z和总时间，
最后将总时间与tmax比较即可。
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,tmax;
int d[10031];

bool check(int x){
    int z=0,maxt=0;
	priority_queue<int,vector<int>,greater<int> > pq;
	for(int i=1;i<=x;i++) pq.push(d[i]);
	for(int i=x+1;i<=n;i++){
	   maxt+=pq.top()-z,z=pq.top();
       pq.pop(),pq.push(d[i]+z); 
	}
	while(x--){
	    maxt+=pq.top()-z,z=pq.top();
        pq.pop();
	}
	return maxt<=tmax; 
}

signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>tmax;
	for(int i=1;i<=n;i++) cin>>d[i];
	
	int l=0,r=n+1;
	while(l+1<r){
		int mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid;
	}	
	cout<<r;
	return 0;
}

T4

/*
思路：
考虑进行深搜，枚举出所有空调的组合方式，在这些组合方式中寻找合法且代价最少的即可。
如何判断合法性？我们仅需在读入时用桶将每个牛栏区间内的温度都累加ci，
最后在合法性验证中，对于每个空调，将每个区间的温度都减去pi，
最后判断每个区间温度都<0即可。
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;

int n,m,ans=1e9;
int tmp[31];
int t[131],tt[131];
bool vis[31];
struct cow{
	int s,t,c;
}cow[31];
struct cold{
	int a,b,p,m;
}cold[31];

bool check(int tot){
	for(int i=1;i<=131;i++) tt[i]=t[i];
	for(int i=1;i<=tot;i++)
		for(int j=cold[tmp[i]].a;j<=cold[tmp[i]].b;j++)
			tt[j]-=cold[tmp[i]].p;
	for(int i=1;i<=131;i++) 
		if(tt[i]>0) return 0;
	return 1;
}
void dfs(int x,int cnt,int sum){
	if(x==m+1){
		if(check(cnt)) ans=min(ans,sum);
		return;
	}
	
	tmp[cnt+1]=x;
	dfs(x+1,cnt+1,sum+cold[x].m);
	
	dfs(x+1,cnt,sum);
}

signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>cow[i].s>>cow[i].t>>cow[i].c;
		for(int j=cow[i].s;j<=cow[i].t;j++) t[j]+=cow[i].c;
	}
	for(int i=1;i<=m;i++)
		cin>>cold[i].a>>cold[i].b>>cold[i].p>>cold[i].m;
	dfs(1,0,0);
	cout<<ans;
	return 0;
}