526互联

AtCoder Beginner Contest 305 ABCDE

发布时间 2023-06-17 08:58:02作者: nannan4128

AtCoder Beginner Contest 305

A - Water Station

Problem Statement

题意：水站每\(5km\)设一个，给你一个\(N\) \(km\)的位置，问你离它最近的水站位置 。

Solution

题解：模5在乘5,比较给出的点的左边和右边的点，取min

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n;
	cin>>n;
	int t = n/5*5;
	if(abs(t-n)<(t+5-n))
		cout<<t<<endl;
	else cout<<(t+5)<<endl;

	return 0;
}

B - ABCDEFG

Problem Statement

题意：告诉你个点间距离，之后询问任意两点间距离

Solution

题解：前缀和(但是手动QAQ)

#include<bits/stdc++.h>
using namespace std;
const int N = 100;
int dist[N];
int main()
{
	dist[0] = 0;
	dist[1] = 3;
	dist[2] = 4;
	dist[3] = 8;
	dist[4] = 9;
	dist[5] = 14;
	dist[6] = 23; 
	char a,b;
	cin>>a>>b;
	if(a>b)
		swap(a,b);
	cout<<dist[b-'A']-dist[a-'A']<<endl;
	return 0;
}

C - Snuke the Cookie Picker

Problem Statement

题意：给你\(N\)行\(M\)列的矩阵，由.和#组成，#表示饼干。

然后，饼干被吃了一口，问你吃的位置(保证答案唯一)。

Solution

题解：枚举每一个.的位置，看它的上下左右的#的个数，取max，最大的那个就是ans。

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
char a[N][N];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	int ans = 0,x,y;
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=m;j++)
		{
			int cnt = 0;
			if(a[i][j]=='.')
			{
				if(i-1>=1)
					cnt+=(a[i-1][j]=='#');
				if(i+1<=n)
					cnt+= (a[i+1][j]=='#');
				if(j-1>=1)
					cnt+=(a[i][j-1]=='#');
				if(j+1<=m)
					cnt+=(a[i][j+1]=='#');
				if(cnt>ans)
				{
					ans = cnt;
					x = i,y = j;
				}
			}
		}
	}
	cout<<x<<" "<<y<<endl;
	return 0;
}

D - Sleep Log

Problem Statement

题意：给你一段长度为\(N\)的序列，且\(N\)是奇数，奇数的时间是起床时间，偶数的时间是睡觉时间。

给你一段区间，询问你睡眠时间。

以样例为例：

输入
7
0 240 720 1320 1440 1800 2160
3
480 1920
720 1200
0 2160

输出
480
0
960

img

Solution

题解：看到对区间操作，很容易想到前缀和。但是数据很大，正常写是不行的。那考虑离散化一下，用下标映射该点的值。这里用下标还有一个原因，因为睡觉时间和下标的奇偶性有关，那这样做前缀和操作就ok了。

之后询问的部分,我们用lower_bound找大于等于它的第一个，找到\(ll\)和\(rr\)。首先前提是下标为奇数，这样才会影响睡眠时间，在修正一下左右边界就ok了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
	int n;
	cin>>n;
	vector<int>a(n);
	for(int i = 0;i<n;i++)cin>>a[i];
	vector<int>s(n+10,0);
	for(int i = 1;i<n;i++)
	{
		s[i] = s[i-1];
		if(i%2==0)
			s[i] += (a[i]-a[i-1]);
	}
	int q;
	cin>>q;
	while(q--)
	{
		int l,r;
		cin>>l>>r;
		int ll = lower_bound(a.begin(), a.end(),l)-a.begin();
		int rr = lower_bound(a.begin(),a.end(),r)-a.begin();
		int ans = s[rr]-s[ll];
		if(ll%2==0)
			ans += (a[ll]-l);
		if(rr%2==0)
			ans -= (a[rr]-r);
		cout<<ans<<endl;
	}
	return 0;
}

E - Art Gallery on Graph

Problem Statement

题意：给你一个\(N\)个点\(M\)条边的简单无向图。

再告诉你，其中\(K\)个点是特别的，对于\(pi\)它会影响离它距离\(<=hi\)的点。问你最后影响的点的编号。

Solution

题解：首先第一反应是跑最短路，但是数据范围，显然会\(TLE\)。

![image-20230613011457245](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230613011457245.png)

以样例一为例，如图，我们可以认为，从该点出发还可以走几步。

比如初始状态dist[5] = 2,dist[1] = 1,其他都是0，我们从当前dist最大的开始走，去更新别的点。对于当前点x到下一个点y，如果dist[x]-1>=dist[y]，那就可以更新。其实就相当于找最长路了。看最远能更新到哪，把被更新的点加入到ans里面，最后输出即可。用dijkstra的板子改一改就可以了。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
vector<int>edge[N*2];
set<pair<int,int>,greater<pair<int,int>>>q;//记录的是不在c中的点的信息
int n,m,k, dist[N*2];
set<int>s;
bool vis[N];
pair<int,int>p[N];
bool cmp(pair<int,int>a,pair<int,int> b)
{
	return a.second>b.second;
}
inline void dijkstra(int st)
{
	memset(dist,0,sizeof(dist));
	for(int i = 1;i<=k;i++)
		dist[p[i].first]=p[i].second;
	q.clear();
	for(int i = 1;i<=n;i++)
	{
		q.insert({dist[i],i});
	}
	while(!q.empty())
	{
		int x = q.begin()->second;
		if(dist[x])s.insert(x);
		q.erase(q.begin());
		for(auto y:edge[x])
		{
			if(dist[x]-1>=dist[y])
			{
				q.erase({dist[y],y});
				dist[y]= dist[x]-1;
				s.insert(y);
				q.insert({dist[y],y});
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m>>k;
	for(int i = 1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	
	
	for(int i = 1;i<=k;i++)
	{
		cin>>p[i].first>>p[i].second;
	}
	sort(p+1,p+k+1,cmp);
	//cout<<"!!!"<<p[1].first<<endl;
	s.insert(p[1].first);
	dijkstra(p[1].first);
	cout<<s.size()<<endl;
	// for(int i = 1;i<=n;i++)
	// 	cout<<dist[i]<<" ";
	// cout<<endl;
	for(auto x:s)
		cout<<x<<" ";
	return 0;
}