Codeforces Round #613 (Div. 2)lyh's blog

A . Mezo Playing Zoma

答案就是$n+1$，没什么说的。

#include <bits/stdc++.h>
using namespace std;
char op[100005];
int main()
{
    int n;
    scanf("%d%s", &n, op);
    printf("%d", n + 1);
    return 0;
}

B. Just Eat It!

前缀和二分一下就可以，特判全选的时候。

#include <bits/stdc++.h>
using namespace std;
int op[100005], n;
long long sum[100005], minn[100005];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", op + i);
        for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + op[i], minn[i] = min(minn[i - 1], sum[i]);
        long long s = -(1ll << 60), p = 0;
        for (int i = 1; i < n; i++) {
            s = max(s, sum[i] - minn[i - 1]);
        }
        for (int i = n; i > 1; i--) {
            p += op[i];
            s = max(s, p);
        }
        if (sum[n] > s)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

C. Fadi and LCM

很明显，我们要找$a$和$b$使得$ab=x$且$gcd(a,b)=1$，最小化$max(a,b)$。
这样的话，可以暴力去找。方法是对$x$跑一个$O(\sqrt n)$的质因分解，可以发现这些质因数的种类很少，最大大约有12左右，二进制暴力筛即可。

#include <bits/stdc++.h>
using namespace std;
vector<long long> vec;
long long minn = 1ll << 60, a, b, yuan;
void DFS(int at, long long v)
{
    if (at == vec.size()) {
        long long p = max(v, yuan / v);
        if (p < minn) {
            minn = p;
            a = v, b = yuan / v;
        }
        return;
    }
    DFS(at + 1, v * vec[at]);
    DFS(at + 1, v);
}
int main()
{
    long long x;
    scanf("%lld", &x);
    yuan = x;
    for (int i = 2; 1ll * i * i <= x; i++) {
        long long tmp = 1;
        while (x % i == 0) x /= i, tmp *= i;
        if (tmp != 1) vec.push_back(tmp);
    }
    if (x != 1) vec.push_back(x);
    DFS(0, 1);
    printf("%lld %lld", min(a, b), max(a, b));
    return 0;
}

D. Dr. Evil Underscores

可以建一个01 Trie树，在树上进行DFS去找答案。在未出现分叉时，可以保证答案这一位为0，否则只能为1。未分叉时只能走一个方向，否则需要两边都走，然后取最小的那一个答案。

#include <bits/stdc++.h>
using namespace std;
int ch[7000005][2], cnt = 1, n, op[100005];
inline void add(int x)
{
    int at = 1;
    for (int i = 30; i >= 0; i--) {
        if (ch[at][(x & (1 << i)) >> i] == 0) ch[at][(x & (1 << i)) >> i] = ++cnt;
        at = ch[at][(x & (1 << i)) >> i];
    }
}
int get(int x, int p = 30)
{
    if (ch[x][0] == 0 && ch[x][1] == 0) return 0;
    if (ch[x][0] && ch[x][1]) {
        return (1 << p) | min(get(ch[x][0], p - 1), get(ch[x][1], p - 1));
    }
    else if (ch[x][0])
        return get(ch[x][0], p - 1);
    else
        return get(ch[x][1], p - 1);
}
int main()
{
    int ans = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", op + i), add(op[i]);
    printf("%d", get(1));
    return 0;
}

E. Delete a Segment

        题意：给$n$个线段，去除其中一个，最小化剩余线段并集元素数量。
        上来想到的一个方法是将所有线段离散化后，将对应区间+1，删线段就是区间-1，用线段树维护非0线段段数。但是线段树虽然可以维护线段的段数，但是不支持修改，这个方法行不通。
        于是逆向思维。考虑删一个线段会引起那些“空洞”把原本连续的线段隔开。容易发现一个空洞会导致最后答案+1，而统计空洞的数量就是统计空洞的线段数，这可以用线段树维护，本题就解决了。
        注意有些空洞对答案不会产生贡献（甚至反贡献），需要对这种情况特判。

