AtCoder Beginner Contest 298-526互联

A - Job Interview (abc298 a)

题目大意

给定包含o-x的字符串，问是否不包含 x且包含o。

解题思路

遍历一遍即可。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    string s;
    cin >> n >> s;
    auto ok = [&](){
        if (s.find('x') != string::npos)
            return false;
        if (s.find('o') == string::npos)
            return false;
        return true;
    };
    if (ok())
        cout << "Yes" << '\n';
    else 
        cout << "No" << '\n';

    return 0;
}

B - Coloring Matrix (abc298 b)

题目大意

给定两个方阵\(A,B\)，问能否将 \(A\)旋转多次 \(90\)度，使得 \(A\)为 \(1\) 的地方\(B\)也为 \(1\)。

解题思路

大小只有\(100\)，四次翻转都试一次就可以了，题意也给出了翻转的位置变换公式。

神奇的代码


#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n, 0)), b(n, vector<int>(n, 0));
    for(auto &i : a)
        for(auto &j : i)
            cin >> j;
    for(auto &i : b)
        for(auto &j : i)
            cin >> j;
    auto check = [&](){
        for(int i = 0; i < n; ++ i)
            for(int j = 0; j < n; ++ j){
                if (a[i][j] == 1 && b[i][j] != 1)
                    return false;
            }
        return true;
    };
    auto ok = [&](){
        vector<vector<int>> tmp(n, vector<int>(n, 0));
        for(int i = 0; i < n; ++ i)
            for(int j = 0; j < n; ++ j){
                tmp[i][j] = a[n - 1 - j][i];
            }
        a = tmp;
        return check();
    };
    if (ok() || ok() || ok() || ok())
        cout << "Yes" << '\n';
    else 
        cout << "No" << '\n';

    return 0;
}

C - Cards Query Problem (abc298 c)

题目大意

有\(n\)个箱子，进行以下三种操作：

1 i j 将写有数字\(i\)的卡片放到 \(j\)号箱
2 i 问\(i\)号箱里放的所有卡片的数字，升序输出
3 i 问写有数字\(i\)的卡片所在的箱子编号，升序输出

解题思路

注意一个箱子里可能有多张一样数字的卡片，因此第二种操作用multiset，第三种操作用set维护即可。

神奇的代码

#include <bits/stdc++.h>
#include <vector>
using namespace std;
using LL = long long;

const int N = 2e5;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, q;
    cin >> n >> q;
    vector<multiset<int>> box(n);
    vector<set<int>> card(N);
    while(q--){
        int op;
        cin >> op;
        if (op == 1){
            int i, j;
            cin >> i >> j;
            i --;
            j --;
            box[j].insert(i);
            card[i].insert(j);
        }else if (op == 2){
            int i;
            cin >> i;
            -- i;
            for(auto &i : box[i])
                cout << i + 1 << ' ';
            cout << '\n';
        }else if (op == 3){
            int i;
            cin >> i;
            -- i;
            for(auto &i : card[i])
                cout << i + 1 << ' ';
            cout << '\n';
        }else {
            assert(1 == 0);
        }
    }

    return 0;
}

D - Writing a Numeral (abc298 d)

题目大意

一个字符串\(S\)，初始值为1。维护以下三种操作：

1 x \(S\)末尾增加个数字 \(x\)
2 剔除\(S\)的第一个数字
3 问\(S\)所表示的数字对 \(998244353\)的取模

解题思路

事先维护下\(10\)的幂对 \(998244343\)的取模结果，然后动态维护这个取模值就可以了。

即操作1相当于 \(s = s \times 10 + x\)，操作2相当于 \(s = s - s[0] * 10^{|S|}\)

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 6e5 + 10;
const int mo = 998244353;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    vector<int> mod(N);
    int mul = 1;
    for(int i = 1; i < N; ++ i){
        mod[i] = mul;
        mul = 1ll * mul * 10 % mo;
    }
    deque<int> s;
    s.push_back(1);
    int q;
    cin >> q;
    int ans = 1;
    while(q--){
        int op;
        cin >> op;
        if (op == 1){
            int x;
            cin >> x;
            s.push_back(x);
            ans = (1ll * ans * 10 + x) % mo;
        }else if (op == 2){
            int x = s.front();
            ans = (ans - 1ll * x * mod[s.size()]) % mo;
            if (ans < 0)
                ans += mo;
            s.pop_front();
        }else if (op == 3){
            cout << ans << '\n';
        }else {
            assert(1 == 0);
        }
    }

    return 0;
}

E - Unfair Sugoroku (abc298 e)

题目大意

一维数轴，高桥在\(a\)号点，青木在 \(b\)号点，高桥先，两人轮流扔骰子，高桥的结果会在 \(1-p\)等概率出现，青木的在 \(1-q\)等概率出现，掷出 \(x\)后，就会往前走 \(x\)步，最多到\(n\)号点。谁先到\(n\)号点谁赢。

问高桥赢的概率。

解题思路

设\(dp[i][j][0/1]\)表示高桥在 \(a\)号点，青木在\(b\)号点，现在轮到高桥/青木时，高桥赢的概率。

然后根据扔骰子的情况和概率转移即可。

比如\(dp[i][j][0] = \frac{dp[i + 1][j][1] + dp[i + 2][j][1] + ... + dp[i + p][j][1]}{p}\)，注意\(i+p\)可能要和 \(n\)取个 \(min\)

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int mo = 998244353;

