Astria's Blog

主题

atcoder-beginner-contest-261-a·b·c·d ​

A - Intersection ​

题目大意 ​

Original Link

给定两个染色区间的端点 \(L_1,R_1,L_2,R_2\)，求同时染上两种颜色的区间长度。

思想 ​

  • 数据范围小，暴力枚举区间
    • 遍历两个区间，用 res[i] 记录被染色的情况
    • 遍历染色后的区间，计算区间长度

代码 ​

cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int res[N];

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;

    for (int i = a; i <= b; i++) res[i]++;
    for (int i = c; i <= d; i++) res[i]++;

    int cnt = 0;
    for (int i = 0; i <= 200; i++) if (res[i] == 2) cnt++;

    if (cnt) cout << cnt - 1 << endl;
    else cout << 0 << endl;

    return 0;
}

B - Tournament Result ​

题目大意 ​

Original Link

给定 \(N \times N\) 的表，单元 \(A_{i,j}\) 记录了 \(i\) 与 \(j\) 的对局输赢平的三种情况，若记录有冲突说明该表不正确。

思想 ​

  • 遍历表格，遍历 \(i\) 行，每一行从 \(j = i + 1\) 列开始
    • 判断 \(A_{i,j}\) 和 \(A_{j,i}\) 的记录是否符合事实
    • 不符合事实则进行标记并退出

代码 ​

cpp
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

char mp[N][N];
int n;

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cin >> mp[i][j];
    }

    // ... 后续代码逻辑 ...
}

C - NewFolder(1) ​

题目大意 ​

Original Link

给定\(N\)个string类型的\(S\)串，按照给出\(S\)的顺序，对于总共出现过\(m\)次\(S_i\)，若当前的\(S_i\)第一次出现，输出\(S_i\)，否则输出\(S_i(u-1)\)，\(u\)表示第几次出现

思想 ​

  • string s[N]存储输入\(S\)的顺序
    • map&lt;string,int&gt; a;记录当前的\(S_i\)出现了多少次
    • 遍历s[N]，使得a[s[i]]++，若a[s[i]] - 1 == 0说明是第一次出现

代码 ​

cpp
#include <bits/stdc++.h>
using namespace std;

map<string, int> a;

int n;

const int N = 1e6 + 3;

string s[N];

int main() {

    cin >> n;

    for (int i = 0; i < n; i++) cin >> s[i];

    for (int i = 0; i < n; i++) {

        a[s[i]]++;
        int t = a[s[i]] - 1;
        if (t != 0) {
            cout << s[i] << '(' << t << ')' << endl;
        } else {
            cout << s[i] << endl;
        }
    }

    return 0;
}

D - Flipping and Bonus ​

题目大意 ​

Original Link

投掷硬币为正面，计数器增加，反之计数器清零，给定\(N\)次投掷硬币为正面得到的钱\(X_i\)，给定\(M\)个奖励规则，若计数器的数值达到\(C_i\)，将获得\(Y_i\)的奖励，求如何使得得到的钱最多

思想 ​

  • a[N]记录\(X_i\)，b[N]记录\(Y_i\)
    • 状态表示：dp[i][j]表示前i次投掷，当前计数器值为j时得到的钱
    • 状态计算：
      • 若投掷结果为正：则dp[i][j] = dp[i - 1][j - 1] + a[i] + b[j]
      • 反之计数器清零，更新之后的结果：dp[i][0] = max(dp[i][0], dp[i - 1][j])
    • 注意开long long

代码 ​

cpp
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

LL n, m;

const LL N = 5010;

LL dp[N][N];

LL a[N];
LL b[N];

int main() {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        b[x] = y;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i][j] = dp[i - 1][j - 1] + a[i] + b[j];
        }

        for (int j = 0; j < i; j++) {
            dp[i][0] = max(dp[i][0], dp[i - 1][j]);
        }
    }

    LL ans = 0;

    for (int i = 0; i <= n; i++) ans = max(ans, dp[n][i]);

    cout << ans << endl;

    return 0;
}