一场CF比赛。

Before the Beginning

转载请将本段放在文章开头显眼处，如有二次创作请标明。
原文链接：https://www.codein.icu/cf1406/

前言

补题。

C

一棵树最多两个重心。
一个重心直接不管，两个重心则将某个叶节点接到另一个重心上。
容易发现，两个重心一定相邻。
将一个重心不在另一个重心子树内的叶子接到另一重心上即可。

#include <algorithm>
#include <cstdio>
const int maxn = 1e5 + 100;
struct node
{
    int to, next;
} E[maxn << 1];
int head[maxn], tot;
inline void add(const int& x, const int& y) { E[++tot].next = head[x], E[tot].to = y, head[x] = tot; }
int T, n;
int size[maxn], maxp[maxn], root1, root2;
void dfs(int u, int fa)
{
    maxp[u] = 0, size[u] = 1;
    for (int p = head[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if (v == fa) continue;
        dfs(v, u), size[u] += size[v];
        maxp[u] = std::max(maxp[u], size[v]);
    }
    maxp[u] = std::max(n - size[u], maxp[u]);
    if (maxp[u] < maxp[root1]) root1 = u, root2 = 0;
    else if (maxp[u] == maxp[root1]) root2 = u;
}
int isleaf[maxn], fat[maxn];
void dfs2(int u, int fa)
{
    fat[u] = fa, isleaf[u] = 1;
    for (int p = head[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if (v == fa) continue;
        dfs2(v, u), isleaf[u] = 0;
    }
}
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d",&n);
        tot = 0;
        for (int i = 1; i <= n; ++i) isleaf[i] = 0, fat[i] = 0, head[i] = 0;
        int tx, ty;
        for (int i = 1, x, y; i < n; ++i) scanf("%d %d", &x, &y), add(x, y), add(y, x), tx = x, ty = y;
        root1 = 0, root2 = 0;
        maxp[0] = 1 << 30;
        dfs(1, 0);
        if (!root2)
        {
            printf("%d %d\n", tx, ty);
            printf("%d %d\n", tx, ty);
            goto end;
        }
        dfs2(root1, root2);
        for (int i = 1; i <= n; ++i)
            if (isleaf[i])
            {
                printf("%d %d\n", fat[i], i);
                printf("%d %d\n", i, root2);
                goto end;
            }
    end:;
    }
    return 0;
}

B

正负数分开讨论，枚举取几个负数。
如果答案是正数，显然正负数都从大到小取。
如果答案是负数，那么正负数都从小到大取。

#include <cstdio>
#include <algorithm>
const int maxn = 1e5 + 100;
int T, n, a[maxn], b[maxn], acnt, bcnt;
long long aprod[10], bprod[10];
long long reaprod[10], rebprod[10];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        acnt = bcnt = 0;
        long long res = -(1ll << 62);
        for (int i = 1, x; i <= n; ++i)
        {
            scanf("%d", &x);
            if (x >= 0) a[++acnt] = x;
            else b[++bcnt] = -x;
        }
        std::sort(a + 1, a + 1 + acnt), std::sort(b + 1, b + 1 + bcnt);
        aprod[0] = bprod[0] = reaprod[0] = rebprod[0] = 1;
        for (int i = 1; i <= 5 && i <= acnt; ++i) aprod[i] = aprod[i - 1] * a[i];
        for (int i = 1; i <= 5 && i <= bcnt; ++i) bprod[i] = bprod[i - 1] * b[i];
        for (int i = 1; i <= 5 && i <= acnt; ++i) reaprod[i] = reaprod[i - 1] * a[acnt - i + 1];
        for (int i = 1; i <= 5 && i <= bcnt; ++i) rebprod[i] = rebprod[i - 1] * b[bcnt - i + 1];
        for (int i = 0; i <= 5; ++i)
        {
            if (i > acnt || 5 - i > bcnt) continue;
            if (i & 1) res = std::max(res, reaprod[i] * rebprod[5 - i]);
            else res = std::max(res, -aprod[i] * bprod[5 - i]);
        }
        printf("%lld\n", res);
    }
}

A

可以发现，一个数出现次数是一次的话，一定分给能接上它的那个序列。
若出现两次或以上，则两个序列都能接上它。
可以贪心地考虑，分别最大化即可。

#include <cstdio>
const int maxn = 110;
int T,n,cnt[maxn];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for (int i = 0; i <= 100; ++i) cnt[i] = 0;
        for (int i = 1,x; i <= n; ++i) scanf("%d",&x),cnt[x]++;
        int mexa = 0,mexb = 0;
        while(mexa <= 100 && cnt[mexa])  cnt[mexa++]--;
        while(mexb <= 100 && cnt[mexb])  cnt[mexb++]--;
        printf("%d\n",mexa + mexb);
    }
    return 0;
}

