problem1

对于数字$x$，检验每个满足$x=y*2^{t}$的$y$能否变成$x$即可。

problem2

如果起点到终点有一条长度为$L$的路径，那么就存在长度为$L+kR$的路径。其中$R$为从路径上某点转一圈再回到这一点的环的长度。

为了保证总是存在这个环，可以令这个环为从起点出发再回到起点。所以如果有一条长度为$d$的边$0\rightarrow t$，那么可以令$R=2d$，即$0\rightarrow t \rightarrow 0$.

只需要记录起点到达某个点长度模$R$的最短路即可。即用$f[m][u]$表示从0到$u$的最小的满足$m+kR$的路径长度。

只要$f[T$%$R][N-1] \leq T$即可。

problem3

红色和绿色需要配对出现。所以可以将一个红色一个绿色看作一个整体。那么就是$M$组中每组要出现$D$个配对的整体。

从前向后进行动态规划，只统计出现了多少个配对的整体以及还有多少个只配对了一半的。

这里有个问题是每一组中的$D$个整体不能交叉出现。为了做到这一点，只需要配对了一半的个数不超过$M$即可.

 

code for problem1

#include 
     
      #include 
      
       class AmebaDiv1 { public:  int count(const std::vector
       
         &X) {    auto Get = [&](int t) {      for (auto e : X) {        if (e == t) {          t *= 2;        }      }      return t;    };    std::set
        
          all(X.begin(), X.end());    int result = 0;    for (auto e : all) {      bool tag = (Get(1) != e);      int t = e;      while (t > 1) {        if (Get(t) == e) {          tag = false;          break;        }        t /= 2;      }      if (tag) {        ++result;      }    }    return result;  }};
        
       
      
     

code for problem2

#include 
     
      #include 
      
       #include 
       
        #include 
        
         constexpr int MAXD = 20000;constexpr int MAXN = 50;long long dist[MAXD][MAXN];class LongLongTripDiv1 { public:  std::string isAble(int N, const std::vector
         
           &A,                     const std::vector
          
            &B, const std::vector
           
             &D, long long T) { int n = static_cast
            
             (A.size()); int d = MAXD + 1; for (int i = 0; i < n; ++i) { if (A[i] == 0 || B[i] == 0) { d = std::min(d, D[i]); } } if (d == MAXD + 1) { return "Impossible"; } std::set
             
              
               >> que; memset(dist, -1, sizeof(dist)); auto Insert = [&](long long dis, int u, int v) { auto iter = que.find({dist[u][v], {u, v}}); if (iter != que.end()) { que.erase(iter); } que.insert({dis, {u, v}}); dist[u][v] = dis; }; Insert(0, 0, 0); while (!que.empty()) { auto node = que.begin()->second; que.erase(que.begin()); int u = node.second; for (int i = 0; i < n; ++i) { if (A[i] != u && B[i] != u) { continue; } int v = A[i] + B[i] - u; int t = (node.first + D[i]) % (2 * d); long long new_dist = dist[node.first][u] + D[i]; if (dist[t][v] == -1 || new_dist < dist[t][v]) { Insert(new_dist, t, v); } } } auto min_dist = dist[T % (d * 2)][N - 1]; return (min_dist != -1 && min_dist <= T) ? "Possible" : "Impossible"; }};
              
             
            
           
          
         
        
       
      
     

code for problem3

#include 
     
      constexpr int MOD = 1000000007;int f[5005][50][51];class AlternativePiles { public:  int count(const std::string &C, int M) {    if (Red(C[0])) {      f[0][0][1] += 1;    }    if (Blud(C[0])) {      f[0][0][0] += 1;    }    for (size_t idx = 1; idx < C.size(); ++idx) {      char c = C[idx];      for (int x = 0; x < M; ++x) {        for (int y = 0; y <= M; ++y) {          int t = f[idx - 1][x][y];          if (t == 0) {            continue;          }          if (Red(c) && y + 1 <= M) {            (f[idx][x][y + 1] += t) %= MOD;          }          if (Blud(c)) {            (f[idx][x][y] += t) %= MOD;          }          if (Green(c) && y > 0) {            (f[idx][(x + 1) % M][y - 1] += t) %= MOD;          }        }      }    }    return f[C.size() - 1][0][0];  } private:  bool Red(char c) { return c == 'R' || c == 'W'; }  bool Green(char c) { return c == 'G' || c == 'W'; }  bool Blud(char c) { return c == 'B' || c == 'W'; }};