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;
}
