滴滴笔试

滴滴笔试太可惜了，<<符号写反了，写成>>一直没检查到，交卷了也没发现

第二题：一个方块。初始为 1 x 1白色

n = 1时分割成2 x 2的方块，左上和右下填充为黑色

n = 2时继续分割白色方块， 左下和右上填充为黑色

......

给定n，输出最终方块颜色

难过，这一题应该有规律，不同的n，白色方块的分布应该遵循规律，不用求，直接一次遍历就可以出结果。下面是第二题修改成<<后的答案，应该是正确的

#include <iostream>
#include <vector>

using namespace std;

int main(){
  int n, q;
  cin >> n >> q;

  vector<int> num(q);
  for(int t = 0; t < q; ++t) cin >> num[t];
  vector<vector<char>> Color(1 << n, vector<char>(1 << n, 'W'));
  
  int i = 0;
  while(i < n){
    for(int j = (1 << i) - 1; j >= 0; --j){
      for(int k = (1 << i) - 1; k >= 0; --k){
        if(Color[j][k] == 'B'){
          int new_j = 2 * (j + 1) - 1;
          int new_k = 2 * (k + 1) - 1;
          
          Color[new_j][new_k] = 'B';
          Color[new_j - 1][new_k] = 'B';
          Color[new_j][new_k - 1] = 'B';
          Color[new_j - 1][new_k - 1] = 'B';
        }
        
        if(Color[j][k] == 'W'){
          int new_j = 2 * (j + 1) - 1;
          int new_k = 2 * (k + 1) - 1;
          
          if(i & 1){
            Color[new_j][new_k] = 'W';
            Color[new_j - 1][new_k - 1] = 'W';
            
            Color[new_j - 1][new_k] = 'B';
            Color[new_j][new_k - 1] = 'B';
            
          }
          else{
            Color[new_j][new_k] = 'B';
            Color[new_j - 1][new_k - 1] = 'B';
            
            Color[new_j - 1][new_k] = 'W';
            Color[new_j][new_k - 1] = 'W';
          }
        }
      }
    }
    
    ++i;
  }
  
  for(int t = 0; t < q; ++t){
    int row = num[t] - 1;
    for(int j = 0; j < 1 << n; ++j){
      cout << Color[row][j];
    }
    cout << endl;
  }
   
  return 0;
}

第一题：

n个积木，m个袋子，值q，每个袋子至少放一个积木，第i 个袋子的价值为 放置积木个数的平方，求放置积木的方案，使总价值为q， 存在这样的方案字典序最小的那个，否则输出 -1

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n, m, q;
    cin >> n >> m >> q;

    vector<int> dp(m, 1);
    dp[m - 1] = n - (m - 1);
    
    int sum = 0;
    for(int i = 0; i < m; ++i){
        sum += dp[i] * dp[i];
    }

    if(sum < q){
        cout << -1;
        return 0;
    }

    int index = m - 1;
    while(sum > q){
        if(dp[index] > dp[index - 1]){
            sum -= dp[index] * dp[index] - dp[index - 1] * dp[index - 1];
            dp[index] -= 1;
            dp[index - 1] += 1;
            sum += dp[index] * dp[index] + dp[index - 1] * dp[index - 1];
        }
        else{
            if(index - 1 > 0){
                index = index - 1;
            }
            else{
                break;
            }
        }
    }

    if(sum == q){
        for(int i = 0; i < m; ++i){
            cout << dp[i] << " ";
        }
    }
    else{
        cout << -1;
    }

    return 0;
}