比赛地址

A. Long Comparison

题意：给两组数，每组包含原数 $x$ 和后面跟的0的个数 $p$，问哪个数字大。

解法：模拟即可

#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}

inline void solve() {
    PLL a, b;
    cin >> a.first >> a.second;
    cin >> b.first >> b.second;
    if (a.first == b.first) {
        if (a.second == b.second) cout << "=" << endl;
        else if (a.second > b.second) cout << ">" << endl;
        else cout << "<" << endl;
        return;
    }
    string p = to_string(a.first), q = to_string(b.first);
    if (p.size() + a.second == q.size() + b.second) {
        while (p.back() == '0') p.pop_back(), a.second ++;
        while (q.back() == '0') q.pop_back(), b.second ++;
        if (p.size() < q.size()) {
            for (int i = 0; i < q.size(); i ++ ) {
                if (i >= p.size()) {
                    if (q[i] > '0') {cout << "<" << endl; return ;}
                } else {
                    if (p[i] < q[i]) {cout << "<" << endl; return ;}
                    else if (p[i] > q[i]) {cout << ">" << endl; return ;}
                }
            }
        } else {
            for (int i = 0; i < p.size(); i ++ ) {
                if (i >= q.size()) {
                    if (p[i] > '0') {cout << ">" << endl; return ;}
                } else {
                    if (p[i] < q[i]) {cout << "<" << endl; return ;}
                    else if (p[i] > q[i]) {cout << ">" << endl; return ;}
                }
            }
        }
        cout << "=" << endl;
    } else if (p.size() + a.second > q.size() + b.second) cout << ">" << endl;
    else cout << "<" << endl;
}
int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto now = clock();
#endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(2);
    int T; cin >> T;
    while (T -- )
        solve();
#ifdef DEBUG
    cout << "============================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}

B. Absent Remainder

题意：给一个长度为 $n$ 的数组 $a$，要求找到 $\lfloor \frac{n}{2} \rfloor$ 组 $x, y$，使得

1、$x ≠ y$

2、$x,y$ 都是数组 $a$ 中的数

3、$x \mod y$ 不是数组中的数

输出方案

解法：注意到只要选定一个 $y$，所有小于 $y$ 的都有可能是模数，因此找到数组中最小的元素当作 $y$ 即可。

#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}

inline void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    sort(a.begin() + 1, a.end());
    reverse(a.begin() + 1, a.end());
    for (int i = 1; i <= n / 2; i ++ ) cout << a[i] << ' ' << a[n] << endl;
}
int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto now = clock();
#endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(2);
    int T; cin >> T;
    while (T -- )
        solve();
#ifdef DEBUG
    cout << "============================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}

C. Poisoned Dagger

题意：你去打一个血量为 $h$ 的怪兽，有 $n$ 次攻击时机，每次攻击完后的 $k$ 秒中，每秒会造成1点伤害。如果上次攻击完后的 $k$ 秒内又进行了一次攻击，那么会重置秒数。当怪兽血量归0则怪兽被打败了。求最小的 $k$ 使得你能打败怪兽。

解法：二分答案验证即可

#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}

inline void solve() {
    int n; cin >> n;
    LL h; cin >> h;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    auto check = [&] (LL x) {
        LL res = 0;
        for (int i = 1; i <= n; i ++ ) {
            if (i < n) {
                if (a[i + 1] - a[i] >= x) res += x;
                else res += a[i + 1] - a[i];
            } else res += x;
        }
        return res >= h;
    };
    LL l = 1, r = h;
    while (l < r) {
        LL mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
}
int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto now = clock();
#endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(2);
    int T; cin >> T;
    while (T -- )
        solve();
#ifdef DEBUG
    cout << "============================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}

D. MEX Sequences

题意：我们称一个长度为 $k$ 的数组 $x$ 是 $MEX-correct$ 的，当且仅当 $\forall i \in [1, k] \,\,\,\, |x_i - MEX(x_1, x_2, …,x_k)| <= 1$。给定一个数组，问满足以上性质的子序列的个数。

对于任意由一个非负整数组成的集合 $s$ 来说， $MEX(s)$ 表示不存在这个集合 $s$ 的最小的非负整数。

解法：dp

状态设计：$dp[i][0/1]$ 表示含有数字 $i$，并且当前序列的 $mex$ 值为 $i - 1$ 或者 $i + 1$ 的时候的方案数

状态转移：

$dp[i][0] += dp[i - 2][1] + dp[i][0]$

$dp[i][1] += dp[i][1] + dp[i - 1][1]$

$dp[i + 2][0] += dp[i + 2][0]$

前面两行转移显然，这里解释下第三行

首先排除一个状态设计的误区，用 $dp[i][0/1]$ 表示以i为结尾，并且当前序列的 $mex$ 值为 $i - 1$ 或者 $i + 1$ 的时候的方案数

给各位一个hack样例

1
7
0 2 0 2 0 2 0

答案是85

如果按照我后面说的设计，那么就会少，原因就在于，当前面重复出现 $a[i]$ 的时候，当前 $a[i]$ 应该插入其中，而不是以 $a[i]$ 结尾，所以方案数会少算。

明白了这个道理，第三行的转移也就显然了，因为要插入其中，所以方案数翻倍

注意特判下0,1即可

#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e6 + 10;
const int MOD = 998244353;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}

