Codeforces Round 902 (Div. 2, based on COMPFEST 15 - Final

A. Goals of Victory

解题思路:

答案为所有元素之和的负数。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define fi first
#define se second
const int mod = 998244353;

void solve()
{
    int n;
    cin >> n;
    ll res = 0;
    for (int i = 1; i < n; i++)
    {
        int x;
        cin >> x;
        res += x;
    }
    cout << -res << endl;
}

int main()
{
    int t = 1;
    scanf("%d", &t);
    while (t--)
    {
        solve();
    }
    return 0;
}

B. Helmets in Night Light

解题思路:

开头我们通知一个\(b_i\)最小的村名，接下来贪心每次都通知花费最小的村民，如果此时花费最小的村民的花费大于\(p\),那么剩下的都亲自通知。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second

void solve()
{
    int n, p;
    scanf("%d %d", &n, &p);
    vector<pll> v(n + 1);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &v[i].se);
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld", &v[i].fi);
    }
    sort(v.begin() + 1, v.end());
    ll res = p;
    ll cnt = 1;
    for (int i = 1; i <= n; i++)
    {
        if (v[i].fi > p)
        {
            break;
        }
        ll t = min(v[i].se, n - cnt);
        v[i].se -= t;
        cnt += t;
        res += t * v[i].fi;
        if (cnt == n)
        {
            break;
        }
    }
    res += (n - cnt) * (ll)p;
    printf("%lld\n", res);
}

int main()
{
    int t = 1;
    scanf("%d", &t);
    while (t--)
    {
        solve();
    }
    return 0;
}

C. Joyboard

解题思路:

从后往前，最终\(a_i\)一定会除以\(1\)变成\(0\)。

所以如果\(k = 1\),那么\(a_{n + 1} = 0\)。答案唯一。

如果\(k = 2\)，那么除了\(0\)只能出现一个数字。

若\(a_{n + 1} \geq n\),一定要是\(a_{n + 1} \% \ n = 0\),如果不为\(0\)一定出现至少三个不同的数。
若\(0<a_{n + 1} < n\),一定刚好出现两个数。

如果\(k =3\)，那么\(k = 1,k = 2\)的情况去掉，就是答案。

否则，答案为\(0\)。因为如果\(a_{n + 1} < n\)，要么除完一次就变\(0\)，要么开始就是\(0\),最多出现两个不同数。

如果\(a_{n + 1}\geq n\),要么\(a_{n + 1} = kn\)，除完一次就成0，要么除完一次后\(a_n < n\),如上，最多再除一次就会变成\(0\)。所以最多三次。

代码:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second

void solve()
{
    int n, k, m;
    scanf("%d %d %d", &n, &m, &k);
    if (k == 1)
    {
        printf("1\n");
    }
    else if (k == 2)
    {
        ll res = (min(n, m)) + (m > n ? m / n - 1 : 0);
        printf("%lld\n", res);
    }
    else if (k == 3)
    {
        ll res = (min(n, m)) + (m > n ? m / n - 1 : 0);
        res = m - res - 1 + 1;
        printf("%lld\n", res);
    }
    else
    {
        printf("0\n");
    }
}

int main()
{
    int t = 1;
    scanf("%d", &t);
    while (t--)
    {
        solve();
    }
    return 0;
}

D. Effects of Anti Pimples

解题思路:

我们通过枚举确定，如果单选\(a_i\),得到的最大值\(ma_i\)是多少。

然后将这些最大值进行排序。对于\(ma_i\)，如果\(ma_j < ma_i\),对答案最大值无影响，所以随便选或不选，方案数为\(2^{i-1}\)。后面大的\(ma_k > ma_i\),选了就不是\(ma_i\)为最大值做贡献了。所以，这里是\(ma_i\)对全局答案做出的贡献。

这里有个问题，如果有多个\(ma_i\)怎么办，即多个位置的最大值贡献一样怎么办？

举例：\(2,2\).答案为\(6\)

如果说，我们只选择比当前值小的，样例中也就是\(2个2^0 * 2\),那么最终答案为\(4\)，是错误的。因为少算了两个都选的情况。

如果说，我们把小于等于当前值的全都是选或者不选(不包括自己,因为自己必选，没有两种可能)，那么就是\(ans = 2 * (2^1 * 2) = 8\)，答案偏大，因为两个都选只有一次。

我们假设这里有三个一样的值，那么选或不选的方案数有\(2^3 = 8\)种。去掉都不选的情况，一共有\(7\)种。

\(2^0 + 2^1 + 2^2 = 7\). 以下选为\(1\)，反之为\(0\)。\(?\)为可选可不选。

\(2^0 : 100\)

\(2^1:?10\)

\(2^2:??1\)

如上，其实顺着遍历过去，前面的都视为可选可不选即可。

\(10\)，可以看为左侧选右侧不选，那么每对\((i,j)\)之间一共只有四种情况\(00,01,10,11\),本题中不能都不选，所以只有三种情况\(01,10,11\),那么如果\(10\)方案有了，剩下的就是\(01,11\),即后一位必选，前一位随意，符合上述思路。

代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define fi first
#define se second
const int mod = 998244353;

ll qmi(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b & 1)
        {
            res = res * a % mod;
        }
        b >>= 1;
        a = a * a % mod;
    }
    return res;
}
void solve()
{
    int n;
    scanf("%d", &n);
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    vector<int> ma(n + 1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= i / j; j++)
        {
            if (i % j == 0)
            {
                ma[j] = max(ma[j], a[i]);
                ma[i / j] = max(ma[i / j], a[i]);
            }
        }
    }
    sort(ma.begin() + 1, ma.end());
    ll t = qmi(1, mod - 2);
    ll ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans = (ans + (ma[i] * t)) % mod;
        t = (t * 2) % mod;
    }
    cout << ans;
}

int main()
{
    int t = 1;
    while (t--)
    {
        solve();
    }
    return 0;
}