QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#745037 | #8334. Gene | dodola | WA | 69ms | 3912kb | C++17 | 3.2kb | 2024-11-14 01:47:20 | 2024-11-14 01:47:20 |
Judging History
answer
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
typedef double ld;
typedef unsigned long ul;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
const int maxn = 3e6 + 50;
const int inf = 0x3f3f3f;
const ll mo998 = 998244353;
const ull mod1 = 212370440130137957, mod2 = 1e9 + 7;
vector<bool> isprime;
vector<ll> primes;
void init_primes() {
isprime.assign(maxn + 1, true);
isprime[0] = isprime[1] = false;
for (ll i = 2; i <= maxn; i++) {
if (!isprime[i])
continue;
for (ll j = 2; i * j <= maxn; j++) {
isprime[i * j] = false;
}
}
}
ull b1 = 131, b2 = 233;
vector<ull> pb1, pb2;
pair<vector<ull>, vector<ull>> get_hash(string s) {
ll n = s.size();
vector<ull> v(n + 1), w(n + 1);
v[0] = 0, w[0] = 0;
for (int i = 0; i < n; i++) {
ll x = s[i] - 'a';
v[i + 1] = (v[i] * b1 + x) % mod1;
w[i + 1] = (w[i] * b2 + x) % mod2;
}
return {v, w};
}
ll n, q, m, k;
ll check(pair<vector<ull>, vector<ull>> v1, pair<vector<ull>, vector<ull>> v2,
ll lp) {
if ((v1.first[m] - v1.first[lp] * pb1[m - lp] + mod1) % mod1 ==
(v2.first[m] - v2.first[lp] * pb1[m - lp] + mod1) % mod1 &&
(v1.second[m] - v1.second[lp] * pb2[m - lp] + mod2) % mod2 ==
(v2.second[m] - v2.second[lp] * pb2[m - lp] + mod2) % mod2) {
return -1;
}
// lp是上一个不同的位置
ll l = lp + 1, r = m + 1; // [l,r]
while (l < r) {
ll mid = (l + r) / 2;
bool f1 = (v1.first[mid] - v1.first[lp] * pb1[mid - lp] + mod1) % mod1 ==
(v2.first[mid] - v2.first[lp] * pb1[mid - lp] + mod1) % mod1;
bool f2 = (v1.second[mid] - v1.second[lp] * pb2[mid - lp] + mod2) % mod2 ==
(v2.second[mid] - v2.second[lp] * pb2[mid - lp] + mod2) % mod2;
if (f1 && f2) {
l = mid + 1;
} else {
r = mid;
}
}
// 返回不同的那一位
return l;
};
void solve() {
cin >> n >> q >> m >> k;
ull bb1 = 1, bb2 = 1;
pb1.assign(m + 6, 0);
pb2.assign(m + 6, 0);
for (int i = 0; i <= m + 5; i++) {
pb1[i] = bb1;
bb1 *= b1;
pb2[i] = bb2;
bb2 *= b2;
}
vector<pair<vector<ull>, vector<ull>>> h1;
string ss;
// vector<string> sv;
for (int i = 0; i < n; i++) {
cin >> ss;
// sv.push_back(ss);
h1.push_back(get_hash(ss));
}
while (q--) {
string s;
cin >> s;
if (k >= m) {
cout << n << '\n';
continue;
}
auto hs = get_hash(s);
ll ans = 0ll;
for (int i = 0; i < n; i++) {
ll p = 0, cnt = 0;
bool flag = true;
while (p + 1 <= m) {
ll tp = check(h1[i], hs, p);
if (tp == -1) {
break;
}
p = tp;
if (p > m) {
break;
}
cnt++;
if (cnt > k) {
flag = false;
break;
}
}
if (flag) {
ans++;
}
}
cout << ans << '\n';
}
}
void init() {}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
init();
int _t = 1;
// cin >> _t;
// cin.get();
while (_t--)
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3580kb
input:
6 4 4 1 kaki kika manu nana tepu tero kaka mana teri anan
output:
2 2 1 0
result:
ok 4 number(s): "2 2 1 0"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
8 6 7 3 delphis aduncus peronii plumbea clymene hectori griseus electra delphis helpiii perphii clumeee eleelea ddlpcus
output:
1 1 2 2 1 2
result:
ok 6 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
300 300 9 10 dmzampmxe bteaudaxb fjfwhhsfq btnfzqtyp ijjrkbyht hkizlvgdc ukwsnhiff hacsdrwyl fbjabnhst ktsxbgbtg jopdbsdsr yxdxxjltd daechsouq klrglgwbn llzhqzlor ckdedutfn lkjxcryoe zvusjevtz cevrcdltg tdmmvvpkj davfsweem spcfhcitm aohsfqrqh lblehevpj soaqryimp tbxlulxmn tnlzbkhda ukfhjykuk eghpuua...
output:
300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 ...
result:
ok 300 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3832kb
input:
300 300 10 10 qoecfhznxd hkoaiunzim lhtzdmbrjs vqesfzpiuv amsgqjxmbq vptwyshswk sofrfmsrpf eplnexhmoh gcjtqavjga azytravylz akpuemdfpq oxkacujrhg bsgieguzuo bojvtfkbdf pmqmrbceej zgpfkqfeyx qkdbfrxqcj effpkigdcw kqyqmgjdzr czlbscrnaq rymhkenugz fuybclhlhj rtmclsdvwy rhfbfqfrfs bpemthjxfi jtcvqyltgj ...
output:
300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 300 ...
result:
ok 300 numbers
Test #5:
score: -100
Wrong Answer
time: 69ms
memory: 3632kb
input:
300 300 11 10 lonodhfyrbj njzuczzviuj usovdmjfjco bljtnmsjhut kkkeybjagck tbuivwfvjit qhjzqocsvod ayobjbagcgv dudupzsvqpe tcapottzyte wdevxapvocr hsvdfaahndr jjplhydycgn srrtpmqmygw gjjbcchwcur uivvuqldryj amlidxfsobz ofpnwqrzhly eolqcyidojx jpiybuplwcf jmxxtjnwsru ivkbixrgnph txjjppqkxgu vmmbwxmvjd...
output:
93 94 109 107 103 93 106 103 111 102 93 92 108 102 94 91 91 97 110 98 104 112 113 106 97 111 114 92 106 94 109 85 87 110 79 95 101 105 84 100 101 82 112 83 119 100 115 103 94 101 101 81 115 102 85 96 96 103 98 99 115 89 110 89 107 97 103 94 99 94 95 101 107 108 101 112 90 92 100 103 106 107 102 78 9...
result:
wrong answer 1st numbers differ - expected: '96', found: '93'