Visits: 243

Codeforces Round #602 (Div. 2, based on Technocup 2020 Elimination Round 3)

Math Problem

贪心。

inline void solve() {
    int l = 1e9 + 1, r = 0, n;
    rd(n);
    for (int i = 1; i <= n; i++) {
        int x, y;
        rd(x), rd(y);
        r = max(r, x);
        l = min(l, y);
    }
    print(max(r - l, 0));
}

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

Box

贪心。

const int N = 1e5 + 7;
int n, a[N], b[N];

inline void solve() {
    rd(n);
    set< int > s;
    for (int i = 1; i <= n; i++) {
        rd(a[i]), s.insert(i);
    }
    for (int i = 1; i <= n; i++) {
        si it = s.upper_bound(a[i]);
        if (it != s.begin()) b[i] = *--it, s.erase(it);
        else return print(-1), void();
    }
    for (int i = 1; i <= n; i++) print(b[i], " \n"[i==n]);
}

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

Messy

构造。

const int N = 1e5 + 7;
int n, k;
char s[N], c[2] = {')', '('};
vector< pi > ans;

inline void solve() {
    ans.clear();
    rd(n), rd(k), rds(s, n);
    for (int i = 1; i <= n; i++)
        if (s[i] != c[i&1]) {
            int t = i;
            for (int j = i + 1; j <= n; j++)
                if (s[j] == c[i&1]) {
                    t = j;
                    break;
                }
            ans.pb(mp(i, t));
            reverse(s + i, s + t + 1);
        }
    if (2 * k != n) ans.pb(mp(2 * k, n - 1));
    print(ans.size());
    for (ui i = 0; i < ans.size(); i++)
        print(ans[i].fi, ' '), print(ans[i].se);
}

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

Optimal Subsequences

二分 + 树状数组，$\mathcal O(n \log^2 n)$。

const int N = 2e5 + 7;
int n, m, a[N], c[N], ans[N];
pq< pi > q;
pair< pi, int > p[N];

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

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

inline int qry(int x) {
    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (ask(mid) < x) l = mid + 1;
        else r = mid;
    }
    return a[l];
}

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) {
        rd(a[i]);
        q.push(mp(a[i], -i));
    }
    rd(m);
    for (int i = 1, x, y; i <= m; i++) {
        rd(x), rd(y), p[i] = mp(mp(x, y), i);
    }
    sort(p + 1, p + m + 1);
    int t = 0;
    for (int i = 1; i <= m; i++) {
        while (t < p[i].fi.fi) {
            int x = -q.top().se;
            q.pop();
            add(x);
            ++t;
        }
        ans[p[i].se] = qry(p[i].fi.se);
    }
    for (int i = 1; i <= m; i++) print(ans[i]);
    return 0;
}

Arson In Berland Forest

（假的）贪心。

const int N = 1e6 + 7;
int n, m, p[N];
string s[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> s[i], s[i].pb('.');
    for (int i = 0; i < m; i++) s[n].pb('.');
    int ans = 1e9;
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= m; j++) {
            p[j] = s[i][j] == 'X' ? j ? p[j-1] + 1 : 1 : 0;
            if (s[i][j] == '.' && j && s[i][j-1] == 'X') ans = min(ans, p[j-1]);
        }
    for (int i = 0; i < m; i++)
        for (int j = 0; j <= n; j++) {
            p[j] = s[j][i] == 'X' ? j ? p[j-1] + 1 : 1 : 0;
            if (s[j][i] == '.' && j && s[j-1][i] == 'X') ans = min(ans, p[j-1]);
        }
    ans = (ans - 1) / 2;
    cout << ans << endl;
    for (int i = 0; i < n; i++)
        for (int j = 0; j <= m; j++) {
            p[j] = s[i][j] == 'X' ? j ? p[j-1] + 1 : 1 : 0;
            if (p[j] <= ans) s[i][j] = '.';
        }
    for (int i = 0; i < n; i++)
        for (int j = m; j >= 0; j--) {
            p[j] = s[i][j] == 'X' ? j < m ? p[j+1] + 1 : 1 : 0;
            if (p[j] <= ans) s[i][j] = '.';
        }
    for (int i = 0; i < m; i++)
        for (int j = 0; j <= n; j++) {
            p[j] = s[j][i] == 'X' ? j ? p[j-1] + 1 : 1 : 0;
            if (p[j] <= ans) s[j][i] = '.';
        }
    for (int i = 0; i < m; i++)
        for (int j = n; j >= 0; j--) {
            p[j] = s[j][i] == 'X' ? j < n ? p[j+1] + 1 : 1 : 0;
            if (p[j] <= ans) s[j][i] = '.';
        }
    for (int i = 0; i < n; i++) s[i].pop_back(), cout << s[i] << endl;
    return 0;
}

Wrong Answer on test 233

首先如果相邻两个正确选项一样，那么这个位置选什么都不会产生影响，因此直接将答案 $\times k$。

如果不一样，那么对于每一个位置的生成函数为 $F(x) = x^{-1} + (k – 2) + x$。

设相邻两个正确选项不一样的位置有 $c$ 个，那么答案就是 $F^c(x)$ 的正项系数和 $\times k^{n-c}$。

枚举 $(k-2)$ 项的次数，设剩下的次数为 $i$，此时正项系数和为 $\binom{c}{i}\sum_{2j > i} \binom{i}{j} = \binom{c}{i} \times \frac{2^i – [2|i]\binom{i}{\frac{i}{2}}}2$。

忽略模运算后时间复杂度为 $\mathcal O(n)$。

const int N = 2e5 + 7;
int n, k, a[N], c;
modint p[N], ans;

int main() {
    rd(n), rd(k);
    for (int i = 1; i <= n; i++) rd(a[i]);
    c = a[1] != a[n];
    for (int i = 1; i < n; i++) c += a[i] != a[i+1];
    p[0] = 1;
    for (int i = 1; i <= c; i++) p[i] = p[i-1] * i;
    for (int i = 0; i <= c; i++) ans += (p[c] / p[i] / p[c-i]) * (((modint)2 ^ i) - ((i & 1) ? 0 : p[i] / p[i>>1] / p[i>>1])) * ((modint)(k - 2) ^ (c - i)) / 2;
    ans *= (modint)k ^ (n - c);
    print(ans);
    return 0;
}