QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#302395#7618. Pattern Searchdefyers#RE 1ms3564kbC++201.4kb2024-01-10 20:24:442024-01-10 20:24:45

Judging History

你现在查看的是最新测评结果

  • [2024-01-10 20:24:45]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3564kb
  • [2024-01-10 20:24:44]
  • 提交

answer

#include "bits/stdc++.h"

using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")

using ll = long long;
using LL = long long;
using pii = pair<int, int>;

void solve(int TC) {
	string s;
	string t;
	cin >> s >> t;

	int n = s.size();
	int m = t.size();

	vector<int> freqs(26), freqt(26);
	for (auto ch: s) {
		freqs[ch - 'a']++;
	}
	for (auto ch: t) {
		freqt[ch - 'a']++;
	}

	for (int i = 0; i < 26; i++) {
		freqs[i] -= freqt[i];
		if (freqs[i] < 0) {
			cout << "0\n";
			return;
		}
	}

	vector<vector<int>> d(26, vector<int>(m + 1, 1e9));
	for (int c = 0; c < 26; c++) {
		for (int i = 1; i <= freqt[c]; i++) {
			if (freqt[c] % i == 0) {
				d[c][freqt[c] / i + 1] = min(d[c][freqt[c] / i + 1], i);
			}
			d[c][freqt[c] / i] = min(d[c][freqt[c] / i], i);
		}
	}

	int ans = 0;

	for (int i = 1; i <= m; i++) {
		bool fail = false;

		for (int c = 0; c < 26; c++) {
			if (freqt[c] == 0) continue;

			if (d[c][i] == 1e9) {
				fail = true;
				break;
			}

		}
		if (fail) continue;

		int mn = 1e9;
		for (int c = 0; c < 26; c++) {
			if (freqt[c] > 0) {
				mn = min(mn, freqs[c] / d[c][i]);
			}
		}

		ans = max(ans, mn + 1);
	}

	cout << ans << "\n";
}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cout << fixed << setprecision(10);

	int t = 1;
	cin >> t;
	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3476kb

input:

2
bajkaaall aal
abca cba

output:

2
1

result:

ok 2 number(s): "2 1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3564kb

input:

16
a a
a b
b a
aa a
ab aa
ab b
ab c
aaz az
abcde edcba
aaaaaaaaaaaabbb aaaaaaaaabb
aaaaaazz az
aaaaaaaaaz zzzzz
gggggggggggggggggggge ggggeeee
hyphyphyphyphyphyphyphyphyphyphyphyp eeeeeeeeee
hyphyphyphyphyphyphyphyphyphyphyphype eeteeteeteet
aaaabbbbbbcccccccc aaabbbbbcccccc

output:

1
0
0
2
0
1
0
1
1
2
2
0
0
0
0
1

result:

ok 16 numbers

Test #3:

score: -100
Runtime Error

input:

90522
cyykzyylklyll ylcyllklzk
ttusuuudtdtqus uuddu
uefyqfkiblyfkyd ffyyqde
qfxqecljeqeedea jqdxf
prrbfxdxffpbpp ffppd
ynjgygygjnjnjg jgynjggn
maenpaksmxyya saxkep
nrdnbnjipnjowjz djbwojzrpni
oputuoufoojupu uoouopo
mphmhphpkpkpmhp phmhpppp
zwznzpzqyjczzy wczjnpzqy
pfxfxxkfffpfx fxffkffxpx
hzdhzhhh h...

output:


result: