Educational Codeforces Round 85 (Rated for Div. 2)

AutumnKite

题解Codeforces

发布于：2020年4月13日

次浏览

罚时被 E 搞没了。

A - Level Statistics

题目传送门

题解

初始状态为 \(p_0=0,c_0=0\)。

由于每进行一次游戏，\(p\) 一定会加 \(1\)，而 \(c\) 可能加 \(1\) 也有可能不变，所以 \(p\) 增加的值一定大于等于 \(c\) 增加的值，并且他们增加的值必须非负。

所以只要判断是否所有 \(i\) 都满足 \(p_{i-1} \le p_i,c_{i-1} \le c_i,p_i-p_{i-1}\ge c_{i}-c_{i-1}\) 即可。

代码

int n;

void solve() {
    read(n);
    int x = 0, y = 0;
    bool flag = true;
    for (int i = 1; i <= n; ++i) {
        int nx, ny;
        read(nx), read(ny);
        if (nx < x || ny < y) {
            flag = false;
        }
        if (nx - x < ny - y) {
            flag = false;
        }
        x = nx, y = ny;
    }
    if (flag) {
        printStr("YES");
    } else {
        printStr("NO");
    }
}

B - Middle Class

题目传送门

题解

假设我们已经知道了答案 \(s\)，考虑如何判断是否合法。

我们需要让 \(s\) 个人的钱数 \(\ge x\)，那么我们的最优策略一定是选择最大的 \(s\) 个人，然后对这 \(s\) 个人进行一次操作，如果得到的平均值 \(\ge x\) 则符合条件，否则一定不可以。

那么我们只要将所有数从大到小排序以后，枚举答案 \(s\) 进行判断即可。

代码

const int N = 100005;

int n, x, a[N];

void solve() {
    read(n), read(x);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
    }
    std::sort(a + 1, a + 1 + n);
    std::reverse(a + 1, a + 1 + n);
    long long sum = 0;
    for (int i = 1; i <= n; ++i) {
        sum += a[i];
        if (sum < 1ll * x * i) {
            print(i - 1);
            return;
        }
    }
    print(n);
}

C - Circle of Monsters

题目传送门

题解

为方便描述，下文中 \(i+1\) 表示环上 \(i\) 的下一个怪物，\(i-1\) 表示环上 \(i\) 的上一个怪物。

首先我们将 \(b_i\) 与 \(a_{i+1}\) 取 \(\min\)，这显然不会影响答案。

对于一个怪物 \(i\)，打败他至少需要的操作次数为 \(a_i-b_{i-1}\)，即打 \(a_i-b_{i-1}\) 枪，剩下的血量用上一个怪物炸。

那么总的操作次数的下界即为 \(\sum\limits_{i=1}^{n} a_i-b_{i-1}\)。

但是这是一个环形，我们不可能做到每个怪物都被上一个怪物炸，必须有一个怪物是手动打死的。

而在之前的操作次数下界的基础上，手动打死怪物 \(i\) 需要花费额外的 \(b_i\) 次操作，所以我们只要选择 \(b_i\) 最小的那个怪物手动打死即可。

总花费即为 \(\min\limits_{1\le i\le n} b_i+\sum\limits_{i=1}^{n} a_i-b_{i-1}\)。

代码

const int N = 300005;
const long long INF = 0x3f3f3f3f3f3f3f3fll;

int n;
long long a[N], b[N];

void solve() {
    read(n);
    long long sum = 0, mn = INF;
    for (int i = 1; i <= n; ++i) {
        read(a[i]), read(b[i]);
        sum += a[i];
    }
    for (int i = 1; i <= n; ++i) {
        b[i] = std::min(b[i], a[i % n + 1]);
        mn = std::min(mn, b[i]);
        sum -= b[i];
    }
    print(sum + mn);
}

D - Minimum Euler Cycle

题目传送门

题解

看到完全图，欧拉回路，以及字典序最小，一个很自然的想法是从 \(1\) 开始，每次走能走的最小的那个点。

模拟发现，这样走一定能恰好走出一条欧拉回路，顶点序列如下： \[1,2,1,3,\cdots,1,n,2,3,2,4,\cdots,2,n,3,4,\cdots,n,n-1,n,1\]

