ZZJC新生训练赛第六场题解

Proaes / 2024-11-07 / 原文

先给出比赛链接：
https://ac.nowcoder.com/acm/contest/93676#question

下面说一下难度分层：(同一难度下按字典序排序)
Easy(简单): B H

Medium(中等): D E

Hard(困难): A G

Anti-AK(防AK): C F

A 扣分扣分扣分！扣分！

二维前缀差分板子题

题目要求对二维区间加某个数或者查询二维区间的和

与一维前缀和类似地，我们定义 $ sa[i][j] $ 为区间(1 < x < i, 1 < y < j) 的和

生成二维前缀和：
遍历原二维数组，$ sa[i][j] = a[i][j] + sa[i - 1][j] + sa[i][j - 1] - sa[i - 1][j - 1] $

区间查询：
要得到任意区间的和可以O1求出，
比如(x1, y1) 到 (x2, y2) 区间的和就是
$ sa[x2][y2] - sa[x2][y1 - 1] - sa[x1 - 1][y2] + sa[x1 - 1][y1 - 1] $

区间加：
定义差分数组da，对da求前缀和即可得到a数组，即a是da的前缀和
那么对da的某一位加上v，就能使得这一位后面的a数组全部加上v
类似的，想要实现在a的某个区间加v，只需要在区间的初始位置+v，结束位置的后一个位置-v
就能实现对a数组的区间加
二维前缀和即是
$ da[x1][y1] += v  da[x1][y2 + 1] -= v  da[x2 + 1][y1] -= v  da[x2 + 1][y2 + 1] += v $

Show Code A


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cout.tie(nullptr)->sync_with_stdio(false);
    auto prefix = [&](vector< vector< ll >> &a, int lena, int lenai) {
        vector< vector< ll >> sa(lena + 1 , vector< ll >(lenai + 1));
        for (int i = 1; i <= lena; ++ i) {
            for (int j = 1; j <= lenai; ++ j) {
                sa[i][j] = a[i][j] + sa[i - 1][j] + sa[i][j - 1] - sa[i - 1][j - 1];
            }
        }
        return sa;
    };
    auto get = [&](vector< vector< ll >> &sa, int xb, int yb, int xe, int ye) {
        ll res = sa[xe][ye] - sa[xe][yb - 1] - sa[xb - 1][ye] + sa[xb - 1][yb - 1];
        return res;
    };
    auto dif = [&](vector< vector< ll >> &a, int lena, int lenai) {
        vector< vector< ll >> da(lena + 1 , vector< ll >(lenai + 1));
        for (int i = 1; i <= lena; ++ i) {
            for (int j = 1; j <= lenai; ++ j) {
                da[i][j] = a[i][j] - a[i - 1][j] - a[i][j - 1] + a[i - 1][j - 1];
            }
        }
        return da;
    };
    auto add = [&](vector< vector< ll >> &da, int si, int sj, int ti, int tj, ll x) {
        int n = da.size(), m = da[si].size();
        da[si][sj] += x;
        if (tj + 1 < m) da[si][tj + 1] -= x;
        if (ti + 1 < n) da[ti + 1][sj] -= x;
        if (ti + 1 < n && tj + 1 < m)da[ti + 1][tj + 1] += x;
    };
    int n, m, q1, q2;
    cin >> n >> m >> q1 >> q2;
    vector< vector< ll >> da(n + 2, vector< ll >(m + 2));
    while (q1--) {
        int a1, b1, a2, b2;
        ll v;
        cin >> a1 >> b1 >> a2 >> b2 >> v;
        add(da, a1, b1, a2, b2, v);
    }
    vector< vector< ll >> a = prefix(da, n, m);
    vector< vector< ll >> sa = prefix(a, n, m);
    while (q2--) {
        int a1, b1, a2, b2;
        cin >> a1 >> b1 >> a2 >> b2;
        cout << get(sa, a1, b1, a2, b2) << "\n";
    }
}

B 明日方舟设计师！

按题意模拟即可，注意本题卡了pow,故不能直接用pow计算

Show Code B


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int tt = 1;
    cin >> tt;
    while (tt--) {
        ll a = 1, b = 1, n, ans = 0, c = 1;
        ll aq, bq;
        cin >> aq >> bq >> n;
        for (int i = 1; i <= n; ++ i) {
            b *= bq;
        }
        for (ll k = 0; k <= n; ++ k) {
            ans += c * a * b;
            a *= aq;
            b /= bq;
            c = c * (n - k) / (k + 1);
        }
        cout << ans << "\n";
    }
}

C 夕瓜的幻想

我们将小自在造成的伤害和夕造成的伤害分开计算

根据小自在个数的递推公式，我们可以发现小自在的个数满足组合数，即小自在个数等于 $ C_{n}^{k} $

下面给出证明，根据递推公式我们可以发现 $ C_{k} = \frac{n! / (n - k)!}{k!} = \frac{n!}{(n - k)!k!} = C_{n}^{k} $

那么答案就能表示成

$ \sum\limits_{k = 0}^{n} C_{n}^{k} a^{k} b^{n - k} = (a + b)^n ~~~~~ (二项式定理) $

然后再计算夕的伤害，显然夕的伤害是一个等比数列求和，公比 $ q = \frac{a}{b} $

$ \sum\limits_{k = 0}^{n} a^{k} b^{n - k} $

$ = b^{n} \frac{1 - \frac{a}{b}^{n + 1}}{1 - \frac{a}{b}} $

$ = \frac{b^{n} - a^{n}\frac{a}{b}}{1 - \frac{a}{b}} ~~~ (将b^{n}与分子相乘) $

