problem1

选择所有的'+'或者所有的‘-’，一定是这两种中的一种最大。

problem2

首先，第$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

这个就是直接搜索就可以了。把原来的树构造出来。

 

code for problem1

#include 
     
      #include 
      
       class MaximumRange { public:  int findMax(const std::string &s) {    int n = static_cast
       
        (s.size());    int x = 0;    for (auto c : s) {      if (c == '+') {        ++x;      }    }    return std::max(x, n - x);  }};
       
      
     

code for problem2

#include 
     
      #include 
      
       class ClassicTowers { public:  std::string findTowers(long long k, const std::vector
       
         &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
        
          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 
     
      #include