概要

我 AK 了，srds因为有Q老师的免费测试套餐，才发现题目名错了(。

题目难度不大

题目

T1

随便脚算一下人数完了

比赛后 \(-\) 比赛前 \(+\) 晋级的。

code:

#include<bits/stdc++.h>
using namespace std;
int x[10],y[10],yin,huang,bai; 
int main()
{
	freopen("promotion.in","r",stdin);
	freopen("promotion.out","w",stdout);
	for(int i=1;i<=4;i++)
	{
		cin>>x[i]>>y[i];
	}
	bai=y[4]-x[4];
	huang=y[3]+bai-x[3];
	yin=y[2]+huang-x[2];
	cout<<yin<<"\n"<<huang<<"\n"<<bai<<"\n";
	return 0;
}

T2

枚举 boom 的源头，再 bfs 一下，把当前能连锁 boom 的 boom 了。

#include<bits/stdc++.h>
using namespace std;
int n,a[110],ans;
int vis[110];
struct node
{
	int x,r;
};
queue <node> q; 
void bfs(int X)
{
	//int times=0;
	while(!q.empty()) q.pop();
	node l;l.x=X;l.r=1;q.push(l);
	while(!q.empty())
	{
		//times++;
		l=q.front();q.pop();
		int x=l.x,r=l.r;
		if(vis[x] || x<1 || x>n) continue;
		//cerr<<"**"<<x<<" "<<r<<"\n";
		vis[x]=1;
		l.r=r+1;
		for(int i=1;i<=n;i++)
		{
			if(abs(a[i]-a[x])<=r && !vis[i])
			{
				l.x=i;
				q.push(l);
				//cerr<<"**"<<x<<" to "<<i<<"\n";
			} 
		}
	}
}
int main()
{
	freopen("angry.in","r",stdin);
	freopen("angry.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++)
	{
		memset(vis,0,sizeof(vis));
		bfs(i);
		int cnt=0;
		for(int j=1;j<=n;j++)
		{
			cnt+=vis[j];
			//cerr<<vis[j]<<" ";
		}
		ans=max(ans,cnt);
		//cerr<<"\n";
	}
	cout<<ans<<"\n";
	return 0;
}

T3

从 \((1,1)\) 开始 bfs，把当前能点亮的访问，如果点亮的四周有，就 \(\texttt{push}\) 一下。

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
const int dx[]={114514,1,-1,0,0},dy[]={1919810,0,0,1,-1};
struct NodeV
{
	int x,y;
};
struct NodeBfs
{
	int x,y;
};
vector <NodeV> v[110][110];
bool vis[110][110],islight[110][110];
queue <NodeBfs> q;
int main()
{
	freopen("lightson.in","r",stdin);
	freopen("lightson.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,a,b;
		scanf("%d%d%d%d",&x,&y,&a,&b);
		v[x][y].push_back({a,b});
	}
	q.push({1,1});
	while(!q.empty())
	{
		int x=q.front().x,y=q.front().y;
		q.pop();
		if(x<1 || y<1 || x>n || y>n || vis[x][y]) continue;
		vis[x][y]=1;
		islight[x][y]=1;
		for(int i=0;i<v[x][y].size();i++)
		{
			int nx=v[x][y][i].x;
			int ny=v[x][y][i].y;
			islight[nx][ny]=1;
			if(vis[nx][ny]==0)
			{
				if(vis[nx-1][ny] || vis[nx+1][ny] || vis[nx][ny-1] || vis[nx][ny+1]) q.push({nx,ny});
			}
		}
		for(int i=1;i<=4;i++)
		{
			int nx=x+dx[i],ny=y+dy[i];
			if(!vis[x][y] || !islight[nx][ny]) continue;
			q.push({nx,ny});
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			//cerr<<islight[i][j];
			ans+=islight[i][j];
		}
		//cerr<<"\n";
	}
	cout<<ans<<"\n";
	return 0;
}

T4

我太菜了，不会用 DP。

可以考虑减半只会对一次影响(因为如果两次及以上就可以换成整的 \(+\) 一半)

枚举 \(4\) 种情况即可

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL T,t,a,b,c,d,ans=11919810;
int main()
{
	freopen("feast.in","r",stdin);
	freopen("feast.out","w",stdout);
	cin>>T>>a>>b;
	if(a<b) swap(a,b);
	T*=2;
	c=a;
	d=b;
	a*=2;
	b*=2;
	
	//the fang'an of 1st
	t=T;
	for(int i=0;i<=t/a;i++)
	{
		ans=min(ans,t-(i*a)-(t-i*a)/b*b);
		//cerr<<ans<<"\n";
	}
	
	//the fang'an of 2nd
	t=T-c;
	for(int i=0;i<=t/a;i++)
	{
		ans=min(ans,t-(i*a)-(t-i*a)/b*b);
		//cerr<<ans<<"\n";
	}
	
	//the fang'an of 3rd
	t=T-d;
	for(int i=0;i<=t/a;i++)
	{
		ans=min(ans,t-(i*a)-(t-i*a)/b*b);
		//cerr<<ans<<"\n";
	}
	
	//the fang'an of 4th
	t=T-c-d;
	for(int i=0;i<=t/a;i++)
	{
		ans=min(ans,t-(i*a)-(t-i*a)/b*b);
		//cerr<<ans<<"\n";
	}
	//cerr<<ans<<"\n";
	cout<<(T-ans)/2<<"\n";
	return 0;
}
/*
4 possible
1st all do not use
2nd use a/2
3rd use b/2
4th use (a+b)/2
*/