QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #718244 | #8334. Gene | xinlengweishang | WA | 12ms | 193528kb | C++20 | 2.1kb | 2024-11-06 20:03:54 | 2024-11-06 20:03:55 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define Mod 998244353ll
#define sushu 23ll
using namespace std;
char s[400][70000],t[70000];
ll f[400][70000];
ll g[70000];
ll qp[70000];
ll n,q,m,k;
ll flag;
int check(ll x,ll l ,ll r){
if((f[x][r]-f[x][l-1]+Mod)%Mod==(g[r]-g[l-1]+Mod)%Mod) return 1;
else return 0;
}
void sslove(ll x,ll l,ll r){
// printf(" %lld %lld %lld\n",x,l,r);
if(r==l){
flag--;
for(int i=l;i<=r;i++){
if(s[x][i]!=t[i]) flag++;
}
// printf(" check : %lld %lld %lld flag=%lld\n",x,l,r,flag);
return ;
}
if(flag>k+1) return ;
flag--;
ll mid=(l+r)>>1;
if(!check(x,l,mid)){
flag++;
sslove(x,l,mid);
}
if(flag>k) return ;
if(!check(x,mid+1,r)){
// for(int i=mid+1;i<=r;i++){
// printf(" %d s: %c t: %c\n",i,s[x][i],t[i]);
// }
// printf(" s: %lld t: %lld\n",f[x][r]-f[x][mid],g[r]-g[mid]);
flag++;
sslove(x,mid+1,r);
}
return ;
}
void slove(){
scanf("%lld%lld%lld%lld",&n,&q,&m,&k);
for(int i=1;i<=n;i++){
scanf("%s",s[i]+1);
f[i][0]=0;
for(int q=1;q<=m;q++){
f[i][q]=(f[i][q-1]+(s[i][q]-'a'+1)*qp[q])%Mod;
}
}
// for(int i=1;i<=n;i++){
// printf("%s\n",s[i]+1);
// for(int q=1;q<=m;q++){
// printf("%d %d %lld\n",i,q,f[i][q]);
// }
// }
for(int i=1;i<=q;i++){
scanf("%s",t+1);
g[0]=0;
int ans=0;
for(int q=1;q<=m;q++){
g[q]=(g[q-1]+(t[q]-'a'+1)*qp[q])%Mod;
// printf(" %d g[q]=%lld g[q-1]=%lld %c \n",i,g[q],g[q-1],t[q]);
}
// printf("%s\n",t+1);
// for(int q=1;q<=m;q++){
// printf(" %d %lld\n",q,g[q]);
// }
for(int q=1;q<=n;q++){
if(check(q,1,m)){
ans++;
}
else{
flag=1;
sslove(q,1,m);
// printf("%d %d %d\n",i,q,flag);
if(flag<=k){
ans++;
}
}
}
printf("%d\n",ans);
}
}
int main(){
qp[0]=1;
for(int i=1;i<=600010;i++){
qp[i]=(qp[i-1]*sushu)%Mod;
}
int T=1;
while(T--) slove();
return 0;
}
/*
6 4 4 1
kaki
kika
manu
nana
tepu
tero
kaka
mana
teri
anan
*/
/*
8 2 7 3
delphis
aduncus
peronii
plumbea
clymene
hectori
griseus
electra
eleelea
ddlpcus
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 11920kb
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: 4ms
memory: 11852kb
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: 4ms
memory: 191688kb
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: 7ms
memory: 193528kb
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: 12ms
memory: 192704kb
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:
96 109 114 109 108 96 108 109 113 106 104 96 111 109 95 107 93 99 112 101 105 116 117 109 106 115 116 97 108 95 114 88 94 116 96 97 104 107 91 104 104 92 115 103 121 102 116 105 101 105 108 95 118 107 91 98 99 115 101 106 120 91 118 91 111 99 104 102 104 96 100 116 111 110 107 118 95 96 103 108 108 ...
result:
wrong answer 4th numbers differ - expected: '108', found: '109'