#include <bits/stdc++.h>
#define N 800005
using namespace std;
struct P
{
    int l, r, v;
} nd[N << 2];
int n, sv, op[N], x[N], y[N], ans, tot;
map<int, int> mmp;
void build(int l = 1, int r = sv, int k = 1)
{
    if (l == r) {
        nd[k].l = nd[k].r = nd[k].v = op[l] == 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, k << 1), build(mid + 1, r, k << 1 | 1);
    if (nd[k << 1].r && nd[k << 1 | 1].l) {
        nd[k].v = nd[k << 1].v + nd[k << 1 | 1].v - 1;
    }
    else {
        nd[k].v = nd[k << 1].v + nd[k << 1 | 1].v;
    }
    nd[k].l = nd[k << 1].l, nd[k].r = nd[k << 1 | 1].r;
}
P get(int l, int r, int L = 1, int R = sv, int k = 1)
{
    if (L >= l && R <= r) return nd[k];
    int mid = (L + R) >> 1;
    if (r <= mid)
        return get(l, r, L, mid, k << 1);
    else if (l > mid)
        return get(l, r, mid + 1, R, k << 1 | 1);
    P a = get(l, mid, L, mid, k << 1), b = get(mid + 1, r, mid + 1, R, k << 1 | 1), tmp;
    if (a.r && b.l)
        tmp.v = a.v + b.v - 1;
    else
        tmp.v = a.v + b.v;
    tmp.l = a.l, tmp.r = b.r;
    return tmp;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d%d", x + i, y + i);
        for (int i = 1, j = 1; i <= n; i++, j += 2) op[j] = x[i], op[j + 1] = y[i];
        sort(op + 1, op + 2 * n + 1), mmp.clear(), tot = 0;
        sv = unique(op + 1, op + 2 * n + 1) - op - 1;
        for (int i = 1; i <= sv; i++) {
            if (i == 1)
                mmp[op[1]] = 1;
            else
                mmp[op[i]] = mmp[op[i - 1]] + 2;
        }
        sv = mmp[op[sv]];
        for (int i = 1; i <= n; i++) x[i] = mmp[x[i]], y[i] = mmp[y[i]];
        for (int i = 1; i <= sv + 5; i++) op[i] = 0;
        for (int i = 1; i <= n; i++) ++op[x[i]], --op[y[i] + 1];
        for (int i = 1; i <= sv; i++) op[i] += op[i - 1];
        op[sv + 1] = 0, ans = 0;
        for (int i = 1; i <= sv + 1; i++) {
            if (op[i - 1] && !op[i]) ++tot;
        }
        build();
        for (int i = 1, np; i <= n; i++) {
            P s = get(x[i], y[i]);
            np = s.v;
            if (op[x[i]] == 1 && op[x[i] - 1] == 0) --np;
            if (op[y[i]] == 1 && op[y[i] + 1] == 0) --np;
            if (np == -1 && s.v == 1) {
                ans = max(ans, tot - 1);
            }
            else {
                np = max(np, 0);
                ans = max(ans, tot + np);
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

F. Classical?

        比较难的数论题。
        首先将所有数的因子集合找出来，计为$S$。
        对于$a\in S$以及$b \in S$，我们证明若$gcd(a,b)=1$，则$ab\leq ans$，这里$ans$就是本题的答案：
        假设$a|x_a$，$b|x_b$，那么$lcm(x_a,x_b)=\frac {x_ax_b}{d}$，这里$d=gcd(x_a,x_b)$。由于$gcd(a,b)=1$，因此可知$ad\leq x_a$并且$bd\leq x_b$，于是$ab\leq \frac {x_ax_b}{d}\leq ans$。
        并且，可以证明满足上面条件的$a$和$b$的乘积$ab$必然可以取到$ans$：
        假设$x_a$与$x_b$的$lcm(x_a,x_b)$最大，若$gcd(x_a,x_b)=d$，则$gcd(x_a,\frac {x_b}{d})=1$，并且$lcm(x_a,\frac {x_b}{d})=lcm(x_a,x_b)=ans$。而$x_a$与$\frac {x_b}{d}$显然在集合$S$中，因此等号一定可以取到。
        这样问题转化成从$S$中找两个互素的数，最大化乘积。
        考虑用栈辅助解决。将因子降序排列，从大到小枚举。当枚举到$x$时，考察当前栈中是否有数与$x$互素，若有，则弹栈，直到栈中没有与$x$互素的数，与此同时更新答案。然后$x$入栈。
        由于后来的数必然比$x$小，它们的乘积不会再比当前的打，因此可以弹栈，将其剔除。
        现在问题是如何判断栈中是否有与$x$互素的数。考虑维护一个$cnt$数组，$cnt[i]$记录当前栈中$i$的倍数的数目。那么这些数中与$x$互素的数的个数就是：

$\sum_{d|x}\mu(d)cnt_d$

$\mu(x)$为莫比乌斯函数，证明见后文。
在弹栈出栈的时候维护一步$cnt$数组，然后用莫比乌斯函数来判断互素，本题就可以解决。

#include <bits/stdc++.h>
#define N 100000
 
using namespace std;
vector<int> vec[N + 5];
int mu[N + 5], pr[N + 5], mk[N + 5], cnt[N + 5], n, tot, ss[N + 5];
long long ans = -(1ll << 60);
stack<int> sta;
inline int get(int to)
{
    int as = 0;
    for (int s : vec[to]) as += mu[s] * cnt[s];
    return as;
}
int main()
{
    mu[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (!mk[i]) pr[++tot] = i, mu[i] = -1;
        for (int j = 1; j <= tot; j++) {
            if (1ll * i * pr[j] > N) break;
            mk[i * pr[j]] = 1;
            if (i % pr[j] == 0) break;
            mu[i * pr[j]] = -mu[i];
        }
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j * j <= i; j++) {
            if (i % j == 0) {
                vec[i].push_back(j);
                if (j * j != i) vec[i].push_back(i / j);
            }
        }
    }
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), ss[x] = 1, ans = max(ans, 1ll * x);
    for (int i = 1; i <= N; i++) {
        for (int j = 2; i * j <= N; j++) ss[i] |= ss[i * j];
    }
    for (int i = N, tp = 0; i >= 1; i--) {
        if (!ss[i]) continue;
        tp = 0;
        while (get(i)) {
            tp = sta.top(), sta.pop();
            for (int j : vec[tp]) --cnt[j];
        }
        ans = max(ans, 1ll * tp * i), sta.push(i);
        for (int j : vec[i]) ++cnt[j];
    }
    printf("%lld", ans);
    return 0;
}

关于其中莫比乌斯函数部分的证明：
互素的数目就是：

$\sum_{i=1}^n[gcd(x,v_i)=1]$

根据莫比乌斯函数的性质：

$\sum_{i=1}^n\sum_{d|gcd(x,v_i)}\mu(d)$

枚举$d$：

$\sum_{d|x}\mu(d)\sum_{i=1}^n[d|v_i]$

就是：

$\sum_{d|x}\mu(d)cnt_d$

证毕。