Algorithm

Codeforces Round #587 (Div. 3) F. Wi-Fi

题目

https://codeforces.com/contest/1216/problem/F

有n个房间，编号[1,n]，路由器范围为k。现要给所有房间通wifi。对于房间i，有两种方案：

  • 直连网线，话费为i
  • 在i建路由器，话费也是i，但这样[i-k, i+k]区间就都连通了
    有些房间不能建路由器。求最少花费。

做法

首先，能建基站的一定不会直连。由于基站之间会相互覆盖，所以只需决定哪些保留哪些基站。感觉像是贪心？不知道能不能做。我是用动态规划做的。设f[i]表示只用[1,i]之间的基站，将[1,i]都连通的最小话费。那么有两种情况：

  • i直连，花费为f[i-1]+i
  • 在某位置j建基站(i-k<=j<=i)，这样[j-k,i]之间就都已经覆盖了，只需前面的可以就行。我们需要将前面的也满足。此时的花费为j+min(f[t], j-k-1<=t<j)。

由于k给定，所以这两个最小值（j和t）都可以用单调队列来维护。DP即可，时间复杂度O(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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>

using namespace std;

long long Work(int N, int K, const vector<bool>& can) {
  vector<long long> f(N + 1);
  deque<pair<int, long long>> q_f;  // min f in [i - K - 1, i - 1]
  deque<pair<int, long long>> q_g;  // min g in [i - K, i]
  q_f.push_back(make_pair(0, 0));
  
  for (int i = 1; i <= N; i++) {
    while (!q_f.empty() && q_f.front().first < i - K - 1) q_f.pop_front();

    if (can[i]) {
      long long min_f = q_f.front().second;
      long long min_g = min_f + i;
      while (!q_g.empty() && q_g.back().second >= min_g) q_g.pop_back();
      q_g.push_back(make_pair(i, min_g));
    }
    while (!q_g.empty() && q_g.front().first < i - K) q_g.pop_front();

    f[i] = f[i - 1] + i;
    if (!q_g.empty()) f[i] = min(f[i], q_g.front().second);

    while (!q_f.empty() && q_f.back().second >= f[i]) q_f.pop_back();
    q_f.push_back(make_pair(i, f[i]));
  }
  return f[N];
}

int main() {
  int N, K;
  cin >> N >> K;
  vector<bool> can(N + 1);
  for (int i = 1; i <= N; i++) {
    char ch;
    cin >> ch;
    while (ch != '0' && ch != '1') cin >> ch;
    can[i] = (ch == '1');
  }
  cout << Work(N, K, can) << endl;
  return 0;
}
Algorithm

Leetcode 4. Median of Two Sorted Arrays

题目

https://leetcode.com/problems/median-of-two-sorted-arrays/

给定两个有序数组，求两个数组中的所有数字的中位数。

做法

二分查找，分情况讨论。参见代码注释。

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

class Solution {
public:
  // 在一个数组中的第K小
  int GetKthFromArray(const vector<int>& a, int l, int r, int K) {
    return a[l + K - 1];
  }
  // 在一个数组和一个额外的数（另一个数组只有一个数）中的第K小。
  int GetKthFromArrayAndNumber(const vector<int>& a, int l, int r,
                               int extra_number, int K) {
    if (l + K - 1 > r) return max(a[r], extra_number);
    if (a[l + K - 1] < extra_number) return a[l + K - 1];
    if (l + K - 2 >= l) return max(a[l + K - 2], extra_number);
    else return extra_number;
  }

  // 两个数组中的第K小
  int GetKth(const vector<int>& a, int l1, int r1,
             const vector<int>& b, int l2, int r2, int K) {
    if (l1 > r1) return GetKthFromArray(b, l2, r2, K);
    if (l2 > r2) return GetKthFromArray(a, l1, r1, K);
    if (l1 == r1) return GetKthFromArrayAndNumber(b, l2, r2, a[l1], K);
    if (l2 == r2) return GetKthFromArrayAndNumber(a, l1, r1, b[l2], K);
    int m1 = (l1 + r1) / 2, cnt1 = m1 - l1 + 1;
    int m2 = (l2 + r2) / 2, cnt2 = m2 - l2 + 1;
    if (K <= cnt1) return GetKth(a, l1, m1, b, l2, r2, K);  // a的后一半不用考虑
    if (K <= cnt2) return GetKth(a, l1, r1, b, l2, m2, K);  // b的后一半不用考虑
    if (K <= cnt1 + cnt2) {  // 去掉一个数组的后一半
      if (a[m1] > b[m2]) return GetKth(a, l1, m1, b, l2, r2, K);
      else return GetKth(a, l1, r1, b, l2, m2, K);
    }
    else {  // 去掉一个数组的前一半，同时维护K
      if (a[m1] > b[m2]) return GetKth(a, l1, r1, b, m2 + 1, r2, K - cnt2);
      else return GetKth(a, m1 + 1, r1, b, l2, r2, K - cnt1);
    }
  }

  double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int n1 = nums1.size();
    int n2 = nums2.size();
    int tot = n1 + n2;
    if (tot % 2 == 1) {
      return GetKth(nums1, 0, n1 - 1, nums2, 0, n2 - 1, tot / 2 + 1);
    }
    else {
      int t1 = GetKth(nums1, 0, n1 - 1, nums2, 0, n2 - 1, tot / 2);
      int t2 = GetKth(nums1, 0, n1 - 1, nums2, 0, n2 - 1, tot / 2 + 1);
      return (t1 + t2) * 0.5;
    }
  }
};

时间复杂度O(log(n+m))

Algorithm

Kick Start 2019 Round D

https://codingcompetitions.withgoogle.com/kickstart/archive/2019

这场的题比较好玩。

T1: X or What? (8pts, 19pts)

题目

给定长度为N的初始int数组A。定义有趣区间[L, R]：A[L] xor A[L+1] xor … xor A[R]结果的二进制具有偶数个1。M个操作，每次修改A中的一个数。求每次操作后A中最长的有趣区间的长度。N, M <= 10^5。

做法

一开始我想用前缀和维护区间异或值，但是貌似没法做。稍微思考一下可以发现，我们要求的有趣区间比较有趣。如果a xor b有偶数个1，因为xor的性质，要么a和b都有偶数个1，要么都有奇数个1。换句话说，我们先把所有数都替换成0和1即可。那么有趣区间中一定包含偶数个1。如果A中有偶数个1，那么[0, N-1]就是答案。否则答案就是0到倒数第二个1，或者第二个1到N-1。用一个set维护所有1的位置即可。时间复杂度O(nlogn)。

