526互联

AtCoder Beginner Contest 306 题解 A - E

发布时间 2023-06-18 18:42:58作者: 叁纔

A - Echo

题目大意

给定一个字符串，需要把它每个字符重复输出。

解题思路

可以读完整个字符串，也可以按照字符读一个输出两个。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;

const int N = 1010;
const int MOD = 998244353;

void solve() {
    int n;
    string s;
    cin >> n >> s;
    for (int i = 0; i < n; ++i) {
        cout << s[i] << s[i];
    }
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

B - Base 2

题目大意

给定倒叙二进制串，需要输出它的十进制表示。

解题思路

最大取到 \(2^{63}\) 需要开unsigned long long 防止溢出。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N = 1010;
const int MOD = 998244353;

void solve() {
    ULL sum = 0;
    for (int i = 0; i <= 63; ++i) {
        ULL x;
        cin >> x;
        sum += (x << i);
    }
    
    cout << sum;
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

C - Centers

题目大意

给定一个由 \(1\sim n\) 中的数每个重复三遍组成的数列，我们现在需要对 \(1\sim n\) 按照每个数第二次出现的顺序排列。

解题思路

我们可以使用两个布尔数组分别存第一次和第二次出现与否，第二次出现时将这个数压入答案数组即可。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N = 3e5 + 10;
const int MOD = 998244353;

bool op[N], oo[N];
int all[N];

void solve() {
    int n;
    cin >> n;

    LL cnt = 0;
    for (int i = 1; i <= 3 * n; ++i) {
        int x;
        cin >> x;
        if (!op[x]) {
            op[x] = true;
        } else if (!oo[x]){
            all[++cnt] = x;
            oo[x] = true;
        }
    }
    for (int i = 1; i <= cnt; ++i) {
        cout << all[i] << ' ';
    }
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

D - Poisonous Full-Course

题目大意

餐馆立有两类食物，有毒的和解毒的，吃到有毒的会不舒服，不舒服状态再吃有毒的就会死掉。无论什么状吃到解毒的就会恢复健康。每种菜肴有一个美味值，每次可以选择吃不吃这道菜，一旦不吃就无法再次吃它。问最后能获得的最多的美味值是多少。

解题思路

题目实际上已经把转移的过程都告诉我们了，我们可以使用dp[i][j] 表示决定完前 \(i\) 道菜，身体状况为 \(j\) 时能获得的最大美味值。发生健康转换的时候我们一定吃了食物，这时候的dp值一定会加上我们当前食物的美味值。同时不能忘了判断不吃的情况，因为数据范围可以让美味值出现负数，那么不吃可能是更好的。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define int LL
const int N = 3e5 + 10;
const int MOD = 998244353;

pair<bool, int> p[N];
LL dp[N][2];

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x, y;
        cin >> x >> y;
        p[i] = {x, y};
    }
    if (p[1].first) {
        dp[1][1] = p[1].second;
        dp[1][0] = 0;
    } else {
        dp[1][0] = max(p[1].second, 0ll);
        dp[1][1] = 0;
    }
    for (int i = 2; i <= n; ++i) {
        if (p[i].first) {
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = max(dp[i - 1][0] + p[i].second, dp[i - 1][1]);
        } else {
            dp[i][0] = max(max(dp[i - 1][0], dp[i - 1][1]) + p[i].second, dp[i - 1][0]);
            dp[i][1] = dp[i - 1][1];
        }
    }
    cout << max(dp[n][1], dp[n][0]) << endl;
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}

E - Best Performances

题目大意

我们有一个长度为 \(n\) 的序列 \(a =(a_1,a_2,…,a_n)\)，初始时所有的元素都是\(0\)。

给定一个整数 \(k\)，我们定义一个函数 \(f(a)\) 如下：

  • 令 \(b\) 是通过将 \(a\) 按降序排序得到的序列（使其成为单调非递增的）。 然后，令 \(f(a)=b_1+b_2+⋯+b_k\)。

我们考虑对该序列应用 \(q\) 次更新。

按照以下操作，对序列 \(a\) 进行操作 \(i=1,2,…,q\)，并在每次更新后打印 \(f(a)\) 的值。

  • 将 \(a_{x_i}\)更改为\(y_i\)。

解题思路

我们使用两个muitiset来进行模拟，一个处理前 \(k\) 大的元素，一个处理剩下的所有元素，再维护一个元素的位置处理即可。

AC Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <numeric>
#include <set>
#define endl '\n'
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

const int N = 5e5 + 10;
const int MOD = 998244353;

multiset<int> st, st1;
int a[N];

void solve() {
    int n, k, q;
    LL res = 0;
    cin >> n >> k >> q;
    for (int i = 0; i < n; ++i) {
        i < k ? st.insert(0) : st1.insert(0);
    }
    while (q--) {
        int x, y;
        cin >> x >> y;
        x--;
        if (st.contains(a[x])) {
            st.extract(a[x]);
            res -= a[x];
        } else {
            st1.extract(a[x]);
        }
        a[x] = y;
        st.insert(a[x]);
        res += a[x];
        while (st.size() > k) {
            int xs = *st.begin();
            st1.insert(st.extract(xs));
            res -= xs;
        }
        while (!st.empty() && !st1.empty() && *st.begin() < *st1.rbegin()) {
            int xx = *st.begin();
            int yy = *st1.rbegin();
            res += yy - xx;
            st1.insert(st.extract(xx));
            st.insert(st1.extract(yy));
        }
        cout << res << endl;
    }
}

signed main() {
    ios;
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
}