Google Kickstart 2019 B

Posted on | In

2019 Google Kickstart Round B Solution

A. Building Palindromes

给一个长度为N的字符串以及Q次询问，每次询问字符串区间$[L_i,R_i]$中的字符能否重构成一个回文串。$N,Q\leq 10^5$

签到题，字符串中只有大写字母，就存一下第i位之前每个字母的数量，然后计算区间内字母数量能否构成回文就AC了

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
#include<bits/stdc++.h>
using namespace std;
int t;
int n,m;
int dp[100005][26];
string str;
int ans;
int main()
{
    scanf("%d",&t);
    for(int tt=1;tt<=t;tt++)
    {
       scanf("%d%d",&n,&m);
       ans=0;
       cin>>str;
       memset(dp,0,sizeof(dp));
       for(int i=1;i<=n;i++)
       {
           for(int j=0;j<26;j++)
           {
               if(str[i-1]-'A'==j)
                   dp[i][j]=dp[i-1][j]+1;
               else dp[i][j]=dp[i-1][j];
           }
       }
       for(int i=1;i<=m;i++)
       {
           int l,r;
           scanf("%d%d",&l,&r);
           int falg=0;
           for(int j=0;j<26&&falg<3;j++)
           {
               //cout<<dp[r][j]-dp[l-1][j]<<endl;
               if((dp[r][j]-dp[l-1][j])%2)
               {
                   falg++;
               }
           }
           if(falg<2) ans++;
       }
        printf("Case #%d: %d\n",tt,ans);
    }
    return 0;
}

B. Energy Stones

有N块能量石，每块能量石能量为$E_i$，每秒损失$L_i$能量，吃掉它要花费时间$S_i$。吃能量石时将立即接收到能量石当前的全部能量，无论要花费多长时间来吃他。问可以接收到的最大能量。$N, S_i \leq 100$

首先，将石头按最优解的顺序排序，考虑相邻两块能量石i和i+1，应该满足$S_iL_{i+1}< S_{i+1}L_{i}$，否则与最优解矛盾，交换i和i+1能量更多。所以我们可以按照这个规则对能量石排序，然后dp一下前i块石头在前j秒获得的最大能量,最后复杂度为O(NT), T为总时间。

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
#include<bits/stdc++.h>
using namespace std;

struct stone{
    int s,e,l;
};
bool cmp(stone x,stone y)
{
    return (x.s*y.l)<(x.l*y.s);
}
int n;
stone stones[110];
int dp[110][10100];
int main()
{
    int t;
    scanf("%d",&t);
    for(int tt=1;tt<=t;tt++)
    {
        memset(dp,0,sizeof(dp));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&stones[i].s,&stones[i].e,&stones[i].l);
        }
        sort(stones+1,stones+1+n,cmp);
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<stones[i].s;j++)
                dp[i][j]=dp[i-1][j];
            for(int j=stones[i].s;j<=10010;j++)
            {
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-stones[i].s]+max(stones[i].e-stones[i].l*(j-stones[i].s),0));
            }
        }
        int ans=0;
        for(int j=0;j<=10000;j++)
            ans=max(ans,dp[n][j]);
        printf("Case #%d: %d\n",tt,ans);
    }
    return 0;
}

C. Diverse Subarray

有N个饰品编号1-N，第i种饰品类型为$A_i$，Vanity要取$[l,r]$区间内的饰品，不过当区间内某一类型的饰品数量超过K时，这个类型的饰品将会全部抛弃，求通过选取了l和r来获取最多的饰品数量。$1 \leq N \leq 10^5$

例如 6个饰品，类型为1 1 4 1 4 4， K为2，则最佳选取为[1,4,1,4]，获得4个饰品

orz….. 有点说不清，线段树单点维护，以及维护连续区间最优解。

首先我们换个角度，我们可以把编号i以后的同一个类型的前K个饰品看为+1，第k+1个饰品看作-K，K+1之后的看为0，最后表达式为0+0+1+1-2+0+0，也就是求这个表达式的连续最大值。