我做的时候比较sb，用一个线段树维护0和1的位置。代码就不贴了。

T2: Latest Guests (12pts, 23pts)

题目

这个题比较好玩。有N个在一个圆圈上的城市，编号1..N，N与1相邻。有G个人，第i个人从Hi城市出发，方向是Di（顺时针或逆时针），每一分钟就走到下一个城市。这样过了M分钟。问每一个人是多少个城市的最后访问者。如果一个城市最后有好多人访问，那么这些人都是最后访问者。N, G <= 10^5，M <= 10^9。

做法

我们先考虑顺时针的情况，显然可以求出每个店最后访问的是谁（只会有一个，从最后的位置倒着找即可），然后求出这个时间。对逆时针的人也同样处理，那么比较两个时间哪个靠后即可。时间复杂度O(nlogn)。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

int GetSum(const vector<int>& sum, int l, int r) {
  if (l <= r) {
    return sum[r] - (l == 0 ? 0 : sum[l - 1]);
  }
  return sum[r] + sum[sum.size() - 1] - sum[l - 1];
}

void Work(int N, int G, int M, const vector<pair<int, bool>>& guests, vector<int>* ans) {
  set<int> clock_end, anti_clock_end;
  for (int i = 0; i < G; i++) {
    if (guests[i].second) {
      int end = (guests[i].first + M) % N;
      clock_end.insert(end);
    }
    else {
      int end = (guests[i].first - M) % N;
      if (end < 0) end += N;
      anti_clock_end.insert(end);
    }
  }
  vector<int> clock_last_time(N), anti_clock_last_time(N);
  for (int i = 0; i < N; i++) {
    clock_last_time[i] = -1;
    anti_clock_last_time[i] = -1;
  }
  for (auto it = clock_end.begin(); it != clock_end.end(); it++) {
    int last;
    if (it == clock_end.begin()) {
      last = *clock_end.rbegin();
    }
    else {
      auto tmp = it;
      tmp--;
      last = *tmp;
    }
    int now = M;
    for (int pos = *it; pos != (last + 1) % N; pos = (pos + N - 1) % N) {
      clock_last_time[pos] = now;
      now--;
      if (now < 0) break;
    }
    if (now >= 0) clock_last_time[(last + 1) % N] = now;
  }
  for (auto it = anti_clock_end.begin(); it != anti_clock_end.end(); it++) {
    int next;
    if ((*it) == (*anti_clock_end.rbegin())) {
      next = *anti_clock_end.begin();
    }
    else {
      auto tmp = it;
      tmp++;
      next = *tmp;
    }
    int now = M;
    for (int pos = *it; pos != (next - 1 + N) % N; pos = (pos + 1) % N) {
      anti_clock_last_time[pos] = now;
      now--;
      if (now < 0) break;
    }
    if (now >= 0) anti_clock_last_time[(next - 1 + N) % N] = now;
  }
  vector<int> clock_sum(N), anti_clock_sum(N);
  for (int i = 0; i < N; i++) {
    int res = max(clock_last_time[i], anti_clock_last_time[i]);
    if (res != -1 && res == clock_last_time[i]) clock_sum[i] = 1;
    if (res != -1 && res == anti_clock_last_time[i]) anti_clock_sum[i] = 1;
    if (i > 0) {
      clock_sum[i] += clock_sum[i - 1];
      anti_clock_sum[i] += anti_clock_sum[i - 1];
    }
  }
  ans->resize(G);
  for (int i = 0; i < G; i++) {
    if (guests[i].second) {
      int end = (guests[i].first + M) % N;
      auto it = clock_end.find(end);
      int last;
      if (it == clock_end.begin()) {
        last = *clock_end.rbegin();
      }
      else {
        auto tmp = it;
        tmp--;
        last = *tmp;
      }
      int len = min(end == last ? N : (end - last + N) % N, M + 1);
      int start = (end - len + 1 + N) % N;
      (*ans)[i] = GetSum(clock_sum, start, end);
    }
    else {
      int end = (guests[i].first - M) % N;
      if (end < 0) end += N;
      auto it = anti_clock_end.find(end);
      int next;
      if ((*it) == (*anti_clock_end.rbegin())) {
        next = *anti_clock_end.begin();
      }
      else {
        auto tmp = it;
        tmp++;
        next = *tmp;
      }
      int len = min(end == next ? N : (next - end + N) % N, M + 1);
      int to = (end + len - 1 + N) % N;
      (*ans)[i] = GetSum(anti_clock_sum, end, to);
    }
  }
}

int main() {
  int T;
  cin >> T;
  for (int test = 1; test <= T; test++) {
    int N, G, M;
    cin >> N >> G >> M;
    vector<pair<int, bool>> guests(G);
    for (int i = 0; i < G; i++) {
      int x;
      cin >> x;
      guests[i].first = x - 1;
      char ch = getchar();
      while (ch != 'C' && ch != 'A') ch = getchar();
      guests[i].second = (ch == 'C');
    }
    vector<int> ans;
    Work(N, G, M, guests, &ans);
    cout << "Case #" << test << ": ";
    for (int x : ans) cout << x << " ";
    cout << endl;
  }
  return 0;
}

T3: Food Stalls (7pts, 31pts)

题目

x轴上有N个点，每个点有坐标Xi和代价Ci。现在要选一个点i建仓库，代价Ci，然后再选K个点建杂货店，每个点代价Cj+|Xi-Xj|。求最小代价。N <= 10^5。

做法

首先可以发现，实际上就是要选出K+1个点，将它们的Ci都算上，然后选一个中心点。这个中心点显然一定是中间的那个。所以枚举每个点作为中心点，左边求Ci-Xi的前K/2小，右边求Ci+Xi的前K/2(+1)小即可。用set维护即可。时间复杂度O(NlogN)。

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
65
66
67
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>

using namespace std;

const long long inf64 = 1ll << 60;

