[Algorithm][综合训练][kotori和n皇后][取金币][矩阵转置]详细讲解

1.kotori和n皇后

1.题目链接

• kotori和n皇后

2.算法原理详解 && 代码实现

• 解法：哈希表 + 数学思维

  • 重点：使⽤哈希表标记⾏列以及两个对⻆线
    

  #include <iostream>
  #include <unordered_set>
  using namespace std;
  
  int main()
  {
      int k = 0, t = 0;
      cin >> k;
      
      unordered_set<long long> row;
      unordered_set<long long> col;
      unordered_set<long long> dig1; // 主对角线
      unordered_set<long long> dig2; // 副对角线
      
      int ret = 0x3f3f3f3f; // 防止没有互相攻击的
      for(int i = 0; i < k; i++)
      {
          int x, y;
          cin >> x >> y;
          
          if(ret != 0x3f3f3f3f)
          {
              continue;
          }
          
          if(row.count(y) || col.count(x) || dig1.count(y - x) || dig2.count(y + x))
          {
              ret = i + 1;
          }
          
          row.insert(y);
          col.insert(x);
          dig1.insert(y - x);
          dig2.insert(y + x);
      }
      
      cin >> t;
      while(t--)
      {
          int i = 0;
          cin >> i;
          
          if(i >= ret)
          {
              cout << "Yes" << endl;
          }
          else
          {
              cout << "No" << endl;
          }
      }
      
      return 0;
  }
  

2.取金币

1.题目链接

• 取金币

2.算法原理详解 && 代码实现

• 解法：动态规划 -> 区间DP

  • 状态表示：dp[i][j]：区间[i, j]的金币全部拿走，能获得的最大积分是多少

  • 状态转移方程：
    

  • 初始化：

    • 原始表两边各加一格，填入1
    • DP表多加两行两列，全部初始化为0
      

  • 填表顺序：从下往上，从左往右

  • 返回值：dp[1][n]

  int getCoins(vector<int>& coins) 
  {
      int n = coins.size();
  
      vector<int> arr(n + 2, 0);
      arr[0] = arr[n + 1] = 1;
      for(int i = 1; i <= n; i++)
      {
          arr[i] = coins[i - 1];
      }
  
      vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
      for(int i = n; i >= 1; i--)
      {
          for(int j = i; j <= n; j++)
          {
              for(int k = i; k <= j; k++)
              {
                  dp[i][j] = max(dp[i][j], 
  							   dp[i][k - 1] + dp[k + 1][j] + arr[i - 1] * arr[k] * arr[j + 1]);
              }
          }
      }
  
      return dp[1][n];
  }
  

3.矩阵转置

1.题目链接

• 矩阵转置

2.算法原理详解 && 代码实现

• 解法：数学 -> 转置前和转置后下标的关系
  

  #include <iostream>
  #include <vector>
  using namespace std;
  
  int main()
  {
      int n = 0, m = 0;
      cin >> n >> m;
  
      vector<vector<int>> nums(n, vector<int>(m, 0));
      for(int i = 0; i < n; i++)
      {
          for(int j = 0; j < m; j++)
          {
              cin >> nums[i][j];
          }
      }
  
      for(int i = 0; i < m; i++)
      {
          for(int j = 0; j < n; j++)
          {
              // ret[i][j] = arr[j][i]
              cout << nums[j][i] << " ";
          }
          cout << endl;
      }
  
      return 0;
  }