cf565(div3)

发表于 | 分类于 ， | 阅读量 次

cf565(div3)

A. Divide it!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int q;
    cin>>q;
    while(q--)
    {
        long long x;
        cin>>x;
        int sum=0;
        while(x%2==0) {x/=2;sum+=1;}
        while(x%3==0) {x/=3;sum+=2;}
        while(x%5==0) {x/=5;sum+=3;}
        if(x!=1) cout<<-1<<endl;
        else cout<<sum<<endl;

    }
    return 0;
}

B. Merge it!

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

int main()
{
    int  T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        int a[3]={0};
        int x;
        for(int i=1;i<=n;i++)
        {cin>>x;a[x%3]++;}
        int sum=0;
        sum+=a[0];
        sum+=min(a[1],a[2]);
        int k=min(a[1],a[2]);
        a[1]-=k;
        a[2]-=k;
        if(a[1]>0)
            sum+=a[1]/3;
        if(a[2]>0)
            sum+=a[2]/3;
        cout<<sum<<endl;
    }
    return 0;
}

C. Lose it!

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

using namespace std;

queue<int>q[10];
int main()
{
    int n;
    cin>>n;
    int x;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        if(x==4) q[0].push(i);
        else if(x==8) q[1].push(i);
        else if(x==15)q[2].push(i);
        else if(x==16)q[3].push(i);
        else if(x==23)q[4].push(i);
        else if(x==42)q[5].push(i);
    }

    int sum=0;
int flag=0;
     while(1)
     {
         if(q[0].empty()) break;
         int cur=q[0].front();
         q[0].pop();
         for(int i=1;i<6;i++)
         {
             if(q[i].empty())
             {
                 sum+=i;
                 flag=1;
                 break;
             }
             int bi=q[i].front();
             q[i].pop();
             while(cur>bi)
             {
                 sum++;
                 if(q[i].empty())
                 {sum+=i;flag=1;break;}
                 bi=q[i].front();
                 q[i].pop();
             }
             if(flag)break;
             cur=bi;
         }
         if(flag)break;
     }
     for(int i=0;i<6;i++)
        sum+=q[i].size();
    cout<<sum<<endl;
    return 0;
}

D. Recover it!

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

int su[3000000];
vector<int> vec;
int vv[3000010];

int main()
{
    memset(su,0,sizeof(su));
    memset(vv,0,sizeof(vv));
    vec.push_back(2);
    for(int i=3;i<=2750131;i++)
    {

        for(int j=0;j<vec.size();j++)
        {
            if(vec[j]*vec[j]>i) break;
            if(i%vec[j]==0) {su[i]=i/vec[j];break;}
        }
        if(su[i]==0) vec.push_back(i);
    }

    int n;
    scanf("%d",&n);
    int h_sum=2*n;
    for(int i=1;i<=2*n;i++)
    {
        int x;
        scanf("%d",&x);
        vv[x]++;
    }

    for(int i=2750131;i>=2;i--)
    {
        while(su[i]&&vv[i]) {printf("%d ",i);vv[i]--;vv[su[i]]--;h_sum-=2;}
    }
    for(int i=2750131;i>=2;i--)
    {
        if(h_sum==0) break;
        while(vv[i]) {int k=lower_bound(vec.begin(),vec.end(),i)-vec.begin()+1;printf("%d ",k);vv[i]--;vv[k]--;h_sum-=2;if(h_sum==0) break;}
    }

    printf("\n");
    return 0;
}

E. Cover it!

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

vector<int> vec[maxn];
int in[maxn];
int color[maxn];

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            vec[i].clear();
            in[i]=color[i]=0;
        }
        for(int i=1;i<=m;i++)
        {
            int a,b;
            cin>>a>>b;
            vec[a].push_back(b);
            vec[b].push_back(a);
        }
        for(int i=1;i<=n;i++)
        {
            if(color[i]) continue;
            in[i]=1;
            for(int j=0;j<vec[i].size();j++)
            {
                color[vec[i][j]]=1;

            }
        }
        for(int i=1;i<=n;i++)
            if(in[i])
            sum++;
        if(sum<=n/2)
        {
            cout<<sum<<endl;
            for(int i=1;i<=n;i++)
                if(in[i])
                cout<<i<<" ";
            cout<<endl;

        }
        else
        {
            cout<<n-sum<<endl;
            for(int i=1;i<=n;i++)
            if(!in[i])
                cout<<i<<" ";
            cout<<endl;
        }
    }
}

F. Destroy it!