2023牛客寒假算法基础集训营3 题解

2023/1/20 算法竞赛 2023 题解 C++ 牛客 寒假算法集训营

OwO

A. 不断减损的时间

题面

既然将偶数除以2的操作可以做无限次，要求所有元素和最小，那必然是将正偶数的2因子除尽，负偶数和奇数不变.

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(x) ((x)&-(x))
const int N=1e5+5;
int a[N];
priority_queue<int> s;
int main() {
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]%2!=0)
            sum+=a[i];
        else
        {
            if(a[i]>0)
            {
                while(a[i]%2==0)
                    a[i]/=2;
                sum+=a[i];
            }
            else
                sum+=a[i];
        }
    }
    cout<<sum<<'\n';
    return 0;
}

B. 勉强拼凑的记忆

题面

一开始没看样例，以为k是固定的(悲)

首先k不是固定的，题目化为找出不超过n块砖拼成的最大正方形边长(因为可以将大砖分成小砖，位置不变).

然后如果要使正方形边长尽可能大，那么就要使正方形面积尽可能大，就要让k尽可能大.

将k取到最大，即 ，使用 个 1 × k 的砖可以拼成 大的正方形，这 块砖都充分利用了，还剩下 块砖可以使用，剩下的砖每三个一组可以将原有正方形扩大一圈.

所以答案应该是 .

即 .

另外需要特判一下 n = 2 的情况.

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(x) ((x)&-(x))
ll ceil(ll n,ll x)
{
    if(n%x==0)
        return n/x;
    else
        return n/x+1;
}
int main() {
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        ll n;
        cin>>n;
        if(n==2)
            cout<<-1<<'\n';
        else
            cout<<ceil(n,2)+n/2/3<<'\n';
    }
    return 0;
}

C. 忽远忽近的距离

题面

先看n比较好的情况.

n = 1, 2, 3 时都不行. n = 4 时， 3, 4, 1, 2 满足题意. n = 5 时， 4, 5, 1, 2, 3 满足题意. n = 6 时， 4, 5, 1, 6, 2, 3 满足题意. n = 7 时，易证此时没有可行构造.

发现如果 4 ∣ n ，设初始状态下 ai = i(i=1,2,...,n) 那么可以四个一组，将 i 与 i + 2 交换，将 i + 1 和 i + 3 交换，这样可以满足题意.

如果 4 ∤ n ，分类讨论n模4的余数.

若 n ≡ 2(mod4)即n = 4k + 2 ，n = 4(k−1) + 6 ，前面 4 * (k−1) 个数按四的倍数的情况搞，剩下6个按 n = 6 的构造.

若 n ≡ 1(mod4)即n = 4k + 1 ， n = 4(k−1) + 5 ，同理，使用 n = 5 的构造.

若 n ≡ 3(mod4)即n = 4k + 3 ，n = 4(k−2) + 6 + 5 ，前 4(k−2) 个用四的倍数的构造，然后接一个 n = 6 的构造，再接一个 n = 5 的构造.

注意特判！

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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(x) ((x)&-(x))
const int N=1e5+5;
int a[N];
int main() {
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    if(n<=3||n==7)
        cout<<-1<<'\n';
    else
    {
        for(int i=1;i<=n;i++)
            a[i]=i;
        if(n%4==0)
        {
            for(int i=1;i<=n-3;i+=4)
            {
                swap(a[i],a[i+2]);
                swap(a[i+1],a[i+3]);
            }
            for(int i=1;i<=n;i++)
                cout<<a[i]<<' ';
            cout<<'\n';
        }
        else if(n%4==2)
        {
            int n1=n/4*4-4;
            for(int i=1;i<=n1-3;i+=4)
            {
                swap(a[i],a[i+2]);
                swap(a[i+1],a[i+3]);
            }
            for(int i=1;i<=n1;i++)
                cout<<a[i]<<' ';
            cout<<n1+4<<' '<<n1+5<<' '<<n1+1<<' '<<n1+6<<' '<<n1+2<<' '<<n1+3<<'\n';
        }
        else if(n%4==1)
        {
            int n1=n/4*4-4;
            for(int i=1;i<=n1-3;i+=4)
            {
                swap(a[i],a[i+2]);
                swap(a[i+1],a[i+3]);
            }
            for(int i=1;i<=n1;i++)
                cout<<a[i]<<' ';
            cout<<n1+4<<' '<<n1+5<<' '<<n1+1<<' '<<n1+2<<' '<<n1+3<<'\n';
        }
        else if(n%4==3)
        {
            int n1=n/4*4-4-4;
            for(int i=1;i<=n1-3;i+=4)
            {
                swap(a[i],a[i+2]);
                swap(a[i+1],a[i+3]);
            }
            int n2=n1+6;
            for(int i=1;i<=n1;i++)
                cout<<a[i]<<' ';
            cout<<n1+4<<' '<<n1+5<<' '<<n1+1<<' '<<n1+6<<' '<<n1+2<<' '<<n1+3<<' ';
            cout<<n2+4<<' '<<n2+5<<' '<<n2+1<<' '<<n2+2<<' '<<n2+3<<'\n';
        }
    }
    return 0;
}

D. 宿命之间的对决

题面

初看上去不太好做，试试 n 比较小的情况.

发现在 n = 1, 2, ..., 8 的时候都是偶数先手赢，奇数后手赢，可以猜测这是普遍规律.

尝试证明，用第二类数学归纳法：

设对于 n = 1, 2, ..., 2k 都是偶数先手赢，奇数后手赢. n = 2k + 1 时，选择的因子只能是奇数，那么 n 减去这个因子得到的 n′ 便是偶数， n′ ∈ {1, 2, ..., 2k} ，此时相当于小紫先手，偶数先手胜，所以 n = 2k + 1 时，后手胜.

n = 2k + 2 时，选择因子 1 ， n′ = n − 1 = 2k + 1 ，此时相当于小紫先手，但 n′ 为奇数，后手胜，所以 n = 2k + 2 时，先手必胜.

综上，由归纳原理，对于 n = 1, 2, ... ，有 2 ∣ n 时，先手必胜， 2 ∤ n 时，后手必胜.

AC代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(x) ((x)&-(x))
int main() {
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    if(n%2==0)
        cout<<"kou"<<'\n';
    else
        cout<<"yukari"<<'\n';
    return 0;
}

E. 公平守望的灯塔

题面

可以直接找出直角顶点，看一下是不是整点就行.

取 AB 中点 ，以 M 为原点建立复平面，则 ，直角顶点 ，原坐标系中直角顶点 .

AC代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(x) ((x)&-(x))
int main() {
    ios::sync_with_stdio(false);
    ll x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    ll x=x1+x2-y2+y1,y=y1+y2+x2-x1;
    if(x%2!=0||y%2!=0)
        cout<<"No Answer!"<<'\n';
    else
        cout<<x/2<<' '<<y/2<<'\n';
    return 0;
}

F. 迎接终结的寂灭

题面

一开始还用python去搞，发现python也算不了带sqrt和↑↑的表达式，突然发现似乎这题就是让输出42(悲).

AC代码： 

1
2
3
4
5
6
7
8
9
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(x) ((x)&-(x))
int main() {
    ios::sync_with_stdio(false);
    cout<<42<<'\n';
    return 0;
}
img_show