problem1 link
将限制按照$x$排序。那么$[upTo_{i}+1,upTo_{i+1}]$中数字个数为$quantity_{i+1}-quantity_{i}$。然后进行动态规划。$f[i][j]$表示考虑了前$i$个区间的限制，其中偶数的个数为$j$时是否成立。
problem2 link
按照如下的规则构造这个图：首先$[1,n]$区间每个节点是单独的一个分量，每次将该区间分为两半。这两半分别需要$k-1$次。最后将这两部分连在一起。
problem3 link
如果出现这样一种情况，就是需要若干种字母去匹配另外若干种字母时，它们一定是多对一或者一对多，而不会出现多对多的情况。
假设字母$a,b,c,d$分别有$3,5,7,1$个。如果$a,b$去匹配$c,d$，不如先让$a,b$匹配一对，$c,d$匹配一对，然后２个$a$，４个$b$去匹配6个$c$。
所以如果前面出现大于一种字母有剩余的话，可以记录最后抵消它们的是哪一种字母即可。
动态规划的方程为$f[i][j][k][t]$表示到第$i$个为止，还剩下$j$个需要与后面的进行配对，其中前面剩余的未参与配对的为$t$个，$k$指示了前面剩余的$j$个是一种还是多种。
code for problem1
#include <algorithm>
#include <string>
#include <vector> class BearFair {
public:
std::string isFair(int n, int b, const std::vector<int> &upTo,
const std::vector<int> &quantity) {
int m = static_cast<int>(upTo.size());
std::vector<std::pair<int, int>> V(m);
for (int i = 0; i < m; ++i) {
V[i] = {upTo[i], quantity[i]};
}
std::sort(V.begin(), V.end());
if (V.back().second > n) {
return "unfair";
} struct node {
int ll, rr, cnt; node() = default;
node(int ll, int rr, int cnt) : ll(ll), rr(rr), cnt(cnt) {}
};
std::vector<node> all; for (int i = 0; i < m; ++i) {
if (0 == i) {
if (V[i].second > V[i].first) {
return "unfair";
}
all.emplace_back(1, V[i].first, V[i].second);
} else {
if (V[i].second < V[i - 1].second ||
(V[i].second - V[i - 1].second > V[i].first - V[i - 1].first) ||
(V[i].second != V[i - 1].second && V[i].first == V[i - 1].first)) {
return "unfair";
}
if (V[i].first != V[i - 1].first) {
all.emplace_back(V[i - 1].first + 1, V[i].first,
V[i].second - V[i - 1].second);
}
}
} if (V.back().first < b) {
all.emplace_back(V.back().first + 1, b, n - V.back().second);
} else if (V.back().second != n) {
return "unfair";
}
if (all.empty()) {
return "fair";
} int M = static_cast<int>(all.size());
std::vector<std::vector<bool>> f(M, std::vector<bool>(n + 1));
for (int i = 0; i <= all[0].cnt && i <= all[0].rr / 2; ++i) {
if (all[0].cnt - i <= all[0].rr - all[0].rr / 2) {
f[0][i] = true;
}
}
for (int i = 1; i < M; ++i) {
int even = all[i].rr / 2 - (all[i].ll - 1) / 2;
int odd = all[i].rr - all[i].ll + 1 - even;
for (int j = 0; j <= n; ++j)
if (f[i - 1][j]) {
for (int k = 0; k <= all[i].cnt && j + k <= n && k <= even; ++k) {
if (all[i].cnt - k <= odd) {
f[i][j + k] = 1;
}
}
}
}
if (f[M - 1][n / 2]) {
return "fair";
}
return "unfair";
}
};
code for problem2
#include <unordered_set>
#include <vector> class BearSpans {
public:
std::vector<int> findAnyGraph(int n, int m, int k) {
this->n = n;
this->m = m;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
all_edges.insert(i * n + j);
}
}
if (!Dfs(0, n - 1, k)) {
return {-1};
}
while (index < m) {
auto p = *all_edges.begin();
Add(p / n, p % n);
all_edges.erase(p);
++index;
}
return result;
} private:
bool Dfs(int L, int R, int k) {
if (k == 1) {
for (int i = L + 1; i <= R; ++i) {
Add(L, i);
++index;
}
return true;
} if (L + 1 == R) {
if (k != 1) {
return false;
}
Add(L, R);
++index;
return true;
}
if (R - L + 1 == 3) {
return false;
}
int M = (L + R) >> 1;
if (!Dfs(L, M, k - 1) || !Dfs(M + 1, R, k - 1)) {
return false;
}
Add(L, R);
++index;
return true;
} void Add(int u, int v) {
result.push_back(u + 1);
result.push_back(v + 1);
all_edges.erase(u * n + v);
}
int n;
int m;
std::unordered_set<int> all_edges;
std::vector<int> result;
int index = 0;
};
code for problem3
#include <limits>
#include <string>
#include <vector> constexpr int kMaxN = 2500;
constexpr int kMaxType = 6;
constexpr int kInfinite = std::numeric_limits<int>::max(); int f[2][kMaxN][kMaxType * 2][kMaxType + 1]; class BearPairs {
public:
int minCost(const std::string &s, const std::vector<int> &cost, int m) {
int n = static_cast<int>(s.size());
auto Clear = [&](int t) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < kMaxType * 2; ++j) {
for (int k = 0; k <= m; ++k) {
f[t][i][j][k] = kInfinite;
}
}
}
};
auto Update = [&](int &x, int y) {
if (x > y) {
x = y;
}
};
Clear(0);
f[0][0][0][1] = 0;
f[0][1][s[0] - 'a'][0] = cost[0];
int pre = 0;
int cur = 1;
for (int i = 1; i < n; ++i) {
Clear(cur);
for (int j = 0; j <= i; ++j) {
for (int k = 0; k < kMaxType * 2; ++k) {
for (int t = 0; t <= m; ++t) {
int c0 = f[pre][j][k][t];
if (c0 == kInfinite) {
continue;
}
int c1 = c0 + cost[i] + 100 * i;
int c2 = c0 + cost[i] - 100 * i;
int v = s[i] - 'a';
if (t < m) {
Update(f[cur][j][k][t + 1], c0);
}
if (j == 0) {
Update(f[cur][1][v][t], c2);
} else if (k < kMaxType) {
if (v == k) {
Update(f[cur][j + 1][v][t], c2);
} else {
Update(f[cur][j - 1][k][t], c1);
for (int other = 0; other < kMaxType; ++other) {
if (other != v && other != k) {
Update(f[cur][j + 1][kMaxType + other][t], c2);
}
}
}
} else {
if (v + kMaxType == k) {
Update(f[cur][j - 1][k][t], c1);
} else {
Update(f[cur][j + 1][k][t], c2);
}
}
}
}
}
pre ^= 1;
cur ^= 1;
}
int result = kInfinite;
for (int k = 0; k < kMaxType * 2; ++k) {
result = std::min(result, f[pre][0][k][m]);
}
if (result == kInfinite) {
return -1;
}
return result;
}
};