Visits: 410

Codeforces Round #622 (Div. 2)

Fast Food Restaurant

贪心。

inline void solve() {
    int a, b, c;
    rd(a), rd(b), rd(c);
    int ans = 0;
    if (a) ++ans, --a;
    if (b) ++ans, --b;
    if (c) ++ans, --c;
    vi p;
    p.pb(a), p.pb(b), p.pb(c);
    sort(p.begin(), p.end());
    a = p[2], b = p[1], c = p[0];
    if (a && b) ++ans, --a, --b;
    if (a && c) ++ans, --a, --c;
    if (b && c) ++ans, --b, --c;
    if (a && b && c) ++ans;
    print(ans);
}

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

Different Rules

屑贪心结论题。

inline void solve() {
    ll n, x, y;
    rd(n), rd(x), rd(y);
    print(min(n, max(1ll, x + y - n + 1)), ' '), print(min(n, x + y - 1));
}

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

Skyscrapers

st 表求区间最小值，每次从区间最小值的位置左右分治，取更优的决策向上传递。

const int N = 5e5 + 7;
int n, a[N], b[N], f[N][21], ans[N];

inline int ask(int l, int r) {
    int k = log2(r - l + 1);
    return a[f[l][k]] < a[f[r-(1<<k)+1][k]] ? f[l][k] : f[r-(1<<k)+1][k];
}

inline ll solve(int l, int r) {
    if (l > r) return 0;
    if (l == r) return a[l];
    int o = ask(l, r);
    ll L = 1ll * (o - l + 1) * a[o] + solve(o + 1, r);
    ll R = 1ll * (r - o + 1) * a[o] + solve(l, o - 1);
    b[o] = L < R;
    return max(L, R);
}

inline void work(int l, int r) {
    if (l > r) return;
    if (l == r) return ans[l] = a[l], void();
    int o = ask(l, r);
    if (b[o]) {
        for (int i = o; i <= r; i++) ans[i] = a[o];
        work(l, o - 1);
    } else {
        for (int i = l; i <= o; i++) ans[i] = a[o];
        work(o + 1, r);
    }
}

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(a[i]), f[i][0] = i;
    int w = log2(n);
    for (int j = 1; j <= w; j++)
        for (int i = 1; i+(1<<(j-1)) <= n; i++)
            f[i][j] = a[f[i][j-1]] < a[f[i+(1<<(j-1))][j-1]] ? f[i][j-1] : f[i+(1<<(j-1))][j-1];
    solve(1, n);
    work(1, n);
    for (int i = 1; i <= n; i++) print(ans[i], " \n"[i==n]);
    return 0;
}

Happy New Year

垃圾离散化 + 状压 dp。

Concatenation with intersection

exkmp 求出 $a$ 的每个后缀和 $s$ 的 LCP，以及 $b$ 的每个后缀和 $s^r$ 的 LCP。

统计每个 $a_i$ 开头的方案数，two pointers 在 $b$ 上扫到对应的区间，树状数组维护即可。

设 $n,m$ 同阶，总时间复杂度 $\mathcal O(n \log n)$，$\log$ 在树状数组上而不在求 LCP 上，常数较小。

const int N = 1e6 + 7;
int n, m, p[N], q[N], d[N], z[N];
ll c[N], ans;
char a[N], b[N], s[N];

inline void Z(char *s, int n) {
    for (int i = 1; i <= n; i++) z[i] = 0;
    z[1] = n;
    for (int i = 2, l = 0, r = 0; i <= n; i++) {
        if (i <= r) z[i] = min(z[i-l+1], r - i + 1);
        while (i + z[i] <= n && s[i+z[i]] == s[z[i]+1]) ++z[i];
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
}

inline void exkmp(char *s, int n, char *t, int m, int *p) {
    Z(t, m);
    for (int i = 1; i <= n; i++) p[i] = 0;
    for (int i = 1, l = 0, r = 0; i <= n; i++) {
        if (i <= r) p[i] = min(z[i-l+1], r - i + 1);
        while (i + p[i] <= n && s[i+p[i]] == t[p[i]+1]) ++p[i];
        if (i + p[i] - 1 > r) l = i, r = i + p[i] - 1;
    }
}

inline void add(int x, int k) {
    if (!x) return;
    while (x <= m) c[x] += k, d[x] += k > 0 ? 1 : -1, x += x & -x;
}

inline pair<ll, int> ask(int x) {
    ll k = 0;
    int p = 0;
    while (x) k += c[x], p += d[x], x -= x & -x;
    return mp(k, p);
}

int main() {
    rd(n), rd(m);
    rds(a, n), rds(b, n), rds(s, m);
    exkmp(a, n, s, m, p);
    reverse(b + 1, b + n + 1);
    reverse(s + 1, s + m + 1);
    exkmp(b, n, s, m, q);
    reverse(q + 1, q + n + 1);
    for (int i = 1, j = 0; i <= n; i++) {
        while (j + 1 <= n && j + 1 < i + m - 1) {
            if (q[++j] == m) --q[j];
            add(q[j], q[j]);
        }
        if (p[i] == m) --p[i];
        pair<ll, int> x = ask(m), y = ask(m - p[i] - 1);
        ans += x.fi - y.fi - 1ll * (x.se - y.se) * (m - p[i] - 1);
        add(q[i], -q[i]);
    }
    print(ans);
    return 0;
}