Visits: 282

Educational Codeforces Round 80 (Rated for Div. 2)

Deadline

在 $\sqrt d$ 附近枚举。

inline void solve() {
    int n, d;
    rd(n), rd(d);
    int x = sqrt(d);
    for (int i = max(0, x - 10); i <= x + 10; i++) {
        if (i + d / (i + 1) + (d % (i + 1) != 0) <= n)
            return prints("YES"), void();
    }
    prints("NO");
}

int main() {
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}

Yet Another Meme Problem

枚举 $b$ 的位数。

inline void solve() {
    ll a, b;
    rd(a), rd(b);
    ll ans = 0;
    for (ll k = 10; k <= b + 1; k *= 10) ans += a;
    print(ans);
}

int main() {
    int T;
    rd(T);
    while (T--) solve();
    return 0;
}

Two Arrays

可以 dp 也可以推公式发现答案就是 $\binom{n+2m-1}{2m}$。

const int N = 1e3 + 7, M = 13;
int n, m;
modint f[M][N], ans;

int main() {
    rd(n), rd(m);
    f[0][1] = 1;
    for (int i = 0; i < m; i++)
        for (int j = 1; j <= n; j++)
            for (int k = j; k <= n; k++)
                f[i+1][k] += f[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            ans += f[m][i] * f[m][n-j+1];
    print(ans);
    return 0;
}

Minimax Problem

贪心 + 状压，复杂度 $\mathcal O(n2^m)$。

const int N = 3e5 + 7, M = 9;
int n, m, a[N][M], s[N], b[1<<M|1], S;
pq <pair <int, pi> > q;

int main() {
    rd(n), rd(m), S = (1 << m) - 1;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < m; j++)
            rd(a[i][j]), q.push(mp(a[i][j], mp(i, j)));
    while (q.size()) {
        int x = q.top().se.fi, y = q.top().se.se;
        q.pop();
        if (b[S^(s[x]|(1<<y))]) {
            print(x, ' '), print(b[S^(s[x]|(1<<y))]);
            return 0;
        }
        b[1<<y] = x;
        for (int k = s[x]; k; k = (k - 1) & s[x]) b[k|(1<<y)] = x;
        s[x] |= 1 << y;
        if (s[x] == S) {
            print(x, ' '), print(x);
            return 0;
        }
    }
    return 0;
}

Messenger Simulator

树状数组维护即可。

const int N = 3e5 + 7;
int n, m, p[N], c1[N], c2[N], v[N], ans[N];

inline void add(int *c, int n, int x, int o) {
    while (x <= n) c[x] += o, x += x & -x;
}

inline int ask(int *c, int x) {
    int o = 0;
    while (x) o += c[x], x -= x & -x;
    return o;
}

int main() {
    rd(n), rd(m);
    for (int i = 1, x; i <= m; i++) {
        rd(x);
        if (!v[x]) {
            v[x] = 1;
            ans[x] = x + ask(c1, n) - ask(c1, x);
            add(c1, n, x, 1);
            add(c2, m, p[x] = i, 1);
            continue;
        }
        ans[x] = max(ans[x], 1 + ask(c2, i - 1) - ask(c2, p[x]));
        add(c2, m, p[x], -1);
        add(c2, m, p[x] = i, 1);
    }
    for (int x = 1; x <= n; x++)
        if (!v[x]) ans[x] = x + ask(c1, n) - ask(c1, x);
        else ans[x] = max(ans[x], 1 + ask(c2, m) - ask(c2, p[x]));
    for (int x = 1; x <= n; x++)
        print(v[x] ? 1 : x, ' '), print(ans[x]);
    return 0;
}

Red-Blue Graph

题目太神仙了，先咕咕咕着。