不过因为要枚举起点，所以需要快速的更新计算结果，用线段树维护，由i到i+1，需要把i位设为0，把i位后面第k个与i位相同类型的饰品设为+1，第K+1个设为-K，更新线段树。

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<bits/stdc++.h>
using namespace std;

int n,s;
int next1[100100];
int next2[100100];
int score[100100];
int pre[100010];
int pre2[100010];
int ci[100010];
struct node{
    int maxsum,sum;
    int lsum,rsum,msum;
    int l,r;
};
vector<int> pos[100010];
node tree[400100];
void init_tree(int i,int l,int r){
    if(l>r) return ;
    tree[i].l=l;
    tree[i].r=r;
    if(l==r)
    {
        tree[i].maxsum=tree[i].sum=tree[i].lsum=tree[i].rsum=tree[i].msum=score[l];
        return;
    }
    if(l<r)
    {
        int mid=(l+r)/2;
        init_tree(i*2,l,mid);
        init_tree(i*2+1,mid+1,r);
        tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
        tree[i].lsum=max(tree[i*2].lsum,tree[i*2].sum+tree[i*2+1].lsum);
        tree[i].rsum=max(tree[i*2+1].rsum,tree[i*2].rsum+tree[i*2+1].sum);
        tree[i].msum=max(tree[i*2+1].msum,tree[i*2].msum);
        tree[i].msum=max(tree[i].msum,tree[i*2].rsum+tree[i*2+1].lsum);
        tree[i].maxsum=max(tree[i].lsum,max(tree[i].rsum,tree[i].msum));
    }
    return;
}
void update(int x,int data,int i)
{
    if(tree[i].l==tree[i].r)
    {
        tree[i].maxsum=tree[i].sum=tree[i].lsum=tree[i].rsum=tree[i].msum=data;
        return;
    }
    int mid=(tree[i].l+tree[i].r)/2;
    if(x<=mid)
        update(x,data,i*2);
    else
        update(x,data,i*2+1);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    tree[i].lsum=max(tree[i*2].lsum,tree[i*2].sum+tree[i*2+1].lsum);
    tree[i].rsum=max(tree[i*2+1].rsum,tree[i*2].rsum+tree[i*2+1].sum);
    tree[i].msum=max(tree[i*2+1].msum,tree[i*2].msum);
    tree[i].msum=max(tree[i].msum,tree[i*2].rsum+tree[i*2+1].lsum);
    tree[i].maxsum=max(tree[i].lsum,max(tree[i].rsum,tree[i].msum));
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int tt=1;tt<=t;tt++)
    {
        int ans;
        scanf("%d%d",&n,&s);
        for(int i=1;i<=n;i++)
            pos[i].clear();
        memset(next1,0,sizeof(next1));
        memset(next2,0,sizeof(next2));
        memset(ci,0,sizeof(ci));
        memset(pre,0,sizeof(pre));
        memset(pre2,0,sizeof(pre2));
        int cnt=1;
        for(int i=1;i<=n;i++)
        {
            int temp;
            scanf("%d",&temp);
            ci[temp]++;
            if(ci[temp]>1)
                next2[pre2[temp]]=i;
            if(ci[temp]==1)
                pre[temp]=i;
            if(ci[temp]<=s)
                score[i]=1;
            else if(ci[temp]==(s+1))
            {
                score[i]=-s;
                next1[pre[temp]]=i;
                pre[temp]=next2[pre[temp]];
            }
            else
            {
                score[i]=0;
                next1[pre[temp]]=i;
                pre[temp]=next2[pre[temp]];
            }
            pre2[temp]=i;
        }
        init_tree(1,1,n);
        ans=tree[1].maxsum;
        for(int i=1;i<=n;i++)
        {
            ans=max(ans,tree[1].maxsum);
            update(i,0,1);
            if(next1[i]==0) continue;
            update(next1[i],1,1);
            if(next2[next1[i]]==0) continue;
            update(next2[next1[i]],-s,1);

        }
        ans=max(ans,tree[1].maxsum);
        printf("Case #%d: %d\n",tt,ans);
    }
        return 0;
}