QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#760447 | #7618. Pattern Search | inksamurai | RE | 0ms | 0kb | C++23 | 1.8kb | 2024-11-18 16:58:55 | 2024-11-18 16:58:56 |
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define vec(...) vector<__VA_ARGS__>
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
const int SI=26;
vi get(string s){
vi cnt(SI);
rep(i,sz(s)) cnt[s[i]-'a']+=1;
return cnt;
}
void slv(){
string s,t;
cin>>s>>t;
int n=sz(s),m=sz(t);
vi cnts=get(s),cntt=get(t);
rep(i,SI){
if(cnts[i]<cntt[i]){
print(0);
return;
}
}
vi can(m+1,1);
vec(vi) qs(m+1,vi(SI));
rng(pat,1,m+1){
int k=m/pat;
int lo=0,hi=0;
rep(i,SI){
if(!cntt[i]) continue;
// x * k >= cntt[i] - x * k
int c=cntt[i];
int x=(c+2*k-1)/(2*k);
int y=c/k;
if(y<c-y*k) can[pat]=0;
assert(x*k>=cntt[i]-x*k);
lo+=x;
hi+=y;
qs[pat][i]=x;
}
if(!(lo<=pat and pat<=hi)) can[pat]=0;
}
auto af=[&](int x){
rng(pat,1,m+1){
if(!can[pat]) continue;
int pok=1;
rep(i,SI){
if(!cntt[i]) continue;
// (cnts[i] - cntt[i]) / p >= x
// (cnts[i] - cntt[i]) / x >= p
int p=(cnts[i]-cntt[i])/x;
while((cnts[i]-cntt[i])/p<x) p+=1;
if(!(qs[pat][i]<=p)){
pok=0;
break;
}
}
if(pok) return 1;
}
return 0;
};
// print(af(1));
int l=1,r=n;
int opt=0;
while(l<=r){
int _m=(l+r)/2;
if(af(_m)) opt=_m,l=_m+1;
else r=_m-1;
}
opt+=1;
print(opt);
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
int t;
cin>>t;
rep(cs,t){
slv();
}
}
详细
Test #1:
score: 0
Runtime Error
input:
2 bajkaaall aal abca cba