problem1 link
选择所有的'+'或者所有的‘-’，一定是这两种中的一种最大。
problem2 link
首先，第$n$个盘子初始时所在的柱子一定的最后所有的盘子都应该挪到的柱子。所以，可以枚举第$n$个盘子在哪个柱子上。
假设目前枚举第$n$个盘子在第三个柱子上，那么假设要求解的问题为 $F(k,x,y,z,3)$, 其中$x=count[0],y=count[1],z=count[2]-1$，表示处理剩下的$n-1=x+y+z$个盘子，三根柱子上的个数为$(x,y,z)$。
那么对于第$n-1$个盘子，如果也放到第三根柱子上，那么接下来就是求解$F(k,x,y,z-1,3)$。如果将其放置到第二根柱子上，那么要首先把把前面的$n-2$个盘子挪到第一根柱子上，然后挪$n-1$盘子，然后再把$n-2$个盘子挪到第三根上，这三步分别需要：$F(k^{'},x,y-1,z,1),1,2^{n-2}-1$ ，所以$k^{'}=k-2^{n-2}=k-2^{x+y+z-1}$，那么接下来要求解的是$F(k-2^{x+y+z-1},x,y-1,z,1)$。
按照上面的思路可以得到结论如果$k\geq 2^{x+y+z-1}$，那么此时的盘子一定要换一根柱子。
problem3 link
这个就是直接搜索就可以了。把原来的树构造出来。
code for problem1
#include <algorithm>
#include <string> class MaximumRange {
public:
int findMax(const std::string &s) {
int n = static_cast<int>(s.size());
int x = 0;
for (auto c : s) {
if (c == '+') {
++x;
}
}
return std::max(x, n - x);
}
};
code for problem2
#include <string>
#include <vector> class ClassicTowers {
public:
std::string findTowers(long long k, const std::vector<int> &count) {
if (Check(k, count[0], count[1], count[2], "ABC")) {
return result;
}
if (Check(k, count[0], count[2], count[1], "ACB")) {
return result;
}
if (Check(k, count[1], count[2], count[0], "BCA")) {
return result;
}
return "";
} private:
std::string result; std::vector<int> all; bool Dfs(long long k, int x, int y, int z, int idx) {
if (x + y + z == 0) {
return k == 0;
}
int curr = x + y + z - 1;
if ((k & (1ll << curr)) == 0) {
all[curr] = idx;
if (idx == 1 && x > 0) {
return Dfs(k, x - 1, y, z, idx);
} else if (idx == 2 && y > 0) {
return Dfs(k, x, y - 1, z, idx);
} else if (idx == 3 && z > 0) {
return Dfs(k, x, y, z - 1, idx);
} else {
return false;
}
} else {
for (int i = 1; i <= 3; ++i) {
if (i != idx) {
all[curr] = i;
if (i == 1 && x > 0 &&
Dfs(k ^ (1ll << curr), x - 1, y, z, 6 - idx - i)) {
return true;
}
if (i == 2 && y > 0 &&
Dfs(k ^ (1ll << curr), x, y - 1, z, 6 - idx - i)) {
return true;
}
if (i == 3 && z > 0 &&
Dfs(k ^ (1ll << curr), x, y, z - 1, 6 - idx - i)) {
return true;
}
}
}
return false;
}
} bool Check(long long k, int x, int y, int z, const std::string &table) {
if (z == 0) {
return false;
}
long long maxk = (1ll << (x + y + z - 1)) - 1;
if (k > maxk) {
return false;
}
all.resize(x + y + z);
all.back() = 3;
if (Dfs(k, x, y, z - 1, 3)) {
result = "";
for (int i = 0; i < x + y + z; ++i) {
result += table[all[i] - 1];
}
return true;
}
return false;
}
};
code for problem3
#include <algorithm>
#include <map>
#include <memory>
#include <string>
#include <vector> class PreInPost {
public:
std::vector<int> findMissing(const std::vector<std::string> &s,
const std::vector<int> &a1,
const std::vector<int> &a2,
const std::string &e1, const std::string &e2) {
table_s = s;
auto status = Dfs(a1, a2, e1, e2);
if (!status.flag) {
return {};
}
std::vector<int> result;
std::string mode = "pre";
for (int i = 0; i < 6; i += 2) {
if (s[i] != e1 && s[i] != e2) {
Order(status.root.get(), s[i], &result);
break;
}
}
return result;
} private:
struct Node {
int idx = -1;
std::shared_ptr<Node> left = nullptr;
std::shared_ptr<Node> right = nullptr; void SetRoot(int x) {
if (idx == -1) {
idx = x;
} else if (idx != x) {
idx = -2;
}
}
}; struct Status {
std::shared_ptr<Node> root = nullptr;
bool flag = false;
}; struct KeyNode {
std::vector<int> a1;
std::vector<int> a2;
std::string e1;
std::string e2; KeyNode() = default;
KeyNode(const std::vector<int> &a1, const std::vector<int> &a2,
const std::string &e1, const std::string &e2)
: a1(a1), a2(a2), e1(e1), e2(e2) {} bool operator<(const KeyNode &key) const {
if (a1 != key.a1) {
return a1 < key.a1;
}
if (a2 != key.a2) {
return a2 < key.a2;
}
if (e1 != key.e1) {
return e1 < key.e1;
}
return e2 < key.e2;
}
};
std::map<KeyNode, Status> visited_states;
std::vector<std::string> table_s; int LeftModeIdx(const std::string &e) {
if (e == "pre") {
return 0;
} else if (e == "in") {
return 2;
} else {
return 4;
}
} void Order(const Node *node, const std::string &e, std::vector<int> *result) {
if (node == nullptr) {
return;
}
if (e == "pre") {
result->push_back(node->idx);
Order(node->left.get(), table_s[0], result);
Order(node->right.get(), table_s[1], result);
} else if (e == "in") {
Order(node->left.get(), table_s[2], result);
result->push_back(node->idx);
Order(node->right.get(), table_s[3], result);
} else {
Order(node->left.get(), table_s[4], result);
Order(node->right.get(), table_s[5], result);
result->push_back(node->idx);
}
} bool SameSet(const std::vector<int> &a1, const std::vector<int> &a2) {
long long s[4] = {0, 0, 0, 0};
constexpr int kEach = 60;
for (size_t i = 0; i < a1.size(); ++i) {
s[a1[i] / kEach] ^= 1ll << (a1[i] % kEach);
s[a2[i] / kEach] ^= 1ll << (a2[i] % kEach);
}
return s[0] == 0 && s[1] == 0 && s[2] == 0 && s[3] == 0;
} Status Dfs(const std::vector<int> &a1, const std::vector<int> &a2,
const std::string &e1, const std::string &e2) {
Status status;
if (a1.empty()) {
status.flag = true;
return status;
}
status.root = std::shared_ptr<Node>(new Node);
auto Set = [&](const std::vector<int> &a, const std::string &e) {
if (e == "pre" || e == "post") {
status.root->SetRoot(e == "pre" ? a.front() : a.back());
}
};
Set(a1, e1);
Set(a2, e2);
if (status.root->idx == -2) {
return status;
}
KeyNode key_node(a1, a2, e1, e2);
if (visited_states.find(key_node) != visited_states.end()) {
return visited_states[key_node];
}
std::vector<int> new_a1 = a1;
std::vector<int> new_a2 = a2;
int m = -1;
auto RemoveRoot = [&](const std::string &e, std::vector<int> *a) {
if (e == "pre") {
a->erase(a->begin());
} else if (e == "post") {
a->pop_back();
} else {
m = static_cast<int>(std::find(a->begin(), a->end(), status.root->idx) -
a->begin());
a->erase(a->begin() + m);
}
};
RemoveRoot(e1, &new_a1);
RemoveRoot(e2, &new_a2);
if (!SameSet(new_a1, new_a2)) {
return visited_states[key_node] = status;
}
int n = static_cast<int>(new_a1.size());
std::vector<int> right1;
std::vector<int> right2;
auto Check = [&]() {
if (SameSet(new_a1, new_a2) && SameSet(right1, right2)) {
Status left = Dfs(new_a1, new_a2, table_s[LeftModeIdx(e1)],
table_s[LeftModeIdx(e2)]);
Status right = Dfs(right1, right2, table_s[LeftModeIdx(e1) + 1],
table_s[LeftModeIdx(e2) + 1]);
if (left.flag && right.flag) {
status.root->left = left.root;
status.root->right = right.root;
status.flag = true;
return true;
}
}
return false;
}; if (m == -1) {
if (!Check()) {
for (int i = n - 1; i >= 0; --i) {
right1.insert(right1.begin(), new_a1.back());
right2.insert(right2.begin(), new_a2.back());
new_a1.pop_back();
new_a2.pop_back();
if (Check()) {
break;
}
}
}
} else {
for (int i = m; i < n; ++i) {
right1.push_back(new_a1[i]);
right2.push_back(new_a2[i]);
}
new_a1.erase(new_a1.begin() + m, new_a1.end());
new_a2.erase(new_a2.begin() + m, new_a2.end());
Check();
}
return visited_states[key_node] = status;
}
};