problem1

对于每个还未切掉的‘X’用cutter作用一次。从左上角到右下角，依次判断即可。

problem2

首先，如果一个顶点不能从0到达或者不能到达节点$n-1$，那么可以直接将这个顶点从图中删掉。所以，可以认为每个顶点都可以从节点0到达且可以到达节点$n-1$.

按照如下策略进行路径选择：

（1）设初始时已访问节点集合$S$只包含节点0；

（2）对于$[1,n-2]$中的每个节点，找到一个节点$t$，满足在$S$中存在一个节点$r$,使得$r$->$t$有一条直接的边，然后将$t$加入到$S$中，并且将边$e(r,t)$加入到已使用边集合$E$；最后$S$中包含$[0,n-2]$共$n-1$个节点,$E$中包含$n-2$个边

（3）对于任意一条当前不在$E$中的边，$e(x,y)$，如果满足$x\in S$且$y$可到达$n-1$，那么就找到了一条路径。然后将$e(x,y)$加入到集合$E$中。这条路径使用了一条之前从未使用的边$e(x,y)$，所以是一条新的路径。（第一条这样的路径一定满足$y=n-1$）

按照上面的策略，假设图一共有$m$条边，那么答案有$m-(n-2)$

problem3

 首先有一个结论：$moves=\frac{1}{2}\sum_{i=0}^{n-1}|T_{i}-S_{i}|$

那么问题可转化为有多少$T$的全排列$T^{'}$满足$\sum_{i=0}^{n-1}|T_{i}-T^{'}_{i}|=moves*2$

将$T$和$T^{'}$看做两行长度为$n$的元素。现在从左向右依次确认$T$的每个元素应该放在$T^{'}$的什么位置。对于第$i$个位置，需要考虑下面两件事情：

（1）$T_{i}$应该放在$T^{'}$的什么位置

（2）$T^{'}_{i}$应该放置$T$的哪一个元素

对于第一个问题，假设$T_{i}$放在了$T^{'}$的$[0,i-1]$的某个位置$x$，那么对移动次数的计算贡献为$T_{i}-T_{x}$。因此，可以将其简记为$+T_{i}$，而如果$T_{i}$被放置在$T^{'}$的$[i+1,n-1]$的位置,那么对移动次数的贡献为$-T_{i}$

这样的话，动态规划的方程可表示为$f[i][j][k]$表示考虑完$T$和$T^{'}$的前$i$个位置，$T$的$[0,i]$中的$j$个数字要放置到$T^{'}$的$[i+1,n-1]$位置，那么同时也意味着需要从$T$的$[i+1,n-1]$位置中选出$j$个放置到$T^{'}$的$[0,i]$位置，且移动次数为$k$的排列种数

设$X=f[i][j][k]$，那么对于第$i+1$个位置，有以下五种转移：

（1）$T_{i+1}$放置在$T^{'}_{i+1}$，$f[i+1][j][k]=X$

（2）$T_{i+1}$放置在$T^{'}$的$[0,i]$（有$j$种选择），且$T^{'}_{i+1}$用$T$的$[0,i]$中的一个(同样有$j$种选择)，那么$f[i+1][j-1][k+2T_{i}]=j*j*X$

（3）$T_{i+1}$放置在$T^{'}$的$[0,i]$（有$j$种选择），且$T^{'}_{i+1}$用$T$的$[i+2,n-1]$中的一个，那么$f[i+1][j][k]=j*X$

（4）$T_{i+1}$放置在$T^{'}$的$[i+2,n-1]$（有$j$种选择），且$T^{'}_{i+1}$用$T$的$[0,i]$中的一个，那么$f[i+1][j][k]=j*X$

（5）$T_{i+1}$放置在$T^{'}$的$[i+2,n-1]$（有$j$种选择），且$T^{'}_{i+1}$用$T$的$[i+2,n-1]$中的一个，那么$f[i+1][j+1][k-2T_{i}]=X$

 

code for problem1

#include 
     
      #include 
      
       using namespace std;class GogoXCake {   public:    string solve(vector
       
         cake, vector
        
          cutter) {        const int cake_height = (int)cake.size();        const int cake_width = (int)cake[0].size();        const int cutter_height = (int)cutter.size();        const int cutter_width = (int)cutter[0].size();        std::vector
         
          
           > a(cake_height, std::vector
           
            (cake_width, 1)); const int first_row_used_cell_column = (int)cutter[0].find_first_of('.'); for (int i = 0; i < cake_height; ++ i) { for (int j = 0; j < cake_width; ++ j) { if (cake[i][j] == 'X') { if (a[i][j] == 0) { return "NO"; } } else { if (a[i][j] == 1) { const int x = i; const int y = j - first_row_used_cell_column; if (y < 0 || y + cutter_width > cake_width || x + cutter_height > cake_height) { return "NO"; } for (int xx = x; xx < x + cutter_height; ++ xx) { for (int yy = y; yy < y + cutter_width; ++ yy) { if (cutter[xx -x][yy - y] == '.') { if (a[xx][yy] != 1) { return "NO"; } a[xx][yy] = 0; } } } } } } } return "YES"; }};
           
          
         
        
       
      
     

code for problem2

#include 
     
      #include 
      
       #include 
       
        using namespace std;class GogoXMarisaKirisima {   public:    int solve(vector
        
          choices) {        const int n = (int)choices.size();        vector
         
          
           > g(n, vector
           
            (n, 0)); for (int i = 0; i < n; ++ i) { for (int j = 0; j < n; ++ j) { g[i][j] = (choices[i][j] == 'Y' ? 1 : 0); } } for (int i = 0; i < n; ++ i) { g[i][i] = 1; } for (int i = 0; i < n; ++ i) { for (int j = 0; j < n; ++ j) { for (int k = 0; k < n; ++ k) { if (g[j][i] != 0 && g[i][k] != 0) { g[j][k] = 1; } } } } if (g[0][n - 1] == 0) { return 0; } long long mask = 0; int valid = 0; for (int i = 0; i < n; ++ i) { if (g[0][i] != 0 && g[i][n - 1] != 0) { mask |= 1ll << i; ++ valid; } } int m = 0; for (int i = 0; i < n; ++ i) { if ((mask & (1ll << i)) == 0) { continue; } for (int j = 0; j < n; ++ j) { if (choices[i][j] == 'Y' && (mask & (1ll << j)) != 0) { ++ m; } } } return m - (valid - 2); }};
           
          
         
        
       
      
     

code for problem3

#include 
     
      #include 
      
       using namespace std;#define mod 1000000009class GogoXBallsAndBins {   public:    int solve(vector
       
         T, int moves) {        const int n = (int)T.size();        int sum = 0;        for (auto x : T) {            sum += x;        }        const int total = sum * 4 + 1;        vector
        
         
          
           >> f( n, vector
           
            
             >(n + 1, vector
             
              (total, 0))); f[0][0][sum * 2] = 1; f[0][1][-T[0] * 2 + sum * 2] = 1; for (int i = 1; i < n; ++ i) { for (int j = 0; j <= i; ++ j) { for (int k = 0; k < total; ++ k) { const int t = f[i- 1][j][k]; if (t == 0) { continue; } Add(f[i][j][k], t); if (j > 0) { Add(f[i][j - 1][k + T[i] * 2], (long long)j * j * t % mod); Add(f[i][j][k], (long)j * t * 2 % mod); } Add(f[i][j + 1][k - T[i] * 2], t); } } } if (moves * 2 + sum * 2 >= total) { return 0; } return f[n - 1][0][moves * 2 + sum * 2]; } private: void Add(int&x, int y) { x += y; if (x >= mod) { x -= mod; } }};