problem1 link
首先计算任意两点的距离。然后枚举选出的集合中的两个点，判断其他点是否可以即可。
problem2 link
假设字符串为$s$，长度为$n$。那么对于$SA$中的两个排名$SA_{i},SA_{i+1}$来说，应该尽量使得$s[SA_{i}]=s[SA_{i+1}]$。如果这个满足的话，那么需要两个后缀满足$s[SA_{i}+1\sim n-1]<s[SA_{i+1}+1\sim n-1]$,设他们的排名分别为$SA_{r},SA_{k}$，也就是说$r<k$即可。
problem3 link
code for problem1
#include <algorithm>
#include <unordered_set>
#include <vector>
class Egalitarianism3 {
public:
int maxCities(int n, const std::vector<int> &a, const std::vector<int> &b,
const std::vector<int> &len) {
if (n == 1) {
return 1;
}
std::vector<std::vector<int>> g(n, std::vector<int>(n, -1));
for (int i = 0; i < n - 1; ++i) {
g[a[i] - 1][b[i] - 1] = g[b[i] - 1][a[i] - 1] = len[i];
}
for (int i = 0; i < n; ++i) {
g[i][i] = 0;
}
for (int i = 0; i < n; ++i) {
for (int u = 0; u < n; ++u) {
if (g[u][i] != -1) {
for (int v = 0; v < n; ++v) {
if (g[i][v] != -1) {
if (g[u][v] == -1 || g[u][v] > g[u][i] + g[i][v]) {
g[u][v] = g[u][i] + g[i][v];
}
}
}
}
}
}
auto Compute = [&](int s, int t) {
std::unordered_set<int> all;
all.insert(s);
all.insert(t);
const int d = g[s][t];
for (int i = 0; i < n; ++i) {
if (all.find(i) == all.end()) {
bool tag = true;
for (auto e : all) {
if (g[i][e] != d) {
tag = false;
break;
}
}
if (tag) {
all.insert(i);
}
}
}
return static_cast<int>(all.size());
};
int result = 0;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
result = std::max(result, Compute(i, j));
}
}
return result;
}
};
code for problem2
#include <vector>
class SuffixArrayDiv1 {
public:
int minimalCharacters(const std::vector<int> &SA) {
int n = static_cast<int>(SA.size());
std::vector<int> s(n + 1, -1);
for (int i = 0; i < n; ++i) {
s[SA[i]] = i;
}
int result = 1;
for (int i = 0; i + 1 < n; ++i) {
if (s[SA[i] + 1] > s[SA[i + 1] + 1]) {
++result;
}
}
return result;
}
};
code for problem3
原文：https://www.cnblogs.com/jianglangcaijin/p/9973151.html