摘要
Title: Acwing 第 87 场周赛
Tag: 二分、树的直径

Acwing 第 87 场周赛

A AcWing 4797. 移动棋子

题意

略
思路

看到1就统计即可

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-29 21:45:10
* @FilePath: \Acwing\87cp\a.cpp
* @LastEditTime: 2023-01-29 21:47:17
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

signed main()
{
    IOS;
    for (int i = 1; i <= 5; ++i)
    {
        for (int j = 1; j <= 5; ++j)
        {
            int x;
            cin >> x;
            if (x)
            {
                cout << abs(i - 3) + abs(j - 3);
                return 0;
            }
        }
    }
    return 0;
}

B AcWing 4798. 打怪兽

题意

略
思路

可以观察到k的取值一定在1到n，而且满足单调性，那么就可以二分来做，每次check mid的时候，对这一区间的值进行排序，每次挑两个当前最大的进行删除，m减去最大的数，如果最后删完m不为负数，返回TRUE
复杂度 $O(nlog^2(n))$

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-29 21:45:13
* @FilePath: \Acwing\87cp\b.cpp
* @LastEditTime: 2023-01-29 21:56:57
*/
#pragma GCC optimize(1)
#pragma GCC optimize(2) // 先开优化
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e3 + 10, INF = 0x3f3f3f3f;

int n, m;
int a[N];

bool check(int id)
{
    int cnt = m;
    vector<int> b;
    for (int i = 1; i <= id; ++i)
        b.push_back(a[i]);
    sort(ALL(b), greater<int>());
    for (int i = 0; i < SZ(b); i += 2)
    {
        cnt -= b[i];
        if (cnt < 0)
            return false;
    }
    return true;
}

signed main()
{
    IOS;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    int l = 1, r = n;
    while (l < r)
    {
        int mid = (l + r + 1) >> 1;
        if (check(mid))
            l = mid;
        else
            r = mid - 1;
    }

    cout << l;
    return 0;
}

C AcWing 4799. 最远距离

题意

我们规定，如果一个无向连通图满足去掉其中的任意一条边都会使得该图变得不连通，则称该图为有效无向连通图。
给定一个 n 个点 m条边的有效无向连通图，点的编号为 1∼n所有边的长度均为 1。
两点之间的距离定义为两点之间的最短距离。
请你计算，给定图中距离最远的两个点之间的距离。
思路

树的直径裸题

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-29 21:45:16
* @FilePath: \Acwing\87cp\c.cpp
* @LastEditTime: 2023-01-29 22:04:13
*/
#pragma GCC optimize(1)
#pragma GCC optimize(2) // 先开优化
#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

int d1[N], d2[N];
vector<int> g[N];
int n, m, ans;

void dfs(int u, int fa)
{

    for (auto v : g[u])
    {
        if (v == fa)
            continue;
        dfs(v, u);
        int dis = d1[v] + 1;
        if (dis > d1[u])
        {
            d2[u] = d1[u];
            d1[u] = dis;
        }
        else if (dis > d2[u])
        {
            d2[u] = dis;
        }
    }
    ans = max(ans, d1[u] + d2[u]);
}

signed main()
{
    IOS;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dfs(1, -1);
    cout << ans;
    return 0;
}

Acwing 第 87 场周赛

A AcWing 4797. 移动棋子

题意

思路

代码

B AcWing 4798. 打怪兽

题意

思路

代码

C AcWing 4799. 最远距离

题意

思路

代码