long long Work(int K, int N, const vector<int>& X, const vector<int>& C) {
  vector<pair<int, int>> spots(N);
  for (int i = 0; i < N; i++) {
    spots[i] = make_pair(X[i], C[i]);
  }
  sort(spots.begin(), spots.end());
  int left_num = K / 2;
  int right_num = K - left_num;
  vector<long long> left(N), right(N);
  multiset<int> now;
  long long sum = 0;
  for (int i = 0; i < N; i++) {
    if (now.size() == left_num) left[i] = sum;
    else left[i] = inf64;
    sum += spots[i].second - spots[i].first;
    now.insert(spots[i].second - spots[i].first);
    if (now.size() > left_num) {
      auto it = --now.end();
      sum -= *it;
      now.erase(it);
    }
  }
  now.clear();
  sum = 0;
  for (int i = N - 1; i >= 0; i--) {
    if (now.size() == right_num) right[i] = sum;
    else right[i] = inf64;
    sum += spots[i].second + spots[i].first;
    now.insert(spots[i].second + spots[i].first);
    if (now.size() > right_num) {
      auto it = --now.end();
      sum -= *it;
      now.erase(it);
    }
  }
  long long res = inf64;
  for (int i = 0; i < N; i++) {
    long long left_cost = left[i] + (long long)left_num * spots[i].first;
    long long right_cost = right[i] - (long long)right_num * spots[i].first;
    res = min(res, left_cost + right_cost + spots[i].second);
  }
  return res;
}

int main() {
  int T;
  cin >> T;
  for (int test = 1; test <= T; test++) {
    int K, N;
    cin >> K >> N;
    vector<int> X(N), C(N);
    for (int i = 0; i < N; i++) cin >> X[i];
    for (int i = 0; i < N; i++) cin >> C[i];
    auto ans = Work(K, N, X, C);
    cout << "Case #" << test << ": " << ans << endl;
  }
  return 0;
}
Algorithm

Leetcode 940. Distinct Subsequences II

题目

https://leetcode.com/problems/distinct-subsequences-ii/

给定一个小写字母组成的字符串s，求s的不同子序列的个数模P。

做法

设f[i]表示s的前i个字符构成的不同子序列个数。那么对于第i个，我们可以选第i个，也可以不选第i个，所以f[i] = f[i-1] * 2。这样肯定是有问题的，会出现重复计算的情况。什么时候会重复呢？首先，选第i个，结果确实是f[i-1]，不选第i个，结果也确实是f[i-1]。问题就在于这两个f[i-1]，选第i个和不选第i个可能会出现同样的子序列。那么重复的最后一定是s[i]。设上一个s[i]字母出现在k位置，那么f[k-1]这些串，后面跟s[k]和s[i]，结果在两个f[i-1]中被算了两次！所以减去f[k-1]即可。时间复杂度O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int P = 1000000007;
int last[26];
int f[2111];

class Solution {
public:
    int distinctSubseqII(string S) {
        for (int i = 0; i < 26; i++) last[i] = -1;
        f[0] = 2;
        last[S[0] - 'a'] = 0;
        for (int i = 1; i < S.length(); i++) {
            f[i] = f[i-1] * 2 % P;
            if (last[S[i] - 'a'] >= 0) {
                f[i] -= last[S[i] - 'a'] == 0 ? 1 : f[last[S[i] - 'a'] - 1];
                if (f[i] < 0) f[i] += P;
            }
            last[S[i] - 'a'] = i;
        }
        int ans = f[S.length() - 1] - 1;
        if (ans < 0) ans += P;
        return ans;
    }
};
Algorithm

Leetcode 1172. Dinner Plate Stacks

题目

https://leetcode.com/problems/dinner-plate-stacks/

做法

用一个stack的数组维护所有栈，一个set维护所有非空的栈，一个set维护所有没有满的栈即可。每次操作时间复杂度O(logn)。

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
#include <iostream>
#include <set>
#include <stack>
#include <vector>

using namespace std;

const int kMaxIndex = 200011;

class DinnerPlates {
public:
  int capacity;
  stack<int> stacks[kMaxIndex];
  set<int> not_empty_stacks;
  set<int> not_full_stacks;
  int now_max;

  DinnerPlates(int capacity) {
    this->capacity = capacity;
    now_max = -1;
  }

  void push(int val) {
    if (not_full_stacks.empty()) {
      now_max++;
      not_full_stacks.insert(now_max);
    }
    int id = *not_full_stacks.begin();
    if (stacks[id].empty()) {
      not_empty_stacks.insert(id);
    }
    stacks[id].push(val);
    if (stacks[id].size() == capacity) {
      not_full_stacks.erase(id);
    }
  }

  int pop() {
    if (not_empty_stacks.empty()) return -1;
    int id = *not_empty_stacks.rbegin();
    int val = stacks[id].top();
    if (stacks[id].size() == capacity) {
      not_full_stacks.insert(id);
    }
    stacks[id].pop();
    if (stacks[id].empty()) {
      not_empty_stacks.erase(id);
    }
    return val;
  }

  int popAtStack(int index) {
    if (stacks[index].empty()) return -1;
    int val = stacks[index].top();
    if (stacks[index].size() == capacity) {
      not_full_stacks.insert(index);
    }
    stacks[index].pop();
    if (stacks[index].empty()) {
      not_empty_stacks.erase(index);
    }
    return val;
  }
};

不过不知道为啥跑得好慢，交了几次过了，faster than 5%。。

Algorithm

Kick Start 2019 Round E

https://codingcompetitions.withgoogle.com/kickstart/archive/2019

这场最后40分钟才想起来参加。。。过了T1，然后T3写错了只过了小数据。太菜了。这轮的题相对来说很简单，AK的人也不少。

T1 Cherries Mesh (9pts, 13pts)

题意

有一个n个点的完全图，其中给定的m条边的长度为1，其他边长度为2。要删掉一些边把这个图变成一棵树。求树上边的长度之和的最小值。n, m <= 10^5。

做法

显然，只需知道m条边时点的联通情况，联通块内的用长度为1的连接，联通块之间用长度为2的连接即为答案。用并查集维护即可。时间复杂度O(n+m)。

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
#include <iostream>
#include <vector>
#include <map>

using namespace std;

vector<int> fa(101111);

int GetFather(int x) {
  if (fa[x] == x) return x;
  return fa[x] = GetFather(fa[x]);
}

void Union(int x, int y) {
  x = GetFather(x);
  y = GetFather(y);
  fa[x] = y;
}

int main() {
  int T;
  cin >> T;
  for (int test = 1; test <= T; test++) {
    int N, M;
    cin >> N >> M;
    for (int i = 1; i <= N; i++) fa[i] = i;
    for (int i = 1; i <= M; i++) {
      int x, y;
      cin >> x >> y;
      Union(x, y);
    }
    map<int, bool> go;
    for (int i = 1; i <= N; i++) go[GetFather(i)] = true;
    int num = go.size();
    int ans = N - num + (num - 1) * 2;
    cout << "Case #" << test << ": " << ans << endl;
  }
  return 0;
}

