# # Codeforces Round 666 (CF1396) 题解

## # Div. 2 Problem A - Juggling Letters (opens new window)

### # 题目描述

$N$个字符串，这些字符串可以任意打乱重新组合，问能否组成$N$个一样的字符串？

### # 题解

from sys import stdin, stdout

def read_int():
return int(stdin.readline().strip())

t = read_int()
for case_num in range(t):
n = read_int()
counter = [0 for _ in range(26)]

for i in range(n):
s = stdin.readline().strip()
for c in s:
counter[ord(c) - ord('a')] += 1
ok = True
for count in counter:
if count % n != 0:
ok = False
break
stdout.write('YES\n' if ok else 'NO\n')

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

## # Div. 2 Problem B - Power Sequence (opens new window)

### # 题解

from sys import stdin, stdout

def read_int():
return int(stdin.readline().strip())

def read_ints():
return map(int, stdin.readline().strip().split(' '))

n = read_int()
a = list(read_ints())
a.sort()
s = sum(a)
cost = s - n
j = 2
while pow(j, n - 1) <= s * 2:
b = [1]
for k in range(n - 1):
b.append(b[-1] * j)
tot = sum([abs(a[i] - b[i]) for i in range(n)])
cost = min(cost, tot)
j += 1
print(cost)

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

## # Problem A - Multiples of Length (opens new window)

### # 题解

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve() {
int n;
read(n);
vector<ll> a(n);
for (int i = 0; i < n; ++i)
read(a[i]);
if (n == 1) {
printf("1 1\n%lld\n1 1\n1\n1 1\n-1\n", -a[0]);
return;
}
printf("1 %d\n", n - 1);
for (int i = 0; i < n - 1; ++i) {
ll r = (a[i] % n + n) % n;
a[i] += r * (n - 1);
printf("%lld ", r * (n - 1));
}
printf("\n2 %d\n", n);
for (int i = 1; i < n; ++i) {
ll r = (a[i] % n + n) % n;
a[i] += r * (n - 1);
printf("%lld ", r * (n - 1));
}
printf("\n1 %d\n", n);
for (ll num : a)
printf("%lld ", -num);
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

## # Problem B - Stoned Game (opens new window)

### # 题解

• 如果当前最大的一堆可以取，就从中取。
• 如果当前最多的一堆不可以取，代表它刚被取过一次，那么此时有$\max a_i\leq\sum a_i - \max a_i - 1$，因此从剩下任何一堆中取了之后，都仍然保持$\max a_i\leq\sum a_i - \max a_i$

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
public:
void solve() {
int n;
read(n);
vector<int> a(n);
int sum = 0, hi = 0;
for (int i = 0; i < n; ++i) {
read(a[i]);
sum += a[i];
hi = max(hi, a[i]);
}
if (hi > sum - hi) {
printf("T\n");
return;
}
printf(sum % 2 == 0 ? "HL\n" : "T\n");
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
read(t);
while (t--) {
Solution solution = Solution();
solution.solve();
}
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

## # Problem C - Monster Invaders (opens new window)

### # 题目描述

$N$个依次相连的山洞，每个山洞有$a_i$个生命值为$1$的小怪和一个生命值为$2$的Boss。你有三种武器：

• 手枪，可以对一个敌人造成$1$点伤害，用一次耗时$r_1$
• 激光枪，可以对所有敌人造成$1$点伤害，用一次耗时$r_2$
• 狙击枪，可以杀死一个敌人，用一次耗时$r_3$

### # 题解

• 一次杀死Boss。用手枪杀死所有小怪，用狙击枪杀死Boss。这个数值记为$p[i]$
• 分两次杀死Boss。用手枪杀死所有小怪再攻击一次Boss，或用一次激光枪杀死所有小怪同时对Boss造成$1$点伤害，此时需要被迫离开；下一次来到这个山洞时，再用一次手枪杀死Boss。不考虑移动耗时，只考虑攻击耗时，我们可以选择两种方案中的较小值，记为$q[i]$

$L[i]$表示清理掉$[1,i]$，最后停留在$i$号山洞的最短耗时；$R[i]$表示清理掉$[i,N]$，最后停留在$i$号山洞的耗时，我们最后的答案就是

$\min_{i=1}^NL[i]+R[i+1]+d$

$R[i]=R[i+1]+2d+\min(p[i],q[i])$

$L[i]=\min(L[i-1]+d+p[i],L[i-2]+4d+\min(p[i-1],q[i-1])+\min(p[i],q[i]))$

#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
x = 0;
char c = getchar();
T sig = 1;
for (; !isdigit(c); c = getchar())
if (c == '-')
sig = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
x *= sig;
}

class Solution {
struct Node {
ll time = 0;
int idx = 0, left = 0;
bool operator<(const Node &other) const { return time > other.time; }
};

public:
void solve() {
ll n, r1, r2, r3, d;
read(n), read(r1), read(r2), read(r3), read(d);
vector<ll> a(n + 1), kill_all(n + 1), leave_one(n + 1);
for (int i = 1; i <= n; ++i) {
read(a[i]);
kill_all[i] = r1 * a[i] + r3;
leave_one[i] = min(r2, r1 * (a[i] + 1)) + r1;
}
vector<ll> L(n + 2), R(n + 2);
R[n] = min(kill_all[n], leave_one[n] + d * 2);
for (int i = n - 1; i >= 1; --i)
R[i] = R[i + 1] + d * 2 + min(kill_all[i], leave_one[i]);
ll cost = R[1];
L[0] = R[n + 1] = -d;
for (int i = 1; i <= n; ++i) {
L[i] = L[i - 1] + d + min(kill_all[i], leave_one[i] + d * 2);
if (i >= 2)
L[i] = min(L[i], L[i - 2] + d * 4 +
min(kill_all[i - 1], leave_one[i - 1]) +
min(kill_all[i], leave_one[i]));
cost = min(cost, L[i] + R[i + 1] + d);
}
cout << cost;
}
};

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solution solution = Solution();
solution.solve();
}

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60