官方题解｜2024新春欢乐赛

userId_undefined

AC君

管理员
倔强青铜

2024-03-04 16:02:42

发布于：浙江

136阅读
0回复
0点赞

赛事传送门

T1、新年快乐 - 题解

题面大意

有nn堆糖果，每次你可以将任意一堆复制到另一堆上。每堆糖果的数量不能超过ff

题意分析

求最多能复制几次。

解题思路

每次我们把较小的一堆复制到较大的一堆，那么考虑找出最小的一堆，由它来当被复制的，复制到其他堆上。这样每堆能操作的次数才会最多。

时间复杂度解析

找出最小的那堆糖果，扫描所有糖果堆，计算最小糖果堆能复制到其它糖果堆的操作次数，复杂度为O(n)O(n)

代码演示

#include <bits/stdc++.h>
using namespace std;
const int N = 1100;
int a[N];
int main() {
    int n,k;
    cin >> n >> k;
    for(int i=0;i<n;i++) {
        cin >> a[i];
    }
    sort(a,a+n,less<int>());
    int r = 0;
    for(int i=1;i<n;i++) {
        r += (k - a[i]) / a[0];
    }
    cout << r << endl;
    return 0;
}

T2、新年大扫除 - 题解

题面大意

给你nn个字符，只由大写字母NN和OO组成，每次可以选择kk个连续的字符，将选中的各个字符变成NN。

题意分析

找到最小的操作数，将所有的OO变成NN

解题思路

每次选择kk个字符，如果从ii开始选，则可变的范围就是[i,i+k−1][i,i+k-1]，考虑只有OO需要变成NN，我们可以找到第一个为OO的字符，从这个字符开始选择kk个字符变成NN,然后继续找到下一个OO。

那么实际上每次我们只需要维护一个值rr，它表示≤r\leq r的字符都能变成NN

时间复杂度解析

我们只需要遍历一次字符即可，复杂度为O(n)O(n)

代码演示

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,k;
    string s;
    cin >> n >> k;
    cin >> s;
    int r = -1;
    int cnt = 0;
    for(int i=0;i<s.length();i++) {
        if (s[i] == 'O' && i > r) {
            cnt ++;
            r = i + k - 1;
        }
    }
    cout << cnt << endl;
    return 0;
}

T3、新年魔法 - 题解

题面大意

给你两个数字，a,ba,b

每次用较大的数去减去较小的数，如果 a>ba > b 那么$ a = a - b $, bb不变。

如果两个数字相等，例a−ba-b或b−ab-a皆符合，直到有一个数字小于等于0，就停止运算。

题意分析

问多少次后会停止运算

解题思路

这个操作过程与辗转相减是一样的

如果每次用减法去模拟，当两个数值相差很大时，就要运算很久，我们可以直接用除法去代替减法。

嗯，如果变成除法的话，这与辗转相除法相同。

时间复杂度解析

复杂度与辗转相除法的复杂度等同，O(log max(a,b))O(log \ max(a,b))

代码演示

#include <iostream>
using namespace std;
int main() {
    int a,b;
    cin >> a >> b;
    int cnt = 0 ;
    while(a > 0 && b > 0) {
        if (a < b) {
            cnt += (b / a);
            b %= a;
        } else {
            cnt += (a / b);
            a %= b;
        }
    }
    cout << cnt << endl;
    return 0;
}

T4、新年排列 - 题解

题面大意

给你一个长度为nn的全排列pp，和一个整数kk，每次可以任意选择kk个元素，以升序移动到pp的末尾，直到pp为升序。

题意分析

求最小操作次数，使得pp变为升序

解题思路

找到以1开头的最长上升序子序列qq，那么不属于qq部分的则都要移动，将非qq部分的元素移动到pp的尾部就好。

时间复杂度解析

我们只需要遍历一次pp序列，就能找到子序列qq，复杂度为O(n)O(n)。

代码演示

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int main() {
    int n,k;
    cin >> n >> k;
    int j = 0;
    for(int i=0;i<n;i++) {
        cin >> a[i];
        if (a[i] == 1) j = i + 1;
    }
    int l = 1, len = 1;
    for(;j<n;j++) {
        if (a[j] == l + 1) {
            l = l + 1;
            len++;
        }
    }
    cout << (n - len) / k + ( (n - len) % k > 0)<< endl;
    return 0;
}

T5、新年游戏 - 题解

题面大意

你有nn个正整数，每次可以选择一对数，pip_i与pjp_j(i≠j,pi>pji \neq j,p_i > p_j)，然后使pip_i = pip_i - pjp_j
最终会得到一个新的序列

题意分析

要求最终序列的和最小

解题思路

每次我们用一个大的数pip_i减去一个小的数pjp_j，操作后，pjp_j会变成那个较大的数，pip_i会变成那个较小的数字，继续重复这个操作。我们发现与辗转相减的操作是一样的，那么实际上就是求最大公约数。