T2 Code-Eat Switcher (11pts, 25pts)

题意

有n个时间段，每个长度为1，在时间段i做x可以获得ai的价值（事情x的价值），做y可以获得bi的价值（事情y的价值）。每个时间段可以按在[0, 1]之间划分，即可以一段做x，一段做y，获得的价值即乘以相应的比率。m个询问A, B，每次询问是否存在一种安排方式使得x的价值不少于A，且y的价值不少于B。n,m<=10^5。

做法

显然，一般来说，某个时间段最好只干一种事情，获得的收益才最大。除了最后一个事情需要a和b划分一下之外。按照ai/bi排序，那么越考前的时间段做x比较好，越靠后的时间段做y比较好。因此维护一个a的前缀和，一个b的后缀和，每次查询A和B，在其中二分查找A的位置，将最后一个按比例划分，然后判断后面的B够不够即可。时间复杂度O(nlogn)。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const double eps = 1e-6;

int D, S;
vector<pair<int, int>> slots, days;

string Work() {
  sort(slots.begin(), slots.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
    //  a.x / a.y > b.x / b.y
    return a.first * b.second > b.first * a.second;
  });
  vector<int> sum_x(S);
  sum_x[0] = slots[0].first;
  for (int i = 1; i < S; i++) {
    sum_x[i] = sum_x[i - 1] + slots[i].first;
  }
  vector<int> rev_sum_y(S);
  rev_sum_y[S - 1] = slots[S - 1].second;
  for (int i = S - 2; i >= 0; i--) {
    rev_sum_y[i] = rev_sum_y[i + 1] + slots[i].second;
  }
  string ans;
  for (const pair<int, int>& day : days) {
    int X = day.first, Y = day.second;
    int l = 0, r = S - 1, res = -1;
    while (l <= r) {
      int mid = (l + r) / 2;
      if (sum_x[mid] >= X) {
        res = mid;
        r = mid - 1;
      }
      else {
        l = mid + 1;
      }
    }
    if (res == -1) {
      ans += 'N';
      continue;
    }
    int x_now = (res == 0) ? 0 : sum_x[res - 1];
    int y_now = (res == S - 1) ? 0 : rev_sum_y[res + 1];
    double x_ratio = double(X - x_now) / slots[res].first;
    double y_ratio = 1 - x_ratio;
    if (y_now + y_ratio * slots[res].second > Y - eps) {
      ans += 'Y';
    }
    else {
      ans += 'N';
    }
  }
  return ans;
}

int main() {
  int T;
  cin >> T;
  for (int test = 1; test <= T; test++) {
    cin >> D >> S;
    slots.resize(S);
    for (int i = 0; i < S; i++) {
      cin >> slots[i].first >> slots[i].second;
    }
    days.resize(D);
    for (int i = 0; i < D; i++) {
      cin >> days[i].first >> days[i].second;
    }
    string ans = Work();
    cout << "Case #" << test << ": " << ans << endl;
  }
  return 0;
}

T3

题意

给定区间[L, R]，求区间中满足以下条件的x的个数：x的偶数因数的个数与x的奇数因数的个数之差的绝对值<=2。L, R<= 10^9 且 R - L<=10^5。

做法

因为区间长度只有10^5，故枚举区间中的每一个数判断即可。设$x=p_1^{q_1}\times p_2^{q_2}\times…\times p_k^{q_k}$，那么x的因数个数即为$(q_1+1)\times(q_2+1)\times…\times(q_k+1)$。而奇数因数的个数，只需将2的那个指数项去掉即可。偶数因数的个数用总因数个数减奇数因数个数得到。因此，首先预处理0至$\sqrt{R}$之间的质数，然后分解区间中的每一个x判断即可。

比赛时我这样交上TLE。我们可以计算一下，$\sqrt{10^9}\approx35000$，小于它的质数个数约有$\frac{35000}{ln(35000)}\approx3000$个。由于区间长度为100000，乘以3000确实有点大。

如何优化呢？由于我们只需要判断奇偶因数只差的绝对值。我们把2的次数单独拿出来，即$x=2^a\times p_1^{q_1}\times p_2^{q_2}…\times p_k^{q_k}$。其中$a$可能等于0。设$(q_1+1)\times(q_2+1)\times…\times(q_k+1)=M$，那么总因数个数即为$(a+1)\times M$，奇数因数个数为$M$，偶数因数个数为$a\times M$，两者只差的绝对值为$|a-1|\times M$。

  • 如果$a=0$，即x是一个奇数，两者之差的绝对值即为M。
  • 如果$a=1$，结果为0，一定满足条件。
  • 如果$a\geq 2$，结果为$(a-1)\times M$。

以上结果可以看出，我们并不需要知道$M$是几，只需要知道$M$是不是大于2就可以了！所以在质因数分解时，如果$M>2$就break。加入这个优化后就可以通过了。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <vector>

using namespace std;

vector<int> primes;

void Prepare() {
  vector<bool> is_prime(40000);
  is_prime[2] = true;
  for (int i = 3; i < 40000; i++) is_prime[i] = true;
  for (int i = 2; i < 40000; i++) {
    if (is_prime[i]) {
      for (int j = i + i; j < 40000; j += i) {
        is_prime[j] = false;
      }
    }
  }
  for (int i = 3; i < 40000; i++) {
    if (is_prime[i]) primes.push_back(i);
  }
}

void Factorize(int x, int& a, int& M) {
  a = 0;
  while ((x & 1) == 0) {
    x >>= 1;
    a++;
  }
  int now = x;
  M = 1;
  for (int prime : primes) {
    if (prime * prime > x) break;
    if (now % prime == 0) {
      int cnt = 0;
      while (now % prime == 0) {
        now /= prime;
        cnt++;
      }
      M *= (cnt + 1);
      if (M > 2) break;
    }
  }
  if (now > 1) M *= 2;
}

bool Check(int x) {
  int a, M;
  Factorize(x, a, M);
  if (a == 0) {
    return M <= 2;
  }
  else if (a == 1) {
    return true;
  }
  else {
    return (a - 1) * M <= 2;
  }
}

int Work(int L, int R) {
  int ans = 0;
  for (int i = L; i <= R; i++) {
    if (Check(i)) ans++;
  }
  return ans;
}

int main() {
  Prepare();
  int T;
  cin >> T;
  for (int test = 1; test <= T; test++) {
    int L, R;
    cin >> L >> R;
    int ans = Work(L, R);
    cout << "Case #" << test << ": " << ans << endl;
  }
  return 0;
}
Algorithm

