Educational Codeforces Round 159 (Rated for Div. 2)

Shiroha白羽的博客

Shiroha · 2024-02-13 · via Shiroha白羽的博客

A. Binary Imbalance

大致题意

有一个 01 字符串，每次允许选择两个相邻的字母中间插入一个 01 字符，如果相邻的两个字母不同则插入 0 否则插入 1

问是否可能经过任意次数操作后，字符串中的 0 比 1 多

思路

只要有 0 就行了

AC code

void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        string str;
        str.reserve(n);
        cin >> str;
        int cnt[2] = {0, 0};
        for (const auto& c: str) ++cnt[c - '0'];
        cout << (cnt[0] ? "YES" : "NO") << endl;
    }
}

B. Getting Points

大致题意

有 $n$ 天的学期，每一天都可以选择是学习还是休息，学习的话，会得到 $l$ 分，同时可以完成至多两个任务，每个任务可以得到 $t$ 分

任务每隔 $7$ 天会生成一个，第一个任务在第 $1$ 天生成，每个任务一旦被完成就不能再次得到分数

问在至少得到 $p$ 分的情况下，最多可以休息多少天

思路

因为任务每 $7$ 天才有一个，而每天可以完成 $2$ 个，所以必然可以把任务做完。即然要休息时间足够久，那么必然是最后几天完成任务即可

所以只需要考虑最后需要多少天进行学习即可。

当然也可以考虑分类讨论，比如所有天都是完成两个任务的学习，或者个别天是不做任何任务的学习

AC code

#define int long longvoid solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n, p, l, t;
        cin >> n >> p >> l >> t;
        const int cnt = (n + 6) / 7, d = (cnt + 1) / 2;
        if (d * l + t * cnt >= p)
            cout << n - ((2 * t + l + p - 1) / (2 * t + l)) << endl;
        else
            cout << n - ((p - cnt * t + l - 1) / l) << endl;
    }
}

C. Insert and Equalize

大致题意

有一个初始的数组，每个值不同，需要往里面加入一个任选的值，让数组仍然保持不同

然后进行 $t$ 次操作，每次操作是选择一个值并将其加上 $x$，问让所有值都相同的，最少多少的 $t$

思路

先不管加入一个值这个事情，如果只是纯粹的做加法，那么非常简单，只需要找到所有差值的最大公约数就行了，那么这个公约数就是 $x$

那么也就可以得到 $t$ 了，即所有值变成 $a_{max}$ 所需要的步数

接下来是加入一个值的部分，因为必须要和原来的数组不同，所以可以考虑尝试 $a_{max} - c \times x$，而 $c$ 就是需要额外增加的成本，所以要尽可能小即可

AC code

#define int long longint gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
void solve() {
    int _;
    cin >> _;
    for (int ts = 0; ts < _; ++ts) {
        int n;
        cin >> n;
        vector<int> data(n);
        for (auto& i: data) cin >> i;
        if (n == 1) {
            cout << 1 << endl;
            continue;
        }
        sort(data.begin(), data.end());
        set<int> dif;
        for (int i = 0; i < n - 1; ++i) dif.insert(data[i + 1] - data[i]);
        int g = dif.begin().operator*();
        for (const auto& s: dif) g = gcd(g, s);
        int ans = 0;
        for (const auto& i: data) ans += (data[n - 1] - i) / g;
        if (dif.size() == 1) ans += n;
        else {
            for (int i = n - 2; i >= 0; --i) {
                if (const int tmp = n - 1 - i; data[i] + tmp * g != data[n - 1]) {
                    ans += tmp;
                    break;
                }
            }
        }
        cout << ans << endl;
    }
}

E. Collapsing Strings

大致题意

有一堆的字符串，使用 $\left | x \right |$ 表示 $x$ 的字符串长度

定义一个函数，$C(a, b)$，其中 $a, b$ 都是字符串

$$ C(a, b) = \left\{\begin{matrix} a, & \left | b \right | = 0 \\ b, & \left | a \right | = 0 \\ C(a_{1 \dots \left | a \right | - 1}, b_{2 \dots \left | b \right |}), & a_{\left | a \right |} = b_1 \\ a + b, & others \end{matrix}\right. $$

问

$$\sum_{i=1}^{n} \sum_{j=1}^{n} \left | C(s_i, s_j) \right |$$

思路

其实就是要找出任意两个字符串之间，前后重叠的部分即可

可以考虑用字典树做，每个字典树的节点上记录下当前节点有多少字符串在这里结束了，又有多少字符串经过了这个节点，总共有多少个字符在其子节点上即可

然后再扫一遍全部的字符串即可

AC code

void solve() {
    int n;
    cin >> n;
    string str;
    str.resize(1e6 + 10, -1);    struct node {
        int arr[26]{};
        int len = 0, cnt = 0, end = 0;
        node() { memset(arr, -1, sizeof arr); }
    };
    vector<node> tree(1e6 + 10);
    constexpr int root = 0;
    int nxt = 1;
    vector<string> data;
    for (int i = 0; i < n; ++i) {
        cin >> str;
        int cur = root;
        for (int l = 0; l < str.size(); ++l) {
            if (!~tree[cur].arr[str[l] - 'a']) {
                tree[cur].arr[str[l] - 'a'] = nxt++;
            }
            cur = tree[cur].arr[str[l] - 'a'];
            tree[cur].len += static_cast<int>(str.size()) - l;
            ++tree[cur].cnt;
        }
        ++tree[cur].end;
        data.push_back(str);
    }
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        string &s = data[i];
        int cur = root;
        for (int l = static_cast<int>(s.size()) - 1; l >= 0; --l) {
            for (int x = 0; x < 26; ++x) if (x != s[l] - 'a' && tree[cur].arr[x] != -1)
                ans += tree[tree[cur].arr[x]].len + 1LL * (l + 1) * tree[tree[cur].arr[x]].cnt;
            ans += 1LL * (l + 1) * tree[cur].end;
            cur = tree[cur].arr[s[l] - 'a'];
            if (!~cur) break;
        }
        if (cur != -1) for (const int x : tree[cur].arr) if (x != -1) ans += tree[x].len;
    }
    cout << ans << endl;
}

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

Shiroha白羽的博客

A. Binary Imbalance

大致题意

思路

AC code

B. Getting Points

大致题意

思路

AC code

C. Insert and Equalize

大致题意

思路

AC code

E. Collapsing Strings

大致题意

思路

AC code