QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#749514 | #7618. Pattern Search | ucup-team3474 | WA | 40ms | 5864kb | C++20 | 3.0kb | 2024-11-15 02:37:10 | 2024-11-15 02:37:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
typedef long long ll;
typedef pair<int,int> PII;
ll n,n1,n2;
char s1[N],s2[N];
int cnt1[26],cnt2[26],ccnt1[26];
int cntneed[26];
int mx[26];
bool check(int c1[],int c2[]){
for(int i=0;i<26;i++){
if(c1[i]<c2[i]) return false;
c1[i]-=c2[i];
}
return true;
}
bool cmp(int leave){
for(int i=0;i<26;i++){
leave-=max(cntneed[i]-mx[i],0);
}
return leave>=0;
}
bool Check(int mid){
// cout<<"--"<<mid<<endl;
memset(mx,0,sizeof mx);
int tot=0;
for(int i=0;i<26;i++){
// if(cnt1[i]<mid) return false;
mx[i]=cnt1[i]/mid;
tot+=cnt1[i];
}
// if(tot<n2*mid) return false;
// for(int i=0;i<26;i++) cout<<mx[i]<<" ";
// cout<<endl;
bool flag=1;
for(int i=0;i<26;i++){
if((cnt2[i]+1)/2>mx[i]) flag=0;
}
if(flag) return true;
for(int border=n2-1;border>=(n2+1)/2;border--){
// cout<<"--"<<" "<<border<<endl;
int cha=n2-border;
if(cha*mid>tot) continue;
int val=n2/cha;
int cntmod=n2%cha,cnt=cha-cntmod;
// cout<<cntmod<<" "<<cnt<<endl;
vector<PII> v;
for(int i=0;i<26;i++) ccnt1[i]=cnt2[i];
memset(cntneed,0,sizeof cntneed);
bool flg=1;
for(int i=0;i<26;i++){
int x=ccnt1[i],y=i;
int t=x%val;
// cout<<x<<" "<<y<<" "<<t*(val+1)<<endl;
if(t*(val+1)>x){
flg=0;
break;
}
x-=t*(val+1);
cntneed[y]+=t;
cntmod-=t;
if(cntmod<0){
flg=0;
break;
}
ccnt1[i]=x;
}
// cout<<"--"<<border<<endl;
if(!flg) continue;
// for(int i=0;i<26;i++) cout<<cntneed[i]<<" ";
// cout<<endl;
int leave=cntmod/val;
for(int i=0;i<26;i++) cntneed[i]+=ccnt1[i]/val;
if(cmp(leave)){
// cout<<"--"<<border<<endl;
//
return true;
}
}
return false;
}
void HuangGuangsheng(){
scanf("%s",s1+1);
scanf("%s",s2+1);
n1=strlen(s1+1),n2=strlen(s2+1);
memset(cnt1,0,sizeof cnt1);
memset(cnt2,0,sizeof cnt2);
memset(cntneed,0,sizeof cntneed);
for(int i=1;i<=n1;i++) cnt1[s1[i]-'a']++;
for(int i=1;i<=n2;i++) cnt2[s2[i]-'a']++;
for(int i=0;i<26;i++) cntneed[i]=(cnt2[i]+1)/2;
int ans=0;
if(check(cnt1,cnt2)) ans++;
else{
puts("0");
return;
}
ll l=1,r=n1;
ll tot=0;
if(!Check(1)){
puts("1");
return;
}
// Check(6);
while(l<r){
ll mid=l+r+1>>1;
if(Check(mid)) l=mid;
else r=mid-1;
}
printf("%lld\n",l+1);
}
int main(){
int hgs;
cin>>hgs;
while(hgs--){
HuangGuangsheng();
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5844kb
input:
2 bajkaaall aal abca cba
output:
2 1
result:
ok 2 number(s): "2 1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 5852kb
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
Wrong Answer
time: 40ms
memory: 5864kb
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:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 4 1 1 1 2 1 1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 2 3 1 2 1 1 1 1 1 1 1 2 2 1 1 1 1 1 2 1 1 1 1 4 1 2 1 1 1 1 1 3 1 1 3 1 1 1 1 1 1 1 1 1 1 1 3 1 1 4 1 1 1 1 1 1 1 1 1 1 5 1 7 1 1 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 ...
result:
wrong answer 55th numbers differ - expected: '1', found: '2'