【HT-049-Div.4】核桃新手组周赛个人题解

NEKO_Daze · 2025-03-08 21:40:24 · 题解

0.序言

AK！ 100+100+100+100=400

T1

说是只需要 O(1) 就能做但我忘了所以打了个 while 也能过。

我就说好像哪次线下比赛打过这道题……

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, ans = 0;
    cin >> n;
    n = 1000 - n;
    while(n != 0)
    {
        if(n>=1000) {ans++,n-=1000;continue;}
        if(n>=500) {ans++,n-=500;continue;}
        if(n>=100) {ans++,n-=100;continue;}
        if(n>=50) {ans++,n-=50;continue;}
        if(n>=10) {ans++,n-=10;continue;}
        if(n>=5) {ans++,n-=5;continue;}
        ans++,n--;
    }
    cout<<ans;
}

T2

枚举即可。

从 4^0 开始枚举直到 4^k > n（不难证明其实 k=\lfloor\frac{n}{4}\rfloor），若 n-4^i \bmod5=0,i\in[0,m]，代表存在 4^i + 5^j=n,j=\frac{n-4^i}{5} 这一种分法，计数器加一。最后输出计数器。

#include <bits/stdc++.h>
using namespace std;
int n, m;
int main()
{
    cin >> n;
    for (int i = 0; i <= n/4; i++)
    {
        if ((n-4*i)%5==0) m++;
    }
    cout<<m;
}

T3

先将输入的数组排序。字符串 ABC 一共只有六种排列情况，写六个 if 判断即可。

#include <bits/stdc++.h>
using namespace std;
int a[4];
string s;
int main()
{
    for(int i = 1;i  <= 3; i++)
    {
        cin >> a[i];
    }
    sort(a+1,a+4);
    cin >> s;
    if(s=="ABC")printf("%d %d %d",a[1],a[2],a[3]);
    if(s=="ACB")printf("%d %d %d",a[1],a[3],a[2]);
    if(s=="BAC")printf("%d %d %d",a[2],a[1],a[3]);
    if(s=="BCA")printf("%d %d %d",a[2],a[3],a[1]);
    if(s=="CAB")printf("%d %d %d",a[3],a[1],a[2]);
    if(s=="CBA")printf("%d %d %d",a[3],a[2],a[1]);
}

T4

无论我们如何操作，所有购物券与口袋里的购物券上的数值总和是不变的，因为我们相当于只能将一张购物券上的 1 点面值转移到另一张购物券上。所以最后地上的购物券的值全部为 0 的同时，口袋中的购物券应该为 \sum_{i=1}^{n}a_i，即初始地上所有购物券的面值总和。

对于一张购物券，面值为 a_i，那么它归零所需的操作次数为 |a_i|。每次操作，我们可以令两张优惠券剩余所需操作次数减少 1，而总需操作次数减少 2。

• 如果 \sum_{i=1}^{n}a_i=0，代表着我们可以在不使用口袋中的购物券的情况下，仅通过正负抵消来完成。此时操作数即为：

  \frac{\sum_{i=1}^{n}|a_i|}{2}

• 否则，在进行 \frac{\sum_{i=1}^{n}|a_i|}{2} 次消除后，还要额外进行 \frac{\sum_{i=1}^{n}a_i}{2} 次操作，使用口袋中的购物券来消除。总操作数为 \frac{\sum_{i=1}^{n}|a_i|+\sum_{i=1}^{n}a_i}{2}。

不难发现当 \sum_{i=1}^{n}a_i=0 时第二种情况推出的式子同样适用于第一种情况，因此连条件判断语句都省了，最终答案即为：

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    long long sum = 0, abs_sum = 0;
    for (int i = 1; i <= n; ++i)
    {
        int x;cin >> x;
        sum += x; abs_sum += abs(x);
    }
    long long ans = (abs_sum + abs(sum)) / 2;
    cout << ans << " " << sum;
    return 0;
}