problem1 link
按照每种字符的数量降序排序，然后从多到少依次放每一种。放的时候一上一下交错放置。
problem2 link
构造的方法如下：（假设$x=25$）
（1）首先构造一个初始答案如下：
现在的'good'子集的个数为15，还需要25-15=10个。下面的每一步添加将不改变之前确定的'good'子集，只会增加新的'good'子集；此时$n=4$
（2）添加一层得到$n=5$
新添加的8个是这样的：从$[0,2]$中任意选出一个集合跟3,4都可以构成一个新的good'集合
（3）再添加一层得到$n=6$
新添加的2个是这样的：从$[0,0]$中任意选出一个集合跟1,2,3,4,5都可以构成一个新的good'集合
problem3 link
每次随机旋转某个角度。 然后假设按照$x$排序前一半跟后一半匹配。每次计算一个凸包，找到一组匹配。去掉这组匹配， 继续计算剩下的凸包。循环这个过程。
code for problem1
#include <algorithm>
#include <string>
#include <vector>
class ColorfulGarden {
public:
std::vector<std::string> rearrange(const std::vector<std::string> &A) {
std::vector<std::pair<int, int>> a(26);
for (int i = 0; i < 26; ++i) {
a[i].first = 0;
a[i].second = i;
}
for (const auto &s : A) {
for (char c : s) {
++a[c - 'a'].first;
}
}
std::sort(a.begin(), a.end(), std::greater<std::pair<int, int>>());
int n = static_cast<int>(A[0].size());
if (a[0].first > n) {
return {};
}
std::string total;
for (const auto &e : a) {
char c = 'a' + e.second;
for (int i = 0; i < e.first; ++i) {
total += c;
}
}
std::string s1 = A[0], s2 = A[1];
for (int i = 0; i < n; ++i) {
if (i % 2 == 1) {
s1[i] = total[i];
} else {
s2[i] = total[i];
}
}
for (int i = n; i < n + n; ++i) {
if ((i - n) % 2 == 1) {
s2[i - n] = total[i];
} else {
s1[i - n] = total[i];
}
}
return {s1, s2};
}
};
code for problem2
#include <algorithm>
#include <vector>
class MultiplicationTable3 {
public:
std::vector<int> construct(int x) {
constexpr int kMaxN = 20;
int a[kMaxN][kMaxN];
int n = Get(x);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
a[i][j] = i;
}
}
x -= (1 << n) - 1;
while (x != 0) {
int k = Get(x);
for (int j = n; j >= k; --j) {
a[n][j] = a[j][n] = j - 1;
}
a[n][k] = a[k][n] = k;
for (int j = k - 1; j >= 0; --j) {
a[n][j] = a[j][n] = n;
}
++n;
x -= 1 << k;
}
std::vector<int> ans;
for (int i = 0; i < n; ++i) {
std::copy(a[i], a[i] + n, std::back_inserter(ans));
}
return ans;
}
private:
int Get(int x) {
for (int i = 20; i >= 0; --i) {
if ((x & (1 << i)) != 0) {
return i;
}
}
return 0;
}
};
code for problem3
#include <algorithm>
#include <queue>
#include <vector>
class ZeroPointSixThreeSix {
public:
std::vector<int> replan(const std::vector<int> &x, const std::vector<int> &y,
const std::vector<int> &match) {
int n = static_cast<int>(x.size());
srand(time(0));
std::vector<Point> points(n);
long double cost = 0;
for (int i = 0; i < n; i++) {
points[i].x = x[i];
points[i].y = y[i];
if (match[i] < i) {
cost += points[match[i]].Distance(points[i]);
}
}
std::vector<int> result(n);
cost = cost * 0.636;
while (true) {
double angle = 2 * M_PI / (rand() + 1) * rand();
std::vector<std::pair<Point, int>> p(n);
for (int i = 0; i < n; ++i) {
p[i].first = points[i].Rotate(angle);
p[i].second = i;
}
std::sort(
p.begin(), p.end(),
[&](const std::pair<Point, int> &a, const std::pair<Point, int> &b) {
return std::make_pair(a.first.x, a.first.y) <
std::make_pair(b.first.x, b.first.y);
});
std::vector<bool> used(n, false);
int num = 0;
double total = 0;
while (num != n) {
std::vector<int> st;
for (int i = 0; i < n; ++i) {
if (used[i]) {
continue;
}
while (st.size() > 1 &&
(p[st[st.size() - 1]].first - p[st[st.size() - 2]].first) *
(p[i].first - p[st[st.size() - 2]].first) <
0) {
st.pop_back();
}
st.emplace_back(i);
}
if (st.empty()) {
break;
}
for (size_t i = 0; i + 1 < st.size(); ++i) {
if (st[i] < n / 2 && st[i + 1] >= n / 2) {
used[st[i]] = used[st[i + 1]] = true;
result[p[st[i]].second] = p[st[i + 1]].second;
result[p[st[i + 1]].second] = p[st[i]].second;
num += 2;
total += p[st[i]].first.Distance(p[st[i + 1]].first);
break;
}
}
}
if (total > cost) {
break;
}
}
return result;
}
private:
struct Point {
double x, y;
Point(double x = 0, double y = 0) : x(x), y(y) {}
double Distance(const Point &p) const {
return std::sqrt(std::pow(x - p.x, 2) + std::pow(y - p.y, 2));
}
Point Rotate(double ang) {
double s = sin(ang), c = cos(ang);
return Point(x * c - y * s, x * s + y * c);
}
double operator*(const Point &p) const { return x * p.y - y * p.x; }
Point operator+(const Point &p) const { return Point(x + p.x, y + p.y); }
Point operator-(const Point &p) const { return Point(x - p.x, y - p.y); }
};
};