我们可以将这个序列分成若干组，可以更直观的看出规律： \[ \begin{aligned} & 1,2,1,3,\cdots,1,n \\ & 2,3,2,4,\cdots,2,n \\ & 3,4,3,5,\cdots,3,n \\ & \vdots \\ & n-2,n-1,n-2,n \\ & n-1,n \\ & 1 \end{aligned} \]

于是我们求出 \(l,r\) 在第几组中的第几个，直接模拟即可。

注意需要特判最后的 \(1\)。

代码

const int N = 100005;

int n;
long long l, r;

std::pair<int, int> get(long long l) {
    int p = 1;
    while (p < n && l > 2 * (n - p)) {
        l -= 2 * (n - p);
        ++p;
    }
    return {p, l};
}

void solve() {
    read(n), read(l), read(r);
    bool flag = 0;
    if (r == 1ll * n * (n - 1) + 1) {
        if (l == r) {
            print(1);
            return;
        }
        flag = 1, --r;
    }
    std::pair<int, int> L = get(l), R = get(r);
    for (int k = L.first; k <= R.first; ++k) {
        int lb = k == L.first ? L.second : 1;
        int rb = k == R.first ? R.second : 2 * (n - k);
        for (int i = lb; i <= rb; ++i) {
            if (i & 1) {
                print(k, ' ');
            } else {
                print(k + i / 2, ' ');
            }
        }
    }
    if (flag) {
        print(1);
    } else {
        putchar('\n');
    }
}

E - Divisor Paths

题目传送门

题解

打 CF 只知道猜结论，一个 WA22 以为结论错了，没想到是没开 long long。当场去世。

~~好的我们开始猜结论。~~

首先，对于两个点 \(x,y\ (x \ge y)\)，若 \(y|x\)，那么 \(x\) 到 \(y\) 的最短路长度一定是 \(d(x)-d(y)\)（\(d(x)\) 表示 \(x\) 的因子数量）。所以，从 \(x\) 开始不断除掉某个质因子直到等于 \(y\) 的一条路径一定是一条最短路。

如果中途增大了会导致因子数量变多，所以反过来也是成立的。

上面的结论可以更加严谨的证明，这里不做详细证明。

那么最短路条数等于将 \(\frac{x}{y}\) 分解质因数后的可重元素排列数量。可以直接预处理阶乘和阶乘逆元求出。

拓展到一般情况，\(x\) 到 \(y\) 的最短路一定经过点 \(\gcd(x,y)\)。大概理解一下，一定不会经过比 \(\gcd(x,y)\) 更小的公因子，这样显然不优；也一定不会往 \(\operatorname{lcm}(x,y)\) 的方向走，由于 \(\frac{a}{b}=\frac{b}{c}\) 时，\(d(a)-d(b) > d(b)-d(c)\)，所以往 \(\operatorname{lcm}(x,y)\) 方向走也是不优的。

那么只要分别求出 \(x\to \gcd(x,y)\) 和 \(y\to \gcd(x,y)\) 的最短路数量，相乘即可。

代码

const int P = 998244353;

long long n;
int q;
int fac[105], inv[105];
std::vector<std::pair<long long, int>> p;

long long gcd(long long a, long long b) {
    return b ? gcd(b, a % b) : a;
}

int qpow(int a, int b) {
    int s = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            s = 1ll * s * a % P;
        }
        a = 1ll * a * a % P;
    }
    return s;
}

void init(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fac[i] = 1ll * fac[i - 1] * i % P;
    }
    inv[n] = qpow(fac[n], P - 2);
    for (int i = n; i; --i) {
        inv[i - 1] = 1ll * inv[i] * i % P;
    }
}

int get(long long x) {
    int res = 1, sum = 0;
    for (auto v : p) {
        int k = 0;
        while (x % v.first == 0) {
            x /= v.first;
            ++k;
        }
        res = 1ll * res * inv[k] % P;
        sum += k;
    }
    return 1ll * res * fac[sum] % P;
}

void solve() {
    read(n);
    init(100);
    long long x = n;
    for (int i = 2; 1ll * i * i <= x; ++i) {
        if (x % i == 0) {
            p.push_back({i, 0});
            while (x % i == 0) {
                x /= i;
                ++p.back().second;
            }
        }
    }
    if (x > 1) {
        p.push_back({x, 1});
    }
    read(q);
    while (q--) {
        long long x, y;
        read(x), read(y);
        long long g = gcd(x, y);
        print(1ll * get(x / g) * get(y / g) % P);
    }
}

