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

0.序言

AK！ 100+100+100+100=400

T1

说是只需要

O(1)

就能做但我忘了所以打了个 while 也能过。

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

CPP

#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}

这一种分法，计数器加一。最后输出计数器。

CPP

#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 判断即可。

CPP

#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

时第二种情况推出的式子同样适用于第一种情况，因此连条件判断语句都省了，最终答案即为：

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

CPP

#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;
}

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

文章操作

0.序言

T1

T2

T3

T4

相关推荐

评论

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