problem1

分别计算可以得到(a,b)的有哪些二元组，以及可以得到(c,d)的有哪些二元组。然后在公共的二元组中找到和最大的即可。

problem2 

设最后的排序为$r=[2,4,1,0,5,3]$.初始时$2=4=1=0=5=3$。从后向前考虑每一个使用的技能。最后一个使用的技能一定是将某些等于符号变成了大于符号。倒数第二次使用的技能一定是将目前的某些等于号变成大于号（或者没有改变）。依次类推直到所有的符号都变成了大于号。假设存在一个正确的序列可以满足要求，将其作为当前答案。如果有一个其他的技能首先被使用也不会冲突的话，那么把它放在当前答案的最前面也无所谓。所以每次选择技能只要使得当前没有冲突即可。

problem3 

将每个数看做一个变量。对每个出现的质因子建立一个方程，要求这个质因子出现偶数次。另外每一行没一列各建立一个方程，表示出现奇数次。然后进行高斯消元，计算自由元的个数。

 

code for problem1

#include 
     
      #include 
      
       class PairGame { public:  int maxSum(int a, int b, int c, int d) {    auto Find = [&](int x, int y, std::set
       
        
         > *result) {      while (x > 0 && y > 0) {        result->insert({x, y});        if (x == y) break;        if (x > y)          x -= y;        else          y -= x;      }    };    std::set
         
          
           > result1; std::set
           
            
             > result2; Find(a, b, &result1); Find(c, d, &result2); int result = -1; for (const auto &e : result1) { if (result2.find(e) != result2.end()) { result = std::max(result, e.first + e.second); } } return result; }};
            
           
          
         
        
       
      
     

code for problem2

#include 
     
      #include 
      
       class CandidatesSelection { public:  std::string possible(const std::vector
       
         &s,                       const std::vector
        
          &v) {    int n = static_cast
         
          (s.size());    int m = static_cast
          
           (s[0].size()); std::vector
           
             rank(n, 0); long long used_skills = 0; while (true) { bool find_one = true; for (int i = 0; i < m; ++i) { if ((used_skills & (1ll << i)) == 0) { bool ok = true; for (int j = 1; j < n && ok; ++j) { ok &= (rank[j] != rank[j - 1] || s[v[j]][i] >= s[v[j - 1]][i]); } if (ok) { used_skills |= 1ll << i; find_one = true; std::vector
            
              new_rank(n); for (int j = 1; j < n; ++j) { if (rank[j] != rank[j - 1] || s[v[j]][i] != s[v[j - 1]][i]) { new_rank[j] = new_rank[j - 1] + 1; } else new_rank[j] = new_rank[j - 1]; } rank = new_rank; } } } if (!find_one) break; } for (int i = 1; i < n; ++i) { if (rank[i] == rank[i - 1] && v[i] < v[i - 1]) { return "Impossible"; } } return "Possible"; }};
            
           
          
         
        
       
      
     

code for problem3

#include 
     
      #include 
      
       #include 
       
        #include 
        
         constexpr int KMAXCOLUMN = 20 * 20 + 1;constexpr int KMOD = 1000000007;class PerfectSquare { public:  int ways(const std::vector
         
           &x) {    const int n = static_cast
          
           (std::sqrt(x.size()) + 0.1); std::unordered_map
           

> mapper; for (int i = 0; i < n * n; ++i) { int t = x[i]; for (int j = 2; j * j <= t; ++j) { int cnt = 0; while (t % j == 0) { cnt ^= 1; t /= j; } if (cnt != 0) { mapper[j].push_back(i); } } if (t > 1) { mapper[t].push_back(i); } } std::vector

> matrix; for (auto it = mapper.begin(); it != mapper.end(); ++it) { std::bitset

row; for (auto x : it->second) { row[x] = 1; } matrix.push_back(row); } for (int i = 0; i < n; ++i) { std::bitset

row1; std::bitset

row2; for (int j = 0; j < n; ++j) { row1[i * n + j] = 1; row2[j * n + i] = 1; } row1[n * n] = 1; row2[n * n] = 1; matrix.push_back(row1); matrix.push_back(row2); } int free_num = Gauss(&matrix, n * n); if (free_num == -1) { return 0; } int result = 1; for (int i = 0; i < free_num; ++i) { result = result * 2 % KMOD; } return result; } private: int Gauss(std::vector

> *matrix, int m) { int n = static_cast

(matrix->size()); std::vector

visit(n, false); int not_free_num = 0; for (int j = 0; j < m; ++j) { for (int i = 0; i < n; ++i) { if ((*matrix)[i][j] != 0 && !visit[i]) { visit[i] = true; ++not_free_num; for (int k = 0; k < n; ++k) { if (k != i && (*matrix)[k][j] != 0) { (*matrix)[k] ^= (*matrix)[i]; } } break; } } } for (int i = 0; i < n; ++i) { if (!visit[i] && (*matrix)[i][m] != 0) { return -1; } } return m - not_free_num; }};