Codeforces Round 578 (Div. 2)

16 August 2019 | duanyll | Tags: OI 题解

好久没有打过cf了… 一直没有时间合适的比赛, rating狂掉.

这次正常Div. 2难度吧, 刚好做出4道题, 我真是太弱了.

A. Hotelier

签到题, 读完题就完事了. (我被网卡了将近十分钟)

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iostream>
using namespace std;

typedef long long int64;

const int INF = 0x3f3f3f3f;
const int MAXN = 1e5 + 10;

bool ans[10];

int main() {
    int n;
    string s;
    cin >> n >> s;
    for (auto i : s) {
        if (i == 'L') {
            for (int j = 0; j < 10; j++) {
                if (!ans[j]) {
                    ans[j] = true;
                    break;
                }
            }
        } else if (i == 'R') {
            for (int j = 9; j >= 0; j--) {
                if (!ans[j]) {
                    ans[j] = true;
                    break;
                }
            }
        } else {
            ans[i - '0'] = false;
        }
    }
    for (int i = 0; i < 10; i++) {
        cout << (ans[i] ? '1' : '0');
    }
    cout << endl;
    return 0;
}

B. Block Adventure

贪心, 背包容量无限, 能拿多少就拿多少, 注意特判柱子拿空了的情况.

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iostream>
using namespace std;

typedef long long int64;

const int INF = 0x3f3f3f3f;
const int MAXN = 110;

int h[110];

#include <cctype>
#include <cstdio>

template <typename T = int>
inline T read() {
    T X = 0, w = 0;
    char ch = 0;
    while (!isdigit(ch)) {
        w |= ch == '-';
        ch = getchar();
    }
    while (isdigit(ch)) {
        X = (X << 3) + (X << 1) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -X : X;
}

int main() {
    int tcnt = read();
    for (int T = 1; T <= tcnt; T++) {
        int n = read();
        int m = read();
        int k = read();

        for (int i = 1; i <= n; i++) {
            h[i] = read();
        }

        int bag = m;
        bool ok = true;
        for (int i = 2; i <= n; i++) {
            bag += min(h[i - 1], h[i - 1] - (h[i] - k));
            if (bag < 0) {
                ok = false;
                break;
            }
        }

        cout << (ok ? "YES" : "NO") << endl;
    }
    return 0;
}

C. Round Corridor

GCD即可, 注意int64.

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <iostream>
#include <numeric>
using namespace std;

typedef long long int64;

const int INF = 0x3f3f3f3f;
// const int MAXN = ;

int main() {
    int64 n, m;
    cin >> n >> m;
    int64 GCD = gcd(n, m);
    int64 ng = n / GCD;
    int64 mg = m / GCD;
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int64 sx, sy, ex, ey;
        cin >> sx >> sy >> ex >> ey;
        int64 sid = (sy - 1) / ((sx == 1) ? ng : mg);
        int64 eid = (ey - 1) / ((ex == 1) ? ng : mg);
        cout << ((sid == eid) ? "YES" : "NO") << endl;
    }
    return 0;
}

D. White Lines

预处理行和列方向上每个长为$k$的区间能否消掉当前行列, 再前缀和判断相对方向的总价值(比赛时写成单调区间了, 不过反正都$O(n^2)$, 没有被卡掉), 最后记得加上原来就是白色的行列

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
using namespace std;

typedef long long int64;

const int INF = 0x3f3f3f3f;
const int MAXN = 2010;

char map[MAXN][MAXN];

int sum_col[MAXN][MAXN];  // 列前缀和
int sum_row[MAXN][MAXN];  // 行前缀和

// bool can_erase_col[MAXN][MAXN];
// bool can_erase_row[MAXN][MAXN];

int sum2_col[MAXN][MAXN];
int sum2_row[MAXN][MAXN];

int n, k;

inline bool can_erase_row(int i, int j) {
    return (sum_row[i][n] != 0) && (sum_row[i][j - 1] == 0) && (sum_row[i][n] == sum_row[i][j + k - 1]);
}

inline bool can_erase_col(int i, int j) {
    return (sum_col[n][j] != 0) && (sum_col[i - 1][j] == 0) && (sum_col[n][j] == sum_col[i + k - 1][j]);
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        scanf("%s", map[i] + 1);
    }
    for (int i = 1; i <= n; i++) {
        sum_row[i][0] = 0;
        for (int j = 1; j <= n; j++) {
            sum_row[i][j] = sum_row[i][j - 1] + ((map[i][j] == 'B') ? 1 : 0);
        }
    }
    for (int j = 1; j <= n; j++) {
        sum_col[0][j] = 0;
        for (int i = 1; i <= n; i++) {
            sum_col[i][j] = sum_col[i - 1][j] + ((map[i][j] == 'B') ? 1 : 0);
        }
    }

    for (int i = 1; i + k - 1 <= n; i++) {
        deque<int> q;
        for (int j = 1; j < k; j++) {
            if (can_erase_col(i, j)) q.push_back(j);
        }
        for (int j = k; j <= n; j++) {
            int seg_head = j - k + 1;
            while (!q.empty() && q.front() < seg_head) q.pop_front();
            if (can_erase_col(i, j)) q.push_back(j);
            sum2_row[i][seg_head] = q.size();
        }
    }

    for (int j = 1; j + k - 1 <= n; j++) {
        deque<int> q;
        for (int i = 1; i < k; i++) {
            if (can_erase_row(i, j)) q.push_back(i);
        }
        for (int i = k; i <= n; i++) {
            int seg_head = i - k + 1;
            while (!q.empty() && q.front() < seg_head) q.pop_front();
            if (can_erase_row(i, j)) q.push_back(i);
            sum2_col[seg_head][j] = q.size();
        }
    }

    // clog << endl;
    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= n; j++) {
    //         clog << sum2_row[i][j] << ' ';
    //     }
    //     clog << endl;
    // }
    // clog << endl;
    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= n; j++) {
    //         clog << sum_col[i][j] << ' ';
    //     }
    //     clog << endl;
    // }

    int ans = 0;
    for (int i = 1; i + k - 1 <= n; i++) {
        for (int j = 1; j + k - 1 <= n; j++) {
            ans = max(ans, sum2_col[i][j] + sum2_row[i][j]);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (sum_row[i][n] == 0) ans++;
        if (sum_col[n][i] == 0) ans++;
    }
    cout << ans << endl;
    return 0;
}

限于我的能力, 后面的题都没有做了, E题看了一下似乎是后缀自动机, F题看都没看了…