HackerRank HourRank 25

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：
本文字数： 4k | 阅读时长 ≈ 0:04

Constructing a Number

计算用给出数的所有数位能否组成一个 33 的倍数

按位累加判断是否是 33 的倍数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int t,n,a;
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        int sum=0;
        while(n--){
            cin>>a;
            while(a){
                sum=(sum+a%10)%3;
                a/=10;
            }
        }
        puts(sum==0?"Yes":"No");
    }
    return 0;
}

Maximum Palindromes

计算使用一个给定字符串的子串中所有字母构成的最长回文串有多少种。每次询问一个子串，1≤∣S∣,q≤1051 \leq |S|,q \leq 10^5，模 109+710^9+7 的值。

预处理每个字母次数的前缀和，预处理阶乘及其逆，直接用多重排列算回文串前一半有多少种。

P(n;r1,r2,…,rk)=n!r1!r2!…rk!P(n;r_1,r_2,\dots,r_k)=\frac{n!}{r_1!r_2!\dots r_k!}

注意回文串中间一位可以是无配对的字母（如 aba），再统计出现奇数次的字母种数乘起来即可。

第一次交，在最后乘法的时候忘记取模了！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN=1e5;
typedef long long LL;
const LL MOD=1e9+7;
int q;
char s[MAXN+10];
int cnt[MAXN+10][26];
int _c[26];
LL fac[MAXN+10],inv[MAXN+10];
LL qpow(LL x,LL n){
    LL ans=1;
    while(n){
        if(n&1)ans=ans*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return ans;
}
LL solve(int l,int r){
    int s=0,rs=0;
    for(int j=0;j<26;j++){
        _c[j]=cnt[r][j]-cnt[l-1][j];
        if(_c[j]&1){
            _c[j]--;
            rs++;
        }
        s+=(_c[j] >> 1);
    }
    LL ans=fac[s];
    for(int j=0;j<26;j++)
        if(_c[j]>0){
            // cout<<j<<" "<<_c[j]<<endl;
            ans=ans*inv[_c[j]>>1]%MOD;
        }
    return rs==0?ans:(ans*rs%MOD);
}
int main(){
    scanf("%s",s+1);
    int len=strlen(s+1);
    fac[0]=1;
    for(int i=1;i<=len+3;i++)fac[i]=(fac[i-1]*i)%MOD;
    inv[len+3]=qpow(fac[len+3],MOD-2);
    for(int i=len+2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%MOD;
    for(int i=1;i<=len;i++){
        for(int j=0;j<26;j++)cnt[i][j]=cnt[i-1][j];
        cnt[i][s[i]-'a']++;
    }
    cin>>q;
    while(q--){
        int l,r;cin>>l>>r;
        cout<<solve(l,r)<<endl;
    }
    return 0;
}

The Strange Function

给一个整数（可负）序列 [a1,a2,…,an][a_1,a_2,\dots,a_n]，定义

f(l,r)=gcd⁡(a_l,a_l+1,…,a_r)((∑_i=lra_i)−max⁡(a_l,a_l+1,…,a_r))f(l,r)=\gcd(a\_l,a\_{l+1},\dots,a\_r)\left((\sum\_{i=l}^r a\_i)-\max(a\_l,a\_{l+1},\dots,a\_r)\right)

求

max⁡1≤l≤r≤nf(l,r)\max_{1\leq l \leq r \leq n} f(l,r)

1≤n≤105,∣ai∣≤1061 \leq n \leq 10^5, |a_i| \leq 10^6

不会做。。然而可以骗分233，先模拟，这一步是 O(n2)O(n^2)的。
一个很有用的优化是当左端点值为负数时可以直接跳过（这对答案没有贡献，显然一个起点正的更优，且答案最小是 00 ，因为 f(i,i)=0f(i,i)=0。

然后过了 22/4422/44 个点，Rank80->Rank35，赚了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN=50000;
typedef long long LL;
int n;
int a[MAXN+3],b[MAXN+3];
int gcd(int x,int y){
    return y?gcd(y,x%y):x;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]<0)b[i]=-a[i];
        else b[i]=a[i];
    }
    LL ans=0;
    for(int i=1;i<=n;i++){
        if(a[i]<=0)continue;
        int m=a[i],g=b[i],s=a[i];
        for(int j=i+1;j<=n;j++){
            if(a[j]>m)m=a[j];
            if(g!=1)g=gcd(g,b[j]);
            s+=a[j];
            if(s-m>0){
                LL t=(LL)g*(s-m);
                if(ans<t)ans=t;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}
0%