[Algorithm][综合训练][对称之美][经此一役小红所向无敌][连续子数组最大和]详细讲解

---

1.对称之美

1.题目链接

• 对称之美

---

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

• 优化版本：双指针(判断回文) + 哈希(判断两个字符串中是否有相同字符)
  • 自己思路的纠正：没必要一定要把所有的字符串找出来再判断，可以直接看对应两字符串是否出现一样的字符即可，出现则这两个位置是"回文"的，否则再也不用判断

  #include <iostream>
  #include <vector>
  #include <string>
  using namespace std;// 判断两个字符串中是否有相同字符
  vector<vector<bool>> visit;bool Check(int left, int right)
  {for(int i = 0; i < 26; i++){if(visit[left][i] && visit[right][i]){return true;}}return false;
  }int main()
  {int t = 0;cin >> t;while(t--){int n = 0;cin >> n;visit.clear();visit.resize(n, vector<bool>(26, false));string str;for(int i = 0; i < n; i++) // 将所有字符串的字符信息存入hash{cin >> str;for(const auto& ch : str){visit[i][ch - 'a'] = true;}}// 判断回文int left = 0, right = n - 1;while(left < right){if(!Check(left, right)){break;}left++, right--;}if(left < right){cout << "No" << endl;}else{cout << "Yes" << endl;}}return 0;
  }
  

---

2.经此一役小红所向无敌

1.题目链接

• 经此一役小红所向无敌

---

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

• 自己的版本：模拟 --> 可能会有超时风险，但本题没超时

  #include <iostream>
  using namespace std;int main()
  {long long a, b, h, k;cin >> a >> h >> b >> k;long long cnt = 0;while(h > 0 && k > 0){cnt += a + b;h -= b, k -= a;}if(h <= 0 && k <= 0){}else if(h <= 0){cnt += b * 10;}else if(k <= 0){cnt += a * 10;}cout << cnt << endl;return 0;
  }
  

• 优化版本：数学 --> 直接计算结果

  #include <iostream>
  using namespace std;int main()
  {long long a, b, h, k, ret = 0;cin >> a >> h >> b >> k;// 1.计算互砍多少回合long long n = min(h / b, k / a);ret += n * (a + b);// 2.计算剩余血量h -= n * b;k -= n * a;// 3.判断是否都还活着if(h > 0 && k > 0){h -= b;k -= a;ret += a + b;}// 4.判断是否会放大if(h > 0 || k > 0){ret += 10 * (h > 0 ? a : b);}cout << ret << endl;return 0;
  }
  

---

3.连续子数组最大和

1.题目链接

• 连续子数组最大和

---

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

• 自己的版本：双指针

  #include <iostream>
  #include <vector>
  using namespace std;int main()
  {int n = 0;cin >> n;vector<long long> nums(n, 0);for(auto& x : nums){cin >> x;}int left = 0, right = 0;long long cnt = 0, maxValue = -0x3f3f3f3f;while(right < n){if((cnt += nums[right]) < nums[right]){cnt = nums[right];left = right;}if(cnt > maxValue){maxValue = cnt;}right++;}cout << maxValue << endl;return 0;
  }
  

• 优化版本：动态规划 – 线性dp
  • 状态表示：dp[i]：以i位置为结尾的所有的子数组中，最大和是多少
  • 状态转移方程：dp[i] = max(dp[i - 1] + arr[i], arr[i]);

  #include <iostream>
  #include <vector>
  using namespace std;int main()
  {int n = 0;cin >> n;vector<int> arr(n + 1, 0);vector<int> dp(n + 1, 0);for(int i = 1; i <= n; i++){cin >> arr[i];}int ret = -0x3f3f3f3f;for(int i = 1; i <= n; i++){dp[i] = max(dp[i - 1], 0) + arr[i];ret = max(ret, dp[i]);}cout << ret << endl;return 0;
  }