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
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\)。
以样例一为例，如图，我们可以认为，从该点出发还可以走几步。
比如初始状态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;
}