F - Strange Function

题目传送门

题解

首先考虑将删去最小的转化成保留最大的。

这种选一个子序列满足什么条件的问题，我们首先考虑一个经典的 DP。

设 \(f_{i,j}\) 表示 \(a\) 的前 \(i\) 个数中选出一个子序列（强制 \(i\) 选），进行题目中的操作后得到的序列与 \(b_{1\ldots j}\) 相等时的最大权值。

由于我们强制 \(i\) 选，所以合法的 \(j\) 是唯一的，我们大可不必记录 \(j\) 这一维状态。

考虑满足 \(a_i=b_j\) 的唯一的 \(j\)，令 \(a_0=b_0=0\)，那么有转移 \[f_i=\max_{0\le k < i,a_k=b_{j-1}}\{f_k+\sum_{t=k+1}^{i-1}[a_t\le a_k][p_t > 0]p_t\}+p_i\]

对于当前的 \(i\)，设 \[g_k=f_k+\sum_{t=k+1}^{i-1}[a_t\le a_k][p_t > 0]p_t\]

考虑将 \(i\) 加 \(1\) 后 \(g_k\) 的变化。对于满足 \(0\le k < i\) 的所有 \(k\)，如果 \(p_i\le 0\) 那么 \(g_k\) 显然不会改变，否则所有满足 \(a_k\ge a_i\) 的 \(g_k\) 会加上 \(p_i\)；对于 \(k=i\) 的 \(g_k\)，有 \(g_k=f_i\)。

考虑一个以 \(a_k\) 为下标的数组，位置 \(v\) 的值即为 \[\max_{0\le k < i,a_k=v}\{g_k\}\]

根据上述分析，我们需要在这个数组上支持后缀加、单点取 \(\max\)、单点查询操作即可。单点取 \(\max\) 操作可以拆分为一个单点查询和两个后缀加操作。

后缀加、单点查询可以用树状数组简单地维护。

时间复杂度 \(O(n\log n)\)。

代码

const int N = 500005;
const long long INF = 0x3f3f3f3f3f3f3f3fll;

int n, a[N], m, b[N];
long long w[N], sum, f[N];

struct BIT{
    long long c[N];
    
    void add(int x, long long v) { // 后缀加
        for (; x <= n; x += x & -x) {
            c[x] += v;
        }
    }

    long long query(int x) { // 单点查询
        long long s = 0;
        for (; x; x ^= x & -x) {
            s += c[x];
        }
        return s;
    }
} T;

int main() {
    read(n);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
    }
    for (int i = 1; i <= n; ++i) {
        read(w[i]);
        sum += w[i];
    }
    read(m);
    for (int i = 1; i <= m; ++i) {
        read(b[i]);
    }
    T.add(1, -INF);
    for (int i = 1; i <= n; ++i) {
        int j = std::lower_bound(b + 1, b + 1 + m, a[i]) - b;
        if (j <= m && a[i] == b[j]) {
            if (j == 1) {
                f[i] = w[i];
            } else {
                f[i] = T.query(b[j - 1]) + w[i];
            }
        } else {
            f[i] = -INF;
        }
        if (w[i] > 0) {
            T.add(a[i], w[i]);
        }
        long long tmp = T.query(a[i]);
        if (f[i] > tmp) {
            T.add(a[i], f[i] - tmp);
            T.add(a[i] + 1, tmp - f[i]);
        }
    }
    long long ans = T.query(b[m]);
    if (ans > -1e15) {
        printStr("YES");
        print(sum - ans); // 用总和减去最大保留的权值
    } else {
        printStr("NO");
    }
}

G - Substring Search

题目传送门

也许会补的吧...

更新于：2020年4月13日

贪心

构造

数论

树状数组

AtCoder Grand Contest 047 题解

比赛地址 A - Integer Product 题意给定 \(n\) 个小数点后最多 \(9\) 位的实数 \(A_1,A_2,A_3,\ldots,A_n\)，求有多少对 \((...

Codeforces Round #632 (Div. 2) 裂开记

打得非常裂开，被 D 续了半年。 A - Little Artem 题目传送门题解首先我们考虑将所有格子填上黑色，此时 \(B=W=0\)。我们尝试将一个格子变成白色，可以发...