摘要
Title: Acwing 第 86 场周赛
Tag: dp、思维

Acwing 第 86 场周赛

A AcWing 4794. 健身

题意

李华一共要进行 n组健身训练。
李华只做三种运动：胸部（chest）运动、二头肌（biceps）运动、背部（back）运动。
而且，三种运动是循环训练的，也就是说他第一组训练是胸部运动，第二组训练是二头肌运动，第三组训练是背部运动，第四组训练是胸部运动，第五组训练是二头肌运动…以此类推直到做完第 n 组训练。
请你计算，他做哪种运动的时长最长。
思路

正常模拟即可，可以通过除余快速进行锁定

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-14 18:59:40
* @FilePath: \Acwing\86cp\a.cpp
* @LastEditTime: 2023-01-14 19:04:37
*/
#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;
    int n;
    cin >> n;
    vector<int> kind(3);
    vector<string> s = {"chest", "biceps", "back"};
    int mx = 0, ans = 0;
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
        kind[i % 3] += x;
        if (kind[i % 3] > mx)
        {
            mx = kind[i % 3];
            ans = i % 3;
        }
    }
    cout << s[ans];
    return 0;
}

B AcWing 4795. 安全区域

题意

略
思路

由于n太大，所以开二维数组进行模拟查点的方法行不通，所以需要另辟蹊径
- 如果没有阻拦，每个车放进去会占 $2n-1$ 个格子
- 但如果有阻拦，就需要再分两种情况（横竖同理，这里以横举例）
  - 如果之前在这一行有车了，那么就没有占的了
  - 如果之前有竖的，那么需要减掉竖的数量，因为竖在每一行占一个格子

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-14 18:59:43
* @FilePath: \Acwing\86cp\b.cpp
* @LastEditTime: 2023-01-14 19:16:22
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long

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

unordered_map<int, bool> shu, heng;

signed main()
{
    IOS;
    int n, m, cnt = 0;
    cin >> n >> m;

    for (int i = 0; i < m; ++i)
    {
        int x, y;
        cin >> x >> y;
        int sum = 0;
        // 首先处理横轴
        if (!heng[x])
        {
            sum += (n - SZ(shu));
        }
        if (!shu[y])
        {
            sum += (n - SZ(heng));
        }
        cnt += sum;
        cout << n * n - cnt << " ";
        heng[x] = true;
        shu[y] = true;
    }

    return 0;
}

C AcWing 4796. 删除序列

题意

原题：Codeforces 455A Boredom

给定一个长度为 n 的正整数序列 a1,a2,…,an
你可以进行任意次删除操作。
每次删除操作分为两步：
选择序列中的一个元素（不妨设其元素值为 x），并将这一个元素删除，这可以给你加 x分。
将所有的元素值为 x−1和 x+1的元素（如果有的话）从序列中删除，这不会给你带来任何分数。
请计算，通过删除操作，你可以获得的最大得分。
思路

典型的线性dp，dp[i]代表前i的数值中，挑选i的最大得分，也就是分为选i和不选i两种情况
递推式

$dp[i] = max(dp[i - 1], dp[i - 2] + a[i] * i)$

注意
- i不是下标，是给出的值
- 当i=1时会越界，所以要特判1

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-14 18:59:46
* @FilePath: \Acwing\86cp\c.cpp
* @LastEditTime: 2023-01-14 19:32:58
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long

#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 n;
int a[N], dp[N];
int mn = INF, mx = -INF;

signed main()
{
    IOS;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x;
        a[x]++;
        mx = max(mx, x);
        mn = min(mn, x);
    }

    for (int i = mn; i <= mx; ++i)
    {
        if (i == 1)
            dp[i] = max(dp[i - 1], a[i] * i);
        else
            dp[i] = max(dp[i - 1], dp[i - 2] + a[i] * i);
    }

    cout << dp[mx];

    return 0;
}

Acwing 第 86 场周赛

A AcWing 4794. 健身

题意

思路

代码

B AcWing 4795. 安全区域

题意

思路

代码

C AcWing 4796. 删除序列

题意

思路

代码