A.Hard KMP Problem
#include <bits/stdc++.h>
using namespace std;
const int N = 30;
int cnt1[N],cnt2[N];
string s,t;
void solve()
{
memset(cnt1,0,sizeof cnt1);
memset(cnt2,0,sizeof cnt2);
cin >> s >> t;
for(int i = 0;s[i];i++) cnt1[s[i]-'a']++;
for(int i = 0;t[i];i++) cnt2[t[i]-'a']++;
int ans = 1e5;
for(int i = 0;t[i];i++)
{
if(cnt1[t[i]-'a']) ans = min(ans,cnt1[t[i]-'a']/cnt2[t[i]-'a']);
else
{
ans = 0;
break;
}
}
cout << ans << endl;
}
int main()
{
int T;
cin >> T;
while(T--)
{
solve();
}
return 0;
}
B.Sum Gcd
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
unordered_map<LL,LL>mp;
LL gcd(LL a,LL b)
{
return b ? gcd(b,a%b) : a;
}
int main()
{
LL n,k;
cin >> n >> k;
LL ans = 0;
for(int i = 0;i<n;i++)
{
LL x;
cin >> x;
mp[x] = gcd(x,k);
mp[x*x] = gcd(x*x,k);
ans += mp[x] * (n-1) + mp[x*x]/mp[x];
}
cout << ans << endl;
return 0;
}
C.Future Machine
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int x[N],y[N];
int main()
{
int n,m,X;
cin >> n >> m >> X;
int yl = 1e9,yr = 0;
for(int i = 0;i<n;i++) scanf("%d",&x[i]);
for(int i = 0;i<m;i++) scanf("%d",&y[i]),yl = min(y[i],yl),yr = max(y[i],yr);
for(int i = 0;i<n;i++)
{
if(X < min(yr,x[i])) X = min(yr,x[i]);
else if(X > max(yl,x[i])) X = max(yl,x[i]);
}
cout << X << endl;
return 0;
}