A：考试分数

知识点：数组、排序

思路： 首先对给出的 n 个数求和。 接下来有 3 种情况。

1. 如果所有数都是 10 的倍数，那么答案为 0。
2. 若这些数的和不是 10 的倍数，则这 n 个数的和即为答案。
3. 如果这 n 个数的和是 10 的倍数，那么在这些数中找一个不是 10 的倍数的最小的数，然后用和减去它即可。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[101],s,ans; 
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s+=a[i];
    }
    if(s%10!=0){
        cout<<s;
        return 0;
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        if(a[i]%10!=0){
            cout<<s-a[i];
            return 0;
        }
    }
    cout<<0;
    return 0;
}

B：回家

知识点：数学、循环

思路：运用高斯的等差数列n(n+1)/2公式

从一开始，依次套公式，直到那个数套进去的值大于小于目标数，输出套到公式的那个数。

代码：

#include<bits/stdc++.h>
using namespace std;
int x,s,ans; 
int main(){
    cin>>x;
    for(int i=1;i<=x;i++){
        s+=i;ans++; 
        if(s>=x){
            break;
        }
    }
    cout<<ans;
    return 0;
}

C：爆炸

知识点：二分答案

思路：每次攻击你可以选一个魔物 i 使其血量减去 x ，其他魔物血量减去 y (x>y) 。问使所有魔物血量 ≤0 至少要几次攻击。

答案很明显攻击次数越多，怪物死亡越多，故可以考虑二分。

每次check考虑攻击x次能否将所有魔物打败。

那么这x次攻击对所有魔物血量减少x*b(不考虑那个魔物减少a滴血)。

这时候可能会有arr[i]>xb，那么这个魔物就需要减少a滴血，也就是说这个魔物每次多减少a-b滴血，所以至少需要攻击ceil(arr[i]-xb)/(a-b))。

最后若总次数<=x，就代表x次攻击可以将所有魔物打败，然后可以尝试最小的x。

代码：

#include<bits/stdc++.h>
using namespace std;
long long n,a,b,arr[100001],l=1,r=1e9,mid,ans;
//x次爆炸够不够消灭怪物 
bool check(long long x){
    long long cnt=0;
    for(int i=1;i<=n;i++)
        if(arr[i]>b*x)
            cnt+=ceil((arr[i]-b*x)*1.0/(a-b));
    return cnt<=x;//可行 
}
int main(){    
    cin>>n>>a>>b;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    while(l<=r){
        mid=(l+r)/2;
        if(check(mid)){
            r=mid-1;
            ans=mid;
        }else{
            l=mid+1;
        }
    }
    cout<<ans;
    return 0;
}

D：货币系统

知识点：动态规划

思路：这道题我们把a数组输入进来后，从小到大排个序，f[0]=1，先枚举i从1到n，然后再枚举j从a[i]到a[n]，dp[j]+=dp[j-a[i]]，dp[i]代表了i元钱的组合方法数，最后算出dp[i]==1的i的个数，就是答案。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int t,n,a[25001],dp[25001];
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        memset(dp,0,sizeof dp);
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }sort(a+1,a+1+n);
        dp[0]=1;
        for(int i=1;i<=n;i++){
            for(int j=a[i];j<=a[n];j++){
                dp[j]+=dp[j-a[i]];
            }
        }int ans=0;
        for(int i=1;i<=n;i++){
            if(dp[a[i]]==1){
                ans++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}