2016保研题：魔法学校

题目

做法

因为要维护的是若干时间区间上的最大值，而且每一个时间点也是另一个学号序列的区间修改。直觉上想用可持久化线段树套个东西来解决。不过最大值这个东西没法维护，想了很长时间也没想出来。

跟别人讨论后感觉这个题只能用莫队算法。可以参考 https://zhuanlan.zhihu.com/p/25017840 。用线段树维护每个学生收到的短信数量。每次端点的移动耗时O(logn)。总时间复杂度O($n\sqrt{n}\log_2{n}$)。

Algorithm

Kick Start 2019 Round A

https://codingcompetitions.withgoogle.com/kickstart/archive/2019

没参加比赛，拿题来练了一下。感觉这题考场上也就能做前两道。

T1 Training

题目

给N个数，你可以花1块钱给一个数加1。要从中选出K个相同的数。求最少花多少钱。$N<=10^5$。

做法

显然要先排序，那么我们要选的K个数一定是排好序后连续的K个。枚举并用前缀和即可。时间复杂度O(nlogn)。

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
#include <cstdio>
#include <algorithm>

using namespace std;
const int maxN = 100005;

int T, N, P;
int a[maxN], sum[maxN];

int main() {
    scanf("%d", &T);
    for (int tt = 1; tt <= T; tt++) {
        scanf("%d%d", &N, &P);
        for (int i = 1; i <= N; i++) scanf("%d", &a[i]);
        sort(a+1, a+N+1);
        for (int i=1;i<=N;i++)
            sum[i] = sum[i-1] + a[i];
        int ans = 1000000000 + 1;
        for (int i=1;i<=N;i++) {
            int r = i;
            int l = r - P + 1;
            if (l < 1) continue;
            ans = min(ans, a[r] * P - sum[r] + sum[l-1]);
        }
        printf("Case #%d: %d\n", tt, ans);
    }
    return 0;
}

T2 Parcels

题目

给定一个$m\times n$的01矩阵。一个矩阵的分数k定义为，矩阵中的所有点到其最近的1的距离的最大值。这里的距离为曼哈顿距离（|r1 - r2| + |c1 - c2|）。现在可以将矩阵中的某个0改成1，求矩阵分数k的最小值。m, n <= 250。

做法

最大值最小 -> 二分答案。二分k，那么只需对于每一个位置(i, j)，距离它k以内是否有1，如果没有的话将其放到一个数组里，最后判断数组中的位置是否可以修改一个1搞定。

那么如何判断距(i, j)最近的1的距离呢？注意到这是曼哈顿距离，所以可以用动态规划。设f[i][j]表示(i, j)的左上角这个矩阵中最近的1的距离。那么f[i][j] = min(f[i-1][j]+1, f[i][j-1]+1)。对四个方向各做一次dp即可。

所以问题就只剩下给定一些点，要判断是否能选择一个位置改成1，使得这些点到该位置的最大值<=k。同样dp一遍即可，不过这次是维护最大值。

时间复杂度O($n^2log_2n$)。如果我们暴力枚举k的话是O($n^3$)，也能通过。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

#define inf 999999999

int m, n;
bool board[255][255], need[255][255];
int f[4][255][255], g[4][255][255];

void Prepare() {
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      f[0][i][j] = board[i][j] ? 0 : inf;
      if (i > 0) f[0][i][j] = min(f[0][i][j], f[0][i - 1][j] + 1);
      if (j > 0) f[0][i][j] = min(f[0][i][j], f[0][i][j - 1] + 1);
    }
  }
  for (int i = 0; i < m; i++) {
    for (int j = n - 1; j >= 0; j--) {
      f[1][i][j] = board[i][j] ? 0 : inf;
      if (i > 0) f[1][i][j] = min(f[1][i][j], f[1][i - 1][j] + 1);
      if (j < n - 1) f[1][i][j] = min(f[1][i][j], f[1][i][j + 1] + 1);
    }
  }
  for (int i = m - 1; i >= 0; i--) {
    for (int j = 0; j < n; j++) {
      f[2][i][j] = board[i][j] ? 0 : inf;
      if (i < m - 1) f[2][i][j] = min(f[2][i][j], f[2][i + 1][j] + 1);
      if (j > 0) f[2][i][j] = min(f[2][i][j], f[2][i][j - 1] + 1);
    }
  }
  for (int i = m - 1; i >= 0; i--) {
    for (int j = n - 1; j >= 0; j--) {
      f[3][i][j] = board[i][j] ? 0 : inf;
      if (i < m - 1) f[3][i][j] = min(f[3][i][j], f[3][i + 1][j] + 1);
      if (j < n - 1) f[3][i][j] = min(f[3][i][j], f[3][i][j + 1] + 1);
    }
  }
}

bool Check(int dist) {
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      int tmp = min(min(f[0][i][j], f[1][i][j]), min(f[2][i][j], f[3][i][j]));
      need[i][j] = tmp > dist;
    }
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      g[0][i][j] = need[i][j] ? 0 : -inf;
      if (i > 0) g[0][i][j] = max(g[0][i][j], g[0][i - 1][j] + 1);
      if (j > 0) g[0][i][j] = max(g[0][i][j], g[0][i][j - 1] + 1);
    }
  }
  for (int i = 0; i < m; i++) {
    for (int j = n - 1; j >= 0; j--) {
      g[1][i][j] = need[i][j] ? 0 : -inf;
      if (i > 0) g[1][i][j] = max(g[1][i][j], g[1][i - 1][j] + 1);
      if (j < n - 1) g[1][i][j] = max(g[1][i][j], g[1][i][j + 1] + 1);
    }
  }
  for (int i = m - 1; i >= 0; i--) {
    for (int j = 0; j < n; j++) {
      g[2][i][j] = need[i][j] ? 0 : -inf;
      if (i < m - 1) g[2][i][j] = max(g[2][i][j], g[2][i + 1][j] + 1);
      if (j > 0) g[2][i][j] = max(g[2][i][j], g[2][i][j - 1] + 1);
    }
  }
  for (int i = m - 1; i >= 0; i--) {
    for (int j = n - 1; j >= 0; j--) {
      g[3][i][j] = need[i][j] ? 0 : -inf;
      if (i < m - 1) g[3][i][j] = max(g[3][i][j], g[3][i + 1][j] + 1);
      if (j < n - 1) g[3][i][j] = max(g[3][i][j], g[3][i][j + 1] + 1);
    }
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      int tmp = max(max(g[0][i][j], g[1][i][j]), max(g[2][i][j], g[3][i][j]));
      if (tmp <= dist) return true;
    }
  }
  return false;
}

