QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#745037#8334. GenedodolaWA 69ms3912kbC++173.2kb2024-11-14 01:47:202024-11-14 01:47:20

Judging History

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

  • [2024-11-14 01:47:20]
  • 评测
  • 测评结果:WA
  • 用时:69ms
  • 内存:3912kb
  • [2024-11-14 01:47:20]
  • 提交

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'