QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#226241 | #7618. Pattern Search | tselmegkh | WA | 1ms | 3468kb | C++17 | 1.7kb | 2023-10-25 18:59:30 | 2023-10-25 18:59:31 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
string s, t;
cin >> s >> t;
vector<int> fs(26);
for (char c : s) {
fs[c - 'a']++;
}
vector<int> ft(26);
for (char c : t) {
ft[c - 'a']++;
}
int mn = 1e9;
for (int i = 0; i < 26; i++) {
if (ft[i] > 0) {
mn = min(mn, ft[i]);
}
}
vector<int> a(26);
for (int i = 0; i < 26; i++) {
a[i] = ft[i] / mn;
ft[i] %= mn;
}
int c = 1e9;
for (int i = 0; i < 26; i++) {
if (a[i] == 0) continue;
c = min(c, fs[i] / a[i]);
}
int ans = max(0, c - mn);
bool ok = c >= mn;
for (int i = 0; i < 26; i++) {
if (ft[i] > fs[i] - a[i] * c) {
ok = 0;
}
}
if (ok) ans++;
vector<int> cntT(26, 0), cntS(26, 0);
for(char c : t){
cntT[c - 'a']++;
}
for(char c : s){
cntS[c - 'a']++;
}
int len = 0;
for(int i = 0; i < 26; i++){
len += cntT[i] / 2;
}
int res = 0;
bool yes = 1;
for(int i = 0; i < 26; i++){
yes &= (cntS[i] >= cntT[i]);
}
if(yes){
res++;
for(int i = 0; i < 26; i++){
cntS[i] -= cntT[i];
}
}
int n = t.size();
for(int i = 0; i < 26; i++){
cntT[i] -= cntT[i] / 2;
}
int men = 1e9;
for(int i = 0; i < 26; i++){
men = min(men, cntS[i] / cntT[i]);
}
res += mn;
ans = max(ans, res);
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3468kb
input:
2 bajkaaall aal abca cba
output:
2 2
result:
wrong answer 2nd numbers differ - expected: '1', found: '2'