Google Kickstart 2019 D

Posted on | In

2019 Google Kickstart Round D Solution

A. X or What?

题意大概：给定n个元素的集合A，以及q次修改，询问 每次修改后 满足区间异或后有偶数个位置为1 (xor-even) 的 最大区间是多长。 $N,Q \leq 10^5$

线段树维护下最长区间大小，就ok了，只有2个 xor_even 或2个 xor-odd 才能构成 xor-even .

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

struct tree{
    int l,r;
    int flag;
    int lmax,rmax;

};
tree node[500000];
int xx[500000];
int n,q,ans;
int bit(int x)
{
    int bits=0;
    while(x)
    {
        bits+=(x%2);
        x/=2;
    }
    return bits%2;
}
void intit(int i,int l,int r)
{
    if(l>r) return;
    node[i].l=l;
    node[i].r=r;
    node[i].flag=0;
    node[i].lmax=999999;
    node[i].rmax=-1;
    if(l==r) return;
    int mid=(l+r)/2;
    intit(i*2,l,mid);
    intit(i*2+1,mid+1,r);
}
void updata(int i,int x,int y)
{
    if(node[i].l==node[i].r)
    {
        node[i].flag=y;
        if(node[i].flag)
        {
            node[i].lmax=node[i].l;
            node[i].rmax=node[i].r;
        }
        else
        {
            node[i].lmax=999999;
            node[i].rmax=-1;
        }
        return;
    }
    int mid=(node[i].l+node[i].r)/2;
    if(x<=mid)
       updata(i*2,x,y);
    else
        updata(i*2+1,x,y);
    node[i].flag=node[i*2].flag|node[i*2+1].flag;
    node[i].lmax=min(node[i*2].lmax,node[i*2+1].lmax);
    node[i].rmax=max(node[i*2].rmax,node[i*2+1].rmax);
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int tt=1;tt<=t;tt++)
    {
        ans=0;
        scanf("%d%d",&n,&q);
        int sum=0;
        intit(1,1,n);
        for(int i=1;i<=n;i++)
        {
            int temp;
            scanf("%d",&temp);
            if(bit(temp))
            {
                xx[i]=1;
                updata(1,i,1);
                sum=(sum+xx[i])%2;
            }
            else
            {
                xx[i]=0;
                updata(1,i,0);
            }
        }
        printf("Case #%d:",tt);
        for(int i=0;i<q;i++)
        {
            ans=0;
            int id, zhi;
            scanf("%d%d",&id,&zhi);
            id++;
            sum=(sum+xx[id])%2;
            xx[id]=bit(zhi);
            sum=(sum+xx[id])%2;
            updata(1,id,xx[id]);
            if(sum==0) ans=n;
            else
            {

                if(node[1].lmax<=n&&node[1].lmax>=0)
                    ans=max(ans,n-node[1].lmax);
                if(node[1].rmax<=n&&node[1].rmax>=0)
                    ans=max(ans,node[1].rmax-1);
            }
            printf(" %d",ans);
        }
        printf("\n");
    }
}

B. Latest Guests

题意：1个环上有N个大使馆，编号1-n，G个访客从各自起始位置顺时针或逆时针访问大使馆，1分钟访客可以从i移动到i+1/i-1，总共访问M分钟，问每个大使馆最后到达的游客编号集合。 $N,G\leq10^5$, $M\leq 10^9$

解法好多，可以二分来做，这里用的滑动窗口来解决，

先只考虑顺时针的情况，存下来每个访客 的结束点 ，然后对于每个大使馆来说，最后访问他的人一定是从大使馆位置开始顺时针方向的第一个人，并且他们之间距离要小于等于M，这样存下每个人的最终位置，就能O(N)时间处理每个大使馆的最后记录的到达时间，同理逆时针也是这样。有了到达时间很容易反推各个位置上的记录起始点在哪里，之后按顺序统计输出就ok，相同位置相同方向的访客的结果是相同的，当一个人处理。

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
#include<bits/stdc++.h>
using namespace std;
int n,g,m;
int c[200100];
int a[200100];
int times[100100];
int pos[100100];
int aorc[100100];
int ans_cre[100100];
int ans_are[100100];
int main()
{
    int t;
    scanf("%d",&t);
    for(int tt=1;tt<=t;tt++)
    {
        scanf("%d%d%d",&n,&g,&m);
        int cnt=0;
        memset(times,-1,sizeof(times));
        memset(c,0,sizeof(c));
        memset(a,0,sizeof(a));
        memset(ans_cre,0,sizeof(ans_cre));
        memset(ans_are,0,sizeof(ans_are));

        for(int i=1;i<=g;i++)
        {
            char temp[10];
            int s;
            scanf("%d%s",&s,&temp);
            s--;
            if(temp[0]=='C')
            {
                c[(s+m)%n]++;
                if(s+m>=n)
                    c[(s+m)%n+n]++;
                pos[i]=s;
                aorc[i]=0;
            }
            else{
                a[((s-m)%n+n)%n]++;
                if(s-m<0)
                    a[((s-m)%n+n)%n+n]++;
                pos[i]=s;
                aorc[i]=1;
            }
        }
        int l=0,r=n-1;
        for(int i=0;i<2*n&&l<n;i++)
        {
            if(c[i]==0) continue;
            l=max(l,i-m);
            while(l<=i&&l<n)
            {
                times[l]=max(times[l],m-(i-l));
                l++;
            }
        }
        for(int i=n-1;r>=0&&i>=-n;i--)
        {
            if(a[(i+n*2)%(2*n)]==0) continue;
            r=min(r,i+m);
            while(r>=i&&r>=0)
            {
                times[r]=max(times[r],m-(r-i));
                r--;
            }
        }
        for(int i=0;i<n;i++)
        {
            if(times[i]<0) continue;
            ans_are[(i+times[i])%n]++;
            ans_cre[((i-times[i])%n+n)%n]++;
        }
        printf("Case #%d:",tt);
        for(int i=1;i<=g;i++)
        {
            if(aorc[i])
                printf(" %d",ans_are[pos[i]]);
            else
                printf(" %d",ans_cre[pos[i]]);
        }
        printf("\n");
    }
}