LL f[N][2];

inline void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = 0; i <= n + 5; i ++ ) f[i][0] = f[i][1] = 0;
    for (int i = 1; i <= n; i ++ ) {
        if (a[i] == 0) {
            f[0][1] = (f[0][1] * 2 + 1) % MOD;
            if (2 <= n) f[2][0] = f[2][0] * 2 % MOD;
        } else if (a[i] == 1) {
            f[1][0] = (f[1][0] * 2 + 1) % MOD;
            f[1][1] = (f[1][1] * 2 + f[0][1]) % MOD;
            if (3 <= n) f[3][0] = f[3][0] * 2 % MOD;
        } else {
            f[a[i]][0] = (f[a[i]][0] * 2 + f[a[i] - 2][1]) % MOD;
            f[a[i]][1] = (f[a[i]][1] * 2 + f[a[i] - 1][1] + f[a[i] + 2][0]) % MOD;
            if (a[i] + 2 <= n) f[a[i] + 2][0] = f[a[i] + 2][0] * 2 % MOD;
        }
    }
    LL res = 0;
    for (int i = 0; i <= n; i ++ ) res = (res + f[i][0] + f[i][1]) % MOD;
    cout << res << endl;
}
int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto now = clock();
#endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(2);
    int T; cin >> T;
    while (T -- )
        solve();
#ifdef DEBUG
    cout << "============================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}

E. Crazy Robot

题意：给定一张形式为二维矩阵的图，包含以下三种元素

1、“.” 表示可到达的点

2、”#”表示不可到达的点

3、”L”表示实验室

现在有一个机器人，他可以在任何一个可到达点处开始走，每次行动你要给出一个指令（上下左右走），他都不会听你的指令，也就是说会朝除了你说的那个方向的另外三个方向找一个可以走的地方走。要求不能走到不可到达点，不能走出地图。

那么对于地图上的每个可到达的点来说，是否存在一种指令方式，使得不论机器人如何行动，都能到达实验室，把这些点用“+”标记后输出。

解法：BFS

自己简单模拟下后会发现，当前点如果只有小于等于2个点可以走的话，说明我们是可以精准控制其走向的。

当前点的可达点中，包含至少一个可到达实验室的点，说明这个点也是可到达实验室的。

或者当前点的可达点中，全部都是可以到达实验室的点，说明这个点也是可以到达实验室的。

从实验室开始BFS回去即可。

#include <bits/stdc++.h>
#define endl '\n'
#define ls u << 1
#define rs u << 1 | 1
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL,LL> PLL;
const int INF = 0x3f3f3f3f, N = 1e5 + 10;
const int MOD = 1e9 + 7;
const double eps = 1e-6;
const double PI = acos(-1);
inline int lowbit(int x) {return x & (-x);}

inline void solve() {
    int n, m; cin >> n >> m;
    vector<vector<char>> g(n + 1,vector<char> (m + 1));
    for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) cin >> g[i][j];
    int px, py;
    for (int i = 1; i <= n; i ++ ) for (int j = 1; j <= m; j ++ ) if (g[i][j] == 'L') px = i, py = j;
    queue<PII> q;
    q.push({px, py});
    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};

    auto check_cell = [&] (int px, int py) {
        int cnt = 0;
        for (int i = 0; i < 4; i ++ ) {
            int x = px + dx[i], y = py + dy[i];
            if (x < 1 || x > n || y < 1 || y > m) continue;
            if (g[x][y] == '.') cnt ++;
        }
        return cnt <= 1;
    };

    while (!q.empty()) {
        auto now = q.front(); q.pop();
        for (int i = 0; i < 4; i ++ ) {
            int x = now.first + dx[i], y = now.second + dy[i];
            if (x < 1 || x > n || y < 1 || y > m) continue;
            if (g[x][y] == '+' || g[x][y] == '#' || g[x][y] == 'L') continue;
            if (check_cell(x, y)) {
                g[x][y] = '+';
                q.push({x, y});
            }
        }
    }
    for (int i = 1; i <= n; i ++ ) {
        for (int j = 1; j <= m; j ++ ) cout << g[i][j];
        cout << endl;
    }
}
int main() {
#ifdef DEBUG
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    auto now = clock();
#endif
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cout << fixed << setprecision(2);
    int T; cin >> T;
    while (T -- )
        solve();
#ifdef DEBUG
    cout << "============================" << endl;
    cout << "Program run for " << (clock() - now) / (double)CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif
    return 0;
}