Codeforces Round 666 (Div. 2)

十月 28, 2020 4925

做题情况

都是 Practice。

A. Juggling Letters

解题思路

显然可以把这些字符集中起来再平均分给每个字符串。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int MAXN = 1000 + 10;
const int MAXL = MAXN;

int n;
char ss[MAXN][MAXL];
int alphabet[26];

int main() {
    int T; scanf("%d", &T);
    while (T --> 0) {
        n = read(); memset(alphabet, 0, sizeof alphabet);
        for (int i = 1; i <= n; ++i) {
            scanf("%s", ss[i] + 1);
            int len = (int) strlen(ss[i] + 1);
            for (int j = 1; j <= len; ++j) {
                ++alphabet[ss[i][j] - 'a'];
            }
        }
        for (int i = 0; i < 26; ++i) {
            if (alphabet[i] % n) goto failed;
        }
        puts("YES"); continue;
        failed: puts("NO");
    }
    return 0;
}

B. Power Sequence

解题思路

乍一看这题只能暴力。

但这题就是暴力。

因为这是一个长为 10^5 的等比数列，即使公比为 2 ， a_{10^5} = 2^{10^5} 也是不可承受的，花费一定不可能这么高。

所以在 n 非常大的情况下，公比不会超过 2 。

但如果 n 非常小呢？

一个显然的性质：最后一项不可能超过 LONG_LONG_MAX，否则花费将超过 10^{18} - 10^{9} ，仍然是不可承受的。

n 最小为 3，那么我们不妨把上界（也就是最后一项的值）定为 10^{18} ，公比自然在 ^3\sqrt{10^{18}} 之内，而这个数仅仅为 10^6 ，一个一个枚举也不是不可承受的。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 1e5 + 10;

int n;
int aa[MAXN];


int main() {
    n = read();
    for (int i = 1; i <= n; ++i) {
        aa[i] = read();
    } std::sort(aa + 1, aa + 1 + n);
    int upbound = powl(1e18, 1.0 / n); // 第 n 项至多是这些，再往上就无法承受了
    long long int ans = 0x7f7f7f7f7f7f7f7f;
    for (int c = 1; c <= upbound; ++c) {
        long long int cost = 0, pow = 1;
        for (int i = 1; i <= n; ++i) {
            cost += std::abs(aa[i] - pow);
            pow *= c;
        }
        ans = std::min(ans, 1ll * cost);
    } printf("%lld\n", ans);
    return 0;
}

C. Multiples of Length

解题思路

又是™的构造题

当 n = 1 时：

1
2
3
4
5
6
1 1
0
1 1
0
1 1
-a[1]

当 n ≠ 1 时：

1
2
3
4
5
6
1 1
-a[1]
2 n
(n-1)*a[2] (n-1)*a[3] ... (n-1) * a[n]
1 n
0 -n*a[2] -n*a[3] ... -n*a[n]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 100000 + 10;

long long int n, aa[MAXN];

int main() {
    n = read();
    for (int i = 1; i <= n; ++i) aa[i] = read();
    if (n == 1) {
        printf("1 1\n0\n");
        printf("1 1\n0\n");
        printf("1 1\n%lld\n", -aa[1]);
    } else {
        printf("1 1\n%lld\n", -aa[1]);
        printf("2 %lld\n", n);
        for (int i = 2; i <= n; ++i) {
            printf("%lld%c", (n - 1) * aa[i], " \n"[i == n]);
        }
        printf("1 %lld\n0 ", n);
        for (int i = 2; i <= n; ++i) {
            printf("%lld%c", -n * aa[i], " \n"[i == n]);
        }
    }
    return 0;
}

D. Stoned Game

解题思路

令 S 为石子的总数量。

通过手玩，可以发现下列情况（我也不知道怎么玩出来的）：

  1. 当存在一堆石子数量 \geq \lfloor \frac{S}{2} \rfloor 时，先手必胜。
    因为他可以一直拿这一堆，直到把剩下所有石子小号干净。
  2. 当所有石子数量 \leq \lfloor \frac{S}{2} \rfloor 且 S 为偶数时，后手必胜。
    简要证明：
    • 当 S = 0 时，后手必胜。
    • 当 S > 0 时，先手拿取一个石子，如果此时出现了一堆石子数量 \geq \lfloor \frac{S}{2} \rfloor ，那么转化为了情况 1，先后手互换，也即后手必胜；如果没出现，那么后手可以再拿一个石子且保证所有石子数量 < \lfloor \frac{S}{2} \rfloor ，此时 S 被减了 2，如此循环往复直到 S = 0 ，后手必胜。
  3. 当所有石子数量 \geq \lfloor \frac{S}{2} \rfloor 且 S 为奇数时，先手必胜。
    先手可以通过拿一个石子来转化为情况 2，此时先后手互换，也即先手必胜。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 100 + 10;
const char ans[2][3] = { "T ", "HL" };

int main() {
    int T = read();
    while (T --> 0) {
        int n = read(); int mxx = 0, sum = 0;
        for (int i = 1; i <= n; ++i) {
            int x = read(); mxx = std::max(mxx, x);
            sum += x;
        } printf("%s\n", ans[!((sum & 1) || (mxx > (sum >> 1)))]);
    }
    return 0;
}