---

1.mari和shiny

1.题目链接

• mari和shiny

---

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

• 自己的版本：三层循环暴力枚举 --> 超时 --> 40%

  #include <iostream>
  #include <string>
  using namespace std;int main()
  {int n = 0, cnt = 0;cin >> n;string str;cin >> str;// 三层暴力枚举for(int i = 0; i < n - 2; i++){if(str[i] != 's'){continue;}for(int j = i + 1; j < n - 1; j++){if(str[j] != 'h'){continue;}for(int k = j + 1; k < n; k++){if(str[k] != 'y'){continue;}else{cnt++;}}}}cout << cnt << endl;return 0;
  }
  

• 优化版本：动态规划 – 多状态的线性dp

  • 状态表示：

    • s[i]：[0, i]区间内，有多少个"s"
    • h[i]：[0, i]区间内，有多少个"sh"
    • y[i]：[0, i]区间内，有多少个"shy"

  • 状态转移方程：
    

  • 初始化：s[0] = str[0] == 's' ? 1 : 0, h[0] = y[0] = 0;

  • 空间优化：
    

  #include <iostream>
  #include <string>
  using namespace std;int main()
  {int n = 0;string str;cin >> n >> str;long long s = 0, h = 0, y = 0;for(int i = 0; i < n; i++){char ch = str[i];if(ch == 's'){s++;}else if(ch == 'h'){h += s;}else if(ch == 'y'){y += h;}}cout << y << endl;return 0;
  }
  

---

2.重排字符串

1.题目链接

• 重排字符串

---

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

• 自己的版本：33.33%

  #include <iostream>
  #include <string>
  #include <unordered_set>
  #include <unordered_map>
  using namespace std;int main()
  {int n = 0;string str;cin >> n >> str;unordered_map<char, int> hash;unordered_set<char> deDup;int maxLen = 0;char maxCh = 'a';for(const auto& ch : str){deDup.insert(ch);hash[ch]++;int tmp = max(maxLen, hash[ch]);if(tmp > maxLen){maxLen = tmp;maxCh = ch;}}bool flag = true;if(maxLen > n / 2 + 1){flag = false;cout << "no" << endl; // 一个字符串的数量如果超过n / 2 + 1，则肯定不可以}// 到这里之后，肯定都是可以的// 这里的重组方法有失偏颇string ret;ret += maxCh, hash[maxCh]--;while(!hash.empty()){for(const auto& ch : deDup){if(hash.count(ch)){ret += ch;hash[ch]--;if(hash[ch] == 0){hash.erase(ch);}}}}if(flag){cout << "yes" << endl<< ret << endl;}return 0;
  }
  

• 优化版本：贪心 + 构造
  • 不能重排：$x>(n+1)/2$
  • 能重排：
    • 每次去处理一批相同的字符 --> [自己的版本没意识到的思路]
    • 优先处理出现次数最多的字符
    • 每次摆放的时候，间隔一个格子
    • 重点：手动控制间隔 --> [自己的版本没能实现的]

  #include <iostream>
  #include <string>
  #include <unordered_map>
  using namespace std;int main()
  {int n = 0;string str;cin >> n >> str;unordered_map<char, int> hash;int maxLen = 0;char maxCh = 'a';for(const auto& ch : str){if(++hash[ch] > maxLen){maxLen = hash[ch];maxCh = ch;}}if(maxLen > (n + 1) / 2){cout << "no" << endl;}else{int index = 0;string ret;ret.resize(n);// 先去拜访出现次数最多的while(maxLen--){ret[index] = maxCh;index += 2;}hash.erase(maxCh);// 再摆放剩下的for(auto& it : hash){if(it.second){while(it.second--){if(index >= n){index = 1;}ret[index] = it.first;index += 2;}}}cout << "yes" << endl<< ret << endl;}return 0;
  }