Practice.

A. Goals of Victory

题意

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

现在，给定 n−1 个队伍的效率，求第 n 个队伍的效率。

思路

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

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

那么，第 n 个队伍的效率为前 n−1 个队伍的效率和的相反数。

时间复杂度：O(n)

对应AC代码

C++
#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，每个居民都具有一个可以分享给其他居民的数量上限 ai，以及分享给一个居民的代价 bi。

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

思路

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

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

时间复杂度：O(nlog⁡n)

对应AC代码

C++
#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] 中选一个数，填入 an+1，然后对于 i∈[1,n]，从后往前递推，有 ai=ai+1modi。

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

思路

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

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

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

那么，列一下式子即可。

时间复杂度：O(1)

对应AC代码

C++
#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 中最大的数。

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

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

那么，我们将 b 从小到大排序，答案就是 b1+21×b2+…+2n×bn。

时间复杂度：O(nlog⁡n)

对应AC代码

C++
#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