int Work() {
  cin >> m >> n;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      char ch = getchar();
      while (ch != '0' && ch != '1') ch = getchar();
      board[i][j] = (ch == '1');
    }
  }
  Prepare();
  int l = 0, r = m + n, res = m + n;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (Check(mid)) {
      res = mid;
      r = mid - 1;
    }
    else {
      l = mid + 1;
    }
  }
  return res;
}

int main() {
  int T;
  cin >> T;
  for (int i = 1; i <= T; i++) {
    int ans = Work();
    cout << "Case #" << i << ": " << ans << endl;
  }
  return 0;
}

T3 Contention

这个题是真的不会。看了题解才明白。

题目

有N个位置，编号1..N。有Q个订单，每个订单是一个区间[Li, Ri]，其将占据[Li, Ri]间所有没有被占据的位置。你可以任意安排订单来的顺序，求最大的k，使得每一个订单都至少占据k个位置。N<=1000000, Q<=30000。

做法

任意安排顺序，那该怎么安排呢？比如说我们首先处理第i个订单，那么后面怎么办？这个订单所占据的位置会影响后面的订单。

这里用到了正难则反的思想，我们到这考虑行不行呢？假设最后处理的是第i个订单，那么它就不影响它前面的订单了，并且无论它前面的订单是按什么顺序排的，订单i能占据的位置是一定的，因为已经被占据的位置就是它前面的区间的并集。

考虑从后往前确定订单的顺序。这里还有一个贪心：每次都选那个放到最后能占据的位置最多的订单。

为什么呢？首先，因为我们要求的是所有订单占据的位置的最小值作为k，所以直观上来说，我们先保证最后的这个尽量大就行。下面用交换法证明：假设这样得到的答案顺序是[…, j, i, …]。显然j之前和i之后的订单占据多少位置与i和j的顺序没有关系。假设订单i能占据x0个位置，订单j能占据y0个位置。那么这样更新是ans = min(ans, min(x0, y0))。如果我们交换i和j的位置，那么顺序变成[…, i, j, …]，设订单i能占据x1个位置，订单j能占据y1个位置。这样更新答案就变成了ans = min(ans, min(x1, y1))。根据我们贪心的顺序，一定有x0 >= y1。并且，由于下面一种情况j之前多了一个i，故一定有y0 >= y1。因此，min(x0, y0) >= y1 >= min(x1, y1)。综上，交换相邻的i和j不会使答案更优。对于任意序列a[1..N]，将贪心得到的序列使用类似冒泡排序的方法，通过交换相邻的两个，最终得到序列a。因此，任意一个序列都不会比贪心得到的序列更优。

以上证明了贪心算法的正确性。那么我们从后往前确定订单顺序。每一次循环，我们需要确定哪一个订单放到最后能占据的位置最多，然后将这个订单放到最后并删除，同时更新答案。这里容易想到用数组num[1..N]来维护每一个位置上剩下的还有多少个订单。开始时先通过num[L]++, num[R+1]–，最后求前缀和的方式预处理出来。这样对于订单i，其能占据的位置就是[Li, Ri]之间1的个数。假设我们选定了订单k，那么我们需要将num[Lk, Rk]之间的数减1。如果num[i]被减成1了，我们就需要把占据i的那个区间上1的个数加1。用一个数组cnt维护每一个订单的区间内有多少个1。总结一下，预处理部分我们要做的有：

  1. 求出初始num[1..N]数组。
  2. 求出初始cnt[1..Q]数组。

每一次循环我们需要做的事情有：

  1. 选择cnt最大的订单i。
  2. 将num[Li..Ri]减1。
  3. 如果num[j]被减成1了，就将j位置对应订单k的cnt加1。
  4. 删除订单i。

暴力做，时间复杂度O(NQ)，可以过小数据。

容易想到用线段树维护。区间修改通过懒标记处理。因为我们要找1，所以我们维护区间最小值。如果发现某个位置j被减成1了，那么将其对应的订单cnt[k]加1即可，然后将其改成inf。这样就可以方便地知道是否有1的位置。因为每个位置只会变成1一次，所以这部分的复杂度为O(nlogn)。怎样找到位置j对应的订单k呢？显然可以在线段树的每个节点上用一个set记录覆盖这个节点的订单id的集合，开始时将区间全部插入，每次询问查一下即可。如果用unordered_set的话这部分就可以不增加复杂度。删除订单i，区间删除unordered_set中的值即可。cnt用一个set维护，可以方便地修改并查询最大值。这样总时间复杂度为O(NlogN)。空间上因为我们用了线段树套set，每一个订单会出现在O(logN)个节点上，故空间复杂度为O(NlogN)。

这样交上去会TLE，因为N比较大，并且我们的算法常数也很大。容易发现Q比较小，因此可以离散化，将位置数量变为O(Q)级别，再使用上面的方法时间复杂度为O(QlogQ)。

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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <unordered_set>
#include <map>

using namespace std;

#define inf 999999999

class Node {
public:
  Node *left, *right;
  int l, r;
  int tag;
  int min_val;
  unordered_set<int> S;

  explicit Node(int l_, int r_) {
    left = right = nullptr;
    l = l_, r = r_;
    tag = 0;
  }

  void Subtract() {
    tag++;
    min_val--;
  }

  void PushDown() {
    if (tag == 0) return;
    if (left != nullptr) {
      left->tag += tag;
      left->min_val -= tag;
    }
    if (right != nullptr) {
      right->tag += tag;
      right->min_val -= tag;
    }
    tag = 0;
  }

  void Update() {
    min_val = min(left->min_val, right->min_val);
  }
};

Node* BuildTree(const vector<int>& a, int l, int r) {
  Node* v = new Node(l, r);
  if (l == r) {
    v->min_val = a[l];
    return v;
  }
  int mid = (l + r) / 2;
  v->left = BuildTree(a, l, mid);
  v->right = BuildTree(a, mid + 1, r);
  v->Update();
  return v;
}

void Insert(Node* v, int ww, int ee, int x) {
  if (ww <= v->l && v->r <= ee) {
    v->S.insert(x);
    return;
  }
  int mid = (v->l + v->r) / 2;
  if (ww <= mid) Insert(v->left, ww, ee, x);
  if (ee > mid) Insert(v->right, ww, ee, x);
}