时间复杂度解析

代码演示

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,r = 0,x;
    cin >> n;
    for(int i=0;i<n;i++) {
        cin >> x;
        if (!r) r = x;
        r = __gcd(r, x);
    }
    cout << r * n<< endl;
    return 0;
}

T6、新年均馔 - 题解

题面大意

有nn盒饼干，每盒的饼干数量可能不同，只能从盒子里拿出饼干，问最少拿多少饼干可以使得每盒饼干数量相同。

题意分析

求拿出饼干的最少数量，使得每盒饼干数量相同

解题思路

因为饼干只能拿出，不能放入，如果使得每盒饼干数量相同，根据木桶原理，那么最终每盒饼干的数量一定等于饼干数量最少的那盒。

时间复杂度解析

我们只需要遍历所有饼干，算这盒饼干与数量最少的那盒饼干的差值就行，复杂度为O(n)O(n)。

代码演示

#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int a[N];
int main() {
    int n;
    cin >> n;
    int x = 0xfffffff;
    for(int i=0;i<n;i++) {
        cin >> a[i];
        x = min(x, a[i]);
    }
    int r = 0;
    for(int i=0;i<n;i++) {
        if (a[i] > x) r += (a[i] - x);
    }
    cout << r << endl;
    return 0;
}

T7、新年花坛守护战 - 题解

题面大意

现在有nn个花坛，每个花坛上有aia_i个小年兽，你需要驱赶所有的小年兽。

有两种驱赶的方案

幸运福花：消费 1个1个 金币可以驱赶一个小年兽

烟花炮：消费 kk个 金币，可以驱赶任意一个花坛上的所有小年兽

题意分析

请问最少花费多少个金币，就可以将小年兽全部驱赶呢？

解题思路

每个花坛只要选择一种方案就行了，然后我们要看是选择幸运福花还是烟花炮，如果某一个花坛上的小年兽数量是小于烟花炮需要的金币数量，那么就选择幸运福花驱赶这个花坛上所有的小年兽，反之选择烟花炮。

时间复杂度解析

遍历所有花坛，进行分析即可，复杂度为O(n)O(n)。

代码演示

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N];
int main() {
    int n,c,k;
    cin >> n >> c;
    for(int i=0;i<n;i++) {
        cin >> a[i];
    };
    int r = 0;
    for(int i = 0;i<n;i++) {
        int x = a[i];
        if (x >= c) {
            r += c;
        } else r+=x;
    }
    cout << r << endl;
    return 0;
}

T8、新年红包 - 题解

题面大意

有nn个数字，只有一个数字出现了一次，其他数字都出现了两次。

题意分析

求出现一次的那个数字

解题思路

用异或去消除两两出现的数字，剩下那个就是出现一次的数字

时间复杂度解析

遍历所有数字，复杂度为O(n)O(n)

代码演示

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n,a,r = 0;
    cin >> n;
    for(int i=0;i<n;i++) {
        cin >> a;
        r ^= a;
    }
    cout << r << endl;
    return 0;
}

T9、新年糖果 - 题解

题面大意

给你一个数hh，可以被分成n+1n+1个数相加，数的取值为pi(0≤pi<n,pi=n×2)p_i(0\leq p_i < n, p_i = n \times 2)

题意分析

问hh最多能被分成几个$ n \times 2 $

解题思路

因为题面告诉我们hh这个数，最多只能被分成n+1n+1个，所以答案的最大值为n+1n+1。

再看一下hh里面有多少个$ n \times 2 $就可以

时间复杂度解析

求得hh能被分成几个$ n \times 2 $，用除法就行。复杂度为: O(1)O(1)

代码演示

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long t,n,s;
	cin >> n >> s;
    cout << s / (2 * n) << endl;
    return 0;
}

T10、新年消消乐 - 题解

题面大意

给你 n×2n \times 2 个数，两个数字相加如果是奇数则消除，且一个数只能被使用一次

题意分析

是否所有数都能被消除。

解题思路

一个偶数加上一个偶数还是一个偶数，一个奇数加上一个奇数会变成偶数，一个奇数加上一个偶数才会是奇数。
所以，统计奇数与偶数的数量是否相等即可。

时间复杂度解析

遍历所有数统计数量即可，复杂度为O(n×2)O(n \times 2)。

代码演示

#include <bits/stdc++.h>
using namespace std;
const int N = 120;
int arr[N];
int main() {
    int n,k;
    cin >> n;
    int x = 0,y = 0;
    for(int i=0;i<n*2;i++) {
        cin >> k;
        if (k & 1) x++;
        else y++;
    }
    if (x == y) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}
userId_undefined
去预览
0/2000

全部评论 4

热门讨论