蚂蚁笔试9-15 算法卷 AK代码

第一题

质因数分解判断奇偶即可

#include <bits/stdc++.h>

using namespace std;

int main(){
    // freopen("1.in","r",stdin);
    int t;
    int n;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int cnt=0;
        for(int i=2;i*i<=n;i++){
            while(n%i==0){
                n/=i;
                cnt++;
            }
        }
        if(n!=1) cnt++;
        if(cnt%2==0) puts("yukari");
        else puts("kou");
    }
    return 0;
}

第二题

找最长数组长度，然后差分一下即可

#include <bits/stdc++.h>

using namespace std;

int a[220000];
int res[220000];
int main(){
    // freopen("1.in","r",stdin);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    int pre=0;
    a[0]=-100000;
    for(int i=1;i<=n;i++){
        if(a[i]>a[i-1]) pre++;
        else pre=1;
        res[pre]++;
    }
    for(int i=n;i>=1;i--) res[i]+=res[i+1];
    for(int i=1;i<=n;i++){
        printf("%d",res[i]);
        if(i==n) puts("");
        else printf(" ");
    }

    return 0;
}

第三题

遍历字符串，对于i这个位置求取子序列不存在i之后字符且包含i的好子序列个数，然后累加起来即可

对于每个位置好串枚举26个字母

若s[i]=j，则个数是C(num[j],1)+C(num[j],3)+C(num[j],5)+... 二项式定理得Pow(2, num[j]-1)

若s[i]!=j，则个数是C(num[j],0)+C(num[j],2)+C(num[j],4)+... 二项式定理得Pow(2,num[j]-1)

具体代码如下

#include <bits/stdc++.h>

using namespace std;

const int N=2e5+7;
char s[N];
int num[30];
long long TMP[30];
long long mod=1e9+7;
long long Pow(long long x){
    long long res=1;
    long long p=2; 
    while(x){
        if(x%2==1) {
            res=res*p%mod;
            x--;
        }
        else{
            x/=2;
            p=p*p%mod;
        }
    }
    return res;
}
int main(){
    // freopen("1.in","r",stdin);
    scanf("%s",s+1);
    int n=strlen(s+1);
    long long ans=0;
    for(int i=0;i<26;i++) TMP[i]=1;
    for(int i=1;i<=n;i++){
        long long p=1;
        for(int j=0;j<26;j++){
            if(num[j]==0){
                if(s[i]-'a'==j) p=0;
                continue;
            }
            if(s[i]-'a'==j){
                TMP[j]=Pow(num[j]-1);
            }
            p=p*TMP[j]%mod;
        }
        ans = (ans+p)%mod;
        num[s[i]-'a']++;
        TMP[s[i]-'a']=Pow(num[s[i]-'a']-1);
    }
    printf("%lld\n",ans);
    return 0;
}

#蚂蚁笔试##笔试##蚂蚁金服##蚂蚁2023秋招笔试凉了啊#