# Google Kick Start 2020 Round H 题解

# Problem A - Retype (opens new window)

一共只有两种选择,我们直接计算出来对应的耗时,取较小的那个即可。

ans=K1+min(N+1,KS+NS+1)ans=K-1+\min(N + 1, K - S + N - S + 1)

时间复杂度为O(1)O(1)

参考代码(C++)
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
  void solve(int case_num) {
    cout << "Case #" << case_num << ": ";
    long long N, K, S;
    cin >> N >> K >> S;
    cout << K - 1 + min(N + 1, K - S + N - S + 1) << endl;
  }
};

int main() {
  int t;
  cin >> t;
  for (int i = 1; i <= t; ++i) {
    Solution solution = Solution();
    solution.solve(i);
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# Problem B - Boring Numbers (opens new window)

所有类似这样求[L,R][L,R]范围内符合条件的数的个数的题目,都可以变为分别求[0,R][0,R]范围和[0,L][0,L]范围内的个数,然后二者相减即可得到答案。

如何求[0,X][0,X]范围内符合条件的数的个数呢?

首先,我们考虑所有位数比XX小的数。对于一个dd位数,Boring Number的总个数显然为5d5^d(每一位有55个数字可以选择)。所以说,如果XXDD位,那么所有位数比XX小的数的贡献为i<D5i\sum_{i<D}5^i

接下来,我们考虑所有小于等于XXDD位数。

我们从最高位开始。假设当前处理到第ii位。

  • 如果XX在当前位置的数字不符合条件(奇偶性),那么我们只要统计出所有比X[i]X[i]小的数字中符合条件的数的个数(预设为b[X[i]]b[X[i]]),然后给总数加上b[X[i]]5Dib[X[i]]\cdot5^{D-i}即可。因为对于这b[X[i]]b[X[i]]个数,后面的DiD-i位是可以任意选择的。在这种情况下,我们不需要继续向后处理了。
  • 否则,我们首先统计出比X[i]X[i]小的数字中符合条件的数的个数(预设为a[X[i]]a[X[i]]),给总数加上a[X[i]]5Dia[X[i]]\cdot5^{D-i}。接下来,我们还需要考虑第ii位取为X[i]X[i]的符合条件的数的个数,继续向后进行即可。需要注意的是,如果i=Di=D,我们直接在总数上加上11,表示XX自己就是一个符合条件的数。

时间复杂度为O(logR)O(\log R)(这里没有考虑预处理的时间)。

参考代码(C++)
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
ll five[20], pre[20];
int a[10] = {0, 0, 1, 1, 2, 2, 3, 3, 4, 4};
int b[10] = {0, 1, 1, 2, 2, 3, 3, 4, 4, 5};

class Solution {
  ll count(ll x) {
    string s = to_string(x);
    int n = s.size();
    ll ans = pre[n - 1];
    for (int i = 1; i <= n; ++i) {
      int c = s[i - 1] - '0';
      if (c % 2 != i % 2) {
        ans += five[n - i] * b[c];
        break;
      } else {
        ans += five[n - i] * a[c];
        if (i == n)
          ans++;
      }
    }
    return ans;
  }

public:
  void solve(int case_num) {
    cout << "Case #" << case_num << ": ";
    ll L, R;
    cin >> L >> R;
    cout << count(R) - count(L - 1) << endl;
  }
};

int main() {
  int t;
  cin >> t;
  five[0] = 1;
  for (int i = 1; i < 20; ++i)
    five[i] = five[i - 1] * 5;
  pre[0] = 0;
  for (int i = 1; i < 20; ++i)
    pre[i] = pre[i - 1] + five[i];
  for (int i = 1; i <= t; ++i) {
    Solution solution = Solution();
    solution.solve(i);
  }
}
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

# Problem C - Rugby (opens new window)

显然,xx方向和yy方向的移动步数是相互独立的。

首先考虑yy方向。因为最后所有数的yy是一样的,所以这就变成了一道经典问题,直接取YiY_i的中位数即可。

接下来考虑xx方向。显然,在起点确定之后,我们的移动方案也就随之确定——所有人按照XiX_i排序,然后从左到右依次去对应的格子即可。

接下来,我们可以用三分查找的方法求出最后的答案。为了说明三分查找的正确性,我们需要说明距离函数dist(x)dist(x)只有一个极小值,同时这个极小值也是最小值(如果考虑整点,则可能有两个,但这两个点必然是相邻的两个整数)。

显然,当x+N1min(Xi)x+N-1\leq\min(X_i)时,随着xx的增大,dist(x)dist(x)总是减小的;而当xmax(Xi)x\geq\max(X_i)时,随着xx的增大,dist(x)dist(x)总是增大的。

我们发现,当xx在某一位置时,将起点从xx移动到x+1x+1,有k(x)k(x)个人的移动距离会减小11,同时有Nk(x)N-k(x)个人的移动距离会增加11,因此dist(x+1)dist(x)=N2k(x)dist(x+1)-dist(x)=N-2\cdot k(x)。在xx-\infty移动到\infty的过程中,k(x)k(x)NN减小到00,并且整个过程中不会增大。所以说,dist(x+1)dist(x)dist(x+1)-dist(x)将会从N-N增加到NN,并且过程中不会减小。因此,dist(x)dist(x)总会在满足dist(x+1)dist(x)0dist(x+1)-dist(x)\geq0的最小的xx处取得极小值,同时也是最小值。

最后的时间复杂度为O(NlogN+NlogMAX)O(N\log N+N\log MAX),这里的MAXMAX为我们进行三分查找的范围。

参考代码(C++,三分查找)
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

class Solution {
public:
  void solve(int case_num) {
    cout << "Case #" << case_num << ": ";
    int N;
    cin >> N;
    vector<int> X(N), Y(N);
    for (int i = 0; i < N; ++i)
      cin >> X[i] >> Y[i];
    sort(Y.begin(), Y.end());
    ll ylo = 0;
    for (int yi : Y)
      ylo += abs(yi - Y[N / 2]);
    sort(X.begin(), X.end());
    ll l = -2e9, r = 2e9;
    ll xlo = LLONG_MAX;
    auto dist = [&](ll start) {
      ll ret = 0;
      int idx = 0;
      for (int xi : X) {
        ret += abs(start + idx - xi);
        idx++;
      }
      xlo = min(xlo, ret);
      return ret;
    };
    while (l <= r) {
      ll ml = l + (r - l) / 3, mr = r - (r - l) / 3;
      ll dl = dist(ml), dr = dist(mr);
      if (dl <= dr)
        r = mr - 1;
      if (dl >= dr)
        l = ml + 1;
    }
    cout << ylo + xlo << endl;
  }
};

int main() {
  int t;
  cin >> t;
  for (int i = 1; i <= t; ++i) {
    Solution solution = Solution();
    solution.solve(i);
  }
}
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

我们也可以对dist(x+1)dist(x)dist(x+1)-dist(x)k(x)k(x)进行二分查找,方法是类似的。

Code (C++,二分查找)
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

class Solution {
public:
  void solve(int case_num) {
    cout << "Case #" << case_num << ": ";
    int N;
    cin >> N;
    vector<int> X(N), Y(N);
    for (int i = 0; i < N; ++i)
      cin >> X[i] >> Y[i];
    sort(Y.begin(), Y.end());
    ll ylo = 0;
    for (int yi : Y)
      ylo += abs(yi - Y[N / 2]);
    sort(X.begin(), X.end());
    ll l = -2e9, r = 2e9;
    ll xlo = LLONG_MAX;
    auto dist = [&](ll start) {
      ll ret = 0;
      int idx = 0;
      for (int xi : X) {
        ret += abs(start + idx - xi);
        idx++;
      }
      xlo = min(xlo, ret);
      return ret;
    };
    while (l <= r) {
      ll mid = (l + r) / 2;
      ll delta = dist(mid + 1) - dist(mid);
      if (delta >= 0)
        r = mid - 1;
      else
        l = mid + 1;
    }
    cout << ylo + xlo << endl;
  }
};

int main() {
  int t;
  cin >> t;
  for (int i = 1; i <= t; ++i) {
    Solution solution = Solution();
    solution.solve(i);
  }
}
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

事实上,我们也可以对xx使用中位数方法。但是,我们需要在第一次排序后,用XiiX_i-i替换XiX_i,然后再次排序。官方题解 (opens new window)给出了很好的解释。

Code (C++,对$x$两次排序)
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

class Solution {
public:
  void solve(int case_num) {
    cout << "Case #" << case_num << ": ";
    int N;
    cin >> N;
    vector<int> X(N), Y(N);
    for (int i = 0; i < N; ++i)
      cin >> X[i] >> Y[i];
    sort(Y.begin(), Y.end());
    ll ylo = 0;
    for (int yi : Y)
      ylo += abs(yi - Y[N / 2]);
    sort(X.begin(), X.end());
    for (int i = 0; i < N; ++i)
      X[i] -= i;
    sort(X.begin(), X.end());
    ll xlo = 0;
    for (int xi : X)
      xlo += abs(xi - X[N / 2]);
    cout << ylo + xlo << endl;
  }
};

int main() {
  int t;
  cin >> t;
  for (int i = 1; i <= t; ++i) {
    Solution solution = Solution();
    solution.solve(i);
  }
}
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

# Problem D - Friends (opens new window)

因为最多有N=5×104N=5\times10^4个不同的字符串,所以如果我们以字符串为节点建图,边数的规模会非常大。

转变思路,我们考虑以字母为节点来建图,并用邻接矩阵来表示这个图。初始状态为d[i][j]=d[i][j]=\inftyd[i][i]=0d[i][i]=0。如果两个不同的字母aabb同时出现在了一个字符串SS中,我们就设置d[a][b]=d[b][a]=1d[a][b]=d[b][a]=1。这里的含义是,如果我们现在有一个含有aa的字符串SS'和另一个含有bb的字符串SS'',那么可以通过SS构建一个链SSSS'\to S\to S'',这个链的中间节点有11个。

接下来,我们在这个邻接矩阵上跑一遍Floyd算法,从而现在d[i][j]d[i][j]就表示iijj的链的最少的中间节点数。

最后,对于每一个查询,我们遍历S[Xi]S[X_i]的字母和S[Yi]S[Y_i]的字母的配对,则最后的答案为

minpS[Xi],qS[Yi]d[p][q]+2\min_{p\in S[X_i],q\in S[Y_i]}d[p][q] + 2

如果结果为\infty,则说明无解。

总时间复杂度为O((N+Q)L2+C3)O((N+Q)L^2+C^3),其中C=26C=26为字母表的大小。

参考代码(C++)
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
const int INF = 0x3f3f3f3f;

class Solution {
public:
  void solve(int case_num) {
    cout << "Case #" << case_num << ": ";
    int N, Q;
    cin >> N >> Q;
    vector<string> S(N + 1);
    for (int i = 1; i <= N; ++i)
      cin >> S[i];
    vector<vector<int>> d(26, vector<int>(26, INF));
    for (string s : S)
      for (char c1 : s)
        for (char c2 : s)
          if (c1 != c2)
            d[c1 - 'A'][c2 - 'A'] = 1;
    for (int k = 0; k < 26; ++k)
      for (int i = 0; i < 26; ++i) {
        if (i == k)
          continue;
        for (int j = 0; j < 26; ++j) {
          if (j == i || j == k)
            continue;
          d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
      }

    for (int i = 1; i <= Q; ++i) {
      int X, Y;
      cin >> X >> Y;
      int ans = INF;
      bool found = false;
      for (char c1 : S[X]) {
        for (char c2 : S[Y]) {
          if (c1 == c2) {
            cout << 2 << " ";
            found = true;
            break;
          }
          ans = min(ans, d[c1 - 'A'][c2 - 'A'] + 2);
        }
        if (found)
          break;
      }
      if (!found)
        cout << (ans == INF ? -1 : ans) << " ";
    }
    cout << endl;
  }
};

int main() {
  int t;
  cin >> t;
  for (int i = 1; i <= t; ++i) {
    Solution solution = Solution();
    solution.solve(i);
  }
}
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
61
62
63
64