)
题目链接：https://codeforces.com/contest/2278/problem/A
题目大意：给两个字符串 `p` 和 `q`，分别表示分子和分母中变量的乘积，每个字符代表一个变量。变量可以任意重排，分子和分母中相同的字符可以一一抵消。判断经过抵消后，分子剩余变量能否恰好组成字符串 `six`，并且分母必须为空。
题目思路：由于最终分子只有six，分母为空，我们可以先判断字符串p的长度-字符串q的长度是否为3，如果不为3则一定不可能会有six，否则我们可以判断s，i，x是否存在并记录位置，然后定义一个字符串t来存储除了s,i,x这三个字符的p字符串，最后比较t,q字符串的长度，如果不等也不合法，相等的话，则挨个比较字符，如果不同则不合法经过上述所有操作后则一定yes
时间复杂度：O(T*nlogn)
代码如下：
#include <bits/stdc++.h> using namespace std; #define endl "\n" using ll = long long; using ld = long double; /* https://codeforces.com/contest/2278/problem/A Div.3 CF 1131A题(排序，模拟) 题目大意：给两个字符串 `p` 和 `q`，分别表示分子和分母中变量的乘积，每个字符代表一个变量。 变量可以任意重排，分子和分母中相同的字符可以一一抵消。判断经过抵消后，分子剩余变量能否恰好组成字符串 `six`，并且分母必须为空。 题目思路：由于最终分子只有six，分母为空，我们可以先判断字符串p的长度-字符串q的长度是否为3， 如果不为3则一定不可能会有six，否则我们可以判断s，i，x是否存在并记录位置， 然后定义一个字符串t来存储除了s,i,x这三个字符的p字符串，最后比较t,q字符串的长度，如果不等也不合法，相等的话，则挨个比较字符，如果不同则不合法 经过上述所有操作后则一定yes 时间复杂度：O(T*nlogn) */ void solve() { int n, m; cin >> n >> m; string s1, s2; cin >> s1 >> s2; if (n - m != 3)//最终分子长度一定为3 { cout << "NO" << endl; return; } bool s = false, i = false, x = false;//判断six是否存在 int s_pos = -1, i_pos = -1, x_pos = -1;//记录six位置 for (int j = 0; j < n; j++) { if (s1[j] == 's') { s = true; s_pos = j; } else if (s1[j] == 'i') { i = true; i_pos = j; } else if (s1[j] == 'x') { x = true; x_pos = j; } } if (s && i && x)//如果six存在 { string t; //存储除了s,i,x这三个字符的p字符串 for (int j = 0; j < n; j++) { if (j == s_pos || j == i_pos || j == x_pos)//如果遇到six就跳过 { continue; } t += s1[j]; } if ((int)t.size() != m)//长度不等也不合法 { cout << "NO" << endl; } else { sort(t.begin(), t.end());//排序方便比较 sort(s2.begin(), s2.end()); for (int j = 0; j < m; j++) { if (t[j] != s2[j])//遇到不同就退出 { cout << "NO" << endl; return; } } cout << "YES" << endl;//经过上面所有操作后，那么一定是可以yes的 } } else//six不存在就直接输出no { cout << "NO" << endl; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { solve(); } return 0; }