void Remove(Node* v, int ww, int ee, int x) {
  if (ww <= v->l && v->r <= ee) {
    v->S.erase(x);
    return;
  }
  int mid = (v->l + v->r) / 2;
  if (ww <= mid) Remove(v->left, ww, ee, x);
  if (ee > mid) Remove(v->right, ww, ee, x);
}

int FindId(Node* v, int pos) {
  if (v->l <= pos && pos <= v->r && v->S.size() == 1) {
    return *(v->S.begin());
  }
  int mid = (v->l + v->r) / 2;
  if (pos <= mid) return FindId(v->left, pos);
  else return FindId(v->right, pos);
}

void Subtract(Node* v, int ww, int ee) {
  if (ww <= v->l && v->r <= ee) {
    v->Subtract();
    return;
  }
  v->PushDown();
  int mid = (v->l + v->r) / 2;
  if (ww <= mid) Subtract(v->left, ww, ee);
  if (ee > mid) Subtract(v->right, ww, ee);
  v->Update();
}

int FindMinValuePosition(Node* v) {
  if (v->l == v->r) {
    return v->l;
  }
  v->PushDown();
  if (v->left->min_val == v->min_val) return FindMinValuePosition(v->left);
  else return FindMinValuePosition(v->right);
}

void SetValue(Node* v, int pos, int val) {
  if (v->l == v->r) {
    v->min_val = val;
    return;
  }
  v->PushDown();
  int mid = (v->l + v->r) / 2;
  if (pos <= mid) SetValue(v->left, pos, val);
  else SetValue(v->right, pos, val);
  v->Update();
}

void ClearTrash(Node* v) {
  if (v->left) ClearTrash(v->left);
  if (v->right) ClearTrash(v->right);
  delete v;
}

int Work(int N, int Q, const vector<pair<int, int>>& bookings) {
  set<int> a;
  a.insert(1);
  a.insert(N);
  for (int i = 0; i < Q; i++) {
    if (bookings[i].first > 1) a.insert(bookings[i].first - 1);
    a.insert(bookings[i].first);
    if (bookings[i].first < N) a.insert(bookings[i].first + 1);
    if (bookings[i].second > 1) a.insert(bookings[i].second - 1);
    a.insert(bookings[i].second);
    if (bookings[i].second < N) a.insert(bookings[i].second + 1);
  }
  int M = a.size();
  int last = 0, t = 0;
  vector<int> cover(M + 1);
  map<int, int> go;
  for (int x : a) {
    t++;
    cover[t] = x - last;
    last = x;
    go[x] = t;
  }
  vector<int> num(M + 2);
  vector<pair<int, int>> new_bookings = bookings;
  for (pair<int, int>& booking : new_bookings) {
    booking.first = go[booking.first];
    booking.second = go[booking.second];
    num[booking.first]++;
    num[booking.second + 1]--;
  }
  for (int i = 1; i <= M; i++) {
    num[i] += num[i - 1];
  }
  for (int i = 1; i <= M; i++) {
    if (num[i] == 0) {
      num[i] = inf;
    }
  }
  Node* root = BuildTree(num, 1, M);
  for (int i = 0; i < Q; i++) {
    Insert(root, new_bookings[i].first, new_bookings[i].second, i);
  }
  vector<int> cnt(Q);
  for (int i = 1; i <= M; i++) {
    if (num[i] == 1) {
      int id = FindId(root, i);
      cnt[id] += cover[i];
      SetValue(root, i, inf);
    }
  }
  set<pair<int, int>> cnt_to_id;
  for (int i = 0; i < Q; i++) {
    cnt_to_id.insert(make_pair(cnt[i], i));
  }
  int ans = inf;
  for (int i = 0; i < Q; i++) {
    int id = cnt_to_id.rbegin()->second;
    cnt_to_id.erase(make_pair(cnt[id], id));
    ans = min(ans, cnt[id]);
    Remove(root, new_bookings[id].first, new_bookings[id].second, id);
    Subtract(root, new_bookings[id].first, new_bookings[id].second);
    while (root->min_val == 1) {
      int pos = FindMinValuePosition(root);
      SetValue(root, pos, inf);
      int now_id = FindId(root, pos);
      cnt_to_id.erase(make_pair(cnt[now_id], now_id));
      cnt[now_id] += cover[pos];
      cnt_to_id.insert(make_pair(cnt[now_id], now_id));
    }
  }
  ClearTrash(root);
  return ans;
}

int main() {
  int T;
  cin >> T;
  for (int test_id = 1; test_id <= T; test_id++) {
    int N, Q;
    cin >> N >> Q;
    vector<pair<int, int>> bookings(Q);
    for (int i = 0; i < Q; i++) {
      cin >> bookings[i].first >> bookings[i].second;
    }
    int k = Work(N, Q, bookings);
    cout << "Case #" << test_id << ": " << k << endl;
  }

  return 0;
}

总结

这三个题一个比一个难，尤其是第三题，考场上有人能做出来也很厉害了，光贪心我就想不出来。还要努力啊。

Algorithm

Leetcode 1163. Last Substring in Lexicographical Order

题目

https://leetcode.com/problems/last-substring-in-lexicographical-order/

给定一个字符串s，求s的所有子串中字典序最大的那一个。s长度<=400000。

分析

首先可以发现，s[l, n-1]的字典序一定比s[l, r]大。因此我们只需在s的n个后缀中找字典许最大的即可。

说到后缀自然我当时想到的是后缀数组。倍增求后缀数组可以参考 https://blog.csdn.net/Sunshine_cfbsl/article/details/52190433 ，时间复杂度O(nlogn)。这种方法我交上去超时了。不过代码还是放一下：

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
65
66
class SuffixArray {
public:
  int n;
  vector<int> rank, sa, height;

  void work(const vector<pair<pair<int, int>, int>>& a) {
    vector<vector<pair<pair<int, int>, int>>> go(n);
    vector<pair<pair<int, int>, int>> now;
    for (auto tmp : a) {
      if (tmp.first.second == -1) now.push_back(tmp);
      else go[tmp.first.second].push_back(tmp);
    }
    for (int i = 0; i < n; i++) {
      for (auto tmp : go[i]) now.push_back(tmp);
    }
    for (int i = 0; i < n; i++) go[i].clear();
    for (auto tmp : now)
      go[tmp.first.first].push_back(tmp);
    now.clear();
    for (int i = 0; i < n; i++) {
      for (auto tmp : go[i]) now.push_back(tmp);
    }
    rank[now[0].second] = 0;
    for (int i = 1, p = 0; i < n; i++) {
      if (now[i].first != now[i-1].first) p++;
      rank[now[i].second] = p;
    }
  }

