Codeforces Round 666 Div2

比赛链接

A Juggling Letters

Description

题目链接

Solution

每个字母出现次数需要是 $n$ 的倍数。

Code

Juggling Letters

#include <bits/stdc++.h>

using namespace std;

int T, n;
string s;

signed main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> n;
        int cnt[26] = {0};
        for (int i = 1; i <= n; i++) {
            cin >> s;
            for (int j = 0; j < s.size(); j++) cnt[s[j] - 'a']++;
        }
        bool tag = 1;
        for (int i = 0; i < 26; i++)
            if (cnt[i] % n) tag = 0;
        cout << (tag ? "YES\n" : "NO\n");
    }
    return 0;
}

B Power Sequence

Description

题目链接

Solution

首先证明将序列调整为升序最优。

证: 若存在有序对 $(a_i,a_j)$，满足 $i<j$ 且 $a_i>a_j$。

由 $|x|+|y|=max(|x+y|,|x-y|)$，可知

$|a_i-c^i|+|a_j-c^j|=max(|(a_i+a_j)-(c^i+c^j)|,|(a_i-a_j)-(c^i-c^j)|)$

$\ge max(|(a_j+a_i)-(c^j+c^i)|,|(a_j-a_i)-(c^i-c^j)|)$

$=|a_j-c^i|+|a_i-c^j|$

故将序列调整为升序会使总代价最小。

接下来考虑求 $f(x)=\sum|a_i-x^i|$ 最小值。假设最小值在 $x=c$ 时取到，那么显然有 $c^{n-1}-a_{n-1}<=f(c)<=f(1)$，即 $c^{n-1}<=f(1)+a_{n-1}$。所以只需要从 1 到 $\sqrt[n-1]{f(1)+a_{n-1}}$ 枚举 $x$，对答案取 $min$ 即可。

Code

Power Sequence

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int MAXN = 1E5 + 5;

int T, n;
LL a[MAXN];

LL qpow(LL a, LL b) {
    LL ans = 1, base = a;
    while (b) {
        if (b & 1) ans = ans * base;
        b >>= 1, base = base * base;
    }
    return ans;
}

LL f(LL x) {
    LL sum = 0;
    for (int i = 0; i < n; i++) sum += abs(qpow(x, i) - a[i]);
    return sum;
}

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(a, a + n);
    int lim = llround(pow(f(1) + a[n - 1], 1.0 / (n - 1)));
    LL ans = LONG_LONG_MAX;
    for (int i = 1; i <= lim; i++) ans = min(ans, f(i));
    cout << ans;
    return 0;
}

C Multiples of Length

Description

题目链接

Solution

第一步，选择区间 $[1,n-1]$，将每个数加上 $(n-1)*a_i$。

第二步, 选取区间 $[n,n]$，将 $a_n$ 加上 $(n-1)*a_n$。

经过前两步操作后每个数变为 $n*a[i]$。

第三步，选择区间 $[1,n]$，将每个数减去 $n*a_i$ 。

注：当 $n=1$ 时不存在区间 $[1,n-1]$，需要单独讨论。

Code

Multiples of Length

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int MAXN = 1E5 + 5;

LL n, a[MAXN];

signed main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n == 1) {
        cout << 1 << " " << 1 << endl;
        cout << 0 << endl;
        cout << 1 << " " << 1 << endl;
        cout << 0 << endl;
        cout << 1 << " " << 1 << endl;
        cout << -a[1] << endl;
        return 0;
    }
    cout << 1 << " " << n - 1 << endl;
    for (int i = 1; i < n; i++) {
        cout << a[i] * (n - 1) << " ";
        a[i] += a[i] * (n - 1);
    }
    cout << endl;

    cout << n << " " << n << endl;
    cout << (n - 1) * a[n] << endl;
    a[n] *= n;

    cout << 1 << " " << n << endl;
    for (int i = 1; i <= n; i++) cout << -a[i] << " ";
    return 0;
}

D Stoned Game

Description

题目链接

Solution

如果只有一堆，或者存在某一堆的石子数比其余堆的石子数之和还大，那么先手选这一堆必胜。否则，两个玩家一定会避免自己操作后产生前面两种局面，那么他们一定会轮流选择当前能选择的数目最大的那一堆，最后石子一定会被取完，即当石子总数为奇数时先手必胜。

Code

Stoned Game

#include <bits/stdc++.h>

using namespace std;

int n, x, T;

signed main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while (T--) {
        cin >> n;
        int sum = 0, mx = 0;
        for (int i = 1; i <= n; i++) cin >> x, sum += x, mx = max(mx, x);
        if (n == 1) {
            cout << "T\n";
            continue;
        }
        if (mx > sum - mx)
            cout << "T\n";
        else {
            if (sum & 1)
                cout << "T\n";
            else
                cout << "HL\n";
        }
    }
    return 0;
}

E Monster Invaders

Description

题目链接

Solution

由于 $r_1<=r_2<=r_3$，那么如果 BOSS 只剩一滴血的话，选择用手枪击杀 BOSS 耗时最少。

易知当玩家第一次进入每一层时有如下选择：

• 用手枪打死所有小怪，用 AWF 打 BOSS，进入下一层。
• 用手枪打死所有小怪，再用手枪打 BOSS，此时有两种选择：
  • 进入下一层后返回补刀。
  • 回到上一层补刀，再回到这一层补刀。
• 用镭射抢打 BOSS 和小怪，此时有两种选择：
  • 进入下一层后返回补刀。
  • 回到上一层补刀，再回到这一层补刀。

容易证明没有比上述选择更优的选择。

设 $dp[i][0]$ 表示打完前 $i-1$ 层的 BOSS，第 $i$ 层的 BOSS 剩 1 滴血所需的最少时间， $dp[i][1]$ 表示打完前 $i$ 层的 BOSS所需的最少时间。根据前面的分析容易推出状态转移方程。需要注意的是，游戏不一定在最后一层结束，即玩家打死第 $n$ 层的 BOSS 后，可能回到第 $n-1$ 层补刀，不需要再回到第 $n$ 层，因此当 $i=n$ 时要单独讨论。

Code

Monster Invaders

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int MAXN = 1E6 + 5;
LL n, d, r1, r2, r3, a[MAXN], dp[MAXN][2];

template <class T>
void read(T& x, T f = 1, char ch = getchar()) {
    x = 0;
    while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : 1), ch = getchar();
    while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    x *= f;
}

signed main() {
    read(n), read(r1), read(r2), read(r3), read(d);
    for (int i = 1; i <= n; i++) read(a[i]);
    dp[1][0] = min(a[1] * r1 + r1, r2), dp[1][1] = a[1] * r1 + r3;
    for (int i = 2; i <= n; i++) {
        dp[i][0] = min(dp[i - 1][0] + 3 * d + min(a[i] * r1 + r1, r2) + r1,
                       dp[i - 1][1] + d + min(a[i] * r1 + r1, r2));
        dp[i][1] = min(dp[i - 1][1] + d + a[i] * r1 + r3,
                       dp[i - 1][0] + 3 * d + min(a[i] * r1 + r1, r2) + 2 * r1);
        if (i == n)
            dp[i][1] =
                min(dp[i][1], dp[i - 1][0] + 2 * d + a[i] * r1 + r3 + r1);
    }
    cout << dp[n][1] << endl;
    return 0;
}