AtCoder Beginner Contest 385（A~E）题解

先写上A~E的题解，后续补题会将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的思维