C. Clamped Sequence

因为\(n\)的范围不大，并且可以猜到\(l,r\)中应该至少有一个在\(a_i，a_i-1,a_i+1\)上。所以直接暴力枚举\(l\)或\(r\)然后暴力的计算一下

#include <bits/stdc++.h>

using namespace std;

#define int long long

using vi = vector<int>;


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int n, d, res = 0;
    cin >> n >> d;
    vector<int> a(n), b;
    for (int &i: a)
        cin >> i, b.push_back(i), b.push_back(i - 1), b.push_back(i + 1);
    sort(b.begin(), b.end());
    b.resize(unique(b.begin(), b.end()) - b.begin());
    for (int r; int l: b) {
        r = l + d;
        auto c = a;
        for (auto &i: c) {
            if (i < l) i = l;
            if (i > r) i = r;
        }
        int cnt = 0;
        for (int i = 1; i < n; i++)
            cnt += abs(c[i] - c[i - 1]);
        res = max(res, cnt);
    }
    for (int l; int r: b) {
        l = r - d;
        auto c = a;
        for (auto &i: c) {
            if (i < l) i = l;
            if (i > r) i = r;
        }
        int cnt = 0;
        for (int i = 1; i < n; i++)
            cnt += abs(c[i] - c[i - 1]);
        res = max(res, cnt);
    }
    cout << res << "\n";
    return 0;
}

D. DRX vs. T1

签到

#include <bits/stdc++.h>

using namespace std;

#define int long long


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    string s;
    cin >> s;
    map<char,int> cnt;
    for( auto i : s )
        cnt[i] ++;
    if( cnt['T'] >= 3 ) cout << "T1\n";
    else if( cnt['D'] >= 3) cout << "DRX\n";
    return 0;
}

F. Half Mixed

#include <bits/stdc++.h>

using namespace std;

#define int long long

using vi = vector<int>;

void solve() {
    int n, m;
    cin >> n >> m;
    if ((n * (n + 1) * m * (m + 1) / 4) & 1) {
        cout << "No\n";
        return;
    }
    cout << "Yes\n";
    int t = n, T = n * (n + 1) / 2;
    if (T & 1) t = m, T = m * (m + 1) / 2;
    T = T / 2 - t;
    auto f = [&t, &T]() {
        int l = 1, r = t, res = -1;
        for (int mid; l <= r;) {
            mid = (l + r) / 2;
            if (mid * (mid - 1) / 2 <= T) res = mid, l = mid + 1;
            else r = mid - 1;
        }
        t -= res, T -= res * (res - 1) / 2;
        return res;
    };
    vector<int> res;
    for (int x = 0, y; t; x ^= 1) {
        y = f();
        for (; y; y--) res.push_back(x);
    }
    if (res.size() == m) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++)
                cout << res[j] << " ";
            cout << "\n";
        }
    } else {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cout << res[i] << " ";
            }
            cout << "\n";
        }
    }
    return;
}

int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}

L. Tavern Chess

直接根据题意模拟，模拟的形式就是用 dfs 去搜索，在搜索的过程中计算出到当前状态的概率。

When a team takes the attack, the leftmost minion with the mininum number of taking attacks from the team attacks one of the alive minios from the other team uniformyly ad random, and then the other team takes the attack.

这句话，在赛时卡了很久，我认为其正确的意思应该是：当一个队伍攻击时，发起攻击次数最少且最靠左的士兵会等概率的随机攻击另一方一个存活的士兵，在攻击后交换攻击。

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using db = long double;

int n, m;
vi atk0, atk1;
db A = 0, B = 0, T = 0;

void dfs(vi hp0, vi hp1, vi cnt0, vi cnt1, int t, db p, int dep) {

    db alive0 = 0, alive1 = 0; // 存活人数
    for (auto i: hp0) alive0 += (i > 0);
    for (auto i: hp1) alive1 += (i > 0);


    if (alive0 == 0 or alive1 == 0) { // 游戏结束
        if (alive0 == alive1) T += p;
        else if (alive0 == 0) B += p;
        else A += p;
        return;
    }


    if (t == 0) { // Alice attack
        int id = -1;
        for (int i = 0; i < n; i++) {
            if (hp0[i] <= 0) continue;
            if (id == -1 or cnt0[id] > cnt0[i]) id = i;
        }
        cnt0[id]++;

        for (int i = 0; i < m; i++) {
            if (hp1[i] <= 0) continue;
            hp0[id] -= atk1[i], hp1[i] -= atk0[id];
            dfs(hp0, hp1, cnt0, cnt1, t ^ 1, p / alive1, dep + 1);
            hp0[id] += atk1[i], hp1[i] += atk0[id];
        }
    } else { // Bob attack
        int id = -1;
        for (int i = 0; i < m; i++) {
            if (hp1[i] <= 0) continue;
            if (id == -1 or cnt1[id] > cnt1[i]) id = i;
        }
        cnt1[id]++;
        for (int i = 0; i < n; i++) {
            if (hp0[i] <= 0) continue;
            hp0[i] -= atk1[id], hp1[id] -= atk0[i];
            dfs(hp0, hp1, cnt0, cnt1, t ^ 1, p / alive0, dep + 1);
            hp0[i] += atk1[id], hp1[id] += atk0[i];
        }
    }
    return;
}


int32_t main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n >> m;
    atk0 = vi(n), atk1 = vi(m);
    for (auto &i: atk0) cin >> i;
    for (auto &i: atk1) cin >> i;
    if (n > m) dfs(atk0, atk1, vi(n), vi(m), 0, 1.0, 0);
    else if (m > n) dfs(atk0, atk1, vi(n), vi(m), 1, 1.0, 0);
    else dfs(atk0, atk1, vi(n), vi(m), 0, 0.5, 0), dfs(atk0, atk1, vi(n), vi(m), 1, 0.5, 0);

    cout << fixed << setprecision(10) << A << "\n" << B << "\n" << T << "\n";
    return 0;
}