  void GetSuffixArray(const string& s) {
    n = s.length();
    rank.resize(n);
    sa.resize(n);
    height.resize(n);
    vector<pair<pair<int, int>, int>> a(n);
    for (int i = 0; i < n; i++)  a[i] = make_pair(make_pair(s[i], -1), i);
    sort(a.begin(), a.end());
    rank[a[0].second] = 0;
    for (int i = 1, p = 0; i < n; i++) {
      if (a[i].first != a[i-1].first) p++;
      rank[a[i].second] = p;
    }
    for (int k = 1; k < n; k <<= 1) {
      for (int i = 0; i < n; i++) a[i] = make_pair(make_pair(rank[i], i + k >= n ? -1 : rank[i + k]), i);
      work(a);
    }
    for (int i = 0; i < n; i++) sa[rank[i]] = i;
    for (int i = 0, p = 0; i < n; i++)  {
      if (rank[i] == 0) continue;
      int a = i, b = sa[rank[i] - 1];
      while (a + p < n && b + p < n && s[a + p] == s[b + p]) p++;
      height[rank[i]] = p;
      if (p > 0) p--;
    }
  }
};

class Solution {
public:
    string lastSubstring(string s) {
        SuffixArray sa;
        sa.GetSuffixArray(s);
        int t = sa.sa[sa.n - 1];
        return s.substr(t);
    }
};

后缀数组写的很傻，尤其是基数排序那里。实在是没法看。。。

做法

那么有没有O(n)的方法呢？我想了一会琢磨了一个乱七八糟的算法。首先，我们可以把所有第一个字母最大的后缀作为candidates。然后，比较candidates的第二个字母，把第二个字母也最大的放到新的candidates中。这样一直比较，知道candidates中只剩下一个后缀即可。

但是这种方法时间上不能保证，比如”aaaaaa…”，就会变成O(n^2)。这时需要利用一下candidates的性质：candidates中的后缀一定比不在candidates中的后缀大。对于candidates中的两个后缀i和j，i < j，且他们前k个字母都相同，s[i, i+k-1] = s[j, j+k-1]，如果i+k-1=j，也就是说长度k使得两个后缀重叠了，会发生很神奇的现象。由于我们需要比较的是s[i, n-1]和s[j, n-1]这两个后缀，由于其前k个相同，那么等价于比较s[i+k-1, n-1]和s[j+k-1, n-1]这两个后缀，也就是比较s[j, n-1]和s[j+k-1, n-1]。由于前面说过，candidates中的后缀一定比不在candidates中的后缀大，所以当j+k-1不是candidates时，s[j, n-1] > s[j+k-1, n-1]，也就是s[i, n-1] > s[j, n-1]。那么j就可以从candidates中删除。如果j+k-1也在candidates中，那么套用上面的理论，j+k-1也可以删除，从而j也可以删除。也就是说，如果我们在比较所有candidates的第k个字母时，如果发现两个candidates出现了重叠，那么前面的就可以把后面的那个吃掉。这样可以做了。代码如下：

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
class Solution {
public:
  string lastSubstring(string s) {
    int n = s.size();
    vector<bool> flag(n);
    vector<int> num(26);
    for (int i = 0; i < n; i++) num[s[i] - 'a']++;
    vector<int> now;
    for (int k = 25; k >= 0; k--) {
      if (num[k] > 0) {
        for (int i = 0; i < n; i++) {
          if (s[i] - 'a' == k) {
            flag[i] =true;
            now.push_back(i);
          }
        }
        break;
      }
    }
    for (int len = 2; len <= n; len++) {
      if (now.size() == 1) break;
      for (int i = 0; i < 26; i++) num[i] = 0;
      for (int pos : now) {
        int t = pos + len - 1;
        if (t >= n) continue;
        num[s[t] - 'a']++;
      }
      for (int k = 25; k >= 0; k--) {
        if (num[k] > 0) {
          for (int pos : now) {
            int t = pos + len - 1;
            if (t >= n) {
              flag[pos] = false;
              continue;
            };
            flag[t] = false;
            if (s[t] - 'a' != k) flag[pos] = false;
          }
          break;
        }
      }
      vector<int> new_now;
      for (int pos : now) {
        if (flag[pos]) new_now.push_back(pos);
      }
      now = new_now;
    }
    return s.substr(now[0]);
  }
};

下面分析复杂度（其实做的时候没想复杂度）。对于开始时的所有candidates，它最多会被遍历d次，d为它之前的那个candidates的距离（先不考虑第一个candidates）。这些距离之和不超过n，再加上第一个candidates最多被遍历n次，故时间复杂度为O(n)。

Algorithm

Leetcode 1074. Number of Submatrices That Sum to Target

题目

https://leetcode.com/problems/number-of-submatrices-that-sum-to-target/

给定一个m * n的矩阵，求有多少个子矩阵，满足其中元素的和等于target。m, n <= 300。

做法

经典题。首先区间求和一定要用前缀和。枚举子矩阵的左右边界[l, r]，那么我们只需要处理[l, r]中间的这一块。这部分的前缀和可以预处理出来。然后用一个hash map统计即可。如果hash map是O(1)的，那么算法时间复杂度为O($n^3$)。

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
class Solution {
public:
    int Count(const vector<int>& sum, int target) {
        unordered_map<int, int> record;
        record[0] = 1;
        int res = 0;
        for (int i = 0; i < sum.size(); i++) {
            res += record[sum[i] - target];
            record[sum[i]]++;
        }
        return res;
    }
    
    int numSubmatrixSumTarget(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> row_sum(m);
        for (int i = 0; i < m; i++) {
            row_sum[i].resize(n);
            row_sum[i][0] = matrix[i][0];
            for (int j = 1; j < n; j++) {
                row_sum[i][j] = row_sum[i][j - 1] + matrix[i][j];
            }
        }
        int ans = 0;
        for (int l = 0; l < n; l++) {
            for (int r = l; r < n; r++) {
                vector<int> sum(m);
                sum[0] = row_sum[0][r] - (l == 0 ? 0 : row_sum[0][l - 1]);
                for (int i = 1; i < m; i++) {
                    sum[i] = sum[i - 1] + row_sum[i][r] - (l == 0 ? 0 : row_sum[i][l - 1]);
                }
                ans += Count(sum, target);
            }
        }
        return ans;
    }
};