2024-03-20竞赛笔记

2024/3/20

惨不忍睹的周赛分数……

P3078 [USACO13MAR] Poker Hands S

#include<bits/stdc++.h>
using namespace std;
long long n,a[114514],ans;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	ans=a[1];
	for(int i=1;i<n;i++){
		if(a[i+1]>a[i])
			ans+=a[i+1]-a[i];
	}
	cout<<ans;
	return 0;
}

P1843 奶牛晒衣服

得分：$\mathbf\color{green} 100$

二分做法2

//核心：二分枚举满足烘干条件的结果，取最优 
#include <bits/stdc++.h>
using namespace std;
long long aaa[10000001]; 
int n;
int a,b,total,l,mid;//设l(必须是整数）是第i件衣服使用的烘干机时长
bool check(int time){//检查是否可以在规定时间干掉，t是指每件衣服都必须在t秒以内干掉
	total=0;//烘干机已经使用的时间 
	for(int i=1;i<=n;i++){
		l=(aaa[i]-time*a);//(time*a)是总共可以烘干的时长
		l/=b;//总共可以烘干的时长/烘干机额外的时长，也就是使用的烘干机时长 
		bool can=(aaa[i]>=time*a);//判断是否多出（为烘干） 
		if(can){
		    int test=aaa[i]-time*a;//如果不能在time规定的时间以内烘干 
			if(test%b!=0) l++;//如果超过烘干机使用的时长就要延长
			total+=l;//烘干机使用时间++ 
		}
	}
	return total<=time;//判断这件衣服可不可以在这个时间内烘干，能true，不能false 
}
signed main() {
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++) cin>>aaa[i];
	int left=1,right=0x7fffff,sum=right;//sum因此也要是极大数，为了后面的比较 
	while(left<=right){//二分 
		mid=(left+right)>>1;
		if(check(mid)){//如果时间多余（不是最优） 
			sum=min(sum,mid);//先取最小值（因为是最少时间） 
			right=mid-1;
		}
		else{
			left=mid+1;
		}
	}//这里一直判断，知道得出满足烘干时间的结果 
	cout<<sum<<endl;//输出 
	return 0;
} 

贪心

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,less<int> > q;
int n,a,b;
int tim,mx;
int main()
{
	cin>>n>>a>>b;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		q.push(x);
	}
	mx=q.top();
	q.pop();
	while(mx>tim*a)
	{
		tim++;
		mx-=b;
		q.push(mx);
		mx=q.top();
		q.pop();
	}
	cout<<tim;
    return 0;
}

P6568 [NOI Online #3 提高组] 水壶

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,k,a[N];
long long s,ans;
int main(){
	cin>>n>>k;
	int l=1,r=k+1;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=l;i<=r;i++) s+=a[i];
	while(r<=n){
		ans=max(ans,s);
		l++;r++;
		s-=a[l-1];
		s+=a[r];
	}
	cout<<ans;
}

P1056 排座椅

#include<bits/stdc++.h>
using namespace std;
int m,n,k,l,d;
int ax,ay,bx,by;
struct hl
{
	int id;
	int n;//需求度 
} x[1010],y[1010];
bool cmp1(hl a,hl b)
{
	return a.n>b.n;
}
bool cmp2(hl a,hl b)
{
	return a.id<b.id;
}
int main()
{
	cin>>m>>n>>k>>l>>d;
	for(int i=1;i<=n;i++) 
		x[i].id=i;
	for(int i=1;i<=n;i++) 
		y[i].id=i;
	for(int i=1;i<=d;i++)
	{
		cin>>ay>>ax>>by>>bx;
		if(ay==by) 
			x[min(ax,bx)].n++;
		else 
			y[min(ay,by)].n++;
	}
	//按需求度排序 
	sort(x+1,x+1+n,cmp1);
	sort(y+1,y+1+m,cmp1);
	//按照id进行排序 
	sort(x+1,x+1+l,cmp2);
	sort(y+1,y+1+k,cmp2);
	for(int i=1;i<=k;i++) 
		cout<<y[i].id<<" ";
	cout<<endl;
	for(int i=1;i<=l;i++) 
		cout<<x[i].id<<" ";
    return 0;
}

P1902 刺杀大使

#include<bits/stdc++.h>
using namespace std;
int n,m,a[1001][1001];
bool v[1001][1001];
int l=0,r=1000,ans=0;
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
struct node{
	int x,y;
};
bool check(int mid){
	memset(v,0,sizeof(v));
	queue<node> q;
	node start;
	start.x=1,start.y=1;
	q.push(start);
	v[1][1]=1;
	while(!q.empty()){
		node head=q.front();
		for(int i=0;i<=3;i++){
			int xx=dx[i]+head.x;
			int yy=dy[i]+head.y;
			if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&v[xx][yy]!=1&&a[xx][yy]<mid){
				if(xx==n) return 1;
				v[xx][yy]=1;
				node next;
				next.x=xx,next.y=yy;
				q.push(next);
			}
		}
		q.pop();
	}
	return 0;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	cout<<ans-1;
	return 0;
}