$ = \frac{b^{n + 1} - a^{n + 1}}{b - a} ~~~ (上下同乘(b)) $

$ = (b^{n + 1} - a^{n + 1})(b - a) ~~~ (上下同乘(b-a)) $

故答案即为 $ (a + b)^n + (b^{n + 1} - a^{n + 1})(b - a) $

Show Code C


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    auto power = [&](ll a , ll b) {
        ll res = 1;
        while (b) {
            if (b & 1) {
                res = res * a % mod;
            }
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    };
    int tt = 1;
    cin >> tt;
    while (tt--) {
        ll x, y, n;
        cin >> x >> y >> n;
        ll ans = power(x + y, n);
        ans += (power(y, n + 1) - power(x, n + 1) + mod) % mod * (y - x + mod) % mod;
        cout << ans << "\n";
    }
}

D 毛民9527

每有一种关系就能把材料的种类减一，所以直接输出 n - m 即可

Show Code D


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m;
    cout << n - m << "\n";
}

E 最简真分数

先 $ O(n^{2}log(n)) $ 求出最简真分数的个数。然后注意到它们的和就是个数除以二

可以注意到，当(x,y)为互质时，(y-x,y)也互质。那么有这些最简真分数的和就是它们的个数除以2。

Show Code E


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    ll ans1 = 0;
    ll n = 2e6; 
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        for (int j = i + 1; j <= n; ++ j) {
            if (gcd(i, j) == 1) {
                ans1++;
            }
        }
    }
    double ans2 = (double)ans1 / 2.0;
    cout << ans1 << " " << fixed << setprecision(9) << ans2 << "\n"; //保留9位
}

F 模意义下的最简真分数

显然有:

$ ans = \sum\limits_{a = 1}^{n} \sum\limits_{b = 1}^{a} ([b < a] * [gcd(a , b) == 1]) = (\sum\limits_{a = 1}^{n} \sum\limits_{b = 1}^{n} [gcd(a , b) == 1]) / 2 $

那么只需求出n以内的互质对即可。即以1为最大公约数的数对

由容斥原理可以得知，先找到所有以1为公约数的数对，再从中剔除所有以1的倍数为公约数的数对，余下的数对就是以1为最大公约数的数对。即f(k)=以1为公约数的数对个数 - 以1的倍数为 公约数 的数对个数。

可以注意到，当(x,y)为互质时，(y-x,y)也互质。那么有这些最简真分数的和就是它们的个数除以2。

Show Code F


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    auto power = [&](ll a , ll b) {
        ll res = 1;
        while (b) {
            if (b & 1) {
                res = res * a % mod;
            }
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    };
    ll ans1 = 0, ans2 = 0; 
    ll nn = 2e6; 
    cin >> nn;
    vector< ll > f(nn + 1);
    // f[i] 表示 gcd == i 的情况有几种
    // 容斥
    for (ll k = nn; k >= 1; k--) { 
        f[k] = (nn / k) * (nn / k);
        for (ll i = k + k; i <= nn; i += k) {
            f[k] -= f[i];
        }
    }
    ans1 = f[1] / 2 % mod;
    ans2 = ans1 * power(2, mod - 2) % mod;
    std::cout << ans1 << " " << ans2 << "\n";
}

G 大猿口算

根据克莱默法则

$ x_{i} = \frac{D_{i}}{D} $

当D为0时，则说明无唯一解

当D不为0时，计算出 $ x_{i} $ 的值再判断符号并且约分并输出即可

Show Code G


int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    auto sgn = [&](ll n) {
        return n < 0 ? 1 : 0;
    };
    int tt = 1;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        vector< vector< ll>> a(n + 1, vector< ll >(n + 2));
        vector< vector< vector< ll >>> d(n + 1, vector< vector< ll >>(n + 1, vector< ll >(n + 1)));
        vector< ll > D(n + 1);
        auto com = [&](vector< vector< ll >> det) {
            if (n == 1) {
                return det[1][1];
            } else if (n == 2) {
                return det[1][1] * det[2][2] - det[1][2] * det[2][1];
            } else {
                ll res = 0;
                res += det[1][1] * det[2][2] * det[3][3];
                res += det[1][2] * det[2][3] * det[3][1];
                res += det[1][3] * det[2][1] * det[3][2];
                res -= det[1][3] * det[2][2] * det[3][1];
                res -= det[1][1] * det[2][3] * det[3][2];
                res -= det[1][2] * det[2][1] * det[3][3];
                return res;
            }
        };
        for (int i = 1; i <= n; ++ i) {
            for (int j = 1; j <= n + 1; ++ j) {
                cin >> a[i][j];
            }
        }
        for (int k = 0; k <= n; ++ k) {
            for (int i = 1; i <= n; ++ i) {
                for (int j = 1; j <= n; ++ j) {
                    d[k][i][j] = a[i][j];
                }
                d[k][i][k] = a[i][n + 1];
            }
        }
        for (int k = 0; k <= n; ++ k) D[k] = com(d[k]);
        if (D[0] == 0) {
            cout << "No\n";
        } else {
            cout << "Yes\n";
            for (int k = 1; k <= n; ++ k) {
                ll g = gcd(D[0], D[k]);
                if (D[k] != 0 && sgn(D[k]) ^ sgn(D[0])) cout << '-';
                cout << abs(D[k] / g) << "/" << abs(D[0] / g) << " \n"[k == n];
            }
        }
    }
}

H 这是签到

保留11位输出 $ \pi $ 即可
可以用反三角函数 acos(-1) 得到 $ \pi $ 的值

Show Code H


const double pi = acos(-1);
int main() {
    std::cout << std::fixed << std::setprecision(11) << pi << "\n";
}