CP Wiki

# Codeforces Round 666 (CF1396) 题解

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

# 题目描述

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

# 题解

统计每种字母的个数，看是否都是NN的倍数即可。

参考代码（Python 3） 
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)

# 题目描述

有一列数，可以无消耗地排列顺序，或者每次消耗11来将某个数的大小改变11（可以增大或减小）。问最少消耗多少，可以将这列数变为{1,c,⋯,cn−1}\{1,c,\cdots,c^{n-1}\}，其中cc是一个正整数。

# 题解

首先将数组排序，然后枚举cc即可。枚举的判断条件可以设置为cn−1<=2∑aic^{n-1}<=2\sum a_i。

参考代码（Python 3） 
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)

# 题目描述

给定一个长度为NN的数组（1≤N≤1000001\leq N\leq100000），要求进行恰好三次操作，每次选取一个非空的区间[L,R][L,R]，其长度len=R−L+1len=R-L+1，给这个区间中的每个数加上lenlen的某个倍数（不同的位置可以加不同的值）。问最后能否将整个数组都变为00。

# 题解

利用N−1N-1和NN互质来求解。第一次操作区间[1,N−1][1,N-1]，第二次操作区间[2,N][2,N]，最后操作区间[1,N][1,N]。因为N−1N-1和NN互质，a(N−1)a(N-1)可以取遍NN的所有余数。经过前两次操作，将所有数都变为NN的倍数，最后一次给每个数加上它的相反数即可。

注意单独处理N=1N=1的情况。

参考代码（C++） 
#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)

# 题目描述

两个人玩石子游戏，一共有NN（1≤N≤1001\leq N\leq100）堆石子，每堆的石子数1≤ai≤1001\leq a_i\leq100。每次可以从任意一堆取出一个石子，但不能从对方刚取的那堆中取。第一个没有石子可取的人输掉游戏。问，给定每堆石子的个数，是先手赢还是后手赢？

# 题解

考虑所有石子中最大的那一堆。如果max⁡ai>∑ai−max⁡ai\max a_i>\sum a_i - \max a_i，那么先手有必胜策略：永远先从最多的那一堆中取，这样后手只能从剩下那些堆中取；那么总有一个时刻，先手取完之后，后手将没有石子可取。

如果所有石子中最大的那一堆不超过剩下的石子总数，也即max⁡ai≤∑ai−max⁡ai\max a_i\leq\sum a_i - \max a_i，那么两个人在取石子时总可以避免出现max⁡ai>∑ai−max⁡ai\max a_i>\sum a_i - \max a_i的情况：

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

因此在这种情况下，最后的获胜方取决于石子总数的奇偶性。如果总数为奇数，则先手获胜；否则后手获胜。

参考代码（C++） 
#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)

# 题目描述

有NN个依次相连的山洞，每个山洞有aia_i个生命值为11的小怪和一个生命值为22的Boss。你有三种武器：

  • 手枪，可以对一个敌人造成11点伤害，用一次耗时r1r_1
  • 激光枪，可以对所有敌人造成11点伤害，用一次耗时r2r_2
  • 狙击枪，可以杀死一个敌人，用一次耗时r3r_3

它们的耗时满足r1≤r2≤r3r_1\leq r_2\leq r_3。手枪和狙击枪只有打死了所有小怪后才能打Boss，而激光枪可以对小怪和Boss同时造成伤害。如果你对Boss造成伤害但没有打死它，你必须强制移动到相邻的另一个山洞。无论是强制移动还是自己移动，从一个山洞走到相邻山洞的用时固定为dd。

求杀死所有怪物的最短用时。

# 题解

首先，考虑一个山洞。我们有两种方式杀死这个山洞中所有的怪物：

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

下面我们考虑整体的路线。不妨从最后一个清空的山洞着手。

P3配图 假设最后我们停在33号山洞，我们整体的最优路线应当是图上这样的，也即首先到33，然后走到头再走回来。如果不这样走，必然会产生额外的路程。

因此，我们可以把最后的路程分为三部分，清理掉[1,2][1,2]的耗时，清理掉[3,8][3,8]的耗时，以及从22走到33的耗时dd。

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

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

为了避免对特殊情况的讨论，我们可以令L[0]=R[N+1]=−dL[0]=R[N+1]=-d。

接下来就是如何求L[i]L[i]和R[i]R[i]。

先看R[i]R[i]。R[n]R[n]比较特殊，我们可以选择一次杀死所有怪物，耗时p[n]p[n]；也可以分两次，但这意味着我们需要额外用2d2d的时间赶路，总耗时q[n]+2dq[n]+2d。对于剩下的R[i]R[i]，因为我们需要从ii走到i+1i+1，再从i+1i+1走回来，所以一定经过了ii号山洞两次，因此总耗时为

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

再看L[i]L[i]。对于每个L[i]L[i]，我们有两种策略，一种是不走回头路，从i−1i-1走过来之后我们一次杀死所有怪物，耗时L[i−1]+d+p[i]L[i-1]+d+p[i]；二是走回头路，走i−2→i−1→i→i−1→ii-2\rightarrow i-1\rightarrow i\rightarrow i-1\rightarrow i这样的路线，从i−2i-2（i≥2i\geq2）开始，在i−1i-1处我们选择min⁡(p[i−1],q[i−1])\min(p[i-1],q[i-1])，之后走到ii，再回到i−1i-1，然后再走回ii，因为经过了ii两次，所以我们在ii处可以选择min⁡(p[i],q[i])\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]))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]))

为什么不考虑更前面的位置？

路线i−3→i−2→i−1→i→i−1→i−2→i−1→ii-3\rightarrow i-2\rightarrow i-1\rightarrow i\rightarrow i-1\rightarrow i-2\rightarrow i-1\rightarrow i可以调整为i−3→i−2→i−1→i−2→i−1→i→i−1→ii-3\rightarrow i-2\rightarrow i-1\rightarrow i-2\rightarrow i-1\rightarrow i\rightarrow i-1\rightarrow i，两条路线的长度都为77，并且都经过了i−2i-2、i−1i-1和ii至少两次，因此这两种方案的最优取值是一样的。而调整后的路线可以视为从i−2i-2出发（因为已经经过了i−2i-2两次），所以已经被我们的讨论所包含。因此，考虑回头的情况，只需要考虑到i−2i-2即可。

最后我们就可以利用上面得到的式子计算出最后的最短用时。

参考代码（C++） 
#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

# Problem D - Rainbow Rectangles (opens new window)

# 题目描述

# 题解

# Problem E - Distance Matching (opens new window)

# 题目描述

# 题解

← Codeforces Round 669 (CF1407) 题解 →