AtCoder Beginner Contest 453 (A ~ E)题解

A

语法

字符串只能操作back, 可以将字符串操作后恢复

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()
#define vec1(T, name, n, val) vector<T> name(n, val)
#define vec2(T, name, n, m, val) vector<vector<T>> name(n, vector<T>(m, val))
#define vec3(T, name, n, m, k, val) vector<vector<vector<T>>> name(n, vector<vector<T>>(m, vector<T>(k, val)))
#define vec4(T, name, n, m, k, p, val) vector<vector<vector<vector<T>>>> name((n), vector<vector<vector<T>>>((m), vector<vector<T>>((k), vector<T>((p), (val)))))

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PLD = pair<LD, LD>;

const int N = 1e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 2e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream& operator>>(istream& is, i128& val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char& c : str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream& operator<<(ostream& os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

LL qpow(LL a, LL b) {
    LL ans = 1;
    a %= MOD;
    while (b) {
        if (b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

void solve() {
    int n;
    string s;
    cin >> n >> s;
    reverse(all(s));
    while (s.back() == 'o') s.pop_back();
    reverse(all(s));
    cout << s << '\n';
/**/ #ifdef LOCAL
    cout << flush;
/**/ #endif
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}

B

有点类似于栈的操作, 只会判断最后一个位置

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()
#define vec1(T, name, n, val) vector<T> name(n, val)
#define vec2(T, name, n, m, val) vector<vector<T>> name(n, vector<T>(m, val))
#define vec3(T, name, n, m, k, val) vector<vector<vector<T>>> name(n, vector<vector<T>>(m, vector<T>(k, val)))
#define vec4(T, name, n, m, k, p, val) vector<vector<vector<vector<T>>>> name((n), vector<vector<vector<T>>>((m), vector<vector<T>>((k), vector<T>((p), (val)))))

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PLD = pair<LD, LD>;

const int N = 1e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 2e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream& operator>>(istream& is, i128& val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char& c : str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream& operator<<(ostream& os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

LL qpow(LL a, LL b) {
    LL ans = 1;
    a %= MOD;
    while (b) {
        if (b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

void solve() {
    int t, x;
    cin >> t >> x;
    vector<int> a(t + 1);
    vector<PII> ans;
    cin >> a[0];
    ans.push_back({0, a[0]});

    for (int i = 1; i <= t; ++i) {
        int v;
        cin >> v;
        int d = abs(ans.back().y - v);
        if (d >= x) {
            ans.push_back({i, v});
        }
    }

    for (auto& [x, y] : ans) cout << x << ' ' << y << '\n';
/**/ #ifdef LOCAL
    cout
        << flush;
/**/ #endif
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}

C

注意到数据范围很小, , 可以暴搜

但是每一步是决策的过程, 也可以用转移, 定义状态表示考虑前步, 并且当前位置是的最大经过的次数

注意到只会由转移过来, 因此可以优化掉一维, 或者滚动数组优化

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()
#define vec1(T, name, n, val) vector<T> name(n, val)
#define vec2(T, name, n, m, val) vector<vector<T>> name(n, vector<T>(m, val))
#define vec3(T, name, n, m, k, val) vector<vector<vector<T>>> name(n, vector<vector<T>>(m, vector<T>(k, val)))
#define vec4(T, name, n, m, k, p, val) vector<vector<vector<vector<T>>>> name((n), vector<vector<vector<T>>>((m), vector<vector<T>>((k), vector<T>((p), (val)))))

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PLD = pair<LD, LD>;

const int N = 1e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 2e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream& operator>>(istream& is, i128& val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char& c : str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream& operator<<(ostream& os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

LL qpow(LL a, LL b) {
    LL ans = 1;
    a %= MOD;
    while (b) {
        if (b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

void solve() {
    int n;
    cin >> n;
    LD cur = 0.5;

    unordered_map<LD, LL> f;
    f[0.5] = 0;

    for (int i = 1; i <= n; ++i) {
        LL v;
        cin >> v;

        unordered_map<LD, LL> g;
        for (auto& [x, y] : f) {
            LD nx = x + v;
            int c = nx * x < 0 ? 1 : 0;
            g[nx] = max(g[nx], y + c);
            nx = x - v;
            c = nx * x < 0 ? 1 : 0;
            g[nx] = max(g[nx], y + c);
        }
        f = g;
    }

    LL ans = 0;
    for (auto& [x, y] : f) ans = max(ans, y);

    cout << ans << '\n';

/**/ #ifdef LOCAL
    cout << flush;
/**/ #endif
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}

D

非常恶心的题, 只需要把当前的方向绑定成为一个状态, 类似于dp转移的方式转移搜索即可

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()
#define vec1(T, name, n, val) vector<T> name(n, val)
#define vec2(T, name, n, m, val) vector<vector<T>> name(n, vector<T>(m, val))
#define vec3(T, name, n, m, k, val) vector<vector<vector<T>>> name(n, vector<vector<T>>(m, vector<T>(k, val)))
#define vec4(T, name, n, m, k, p, val) vector<vector<vector<vector<T>>>> name((n), vector<vector<vector<T>>>((m), vector<vector<T>>((k), vector<T>((p), (val)))))

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PLD = pair<LD, LD>;

const int N = 1e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 2e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream& operator>>(istream& is, i128& val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char& c : str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream& operator<<(ostream& os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

LL qpow(LL a, LL b) {
    LL ans = 1;
    a %= MOD;
    while (b) {
        if (b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> g(n);
    for (int i = 0; i < n; ++i) cin >> g[i];

    PII st, ed;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (g[i][j] == 'S') st.x = i, st.y = j;
            if (g[i][j] == 'G') ed.x = i, ed.y = j;
        }
    }

    struct F {
        int x, y, d;

        F(int a, int b, int c) : x(a), y(b), d(c) {};
    };

    vec3(int, vis, n + 1, m + 1, 4, 0);
    queue<F> q;
    vec3(F, p, n + 1, m + 1, 4, F(-1, -1, -1));

    for (int i = 0; i < 4; ++i) {
        int nx = st.x + dx4[i];
        int ny = st.y + dy4[i];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m || g[nx][ny] == '#' || vis[nx][ny][i]) continue;
        if (!vis[nx][ny][i]) {
            p[nx][ny][i] = {st.x, st.y, -1};
            vis[nx][ny][i] = 1;
            q.push({nx, ny, i});
        }
    }

    F eds = {-1, -1, -1};
    while (q.size()) {
        auto [x, y, d] = q.front();
        q.pop();
        if (x == ed.x && y == ed.y) {
            eds = {x, y, d};
            break;
        }

        char c = g[x][y];
        for (int k = 0; k < 4; ++k) {
            if (c == 'o' && k != d) continue;
            if (c == 'x' && k == d) continue;
            int nx = x + dx4[k], ny = y + dy4[k];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny][k] || g[nx][ny] == '#') continue;
            vis[nx][ny][k] = 1;
            q.push({nx, ny, k});
            p[nx][ny][k] = {x, y, d};
        }
    }

    if (eds.x == -1) {
        cout << "No" << '\n';
        return;
    }

    vector<char> t = {'U', 'R', 'D', 'L'};
    string ans;
    while (1) {
        ans += t[eds.d];
        F fa = p[eds.x][eds.y][eds.d];
        if (fa.d == -1) break;
        eds = fa;
    }

    reverse(all(ans));

    cout << "Yes" << '\n';
    cout << ans << '\n';

/**/ #ifdef LOCAL
    cout
        << flush;
/**/ #endif
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}

E

注意数据范围, 的做法一定是通过不了的

假设枚举了队的人数假设是, 那么自然而然队的人数就是

队员分为四类

  • 只能去,
  • 只能去,
  • 都能去,
  • 都不能去

第四种情况是非法的

形式化的来说, 就是非法情况下

否则, 还需要在中选的球员, 也就是

容斥原理 + 差分预处理即可

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) x.begin(), x.end()
#define vec1(T, name, n, val) vector<T> name(n, val)
#define vec2(T, name, n, m, val) vector<vector<T>> name(n, vector<T>(m, val))
#define vec3(T, name, n, m, k, val) vector<vector<vector<T>>> name(n, vector<vector<T>>(m, vector<T>(k, val)))
#define vec4(T, name, n, m, k, p, val) vector<vector<vector<vector<T>>>> name((n), vector<vector<vector<T>>>((m), vector<vector<T>>((k), vector<T>((p), (val)))))

using namespace std;
using i128 = __int128;
using u128 = unsigned __int128;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PLL = pair<LL, LL>;
using PLD = pair<LD, LD>;

const int N = 2e5 + 10, MOD = 998244353;
const int INF = 1e9;
const LL LL_INF = 2e18;
const LD EPS = 1e-8;
const int dx4[] = {-1, 0, 1, 0}, dy4[] = {0, 1, 0, -1};
const int dx8[] = {-1, -1, -1, 0, 0, 1, 1, 1}, dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

istream& operator>>(istream& is, i128& val) {
    string str;
    is >> str;
    val = 0;
    bool flag = false;
    if (str[0] == '-') flag = true, str = str.substr(1);
    for (char& c : str) val = val * 10 + c - '0';
    if (flag) val = -val;
    return is;
}

ostream& operator<<(ostream& os, i128 val) {
    if (val < 0) os << "-", val = -val;
    if (val > 9) os << val / 10;
    os << static_cast<char>(val % 10 + '0');
    return os;
}

bool cmp(LD a, LD b) {
    if (fabs(a - b) < EPS) return 1;
    return 0;
}

LL qpow(LL a, LL b) {
    LL ans = 1;
    a %= MOD;
    while (b) {
        if (b & 1) ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

LL fact[N], infact[N];

void init() {
    fact[0] = 1, infact[0] = 1;
    for (LL i = 1; i < N; ++i) {
        fact[i] = fact[i - 1] * i % MOD;
        infact[i] = qpow(fact[i], MOD - 2) % MOD;
    }
}

LL C(LL a, LL b) {
    if (a < b || b < 0) return 0;
    return fact[a] % MOD * infact[b] % MOD * infact[a - b] % MOD;
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 3), b(n + 3), c(n + 3);
    
    for (int i = 1; i <= n; ++i) {
        int l, r;
        cin >> l >> r;
        a[l]++, a[r + 1]--;
        int x = n - r, y = n - l;
        b[x]++, b[y + 1]--;

        int p = max(l, x), q = min(r, y);
        if (p <= q) {
            c[p]++;
            c[q + 1]--;
        }
    }

    LL ans = 0;
    LL x = 0, y = 0, z = 0;
    for (int k = 1; k <= n - 1; ++k) {
        x += a[k];
        y += b[k];
        z += c[k];

        if (x + y - z != n) continue;
        int nd = k - (x - z);
        ans = (ans + C(z, nd) % MOD) % MOD;
    }

    ans %= MOD;
    ans = (ans + MOD) % MOD;

    cout << ans << '\n';

/**/ #ifdef LOCAL
    cout << flush;
/**/ #endif
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    init();

    int T = 1;
    while (T--) solve();
    cout << fixed << setprecision(15);

    return 0;
}
全部评论

相关推荐

04-14 08:50
广西大学 算法工程师
特斯拉 自动驾驶 一面
1.&nbsp;自我介绍自我介绍不要按履历流水账去讲，直接围绕岗位匹配展开。比较稳的方式是先一句话说明自己主要做&nbsp;RAG、Agent、AI&nbsp;应用后端和推理服务，再挑两段最能打的经历展开：一段讲检索增强、知识入库、召回排序、长上下文记忆和评测闭环；另一段讲系统工程，比如高并发服务、索引构建、异步任务编排、可观测性和线上稳定性。最后补一句最近做得最深的方向，比如多路召回融合、长任务记忆回溯、RAG&nbsp;事实性评估或者工具调用治理，把后面的追问引到自己准备过的区域。2&nbsp;RAG&nbsp;摄入数据时，文档预处理最值得讲的几个难点是什么难点通常不是“把文本读出来”，而是结构恢复和知识标准化。像&nbsp;PDF、扫描件、网页、表格、工单...
AI-Agent面试实战...
点赞 评论 收藏
分享
03-24 14:52
山东大学 C++
点赞 评论 收藏
分享
02-25 16:10
南京邮电大学 golang
点赞 评论 收藏
分享
04-10 11:04
门头沟学院 后端工程师
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

更多

创作者周榜

更多
正在热议
更多
# AI时代还有必要刷leetcode吗？ #
30949次浏览 397人参与
# 大学生该如何认清当下的就业环境？ #
161688次浏览 872人参与
# 有哪些公司在面试时考察AICoding？ #
17637次浏览 331人参与
# 运营来爆料 #
98658次浏览 508人参与
# HR面都在聊什么？ #
12570次浏览 153人参与
# 美团开奖 #
407513次浏览 1805人参与
# 百度工作体验 #
325162次浏览 2247人参与
# 想从事Agent应该学习哪些技术？ #
7665次浏览 259人参与
# 26届春招投递记录 #
3355次浏览 38人参与
# OPPO求职进展汇总 #
808584次浏览 5441人参与
# 校招生月薪1W算什么水平 #
143194次浏览 492人参与
# 你觉得什么岗位会被AI替代 #
56986次浏览 369人参与
# 从投递到OC，你用了多久 #
22228次浏览 228人参与
# 什么人最适合大厂？ #
11934次浏览 123人参与
# 父母问你工作找得怎么样，怎么回 #
21810次浏览 258人参与
# 哪些公司面试还在问八股？ #
13038次浏览 112人参与
# 许愿池 #
373588次浏览 2921人参与
# 我与AI的日常 #
3182次浏览 16人参与
# 实习最想跑路的瞬间 #
137540次浏览 762人参与
# 我的求职进度条 #
1099676次浏览 7909人参与
牛客网
牛客网在线编程
牛客网题解
牛客企业服务