Practice.

A. Goals of Victory

题意

对于 \(n\) 只队伍，存在 \(\frac{n(n - 1)}{2}\) 个任意两只队伍间的比赛。每支队伍具有一个效率值，为队伍的所有比赛中自己的进球数减去其他队伍进球数的总和。

现在，给定 \(n - 1\) 个队伍的效率，求第 \(n\) 个队伍的效率。

思路

对于一场比赛，如果 \(A\) 赢，那么 \(A\) 的效率 \(+ 1\)，\(B\) 的效率 \(-1\)。

因而，所有队伍的效率和为定值 \(0\)。

那么，第 \(n\) 个队伍的效率为前 \(n - 1\) 个队伍的效率和的相反数。

时间复杂度：\(O(n)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    int ans = 0;
    for(int i=1;i<n;i++){
        int x;
        cin >> x;
        ans += -x;
    }
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

乱猜都猜得出来（x

B. Helmets in Night Light

题意

\(A\) 在分享一则公告，他每直接分享给一个居民，就会消耗 \(p\) 代价。

但是，对于所有居民 \(i\)，每个居民都具有一个可以分享给其他居民的数量上限 \(a_i\)，以及分享给一个居民的代价 \(b_i\)。

现在，需要将公告传给所有人，输出最小代价和。

思路

首先，如果 \(A\) 只会分享给一个人，那么我们只需从代价最小的开始分享，遍历一遍即可。

但是，\(A\) 会分享给不同的人，此时我们可以用 \(p\) 来进行替换，将所有要进行分享的人中，所有超过 \(b_i\) 的代价全都替换为 \(p\) 即可。

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

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n, p;
    cin >> n >> p;
    vector<pii> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i].sc;
    for(int i=1;i<=n;i++) cin >> a[i].fs;
    sort(all(a));
    int cnt = 1, ans = p;
    for(int i=1;i<=n;i++){
        ans += min(p, a[i].fs) * min(n - cnt, a[i].sc);
        cnt += min(n - cnt, a[i].sc);
        if(cnt == n) break;
    }
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

签到

C. Joyboard

题意

给定三个整数 \(n, m, k\)，对于长为 \(n + 1\) 的序列 \(a\)，定义一种方案为从 \([0, m]\) 中选一个数，填入 \(a_{n + 1}\)，然后对于 \(i \in [1, n]\)，从后往前递推，有 \(a_i = a_{i + 1} \bmod i\)。

输出满足序列 \(a\) 中恰好有 \(k\) 个不同的数的方案总数。

思路

我们直接打表，可以发现，如果选 \(0\)，那么恰好只有 \(1\) 种不同的数字。

如果选 \([1, n - 1], kn\)，那么恰好有 \(2\) 种不同的数字。

否则，恰好有 \(3\) 种不同的数字。

那么，列一下式子即可。

时间复杂度：\(O(1)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    if(k > 3){
        cout << 0 << '\n';
        return;
    }
    if(k == 1){
        cout << 1 << '\n';
    }else if(k == 2){
        cout << (m > n ? n + m / n - 1 : m) << '\n';
    }else{
        cout << max(0ll, m - (m > n ? n + m / n - 1 : m)) << '\n';
    }
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

《Div.2 C》

D. Effects of Anti Pimples

题意

给定一个序列 \(a\)，一开始所有元素都是白色。

定义一种方案为挑选一部分元素，将其染为黑色，然后对于每个黑色元素，将其下标的倍数对应的白色元素染成绿色。

定义方案的值为所有染成黑色或绿色的元素的值的最大值。

现在，对于所有方案，输出值的总和。

思路

首先，如果选第 \(i\) 位，那么最大值至少是 \(ki\) 中最大的数。

那么，我们对于每一位，先去把选上该位后可能的最大值预处理出来。

我们记 \(b_i\) 为选上第 \(i\) 位后，对应的最大值，本题就转化为了从 \(b\) 中选取一些数，所有方案的最大值总和。

那么，我们将 \(b\) 从小到大排序，答案就是 \(b_1 + 2 ^ 1 \times b_2 + \ldots + 2 ^ n \times b_n\)。

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

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++){
        int mx = 0;
        for(int j=i;j<=n;j+=i) mx = max(mx, a[j]);
        a[i] = mx;
    }
    sort(all(a));
    int ans = 0;
    for(int i=n;i>=1;i--){
        ans = (ans * 2 % mod + a[i]) % mod;
    }
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
//    cin >> t;
    while (t--) solve();
}

难得 \(D\) 只有以往的 \(C\) 难度（x