QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#749514#7618. Pattern Searchucup-team3474WA 40ms5864kbC++203.0kb2024-11-15 02:37:102024-11-15 02:37:12

Judging History

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

  • [2024-11-15 02:37:12]
  • 评测
  • 测评结果:WA
  • 用时:40ms
  • 内存:5864kb
  • [2024-11-15 02:37:10]
  • 提交

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'