比赛链接：https://codeforces.com/contest/1342

A - Road To Zero

题意

有两个非负整数 x, y 以及两种操作：

支付 a 点代价使其中一个数加一或减一
支付 b 点代价使两个数都加一或减一

问使二者为 0 的最小代价。

思路

把较大的数减至与较小数相等再选取 min(2 * a, b) 把二者减为 0 即可。

代码

#include <bits/stdc++.h>

using namespace std;

void solve() {

    long long x, y, a, b; cin >> x >> y >> a >> b;

    cout << min(2 * a, b) * min(x, y) + a * (max(x, y) - min(x, y)) << "\n";

}

int main() {

    int t; cin >> t;

    while (t--) solve();

}

B - Binary Period

题意

给定 01 串 t，构造 01 串 s，要求满足：

长度不超过 2 * | t |
t 为 s 的一个子序列
s 由最短的字符串重复而成

思路

如果 t 中只含有一种字符直接输出 t 即可，否则对于 t 中的每位均用“01”代替。

代码

#include <bits/stdc++.h>

using namespace std;

void solve() {

    string t; cin >> t;

    int zero = 0, one = 0;

    for (char c : t)

        if (c == '0') zero = 1;

        else one = 1;

    if (zero + one == 1) cout << t << "\n";

    else {

        for (int i = 0; i < t.size(); i++)

            cout << "01";

        cout << "\n";

    }

}

int main() {

    int t; cin >> t;

    while (t--) solve();

}

C - Yet Another Counting Problem

题意

给你两个正整数 a, b，回答 q 次询问：[l, r] 区间中有多少数 x % a % b != x % b % a 。

思路

观察到条件为 x % a % b != x % b % a，可以联想到 (x + lcm(a, b)) % a % b != (x + lcm(a, b)) % b % a ，所以只需计算 [1, lcm] 区间内满足条件的数的个数，然后计算 [1, l - 1], [1, r] 中各有多少个长为 lcm 的区间，考虑到可能有不完全包含区间，所以可以计算 [1, lcm] 内的前缀和，查询长度对 lcm 取余对应的前缀和即为不完全包含区间中满足条件的数的个数。

代码

#include <bits/stdc++.h>

using LL = long long;

using namespace std;

void solve() {

    int a, b, q; cin >> a >> b >> q;

    int lcm = a * b / __gcd(a, b);

    int cnt[lcm + 1] = {};

    for (int i = 1; i <= lcm; i++) {

        cnt[i] = cnt[i - 1] + (i % a % b != i % b % a);

    }

    auto f = [&] (LL n) -> LL {

        return cnt[lcm] * (n / lcm) + cnt[n % lcm];

    };

    for (int i = 0; i < q; i++) {

        LL l, r; cin >> l >> r;

        cout << f(r) - f(l - 1) << " \n"[i == q - 1];

    }

}

int main() {

    int t; cin >> t;

    while (t--) solve();

}

D - Multiple Testcases

题意

将 n 个数分为尽可能少的数组，要求每个数组中大于等于 i 的数不超过 c_i 个。

思路

一种较为简便的方法是：利用后缀和算出大于等于 i 的数共有多少个，最少需要的数组即为 $max \lceil \frac{n_i}{c_i} \rceil$，之后从小到大循环推入数组元素。但是这种贪心的原理仍有待证明。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    int n, k; cin >> n >> k;

    int suf[k + 1] = {};

    int m[n]; for (int &i : m) cin >> i, ++suf[i - 1];

    int c[k]; for (int &i : c) cin >> i;

    int ans = 0;

    for (int i = k - 1; i >= 0; i--) {

        suf[i] += suf[i + 1];

        ans = max(ans, (suf[i] - 1) / c[i] + 1);

    }

    vector<int> vec[ans];

    sort(m, m + n);

    for (int i = 0; i < n; i++)

        vec[i % ans].push_back(m[i]);

    cout << ans << "\n";

    for (auto v : vec) {

        cout << v.size();

        for (auto i : v) cout << ' ' << i;

        cout << "\n";

    }

}

巴特西

Educational Codeforces Round 86 (Div. 2)

A - Road To Zero

题意

思路

代码

B - Binary Period

题意

思路

代码

C - Yet Another Counting Problem

题意

思路

代码

D - Multiple Testcases

题意

思路

代码

最新文章

热门文章