Educational Codeforces Round 117 (Rated for Div. 2) ABCDEG题解

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

Educational Codeforces Round 117 (Rated for Div. 2) ABCDEG题解

作者：

Time_Limit_Exceeded , 2021-11-23 16:33:35 , 所有人可见 , 阅读 444

5

1

比赛地址

A. Distance

题意：给出一个点 $p$，设其离原点的曼哈顿距离为 $x$，找出一个点，使得其离原点和离 $p$ 的曼哈顿距离都为 $\frac{x}{2}$，输出找到的点，否则输出-1

解法：首先当 $x$ 为奇数的时候必定不存在，否则直接分类讨论找中点即可

#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 x, y; cin >> x >> y;
    if (x == y) cout << x << ' ' << 0 << endl;
    else {
        if ((x + y) & 1) cout << -1 << ' ' << -1 << endl;
        else {
            if (x > y) cout << (x + y) / 2 << ' ' << 0 << endl;
            else cout << x << ' ' << y - (x + y) / 2 << 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. Special Permutation

题意：给定 $n,a,b$，构造出一个 $n$ 的排列，使得左边一半元素的最小值为 $a$，右边一半元素的最大值为 $b$

解法：对于左边，一定是从小到大选，对于右边一定是从大到小选，选完后检查即可

#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, a, b; cin >> n >> a >> b;
    vector<bool> st(n + 1);
    vector<int> l, r;
    l.push_back(a), r.push_back(b);
    st[a] = st[b] = true;
    for (int i = n; i; i -- ) {
        if (st[i]) continue;
        l.push_back(i);
        st[i] = true;
        if (l.size() == n / 2) break;
    }
    for (int i = 1; i <= n; i ++ ) {
        if (st[i]) continue;
        r.push_back(i);
        st[i] = true;
        if (r.size() == n / 2) break;
    }
    for (int i = 0; i < n / 2; i ++ ) {
        if (l[i] < a) {cout << -1 << endl; return ;}
    }
    for (int i = 0; i < n / 2; i ++ ) {
        if (r[i] > b) {cout << -1 << endl; return ;}
    }
    for (int i = 0; i < n / 2; i ++ ) cout << l[i] << ' ';
    for (int i = 0; i < n / 2; i ++ ) cout << r[i] << ' ';
    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;
}

C. Chat Ban

题意：定义一个序列$1,2,3,…,k - 1,k, k - 1,…,3, 2, 1$，当你发了 $p$ 条信息的时候，代价是之前那个序列的前 $p$ 个数的和，现在给定 $k, x$，如果当前的代价一旦超过 $x$，那么就会被禁言，发不了信息。求最多可以发多少条信息。

解法：二分答案验证即可

#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);}

LL k, x;

__int128 calc(LL tmp) {
    if (tmp <= k) return tmp * (1 + tmp) / 2;
    __int128 res = k * (1 + k) / 2;
    tmp -= k;
    res += __int128((2 * k - 1 - tmp) * tmp) / 2;
    return res;
}

inline void solve() {
    cin >> k >> x;
    LL l = 1, r = 2 * k - 1;
    while (l < r) {
        LL mid = (l + r) >> 1;
        if (calc(mid) >= x) 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. X-Magic Pair

题意：给定数对 $(a, b)$ 与 $x$，给定两个操作

操作1：$a = |a - b|$

操作2：$b = |a - b|$

你可以进行若干次操作，问能否得到 $a = x \,or \, b = x$

解法：魔改gcd

建议模拟下 $15,38,7$ 这组样例，会发现得到答案的过程像欧几里得求gcd过程，于是在求的过程加上判断即可

#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);}

LL x;

bool gcd(LL a, LL b) {
    if (a < b) swap(a, b);
    if (b == 0 || a == 0) return false;
    if (x > a && x > b) return false;
    if (a > x && (a - x) % b == 0) return true;
    if (a == x || b == x) return true;
    return gcd(a % b, b);
}

inline void solve() {
    LL a, b; cin >> a >> b >> x;
    if (x > a && x > b) {cout << "NO" << endl; return ;}
    if (x == a || x == b) {cout << "YES" << endl; return ;}
    if (gcd(a, b)) cout << "YES" << endl;
    else cout << "NO" << 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. Messages

题意：有 $n$ 个学生，老师想让第 $i$ 个学生看第 $m_i$ 条信息，并且对于第 $i$ 个学生来说，如果老师贴出的信息条数 $\le k_i$ 时，该学生会把信息全看了，否则就会随机挑 $k_i$ 条看。问期望让更多的学生看到老师希望其看到的信息的情况下，老师应该贴出哪些信息？

解法：枚举+统计答案

一开始想到三分答案验证，但是群友说T了，应该是目标函数不是一个单极值的，注意到 $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 = 2e5 + 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> m(n + 1), k(n + 1);
    for (int i = 1; i <= n; i ++ ) cin >> m[i] >> k[i];
    vector<int> p(N);
    for (int i = 1; i < N; i ++ ) p[i] = i;
    vector<int> ans;
    double res = 0.0;//最优的期望
    for (int i = 1; i <= 21; i ++ ) {
        vector<double> cnt(N, 0.0);//统计每条信息贴出去的时候，期望会有多少
        for (int j = 1; j <= n; j ++ ) {
            if (k[j] >= i) cnt[m[j]] += 1.0;
            else cnt[m[j]] += (double)k[j] / i;//这里的原始公式应该是c[i - 1][k[j] - 1] / c[i][k[j]]，化简后就是这样，c是组合数
        }
        sort(p.begin() + 1, p.end(), [&] (int a, int b) {
            return cnt[a] > cnt[b];//根据信息的期望值从大到小选
        });
        double tmp = 0.0;
        for (int j = 1; j <= i; j ++ ) tmp += cnt[p[j]];//统计当前的期望
        if (tmp > res) {//如果当前更优，更新答案
            res = tmp;
            ans.clear();
            for (int j = 1; j <= i; j ++ ) ans.push_back(p[j]);
        }
    }
    cout << ans.size() << endl;
    for (auto ite : ans) cout << ite << ' ';
    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;
}

G. Max Sum Array

首先感谢 @hunzia 的帮助

题意：给定数组 $c = [c_1, c_2, …,c_m]$，要构造出另外一个长度为 $n$ 的数组 $a = [a_1, a_2,…,a_n]$，使得 $\forall i\in[1,m]$ 恰好有 $c_i$ 个 $i$ 出现在数组 $a$ 中。

再定义一个函数 $f(a) = \sum_{1 \le i < j \le n,a_i = a_j} j -i$

求出 $f(a)$ 的最大值，并且求出当 $f(a)$ 最大时，$a$ 的构造方案数

解法：贪心

容易想到一个贪心，注意到相同的数字间的距离越远，对答案的贡献越大，于是对数字个数从大到小来考虑，每次都拿出两个放到 $a$ 两边，这就是构造的方法。

接下来考虑对答案的贡献以及方案数的计算。

首先考虑对答案的贡献，设当前 $a$ 中还有 $num$ 个位置没排，当前排个数为 $i$ 的数，设有 $cnt[i]$ 个，根据刚刚的策略，容易得出要对 $i$ 从大到小考虑。首先就是这 $cnt[i]$ 个数依次放到数组两边，那么每个数字的贡献就是 $$num - cnt[i] * 2 + cnt[i]$$，一共有 $cnt[i]$ 个数字，乘起来，最后还要算上两边对中间的 $(i - 2) * cnt[i]$ 个数的贡献 $$(i - 2) * cnt[i] * (num - cnt[i] * 2 + cnt[i])$$，化简后就是 $$(num - cnt[i]) * cnt[i] * (i - 1)$$

每轮放数字结束后记得把 $num -= 2 * cnt[i]$，因为有这么多的位置被占了。

方案数的话就很简单了，对当前个数为1的时候进行特判，因为这个只能放一边，其他的都是可以两边随意放，所以是 $cnt[i]!$ 种，乘法原理即可，具体看代码

#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 = 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> cnt(N);
    vector<LL> f(N);
    LL num = 0;
    for (int i = 1; i <= n; i ++ ) {
        int x; cin >> x;
        num += x;
        cnt[x] ++;
    }
    f[0] = 1;
    for (int i = 1; i <= n; i ++ ) f[i] = f[i - 1] * i % MOD;
    LL res = 0, ways = 1;
    for (int i = 1000000; i; i -- ) {
        cnt[i] += cnt[i + 2];//注意，之前的数都只排了两个，肯定有剩下的，所以需要隔位后缀和
        if (i == 1) ways = ways * f[cnt[i]] % MOD;
        else ways = ways * f[cnt[i]] % MOD * f[cnt[i]] % MOD;
        res = (res + (num - cnt[i]) * cnt[i] % MOD * (i - 1) % MOD) % MOD;
        num -= 2 * cnt[i];
    }
    cout << res << ' ' << ways << 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;
}

4 评论

Kath 2021-11-23 19:25

Orz

IEE 2021-11-23 18:40

tql

hunzia 2021-11-23 16:42

Orz

海绵宝宝lll 2021-11-23 16:39

orz

App 内打开