QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#757255 | #7618. Pattern Search | inksamurai | WA | 0ms | 3752kb | C++23 | 1.3kb | 2024-11-17 03:09:24 | 2024-11-17 03:09:25 |
Judging History
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 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...);}
vi get(string s){
vi cnt(26);
rep(i,sz(s)){
cnt[s[i]-'a']+=1;
}
return cnt;
}
void slv(){
string s,t;
cin>>s>>t;
const int n=sz(s);
const int m=sz(t);
auto cnt_s=get(s);
auto cnt_t=get(t);
int si=26;
rep(i,si){
if(cnt_s[i]<cnt_t[i]){
print(0);
return;
}
}
int ans=0;
rng(pat,1,m+1){
int take=0;
int k=m/pat;
int pok=1;
rep(i,si){
int x=cnt_t[i]/k,c=cnt_t[i]%k;
if(x<c) pok=0;
take+=x;
}
if(!pok) continue;
if(take==pat){
int now=1e9;
rep(i,si){
if(!cnt_t[i]) continue;
int x=cnt_t[i]/k,c=cnt_t[i]%k;
now=min(now,(cnt_s[i]-cnt_t[i])/x);
}
now+=1;
ans=max(ans,now);
}
}
print(ans);
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0);
int t;
cin>>t;
rep(cs,t){
slv();
}
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
input:
2 bajkaaall aal abca cba
output:
2 1
result:
ok 2 number(s): "2 1"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3752kb
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 1 2 0 0 0 0 1
result:
wrong answer 10th numbers differ - expected: '2', found: '1'