D

考虑化简下不等式。
$b_i + c_i = a_i$
$b_i \geq b_{i-1}$
$\implies a_i – c_i \geq a_{i-1} – c_{i-1}$
$\implies a_i – a_{i-1} \geq c_i – c_{i-1}$
且要求 $c_i \leq c_{i-1}$，即 $c_i – c_{i-1} \leq 0$.
综上：
$c_i – c_{i-1} \leq \min(0,a_i – a_{i-1})$

要求 $\max(b_i,c_i)$ 最小，即要求 $\max(a_i – c_i,c_i)$ 最小。
可以发现， $\max(c_i) = c_1$，只需要考虑 $\max(a_i – c_i)$ 即可。
让 $c_1$ 最小，$a_i – c_i$ 最小，且 $c$ 单调递减。
$c_i$ 越大，$a_i – c_i$ 越小，因此每次尽可能地少减少。
然而若 $c_1$ 减小，则 $a_i – c_i$ 一定会增大，二者取最大值，要如何使这个最大值最小呢？

假定初始令 $c_1 = 0$，而 $a_i – c_i$ 都为当前状态下的最小值。
那么改变 $c_1$ 后，原值改变为 $a_i – (c_i + c_1)$，即 $a_i – c_i – c_1$.

取最大的 $a_i – c_i$，在改变后一定依然是最大的，讨论第一个 $a_i – c_i – c_1 \leq c_1$ 与 $a_i – c_i – c_1 \geq c_1$ 的情况，答案就在这两种中择优取得。
$ans = \min(c_1,a_i – c_i – c_1)$

$\lfloor \dfrac{a_i – c_i}{2} \rfloor \leq c_1 \leq \lceil \dfrac{a_i – c_i}{2} \rceil$

枚举对应的 $c_1$，计算最优答案即可。

我们已经解决了静态的问题，现在考虑修改如何处理。
改变一段的 $a_i$，对应的 $c_i$ 的不等式条件也会发生变化，而 $a_i$ 也会变化，因此需要全面地考虑 $a_i – c_i$ 的变化。

首先考虑不等式条件的变化。
对于更改的区间 $[l,r]$，区间中的不等式条件没有变化，因为 $a_i – a_{i-1}$ 不变，只有两端点处改变了。
对于位置 $l$，原先是 $\min(a_l – a_{l-1},0)$，现在是 $\min(x + a_l – a_{l-1},0)$，那么计算出 $c_l$ 改变量 $\min(x + a_l – a_{l-1},0) – \min(a_l – a_{l-1},0)$，对 $[l,n]$ 区间中的 $a_i – c_i$ 做更改。

对于位置 $r + 1$，原先是 $\min(a_{r+1} – a_r,0)$，现在是 $\min(a_{r+1} – a_r – x,0)$，计算出 $c_{r+1}$ 改变量 $\min(a_{r+1} – a_r – x,0) – \min(a_{r+1} – a_r,0)$，对 $[r + 1,n]$ 区间中的 $a_i – c_i$ 做更改。

而 $a_i$ 的变化就相当简单了。

可以利用一个差分树状数组维护 $a_i$，用线段树维护 $a_i – c_i$，每次询问枚举 $c_1$ 得到答案。

然而这个做法过于繁琐，其实 $a_i – c_i$ 就是 $b_i$，而 $b_i$ 单增，因此……
懒得改了，凑合看吧。代码没问题。

