Visits: 258

Codeforces Round #613 (Div. 2)

Mezo Playing Zoma

贪心。

int main() {
    int n;
    string s;
    cin >> n >> s;
    int l = 0, r = 0;
    for (int i = 0; i < n; i++)
        if (s[i] == 'L') ++l;
        else ++r;
    print(r + l + 1);
    return 0;
}

Just Eat It!

前后缀和，贪心。

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

inline void solve() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(a[i]), b[i] = a[i] + b[i-1];
    c[n+1] = 0;
    for (int i = n; i; i--) c[i] = c[i+1] + a[i];
    bool ok = 1;
    for (int i = 1; i <= n; i++)
        if (b[i] <= 0 || c[i] <= 0) ok = 0;
    prints(ok ? "YES" : "NO");
}

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

Fadi and LCM

显然两个数要互质。

由于 $X \le 10^{12}$ 因此最多只有 $11$ 个质因数，状压即可。

显然还有更简单的方法。

vector <ll> p;

int main() {
    ll x, X;
    rd(x), X = x;
    for (ll i = 2; i * i <= x; i++)
        if (x % i == 0) {
            ll o = 1;
            while (x % i == 0) o *= i, x /= i;
            p.pb(o);
        }
    if (x != 1) p.pb(x);
    sort(p.begin(), p.end());
    int c = p.size();
    ll ans = 1e18;
    for (int i = 0; i < (1 << c); i++) {
        ll o = 1;
        for (int j = 0; j < c; j++)
            if ((i >> j) & 1) o *= p[j];
        ans = min(ans, max(o, X / o));
    }
    print(ans, ' '), print(X / ans);
    return 0;
}

Dr. Evil Underscores

01 trie 上贪心一下即可。

const int N = 1e5 + 7, M = 29;
int n, a[N], trie[N<<5|1][2], t = 1;

inline void ins(int x) {
    int p = 1;
    for (int i = M; ~i; i--) {
        int c = (x >> i) & 1;
        if (!trie[p][c]) trie[p][c] = ++t;
        p = trie[p][c];
    }
}

int dfs(int x, int d) {
    if (!trie[x][0] && !trie[x][1]) return 0;
    if (!trie[x][0]) return dfs(trie[x][1], d - 1);
    if (!trie[x][1]) return dfs(trie[x][0], d - 1);
    return 1 << d | min(dfs(trie[x][0], d - 1), dfs(trie[x][1], d - 1));
}

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(a[i]), ins(a[i]);
    print(dfs(1, M));
    return 0;
}

Delete a Segment

离散化 + 差分 + two pointers。

垃圾特判题。

const int N = 2e5 + 7;
int n, l[N], r[N], c[N<<2], p[N<<2], d[N<<2], t, s;

inline void solve() {
    rd(n), t = 0;
    for (int i = 1; i <= n; i++)
        rd(l[i]), rd(r[i]), l[i] *= 2, r[i] *= 2,
        p[++t] = l[i] - 1, p[++t] = l[i],
        p[++t] = r[i], p[++t] = r[i] + 1;
    sort(p + 1, p + t + 1);
    t = unique(p + 1, p + t + 1) - (p + 1);
    for (int i = 1; i <= t + 1; i++) c[i] = d[i] = 0;
    for (int i = 1; i <= n; i++)
        l[i] = lower_bound(p + 1, p + t + 1, l[i]) - p,
        r[i] = lower_bound(p + 1, p + t + 1, r[i]) - p,
        ++c[l[i]], --c[r[i]+1];
    for (int i = 1; i <= t; i++) c[i] += c[i-1];
    s = 0;
    for (int i = 1; i <= t; i++) s += c[i] && !c[i-1];
    set< pi > st;
    for (int i = 1, j = 1; i <= t; i = ++j) {
        if (c[i] != 1) continue;
        while (c[j+1] == 1) ++j;
        if (!c[i-1] && !c[j+1]) {
            st.insert(mp(i, j));
            continue;
        }
        if (!c[i-1] || !c[j+1]) continue;
        d[i] = 1;
    }
    for (int i = 1; i <= t; i++) d[i] += d[i-1];
    int ans = -1;
    for (int i = 1; i <= n; i++)
        ans = max(ans, d[r[i]] - d[l[i]-1] - (st.find(mp(l[i], r[i])) != st.end()));
    print(ans + s);
}

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

Classical?

设 $m = \max_{i=1}^n a_i$。

首先，将每个 $a_i$ 中的数的所有因数都加入集合，那么最终的答案一定是这个集合中的两个互质的数的乘积，因此在之后的讨论中我们要求用于更新答案的数互质。

从大到小考虑集合中的数，每考虑一个数，都将它和之前考虑过的数中互质的一一相乘更新答案。

注意到若此时考虑的数为 $x$，若存在之前考虑过的数 $y$ 满足 $\gcd(x,y) = 1$，则所有满足 $z \in (x,y)$ 的 $z$ 都不会更优。

因此我们可以用栈维护考虑过的数，每当考虑一个数 $x$ 的时候，判断此时栈中有没有与 $x$ 互质的数，如果有则弹栈同时更新答案，直到没有。

现在的问题就是如何快速判断栈中有没有与 $x$ 互质的数。

考虑容斥，记 $c_i$ 为栈中 $i$ 的倍数的个数，则与 $x$ 互质的数的个数为 $\sum_{d|x} \mu(d) c_d$。

这个过程的总时间复杂度为 $\mathcal O(\sum_{i=1}^m d(i)) = \mathcal O(m \log m)$。

另外，在本题中，求 $\mu(1\dots m)$ 的过程不需要做到线性，因为同时我们还需要预处理出 $1 \sim m$ 的所有因数，因此在求 $\mu$ 的时候可以利用公式 $\mu(i) = -\sum_{d|i,d<i} \mu(d)(i > 1)$。

const int N = 1e5 + 7;
int n, m, a[N], u[N], c[N];
vi p[N], s;

int main() {
    rd(n);
    for (int i = 1, x; i <= n; i++) rd(x), a[x] = 1, m = max(m, x);
    ll ans = m;
    u[1] = 1;
    for (int i = 1; i <= m; i++) {
        p[i].pb(i);
        for (int j = 2 * i; j <= m; j += i)
            p[j].pb(i), a[i] |= a[j], u[j] -= u[i];
    }
    for (int i = m; i; i--)
        if (a[i]) {
            int o = 0;
            for (int j : p[i]) o += u[j] * c[j];
            while (o) {
                for (int j : p[s.back()]) {
                    --c[j];
                    if (i % j == 0) o -= u[j];
                }
                ans = max(ans, 1ll * i * s.back());
                s.pop_back();
            }
            for (int j : p[i]) ++c[j];
            s.pb(i);
        }
    print(ans);
    return 0;
}