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

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

OwO

A. 不断减损的时间

题面

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

#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取到最大，即 ，使用 个 的砖可以拼成 大的正方形，这 块砖都充分利用了，还剩下 块砖可以使用，剩下的砖每三个一组可以将原有正方形扩大一圈.

所以答案应该是 .

即 .

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

AC代码：

#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模4的余数.

若 即 ， ，前面 个数按四的倍数的情况搞，剩下6个按 的构造.

若 即 ， ，同理，使用 的构造.

若 即 ， ，前 个用四的倍数的构造，然后接一个 的构造，再接一个 的构造.

注意特判！

AC代码：

#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. 宿命之间的对决

题面

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

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

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

设对于 都是偶数先手赢，奇数后手赢.
时，选择的因子只能是奇数，那么 减去这个因子得到的 便是偶数， ，此时相当于小紫先手，偶数先手胜，所以 时，后手胜.

时，选择因子 ， ，此时相当于小紫先手，但 为奇数，后手胜，所以 时，先手必胜.

综上，由归纳原理，对于 ，有 时，先手必胜， 时，后手必胜.

AC代码：

#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. 公平守望的灯塔

题面

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

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

AC代码：

#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代码：

#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