牛客练习赛118

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;
}