#include <algorithm>
#include <cstdio>
using namespace std;
#define int long long
const int maxn = 1e5 + 100;
int n, q;
namespace Bit
{
int a[maxn];
inline int lowbit(const int& x) { return x & -x; }
inline void add(int x, int k) { for (; x <= n; x += lowbit(x)) a[x] += k; }
inline int ask(int x)
{
    int res = 0;
    for (; x > 0; x -= lowbit(x)) res += a[x];
    return res;
}
}  // namespace Bit
int origina[maxn], originc[maxn];
namespace Seg
{
#define ls p << 1
#define rs p << 1 | 1
int maxx[maxn << 2], tag[maxn << 2];
inline void pushup(const int& p) { maxx[p] = max(maxx[ls], maxx[rs]); }
inline void pushdown(const int& p)
{
    if (!tag[p]) return;
    maxx[ls] += tag[p], maxx[rs] += tag[p];
    tag[ls] += tag[p], tag[rs] += tag[p];
    tag[p] = 0;
}
void build(int l, int r, int p)
{
    maxx[p] = -(1 << 30);
    if (l == r) return (void)(maxx[p] = origina[l] - originc[l]);
    int mid = l + r >> 1;
    build(l, mid, ls), build(mid + 1, r, rs);
    pushup(p);
}
void add(int l, int r, int p, int ll, int rr, int k)
{
    if (ll > rr) return;
    if (l >= ll && r <= rr) return (void)(maxx[p] += k, tag[p] += k);
    pushdown(p);
    int mid = l + r >> 1;
    if (ll <= mid) add(l, mid, ls, ll, rr, k);
    if (rr > mid) add(mid + 1, r, rs, ll, rr, k);
    pushup(p);
}
}  // namespace Seg
inline void output()
{
    int bottom = Seg::maxx[1] / 2, top = (Seg::maxx[1] + 1) / 2;
    int res = 1ll << 60;
    for (int c1 = bottom; c1 <= top; ++c1) res = std::min(res, max(c1, Seg::maxx[1] - c1));
    printf("%lld\n", res);
}
signed main()
{
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i) scanf("%lld", origina + i), Bit::add(i, origina[i]), Bit::add(i + 1, -origina[i]);
    for (int i = 2; i <= n; ++i) originc[i] = originc[i - 1] + min(0ll, origina[i] - origina[i - 1]);
    Seg::build(1, n, 1);
    output();
    scanf("%lld", &q);
    while (q--)
    {
        int l, r, x;
        scanf("%lld %lld %lld", &l, &r, &x);
        Seg::add(1, n, 1, l, r, x);
        if (l != 1)
        {
            int al1 = Bit::ask(l - 1), al2 = Bit::ask(l);
            Seg::add(1, n, 1, l, n, min(al2 - al1, 0ll) - min(x + al2 - al1, 0ll));
        }
        if (r != n)
        {
            int ar1 = Bit::ask(r), ar2 = Bit::ask(r + 1);
            Seg::add(1, n, 1, r + 1, n, min(ar2 - ar1, 0ll) - min(ar2 - ar1 - x, 0ll));
        }
        Bit::add(l, x), Bit::add(r + 1, -x);
        output();
    }
}

E

显然先筛出质数再考虑。
每个质数都删除一遍，模拟删除找出当 $x$ 不包含该质数因子时的答案，若与返回值不同，则 $x$ 一定包含该质数。
然而是先回答再删除，第一个询问的被包含的质数是无法找出的。
因此可以分块处理，每处理完一块的质数后，询问全局剩余多少个数，来判断第一个质数是否在该块内。如果是，暴力遍历该块。
最后确定了质数，只需要确定指数即可。

#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
const int maxn = 1e5 + 100;
int n;
int primes[maxn], notprime[maxn], cnt;
void getprime()
{
    notprime[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (!notprime[i]) primes[++cnt] = i;
        for (int j = 1; j <= cnt && primes[j] * i <= n; ++j)
        {
            notprime[i * primes[j]] = 1;
            if ((i % primes[j]) == 0) break;
        }
    }
}
inline int A(const int& x)
{
    cout << "A " << x << endl;
    int res;
    cin >> res;
    return res;
}
inline int B(const int& x)
{
    cout << "B " << x << endl;
    int res;
    cin >> res;
    return res;
}
inline void C(const int& x)
{
    cout << "C " << x << endl;
}
int vis[maxn];
int has[maxn], tot;
int main()
{
    cin >> n;
    if (n == 1)
    {
        C(1);
        return 0;
    }
    getprime();
    int len = sqrt(cnt), num = (cnt + len - 1) / len;
    if (len * len < cnt) ++len;
    int totalnum = n, flag = 0;
    for (int i = 1; i <= num; ++i)
    {
        int L = len * (i - 1) + 1;
        int R = std::min(cnt, len * i);
        for (int j = L; j <= R; ++j)
        {
            int res = B(primes[j]);
            int exp = 0;
            for (int k = primes[j]; k <= n; k += primes[j]) exp += !vis[k], totalnum -= !vis[k], vis[k] = 1;
            if (res != exp) has[++tot] = primes[j];
        }
        if (flag) continue;
        int res = A(1);
        if (res != totalnum)
        {
            flag = 1;
            totalnum = res;
            for (int j = L; j <= R; ++j)
            {
                int t = A(primes[j]);
                int exp2 = 0;
                for (int k = primes[j]; k <= n; k += primes[j]) exp2 += !vis[k];
                if (exp2 != t) has[++tot] = primes[j];
            }
        }
    }
    std::sort(has + 1, has + 1 + tot), tot = std::unique(has + 1, has + 1 + tot) - has - 1;
    int ans = 1;
    for (int i = 1; i <= tot; ++i)
    {
        long long t = 1ll * has[i] * has[i];
        while (t <= n && A(t)) t = t * has[i];
        ans = ans * (t / has[i]);
    }
    C(ans);
    return 0;
}