A：https://ac.nowcoder.com/acm/contest/1083/A

题意：

给出字符串s只包含abc，问你字符串中包含abc子串的个数

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
char s[100010];
int main()
{
    scanf("%s",s+1);
    int l = strlen(s+1);
    ll ans = 0,prea = 0,preab = 0;
    for(int i=1;i<=l;i++){
        if(s[i] == 'a'){
            prea++;
        }
        if(s[i] == 'b'){
            if(prea){
                preab += prea;
            }
        }
        if(s[i] == 'c'){
            ans += preab;
        }
    }
    cout<<ans<<endl;


    return 0;
}

B：https://ac.nowcoder.com/acm/contest/1083/B

题意：

给出一个字符串s1，给出m个询问，每次询问输入一个字符串s2，s2是否是s1的子串

题解：

vector存放每一个字母的下标，
遍历s2的每一个字母

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxx = 1e5+10;
vector<int> v[40];
vector<int>::iterator it;
char s1[maxx],s2[55];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    scanf("%s",s1+1);
    for(int i=1;i<=n;i++){
        v[s1[i]-'a'].push_back(i);
    }
    while(m--)
    {
        int x = 0;
        int flag = 0;
        scanf("%s",s2+1);
        int len = strlen(s2+1);
        for(int i=1;i<=len;i++){
            vector<int> &now = v[s2[i]-'a'];
            it = upper_bound(now.begin(),now.end(),x);
            if(it == now.end()){
                flag = 1;break;
            }
            x = *it;
        }
        if(flag){
            printf("NO\n");
        }else{
            printf("YES\n");
        }
    }
    return 0;
}

C：https://ac.nowcoder.com/acm/contest/1083/C

题意：

输入n，是否能找到另外俩条边a，b，使得a，b，n构成直角三角形，如果不能输出-1，否则输出俩条边

题解：

勾股数定理
当a为大于1的奇数2n+1时，b=2n^2+2n, c=2n^2+2n+1
当a为大于4的偶数2n时，b=n^2-1, c=n^2+1

代码:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll pow(ll x)
{
    return x*x;
}
int main()
{
    ll n;
    cin>>n;
    if(n <= 2){
        printf("-1\n");
    }
    if(n%2){
        n = (n-1)/2;
        printf("%lld %lld\n",2*1ll*pow(n)+2*n,2*1ll*pow(n)+2*n+1);
    }else{
        n = n/2;
        printf("%lld %lld\n",1ll*pow(n)-1,1ll*pow(n)+1);
    }
    return 0;
}

D：https://ac.nowcoder.com/acm/contest/1083/D

题意：

在一个长为400的数轴上，有n只羊，每只羊都会在固定的[l,r]区间的下标上吃草，一只羊只能吃一个下标的草，不能多个羊吃同一个下标的草。
每次询问在[l,r]区间上最多有多少只羊在吃草。

题解：

multiset，贪心

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxx = 410;
int a[maxx],b[maxx];
int main()
{
    int n,m,l,r,ans = 0;
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    while(m--)
    {
        ans = 0;
        multiset<int> s;
        scanf("%d%d",&l,&r);
        for(int i=1;i<=n;i++){
            if(a[i] < l && b[i] >= l)
                s.insert(b[i]);
        }
        for(int i=l;i<=r;i++){
            for(int j=1;j<=n;j++)
                if(a[j] == i)
                    s.insert(b[j]);
            if(s.size()){
                ans++,s.erase(s.begin());
            }
            s.erase(i);
        }
        cout<<ans<<endl;
    }
    return 0;
}