比赛链接：https://atcoder.jp/contests/abc172/tasks

A - Calc

题意

给出一个正整数 $a$，计算 $a + a^2 + a^3$ 。($1 \le a \le 10$)

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    int a; cin >> a;

    cout << a + a * a + a * a * a;

}

B - Minor Change

题意

给出两个等长的字符串 $s$ 和 $t$，每次可以替换 $s$ 中的一个字符，问使 $s$ 和 $t$ 相等至少要替换多少字符。

题解

不同的字符是一定要替换的。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

    string s, t; cin >> s >> t;

    int cnt = 0;

    for (int i = 0; i < s.size(); i++)

        if (s[i] != t[i]) ++cnt;

    cout << cnt << "\n";

}

C - Tsundoku

题意

有两摞书，一摞有 $n$ 本，从上至下每本需阅读 $a_i$ 分钟，一摞有 $m$ 本，从上至下每本需阅读 $b_i$ 分钟，问最多能在 $k$ 分钟内读多少本书。

题解

计算两摞书阅读时长的前缀和，枚举从第一摞书中读多少本，余下的时间用二分或双指针查找能在第二摞书中读多少本。

代码一

二分

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

int main() {

    int n, m, k; cin >> n >> m >> k;

    ll pre_a[n + 1] = {};

    for (int i = 0; i < n; i++) {

        int x; cin >> x;

        pre_a[i + 1] = pre_a[i] + x;

    }

    ll pre_b[m + 1] = {};

    for (int i = 0; i < m; i++) {

        int x; cin >> x;

        pre_b[i + 1] = pre_b[i] + x;

    }

    int ans = 0;

    for (int i = 0; i < n + 1; i++) {

        ll ex = k - pre_a[i];

        if (ex >= 0) {

            int j = upper_bound(pre_b, pre_b + m + 1, ex) - pre_b - 1;

            ans = max(ans, i + j);

        }

    }

    cout << ans << "\n";

}

代码二

双指针

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

int main() {

    int n, m, k; cin >> n >> m >> k;

    ll pre_a[n + 1] = {};

    for (int i = 0; i < n; i++) {

        int x; cin >> x;

        pre_a[i + 1] = pre_a[i] + x;

    }

    ll pre_b[m + 1] = {};

    for (int i = 0; i < m; i++) {

        int x; cin >> x;

        pre_b[i + 1] = pre_b[i] + x;

    }

    int ans = 0;

    for (int i = 0, j = m; i < n + 1; i++) {

        ll ex = k - pre_a[i];

        if (ex >= 0) {

            while (j >= 0 and pre_b[j] > ex) --j;

            ans = max(ans, i + j);

        }

    }

    cout << ans << "\n";

}

D - Sum of Divisors

题意

设 $f_{(x)}$ 为 $x$ 正因子的个数。计算 $\sum_{i = 1}^n i \times f_{(i)}$ 。

题解

筛得每个数的 $f_{(x)}$，求和即可。

代码一

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

const int N = 1e7 + 10;

ll f[N];

int main() {

    int n; cin >> n;

    for (int i = 1; i <= n; i++)

        for (int j = i; j <= n; j += i)

            ++f[j];

    ll ans = 0;

    for (int i = 1; i <= n; i++)

        ans += i * f[i];

    cout << ans << "\n";

}

代码二

代码一简化而得

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

int main() {

    int n; cin >> n;

    ll ans = 0;

    for (int i = 1; i <= n; i++)

        for (int j = i; j <= n; j += i)

            ans += j;

    cout << ans << "\n";

}

E - NEQ

题意

给出 $n, m$，计算有多少对大小为 $n$ 的数列 $a, b$ 满足：

$1 \le a_i, b_i \le m$
$a_i \neq a_j\ \ \ if\ \ \ i \neq j$
$b_i \neq b_j\ \ \ if\ \ \ i \neq j$
$a_i \neq b_i$

题解

\begin{equation} A_m^n ( \sum_{i = 0}^n (-1)^{i} C_n^i A_{m - i}^{n - i}) \nonumber \end{equation}

$A_m^n$，$m$ 个数排 $n$ 个位置，即合法的 $a$ 的个数；
$\sum$，对于每个合法的 $a$ 来说，合法的 $b$ 的个数；
- $(-1)^i$，容斥原理；
- $C_n^i A_{m - i}^{n - i}$，从 $b$ 的 $n$ 个位置中选 $i$ 个位置与 $a$ 中的数相等，余下 $n - i$ 个位置共有 $m - i$ 个数可选；
- - 当 $i = 0$ 时，$C_n^i A_{m - i}^{n - i} = A_m^n$，即合法的 $b$ 的个数；
  - 当 $i \ge 1$ 时，$C_n^i A_{m - i}^{n - i}$ 即代表对 $a$ 来说不合法的 $b$ 的个数；
  - 所以右式即用容斥原理从合法的 $b$ 中减去对 $a$ 来说不合法的 $b$ 的个数。

代码

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

const int N = 5e5 + 10;

const int mod = 1e9 + 7;

ll fac[N];

ll binpow(ll a, ll b) {

    ll res = 1;

    while (b > 0) {

        if (b & 1) res = res * a % mod;

        a = a * a % mod;

        b >>= 1;

    }

    return res;

}

void init() {

    fac[0] = 1;

    for (int i = 1; i < N; i++)

        fac[i] = fac[i - 1] * i % mod;

}

ll inv(ll a) {

    return binpow(a, mod - 2);

}

ll A(ll n, ll m) {

    return fac[n] * inv(fac[n - m]) % mod;

}

ll C(ll n, ll m) {

    return fac[n] * inv(fac[m]) % mod * inv(fac[n - m]) % mod;

}

int main() {

    init();

    int n, m; cin >> n >> m;

    ll sum = 0;

    for (int i = 0; i <= n; i++) {

        sum += binpow(-1, i) * C(n, i) * A(m - i, n - i) % mod;

        sum = (sum + mod) % mod;

    }

    cout << A(m, n) * sum % mod << "\n";

}

巴特西

AtCoder Beginner Contest 172

A - Calc

题意

代码

B - Minor Change

题意

题解

代码

C - Tsundoku

题意

题解

代码一

代码二

D - Sum of Divisors

题意

题解

代码一

代码二

E - NEQ

题意

题解

代码

最新文章

热门文章