AtCoder Beginner Contest 127 解题报告

非常遗憾。当天晚上错过这一场。不过感觉也会掉分的吧。后面两题偏结论题，打了的话应该想不出来。

#include <bits/stdc++.h>

using namespace std;

inline int read() {

    int x = , f = ; char ch = getchar();

    while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }

    while (ch >= '' && ch <= '') { x = x *  + ch - ; ch = getchar(); }

    return x * f;

}

int main() {

    int a = read(), b = read();

    if (a >= ) b = b;

    else if (a > ) b /= ;

    else b = ;

    cout << b << '\n';

    return ;

}

B - Algae

#include <bits/stdc++.h>

using namespace std;

inline int read() {

    int x = , f = ; char ch = getchar();

    while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }

    while (ch >= '' && ch <= '') { x = x *  + ch - ; ch = getchar(); }

    return x * f;

}

int main() {

    int r = read(), d = read(), x = read();

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

        x = r * x - d;

        printf("%d\n", x);

    }

    return ;

}

C - Prison

题意：有$N$张ID卡，编号为1到$N$，$M$扇门，每扇门对应着一个区间$\left[ L,R\right]$，在闭区间内的ID卡才能打开门，问有多少张ID卡能打开所有门。

思路：相当于$M$个区间求交集。然后就是求$L$的最大值和$R$的最小值，$L$大于$R$就无解，否则就是$R - L + 1$

#include <bits/stdc++.h>

using namespace std;

inline int read() {

    int x = , f = ; char ch = getchar();

    while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }

    while (ch >= '' && ch <= '') { x = x *  + ch - ; ch = getchar(); }

    return x * f;

}

int main() {

    int n = read(), m = read();

    int l = , r = n;

    while (m--) {

        int u = read(), v = read();

        l = max(l, u); r = min(r, v);

    }

    int ans;

    if (l > r) ans = ;

    else ans = r - l + ;

    printf("%d\n", ans);

    return ;

}

D - Integer Cards

题意：给$N$张卡片，有$M$次操作，每次可以至多把$B$张卡片上的数改成$C$，问最后$N$个数的和最大是多少。

思路：可以证(举例)明(发现)，最后结果与操作顺序无关。

那么就把$N$个数放进小根堆，然后把操作按$C$ 的大小排，每次从最小的开始替换，如果最小的值比当前的$C$大就可以不用换了。这样保证了每个数最多进出队一次。

时间复杂度$O\left( n\log \left( n\right) \right)$(对吗?)

#include <bits/stdc++.h>

#define ll long long

using namespace std;

inline int read() {

    int x = , f = ; char ch = getchar();

    while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }

    while (ch >= '' && ch <= '') { x = x *  + ch - ; ch = getchar(); }

    return x * f;

}

const int M = 1e5 + ;

struct P {

    int b;ll c;

    bool operator < (const P &rhs) const {

        return c > rhs.c;

    }

} p[M];

int main() {

    int n = read(), m = read();

    priority_queue<ll, vector<ll>, greater<ll> > que;

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

        int x = read();

        que.push((ll)x);

    }

    for (int i = ; i < m; i++) p[i].b = read(), p[i].c = (ll)read();

    sort(p, p + m);

    for (int i = ; i < m; i++) {

        int b = p[i].b;

        if (p[i].c <= que.top()) break;

        while (b--) {

            if (que.top() < p[i].c) {

                que.pop();

                que.push(p[i].c);

            } else {

                break;

            }

        }

    }

    ll sum = ;

    while (!que.empty()) {

        int x = que.top(); que.pop();

        sum += x;

    }

    cout << sum << '\n';

    return ;

}

E - Cell Distance

题意：求一个网格图里面任取$K$点的曼哈顿距离之和

思路：$N\times M$的网格图里面任意两点的曼哈顿距离的平均值是$\dfrac {N+M}{3}$

答案就是$C^{k}_{N\times M}C^{2}_{k}\dfrac {N+M}{3}$

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const ll MOD = 1e9 + ;

inline ll read() {

    ll x = , f = ; char ch = getchar();

    while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }

    while (ch >= '' && ch <= '') { x = x *  + ch - ; ch = getchar(); }

    return x * f;

}

ll qp(ll a, ll b) {

    ll ans = ;

    while (b) {

        if (b & ) ans = ans * a % MOD;

        a = a * a % MOD;

        b >>= ;

    }

    return ans;

}

const int N = 2e5 + ;

ll fac[N];

ll C(ll a, ll b) {

    ll ans = fac[a] * qp(fac[b], MOD - ) % MOD;

    ans = ans * qp((fac[a-b] + MOD) % MOD, MOD - ) % MOD;

    return ans;

}

int main() {

    fac[] = ;

    for (int i = ; i < N; i++) fac[i] = fac[i - ] * i % MOD;

    ll n = read(), m = read(), k = read();

    ll ans = C(n * m, k) * C(k, ) % MOD * qp(, MOD - ) % MOD;

    ans = ans * (n + m) % MOD;

    ans %= MOD;

    cout << ans << '\n';

    return ;

}

F - Absolute Minima

题意：有函数$f\left( x\right)$初始为0，两个操作，1是给$f\left( x\right)$加上$\left| x-a\right| +b$，2是询问函数的最小值及$x$

思路：可以证(举例)明(发现)，函数的最小值一定$a$序列的中位数取到。

两个优先队列，一个降序一个升序，每次加入$a$都加入两个队列里，在比较他们的顶，降序的顶必须小于等于升序的顶，这样就能实现两个堆分别存储了序列的左半部分和右半部分。

同时，降序的顶就是取到的$x$

#include <bits/stdc++.h>

using namespace std;

inline int read() {

    int x = , f = ; char ch = getchar();

    while (ch < '' || ch > '') { if (ch == '-') f = -; ch = getchar(); }

    while (ch >= '' && ch <= '') { x = x *  + ch - ; ch = getchar(); }

    return x * f;

}

int main() {

    int q = read();

    priority_queue<int> l;

    priority_queue<int, vector<int>, greater<int> > r;

    long long ans = ;

    while (q--) {

        int t = read();

        if (t == ) {

            int a = read(), b = read();

            ans += b;

            l.push(a);

            r.push(a);

            if (l.top() > r.top()) {

                int x = l.top(); l.pop();

                int y = r.top(); r.pop();

                ans += abs(x - y);

                l.push(y); r.push(x);

            }

        } else {

            printf("%d %lld\n", l.top(), ans);

        }

    }

    return ;

}

巴特西

AtCoder Beginner Contest 127 解题报告

最新文章

热门文章