Codeforces Round 942 (Div. 2)

这次终于不是vp了

A

双指针，每次找到最大的不行就跳过，答案加一，因为最大的转换成最小的总能满足要求

另外题目里好像没说一开始有序，还特判了一下，结果std里默认有序了

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    bool ok = true;
    for (int i = 0; i < n; i++) {
        std::cin >> b[i];
        ok &= a[i] <= b[i];
    }

    if (ok) {
        std::cout << "0\n";
        return;
    }

    int ans = 1;
    std::sort(a.begin(), a.end());
    for (int i = n - 2, j = n - 1; i >= 0; i--, j--) {
        while (i >= 0 && a[i] > b[j]) {
            ans++;
            i--;
        }
    }

    std::cout << ans << "\n";

}

B

和2024牛客寒假的诈骗题很像，都是操作一次不改变可操作数奇偶性

另外，这里范围for改成 std::count会更直观一些

void solve() {
    int n;
    std::string s;
    std::cin >> n >> s;

    int cnt = 0;
    for (auto ch : s) {
        cnt += ch == 'U';
    }

    std::cout << (cnt & 1 ? "YES\n" : "NO\n");
}

C

发现当排列形成后，后面加的数只有和它往前$n-1$个数一样，才能保证答案增加，且这是最优解

而这样操作所形成的是多个相同排列的序列，于是我们尽可能地先形成多个排列

对每个card的数量进行排序，若要使排列数量增加，必须至少将所有最小的card数量增加$1$，如果分开来维护每个最小的card数量会很难操作

考虑两个状态：

  • 状态$1$：考虑将每一个最小card数量增加到次小card数量，如果可以满足，就增加并继续状态$1$,否则状态$2$
  • 状态$2$：此时必定存在一个最小card数量只能增加到$\lt$次小card数量的数量，但还有可能增加排列数量，于是我们先把排列数量能增加的增加了，且必定存在一种组合方式可以容纳剩下的不满足一个排列的card数量（对应剩下的card的任意排列顺序），且剩下的card因为不满足全排列，每个只能贡献$1$

可以说状态$1$的作用就是通过最小card数量一定递增的特点，优化时间复杂度

void solve() {
    int n;
    ll k;
    std::cin >> n >> k;

    std::vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    std::sort(a.begin(), a.end());

    int id = 0;
    for (int i = 1; i < n; i++) {
        auto c = (a[i] - a[i - 1]) * i;
        if (k < c) {
            break;
        }
        k -= c;
        id = i;
    }

    std::cout << (a[id] + k / (id + 1)) * n - id + k % (id + 1) << "\n";
}

D1

设$\gcd(a,b)=d,a=Ad,b=Bd,\gcd(A,B)=1$，满足：

$$
(A+B)*d=CBd^2\space \text{(C is const)}\
C=\frac{A+B}{Bd}\
\because \gcd(A,B)=1,\therefore B=1,b=d=\gcd(a,b)\
C=\frac{A+1}d
$$

故枚举$d$的范围$[1,m]$，此时$A$取值$[1,\frac n d]$，$A+1$取值$[2,\frac n d+1]$

每个$d$的贡献是$\lfloor\frac n d+1\rfloor$，$d=1$时会多算$A+1=1$的贡献，最后减掉即可

void solve() {
    int n, m;
    std::cin >> n >> m;

    ll ans = 0;
    for (int i = 1; i <= m; i++) {
        ans += (n / i + 1) / i;
    }

    std::cout << ans - 1 << "\n";
}

D2

设$\gcd(a,b)=d,a=Ad,b=Bd,\gcd(A,B)=1$，满足：

$$
C(A+B)*d=Bd^2\space \text{(C is const)}\
d=C\frac{A+B}B\
\because \gcd(A,B)=1,\therefore B|C\
d=C(A+B)
$$

因为$\gcd(A,B)=1$，考虑枚举$A,B$

$$
a=Ad\le n\
d\le \frac n A\
\because d=C(A+B),d>A\
\therefore A^2<n
$$

这里有了$A$的限制，$B$的限制同理，然而其实还有：

$$
A+B\le d \le \min(\frac n A, \frac n B)
$$

更强的限制

统计答案：条件为$\gcd(A,B)=1$，$d$的范围为$[1,\min(\frac n A,\frac n B)]$且$A+B|d$，

故贡献为$\min(\frac n A, \frac n B) \over A+B$

void solve() {
    int n, m;
    std::cin >> n >> m;

    ll ans = 0;
    for (int a = 1; a * a < n; a++) {
        for (int b = 1; (a + b) * a <= n && (a + b) * b <= m; b++) {
            if (std::gcd(a, b) == 1) {
                ans += std::min(n / a, m / b) / (a + b);
            }
        }
    }
    std::cout << ans << "\n";
}

E

考察fenwick tree的思想，$[x-lowbit(i)+1,x]$是$x$管辖的区间，而每次更新$x$时，需要更新$x+lowbit(x)$对应的点（$x+lowbit(x)$管辖了$x$），这里每次求sum也是，可以根据上升次数和$k$得到更新$x+lowbit(x)$的系数

一开始想用矩阵快速幂做，内存不够，但是可以用来辅助观察，相当于$x+lowbit(x)$包含的位每次做前缀和，一开始全都是$1$，推断上升$d$次，做$k$次sum后系数是$\binom{d+k-1}{d}$

从最小的$1$开始更新大的值，这样能保证每一个值在使用前都得到了

复杂度$O(nlogn)$

void solve() {
    int n, k;
    std::cin >> n >> k;

    std::vector<Z> a(n);
    for (auto &i : a) {
        std::cin >> i;
    }

    std::vector<Z> f(n + 1);
    f[0] = 1;
    for (int i = 1; i <= n; i++) {
        f[i] = f[i - 1] * (k + i - 1) * Z(i).inv();
    }

    for (int i = 1; i <= n; i++) {
        for (int j = i + (i & -i), c = 1; j <= n; j += (j & -j), c++) {
            a[j - 1] -= f[c] * a[i - 1];
        }
    }

    for (int i = 0; i < n; i++) {
        std::cout << a[i] << " \n"[i == n - 1];
    }

}

剩下待补

电波交流