AtCoder Beginner Contest 385（A~F）题解

A - Equally

思路：由题可知最多只能分成三组，我们只需要判断是否三个数都相等，或者两个数相加等于另外一个数即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
string s;
int a,b,c;
signed main()
{cin>>a>>b>>c;if(a==b+c||b==a+c||c==a+b||(a==b&&b==c)){cout<<"Yes\n";}else{cout<<"No\n";}return 0;
}

 B - Santa Claus 1

思路：数据很小，直接暴力模拟即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,x,y;
char c[105][105];
int vis[105][105];
string t;
int ans=0;
signed main()
{cin>>n>>m>>x>>y;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>c[i][j];}}cin>>t;if(vis[x][y]==0&&c[x][y]=='@'){vis[x][y]=1;ans++;}for(int i=0;i<t.size();i++){if(t[i]=='U'&&c[x-1][y]!='#'&&x-1>=1&&x-1<=n){x-=1;if(c[x][y]=='@'&&vis[x][y]==0){vis[x][y]=1;ans++;}}else if(t[i]=='D'&&c[x+1][y]!='#'&&x+1>=1&&x+1<=n){x+=1;if(c[x][y]=='@'&&vis[x][y]==0){vis[x][y]=1;ans++;}}else if(t[i]=='L'&&c[x][y-1]!='#'&&y-1>=1&&y-1<=m){y-=1;if(c[x][y]=='@'&&vis[x][y]==0){vis[x][y]=1;ans++;}}else if(t[i]=='R'&&c[x][y+1]!='#'&&y+1>=1&&y+1<=m){y+=1;if(c[x][y]=='@'&&vis[x][y]==0){vis[x][y]=1;ans++;}}}cout<<x<<" "<<y<<" "<<ans;return 0;
}

C - Illuminate Buildings

 思路：用map去存储每一个高度的大楼，然后去寻找每一个高度内的最长等差数列即可

#include <bits/stdc++.h>  
using namespace std;  
#define int long long  signed main() {  int n;  cin >> n;  vector<int> heights(n);  for (int i = 0; i < n; i++) {  cin >> heights[i];  }  unordered_map<int, vector<int>> index_map;  for (int i = 0; i < n; i++) {  index_map[heights[i]].push_back(i + 1);  }  int max_count = 1;  for (auto& entry : index_map) {  vector<int>& indices = entry.second;  int size = indices.size();  if (size <= 2) {  max_count = max(max_count, size);  continue;  }  unordered_set<int> index_set(indices.begin(), indices.end());  for (int i = 0; i < size; i++) {  for (int j = i + 1; j < size; j++) {  int d = indices[j] - indices[i];int count = 2;   int next_index = indices[j] + d;  while (index_set.count(next_index)) { count++;  next_index += d;  }  max_count = max(max_count, count);  }  }  }  cout << max_count << endl;  return 0;  
}

D - Santa Claus 2

 思路：这题和b题唯一的区别就是数据量很大，因此我们在处理这种问题可以考虑将其一行和一列存储起来，因此我们可以用一个map<int,set<int>>去存储，前面的键值表示的是当前行/列，后面的键值表示在当前行/列，set[i]位置上有一个房子，我们去用二分寻找区间，如果碰到房子，就将房子从这两个map的set里面弹出，然后个数+1

#include<bits/stdc++.h>
using namespace std;#define int long long
#define rep(i,n) for(int i=0;i<(int)(n);i++)
void solve()
{int n, m;int sx, sy;cin >> n >> m >> sx >> sy;map<int, set<int> > mx, my;rep(i, n) {int x, y;cin >> x >> y;mx[x].insert(y);my[y].insert(x);}map<char, int> dx, dy;dx['U'] = 0, dx['D'] = 0, dx['L'] = -1, dx['R'] = 1;dy['U'] = 1, dy['D'] = -1, dy['L'] = 0, dy['R'] = 0;int x = sx, y = sy;rep(tt, m) {char d;int c;cin >> d >> c;int nx = x + dx[d] * c;int ny = y + dy[d] * c;if (d == 'U' || d == 'D') {if (!mx.count(nx)) {x = nx;y = ny;continue;}int st = y, ed = ny;if (st > ed) swap(st, ed);auto l = mx[nx].lower_bound(st);auto r = mx[nx].upper_bound(ed);if (r == mx[nx].begin()) {x = nx;y = ny;continue;}vector<int> v;for (auto i = l; i != r; i++) {v.push_back(*i);}for (auto i : v) {mx[x].erase(i);if (my.count(i)) my[i].erase(nx);}}if (d == 'L' || d == 'R') {if (!my.count(ny)) {x = nx;y = ny;continue;}int st = x, ed = nx;if (st > ed) swap(st, ed);auto l = my[ny].lower_bound(st);auto r = my[ny].upper_bound(ed);if (r == my[ny].begin()) {x = nx;y = ny;continue;}vector<int> v;for (auto i = l; i != r; i++) {v.push_back(*i);}for (auto i : v) {my[y].erase(i);if (mx.count(i)) mx[i].erase(ny);}}x = nx;y = ny;}int sum = 0;for (auto i : mx) sum += i.second.size();cout << x << " " << y << " " << n - sum;
}signed main()
{solve();
}

 E - Snowflake Tree

这题其实并未涉及算法，更多的是思维，首先我们可以发现，根节点连接的点x上的连接的点都是相同的，因此我们的雪花树的深度最大为2（设我们的根节点深度为1），因此我们可以将每一个点的度统计出来，然后遍历每一个点，让每一个点都去当一次根节点，然后，用set去存储其子节点的度-1（表示孙子节点的度），然后从大到小排序，j*（当前节点的度+1），就是能够连接的最多的节点，然后去不断更新最大值即可

#include <bits/stdc++.h>  
using namespace std;  
#define int long long  
int n;  
vector<int> e[300005];  
signed main() {  cin >> n;  for(int i = 1; i < n; i++) {  int u, v;  cin >> u >> v;  e[u].push_back(v);  e[v].push_back(u);  }  int ans = 0;  for(int i = 1; i <= n; i++) {  vector<int> a;  for(int u : e[i]) {  a.push_back(e[u].size() - 1);  }  sort(a.rbegin(), a.rend());   for(int j = 0; j < a.size(); j++) {  ans = max(ans, (j + 1) * (a[j]+1) + 1);  }  }  cout << n - ans;  return 0;  
}

总体来说这场难度不高，f有一个卡精度问题，要用long double，后续更新，最重要的是e的思维 

F - Visible Buildings

 

思路：我们直接从斜率入手算出在y轴上的截距即可， 我们去取y轴上的截距，如果截距最大值都小于0，那么就输出-1，否则就输出截距的最大值

注意精度问题，用long double即可轻易ac掉这道题

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
long double x[200005];
long double h[200005];
signed main()
{cin>>n;for(int i=1;i<=n;i++){cin>>x[i]>>h[i];}long double ans=-LLONG_MAX;for(int i=2;i<=n;i++){long double xie=(h[i]-h[i-1])/(x[i]-x[i-1]);long double jie=h[i]-xie*x[i];ans=max(ans,jie);}if(ans<0){cout<<"-1";}else{cout<<fixed<<setprecision(10)<<ans<<"\n";}return 0;
}