牛客小白月赛12

牛客小白月赛12
A题:贪心—不会
B题:快速幂取模
C题:线性筛选，快速幂—不会
E题:二分—不会
G题:gcd
I题:tarjan算法—不会
J题:找子字符串，可以非连续

##A题
题目链接:
https://ac.nowcoder.com/acm/contest/392/A
贪心不会，用pair去存数

B题

题目链接:
https://ac.nowcoder.com/acm/contest/392/B
快速幂取模模板
超大数，定义__int128


#define lll __int128
#define ll long long
ll (lll a, lll b, lll p) {
    lll s = 1;
    while (b) {
        if (b & 1)
            s = (s * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return (ll) s%p;
}
int main() {
    int t;
    ll a, b, p;
    scanf("%d", &t);
    while (t--) {
        scanf("%lld%lld%lld", &a, &b, &p);
        printf("%lldn", quick(a, b, p));
    }
    return 0;
}

C题

线性筛选，快速幂

E题

题目链接:
https://ac.nowcoder.com/acm/contest/392/E
二分
但为什么条件是r-l>1
为什么输出的是left？？？

#include<iostream>
#include<cstdio>
using namespace std;
const int maxn=200005;
int main(){
    int n,k;
    while(scanf("%d%d",&n,&k)!=EOF){
        int l[maxn];
        for(int i=0;i<n;i++){
            scanf("%d",&l[i]);
        }
        
        int left=0,right=0x7fffffff;
        int mid;
        while((right-left)>1){
            mid=(right+left)/2;
            int sum=0;
            for 大专栏  牛客小白月赛12(int i=0;i<n;i++){
                sum+=l[i]/mid;
            }
            if(sum>=k){
                left=mid;
            }else{
                right=mid;
            }
        }
        printf("%dn",left);

    }
    return 0;
}

G题

题目链接:
https://ac.nowcoder.com/acm/contest/392/G
算法库里自带gcd函数
类斐波那契数列的gcd，只需求出前两个数的gcd即可

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll a,b,n;
int main(){
    while(scanf("%lld%lld%lld",&a,&b,&n)!=EOF){
        printf("%lldn",__gcd(a,b));
    }

    return 0;
}

I题

tarjan算法

tarjan算法详解，强连通图，强连通分量，强连通

j题

题目链接:
https://ac.nowcoder.com/acm/contest/392/A
找子字符串，可以非连续
新输出方式

#include<cstdio>
#include<cstring>
using namespace std;
const int N=1000005;
int main(){
    char a[N];
    char b[N];
    int n;
    scanf("%s",a);
    int l1=strlen(a);
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%s",b);
        int l2=strlen(b);
        int cnt=0;
        for(int j=0;j<l1;j++){
            if(a[j]==b[cnt])cnt++;
            if(cnt>=l2)break;
        }
        printf("%sn",cnt>=l2?"Yes":"No");
    }
    return 0;
}