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

A - Lucky 7

#include <bits/stdc++.h>

using namespace std;

int main() {

    int n; cin >> n;

    cout << (to_string(n).find("7") != -1 ? "Yes" : "No");

}

B - FizzBuzz Sum

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

int main() {

    ll n; cin >> n;

    ll ans = 0;

    for (ll i = 1; i <= n; i++) {

        if (i%3 && i%5) ans += i;

    }

    cout << ans;

}

C - Sum of gcd of Tuples (Easy)

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

int main() {

    ll k; cin >> k;

    ll ans = 0;

    for (ll a = 1; a <=k ; a++) {

        for (ll b = 1; b <= k; b++) {

            for (ll c = 1; c <=k; c++) {

                ans += __gcd(__gcd(a,b),c);

            }

        }

    }

    cout << ans;

}

D - RGB Triplets

题意

一字符串由 $RBG$ 组成，找出三元组 $(i, j, k)$ 满足：

$i<j<k$
$s[i]!=s[j]\ \&\&\ s[i]!=s[k]\ \&\&\ s[j]!=s[k]$
$j-i\ !=\ k-j$

思路一

存储 $3$ 个字母的位置，枚举 $9$ 种前后情况，二分查找满足 $j>i,k>j$ 的下标。

代码一

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

int n; string s;

vector<int> v[3];

inline int idx(int b, int a, int i) { //在 v[b] 中寻找第一个不小于 v[a][i] 的下标

    return upper_bound(v[b].begin(), v[b].end(), v[a][i]) - v[b].begin();

}

ll cal(int a, int b, int c) {

    ll ret = 0;

    for (int i = 0; i < v[a].size(); i++) {

        for (int j = idx(b, a, i); j < v[b].size(); j++) {

            for (int k = idx(c, b, j); k < v[c].size(); k++) {

                if (v[b][j] - v[a][i] != v[c][k] - v[b][j]) { //等价于条件中的 j - i != k - j

                    ++ret;

                }

            }

        }

    }

    return ret;

}

int main() {

    cin >> n >> s;

    for (int i = 0; i < n; i++) { //存储不同字母的位置

        if (s[i] == 'R') v[0].push_back(i);

        else if (s[i] == 'G') v[1].push_back(i);

        else v[2].push_back(i);

    }

    ll ans = 0;

    for (int i = 0; i < 3; i++) { //枚举RGB的前后情况

        for (int j = 0; j < 3; j++) {

            for (int k = 0; k < 3; k++) {

                if (i != j && i !=k && j != k) {

                    ans += cal(i, j, k);

                }

            }

        }

    }

    cout << ans;

}

思路二

求出总的情况数减去不满足条件的情况。

代码二

#include <bits/stdc++.h>

#define c1 s[i]

#define c2 s[i + d]

#define c3 s[i + d + d]

using ll = long long;

using namespace std;

int main() {

    int n; cin >> n;

    string s; cin >> s;

    int a[3] = {};

    for (char c : s) {

        if (c == 'R') ++a[0];

        else if (c == 'G') ++a[1];

        else ++a[2];

    }

    ll ans = 1LL * a[0] * a[1] * a[2];

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

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

            if (c1 != c2 and c1 != c3 and c2 != c3)

                --ans;

        }

    }

    cout << ans;

}

E - Sum of gcd of Tuples (Hard)

题意

有 $n$ 个大小为 $1{\sim}k$ 的数，找出所有情况中的 $gcd(a_1,a_2,...,a_n)$ 之和。

思路

设 $gcd_i$ 为 $gcd(a_1,a_2,...,a_n)=i$ 的排列个数，答案即 $\sum_{i=1}^{k}i{\times}gcd_i$。

$k$ 中 $i$ 的倍数有 $\lfloor \frac{k}{i} \rfloor$ 个，所以 $gcd=i$ 的情况共有 ${\lfloor \frac{k}{i} \rfloor}^n$ 种，但这其中有重复的情况，比如当计算 $gcd=2$ 时，同时也会得到 $gcd=4、6、8$ 等等的排列，所以我们需要从 $\frac{k}{2}$ 起反向遍历减去重复的情况。

代码

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

const ll mod = 1e9 + 7;

ll fpow(ll a, ll b) { ll ret = 1; while (b) { if (b & 1) ret = ret * a %mod; a = a * a % mod; b >>= 1; } return ret; }

int main() {

    ll n, k; cin >> n >> k;

    ll gcd[k+1] = {};

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

        gcd[i] = fpow(k / i, n);

    for (int i = k / 2; i >= 1; i--)

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

            gcd[i] -= gcd[j];

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

        gcd[i] = i * gcd[i] % mod;

    cout << accumulate(gcd + 1, gcd + 1 + k, 0LL) % mod;

}

F - Select Half

题意

有 $n$ 个数，求取 $\lfloor\frac{n}{2}\rfloor$ 个两两不相邻的数的最大和。

思路

设 $dp[i]$ 为长为 $i$ 时取 $\lfloor\frac{i}{2}\rfloor$ 个数的最大和。

当 $i$ 为奇数时，如果取 $a_i$，$dp_i=dp_{i-2}+a_i$，否则 $dp_i=dp_{i-1}$。

当 $i$ 为偶数时，如果取 $a_i$，$dp_i=dp_{i-2}+a_i$，否则 $dp_i=pre\_sum_{i-1}$。

比如当 $i=4$ 时，如果不取 $a_4$，要想在之前的 $a_1\ a_2\ a_3$ 中取够 $2$ 个数，只能取 $a_1\ a_3$，即从 $a_1$ 起间隔为 $2$ 取数作奇数位的前缀和。

代码

#include <bits/stdc++.h>

using ll = long long;

using namespace std;

int main() {

    int n; cin >> n;

    int a[n + 1]; for (int i = 1; i <= n; i++) cin >> a[i];

    ll pre_sum[n + 1] = {};

    pre_sum[1] = a[1];

    for (int i = 3; i <= n; i += 2)

        pre_sum[i] = pre_sum[i - 2] + a[i];

    ll dp[n + 1] = {};

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

        if (i & 1) {

            dp[i] = max(dp[i - 1], dp[i - 2] + a[i]);

        } else {

            dp[i] = max(pre_sum[i - 1], dp[i - 2] + a[i]);

        }

    }

    cout << dp[n];

}

巴特西

AtCoder Beginner Contest 162