long long qpower(long long a, long long b){
    long long qwq = 1;
    while(b){
        if (b & 1)
            qwq = qwq * a % mo;
        a = a * a % mo;
        b >>= 1;
    }
    return qwq;
}

long long inv(long long x){
    return qpower(x, mo - 2);
}

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n, a, b, p, q;
    cin >> n >> a >> b >> p >> q;
    int invp = inv(p);
    int invq = inv(q);
    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n + 1, vector<int>(2, -1)));
    function<int(int, int, int)> dfs = [&](int x, int y, int pos){
        if (x == n)
            return 1;
        else if (y == n)
            return 0;
        if (dp[x][y][pos] != -1)
            return dp[x][y][pos];
        int val = 0;
        if (pos == 0){
            for(int i = 1; i <= p; ++ i){
                int nx = min(n, x + i);
                val += dfs(nx, y, pos ^ 1);
                if (val >= mo)
                    val -= mo;
            }
            val = 1ll * val * invp % mo;
        }else{
            for(int i = 1; i <= q; ++ i){
                int ny = min(n, y + i);
                val += dfs(x, ny, pos ^ 1);
                if (val >= mo)
                    val -= mo;
            }
            val = 1ll * val * invq % mo;
        }
        return dp[x][y][pos] = val;
    };
    cout << dfs(a, b, 0) << '\n';

    return 0;
}

F - Rook Score (abc298 f)

题目大意

给定一个\(10^9 \times 10^9\)大小的网格，以及 \(n\)个格子上写的正数。

指定一个格子位置\((R,C)\)，问 \(R\)行格子和 \(C\)列格子的所有数的和。

解题思路

设 \(rsum[i]\)表示第 \(i\)行的和， \(csum[i]\)表示第 \(i\)列的和。

首先考虑选的\((R,C)\)有正数的情况，这个枚举一下取个最大值即可，即\(\max(rsum[R] + csum[C] - val[R,C])\)

然后还剩下一种就是 \((R,C)\)上没有数的情况。这个情况相当于从\(rsum\)和 \(csum\)两个数组选一个数，求最大值，且 \((R,C)\)没数的。

一开始就是考虑用堆，就是两个数组选两个数求第 \(k\)大的 \(k\log k\)的做法，直到找到一个没有数的位置就直接 \(break\)，理论上最多也就判断个 \(n\)次就会 \(break\)的，复杂度应该是\(O(n\log n)\) ，但是一直超时，感觉不太懂。

然后改成直接\(for\)循环的，遇到第一个格子上没有数值的直接 \(break\)，这样最多也就遍历到 \(n\)个点，复杂度是 \(O(n)\)。

多个 \(\log\)不至于吧。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false); 
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    map<int, LL> csum, rsum;
    set<pair<int, int>> po;
    set<pair<pair<int, int>, int>> po2;
    for(int i = 1; i <= n; ++ i){
        int x, y, v;
        cin >> x >> y >> v;
        csum[y] += v;
        rsum[x] += v;
        po.insert({x, y});
        po2.insert({{x, y}, v});
    }
    LL ans = 0;
    for(auto &[pos, v] : po2){
        auto &[x, y] = pos;
        ans = max(ans, rsum[x] + csum[y] - v);
    }
    vector<pair<int, LL>> COLSUM, ROWSUM;
    ROWSUM.reserve(rsum.size());
    COLSUM.reserve(csum.size());
    for(auto &i : rsum){
        ROWSUM.push_back({i.first, i.second});
    }
    for(auto &i : csum){
        COLSUM.push_back({i.first, i.second});
    }
    vector<int> col_id(COLSUM.size()), row_id(ROWSUM.size());
    iota(row_id.begin(), row_id.end(), 0);
    iota(col_id.begin(), col_id.end(), 0);
    sort(row_id.begin(), row_id.end(), [&](const int a, const int b){
            return ROWSUM[a].second > ROWSUM[b].second;
            });
    sort(col_id.begin(), col_id.end(), [&](const int a, const int b){
            return COLSUM[a].second > COLSUM[b].second;
            });
    for(auto &r : row_id)
        for(auto &c: col_id){
            int x = ROWSUM[r].first, y = COLSUM[c].first;
            if (po.find({x, y}) == po.end()){
                ans = max(ans, ROWSUM[r].second + COLSUM[c].second);
                break;
            }
        }
    // ans = max({ans, COLSUM[col_id[0]].second, ROWSUM[row_id[0]].second});
    // priority_queue<pair<LL, pair<int, int>>> qwq;
    // qwq.push({COLSUM[col_id[0]].second + ROWSUM[row_id[0]].second, {0, 0}});
    // while(!qwq.empty()){
    //     auto [val, pos] = qwq.top();
    //     auto &[x, y] = pos;
    //     qwq.pop();
    //     int real_row = ROWSUM[row_id[x]].first;
    //     int real_col = COLSUM[col_id[y]].first;
    //     if (po.find({real_row, real_col}) == po.end()){
    //         ans = max(ans, val);
    //         break;
    //     }
    //     int nx = x + 1, ny = y + 1;
    //     if (nx < row_id.size()){
    //         qwq.push({ROWSUM[row_id[nx]].second + COLSUM[col_id[y]].second, {nx, y}});
    //     }
    //     if (ny < col_id.size()){
    //         qwq.push({ROWSUM[row_id[x]].second + COLSUM[col_id[ny]].second, {x, ny}});
    //     }
    // }
    cout << ans << '\n';

    return 0;
}