Google Kickstart 2019 E

Posted on | In

2019 Google Kickstart Round E Solution

A. Cherries Mesh

题目大意：给定一个N个点的无向的全连接图，其中M条边权值为1，其余边权值为2，求保持任意两点直接或间接相连的最小权值。其中 $ 0<=N<=10^5 $ , $ 0<=M<=10^5 $

先用并查集维护权值为1的边构造的连通块，再加上(连通块个数减-1)*2，就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
#include<bits/stdc++.h>
using namespace std;
int parent[100010];
int rankp[100010];
void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        parent[i]=i;
        rankp[i]=1;
    }
}
int find(int x)
{
    int t=x,temp;
    while(parent[x]!=x)
        x=parent[x];
    while(parent[t]!=x)
    {
        temp=parent[t];
        parent[t]=x;
        rankp[t]=1;
        t=temp;
    }
    return x;
}
void merge(int x,int y)
{
    int tx=find(x);
    int ty=find(y);
    if(tx!=ty)
    {
        if(rankp[tx]<rankp[ty])
        {
            parent[ty]=tx;
            rankp[ty]+=rankp[tx];
            rankp[tx]=1;
        }
        else
        {
            parent[tx]=ty;
            rankp[tx]+=rankp[ty];
            rankp[ty]=1;
        }
    }
}

int n,m,ans;
int main()
{
    int t;
    scanf("%d",&t);
    for(int tt=1;tt<=t;tt++)
    {
        ans=0;
        scanf("%d%d",&n,&m);
        init(n);
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if(find(x)!=find(y))
            {
                ans++;
                merge(x,y);
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(parent[i]==i)
                ans+=2;
        }
        ans-=2;
        printf("Case #%d: %d\n",tt,ans);
    }
}

B. Code-Eat Switcher

Umon一天只做两件事，coding/eating（== 似曾相识的一天 ）。一天可以分成s段，第i段时间可以做$f*c_i$单位的coding 与$(1-f)e_i$ 的eating， 其中$0\leq f\leq1$，给出D次询问，询问一天是否 可以做完$A_i$ coding和$B_i$eating。$1 \leq S,D\leq 10^5$

既然时间是可以拆分的，明显是个贪心（=。= 赛后诸葛）。直接按照性价比排序，判断$coding \geq A_i $情况下，$ eating \geq B_i$是否成立，因为D规模太大，所以对于询问也按照coding从大到小排列，从而$o(S)$时间解决所有询问。

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
#include<bits/stdc++.h>
using namespace std;
int d,s;
struct node{
    int c,e;
};
bool cmp(node x ,node y){
    return x.e*y.c>x.c*y.e;
}
node nodes[100010];
int ans[100010];
struct querry{
    int i,a,b;
};
querry que[100010];
bool cmpq(querry x ,querry y){
    return x.a>y.a;
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int tt=1;tt<=t;tt++)
    {
        scanf("%d%d",&d,&s);
        long long sumc=0,sume=0;
        for(int i=0;i<s;i++)
        {
            scanf("%d%d",&nodes[i].c,&nodes[i].e);
            sumc+=nodes[i].c;
        }
        for(int i=0;i<d;i++)
        {
            scanf("%d%d",&que[i].a,&que[i].b);
            que[i].i=i;
        }
        sort(que,que+d,cmpq);
        sort(nodes,nodes+s,cmp);
        printf("Case #%d: ",tt);
        int temp=0;
        for(int i=0;i<d;i++)
        {
            while(temp<s&&sumc-nodes[temp].c>que[i].a) 
            {	
                sume+=nodes[temp].e;
             	sumc-=nodes[temp].c;
                temp++;
            }
            if(sume+(sumc-que[i].a)*nodes[temp].e/nodes[temp].c>=que[i].b)
                ans[que[i].i]=1;
            else
                ans[que[i].i]=0;
        }
        for(int i=0;i<d;i++)
        {
            if(ans[i])
                printf("Y");
            else
                printf("N");
        }
        printf("\n");
    }
}

C Street Checkers

在$[L,R]$中随机数X，X的奇因子与偶因子的个数差不大于2，问这样X有多少个。

$ 1\leq L\leq R \leq 10^9$ , $R-L\leq 10^5$

满足条件的X只有4种情况

  • 质数
  • 2 * 任意奇数
  • 4 * 质数
  • 8

所以区间素数筛判断素数，就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
85
#include<bits/stdc++.h>
using namespace std;
#include<cstdio>
#include<cstring>
#define ll long long int
ll tot;
const ll Maxn=1000010;
ll Is_or[1050400];
ll ans[1050400];
ll ans1[1050400];
ll prime[1050400];
void init()
{
    tot=0;
    memset(Is_or,0,sizeof(Is_or));
    for(ll i=2;i<=Maxn;i++)
    {
        if(Is_or[i]==0)
        {
            prime[tot++]=i;
            for(ll j=i+i;j<=Maxn;j+=i)
                Is_or[j]=1;
        }
    }
}
void Get_prime(ll L,ll R)
{
    memset(ans,0,sizeof(ans));
    for(ll i=0;i<tot;i++)
    {
        ll b=L/prime[i];
        while(b*prime[i]<L||b<=1)b++;
        for(ll j=b*prime[i];j<=R;j+=prime[i])
            if(j>=L)
                ans[j-L]=1;
    }
}

void Get_prime1(ll L,ll R)
{
    memset(ans1,0,sizeof(ans1));
    for(ll i=0;i<tot;i++)
    {
        ll b=L/prime[i];
        while(b*prime[i]<L||b<=1)b++;
        for(ll j=b*prime[i];j<=R;j+=prime[i])
            if(j>=L)
                ans1[j-L]=1;
    }
}
int l,r;
int ansaly(int &x)
{
    int tot=0;
    while(x%2==0)
    {
        tot++;
        x=x/2;
    }
    return tot;
}
int main()
{
    int t;
    scanf("%d",&t);
    init();
    for(int tt=1;tt<=t;tt++)
    {
        scanf("%d%d",&l,&r);
        Get_prime((ll)l,(ll)r);
        Get_prime1((ll)l/4,(ll)r/4);
        int ans2=0;
        for(int i=l;i<=r;i++)
        {
           int x=i;
           int temp=ansaly(x);
           if(temp==1) ans2++;
           if(temp==0&&ans[x-l]==0) ans2++;
           if(temp==2&&ans1[x-l/4]==0) ans2++;
           if(temp==3&&x==1)	ans2++;

        }
        printf("Case #%d: %d\n",tt,ans2);
    }
}