C. Food Stalls

题意：建K个摊位，1个仓库，有N个候选建造位置$X_i$ ，每个位置的 建造 花费为$C_i$，此外如果仓库建在$X_j$，在$X_i$建造摊位要额外付出$|X_j- X_i|$

先考虑已经选好K+1个位置，那么仓库一定会修在中间位置，所以仓库左边有$\lfloor k/2 \rfloor$个摊位，右边有$k -\lfloor k/2 \rfloor$个摊位，那我们可以枚举仓库所在的位置，找出左右两边代价最小的$\lfloor k/2 \rfloor$和$k -\lfloor k/2 \rfloor$摊位即可。

假设固定仓库为$x_j$，那么左边摊位$x_i$代价为$c_i+x_j-x_i$，其中$x_j$是固定的，所以最大堆来维护左边$c_i-x_i$最小的$\lfloor k/2 \rfloor$个摊位，右边同理，最后每个仓库位置再加上仓库建造费用$C_j$以及$\lfloor k/2 \rfloorx_j-(k-\lfloor k/2 \rfloor)x_j$，求一个最小值就是答案。

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

int n,k;
long long ans;
struct node{
    long long x,c;
};
node nodes[100100];
bool cmp(node x,node y)
{
    return x.x<y.x;
}
long long sum[100100];
priority_queue<long long ,vector<long long>,less<long long> > max_heap;
int main()
{
    int t;
    scanf("%d",&t);
    for(int tt=1;tt<=t;tt++)
    {
        memset(sum,0,sizeof(sum));
        scanf("%d%d",&k,&n);
        for(int i=0;i<n;i++)
            scanf("%lld",&nodes[i].x);
        for(int i=0;i<n;i++)
            scanf("%lld",&nodes[i].c);
        sort(nodes,nodes+n,cmp);
        long long sumc=0;
        while(!max_heap.empty()) max_heap.pop();
        for(int i=0;i<k/2;i++)
        {
            max_heap.push(nodes[i].c-nodes[i].x);
            sumc=sumc+(nodes[i].c-nodes[i].x);
        }
        for(int i=k/2;i<n;i++)
        {
            sum[i]=sumc;
            if(!max_heap.empty()&&max_heap.top()>(nodes[i].c-nodes[i].x))
            {
                sumc=sumc-max_heap.top();
                max_heap.pop();
                max_heap.push(nodes[i].c-nodes[i].x);
                sumc=sumc+(nodes[i].c-nodes[i].x);
            }
        }

        while(!max_heap.empty()) max_heap.pop();
        sumc=0;
        for(int j=0;j<k-k/2;j++)
        {
            max_heap.push(nodes[n-1-j].c+nodes[n-1-j].x);
            sumc=sumc+(nodes[n-1-j].c+nodes[n-1-j].x);
        }
        for(int j=k-k/2;j<n;j++)
        {
            sum[n-j-1]+=sumc;
            if(!max_heap.empty()&&max_heap.top()>(nodes[n-j-1].c+nodes[n-j-1].x))
            {
                sumc=sumc-max_heap.top();
                max_heap.pop();
                max_heap.push(nodes[n-j-1].c+nodes[n-j-1].x);
                sumc=sumc+(nodes[n-j-1].c+nodes[n-j-1].x);
            }
        }
        ans=sum[k/2]+k/2*nodes[k/2].x-(k-k/2)*nodes[k/2].x+nodes[k/2].c;
        for(int i=k/2;i<n-k+k/2;i++)
        {
            ans=min(ans,sum[i]+k/2*nodes[i].x-(k-k/2)*nodes[i].x+nodes[i].c);
        }
        printf("Case #%d: %lld\n",tt,ans);
    }

}