蚂蚁笔试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;
}
类似资料：