A：硬币

知识点：贪心

思路：即然每种硬币数量不限，那就可以考虑每次都使用最大的硬币来兑换(硬币值越大，个数越少)，这样就能达到最优解，故让自己的总值s每次都购买s/n的张数，直到总值s为0即可。

参考代码：

#include <bits/stdc++.h>
using namespace std;
int n,s,ans;
int main() {    
    cin>>n>>s;
    if(s<=n){
        cout<<1;
        return 0;
    }
    while(s){//有钱就需要硬币 
        int cnt=s/n;//看看s能买几张n元硬币
        ans+=cnt;
        s-=cnt*n;
        if(!s)break;
        n--;
    }
    cout<<ans;
    return 0;
}

B：完美字符串

知识点：字符串、结构体排序

思路：题目说明不在乎字母大小写，那就全部处理成小写字母或者大写字母，统计看看那个字母出现的次数最多，对字母进行排序。那就可以想到使用结构体来进行存储，成员有两个，出现的次数n和字符c,最后按照出现的次数进行排序，进而累加求和即可。

参考代码：

#include<bits/stdc++.h>
using namespace std;
struct node {
    int n;
    char c;
    bool operator<(const node & b) const {
        return n>b.n;
    }
} a[27];
string s;
int ans;
int main() {
    cin>>s;
    for(int i=0; i<s.size(); i++) {
        if(s[i]>='A'&&s[i]<='Z')s[i]+=32;
        a[s[i]-'a'+1].n++;
        a[s[i]-'a'+1].c=s[i];
    }
    sort(a+1,a+1+26);
    for(int i=1,cnt=26; i<=26; i++,cnt--) {
        if(a[i].c>='a'&&a[i].c<='z') {
            ans+=cnt*a[i].n;
        }
    }
    cout<<ans;
    return 0;
}

C：守门骑士

知识点：广度优先搜索

思路：考虑到贝西把灌木交给骑士，那就遍历每个灌木的位置，然后进行广搜，分别统计到达贝西的位置至少需要几步，统计到达骑士的位置至少需要几步，擂台比较其最小值即可。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a[101][101],stx,sty,qix,qiy,ans=INT_MAX,posx,posy;
int d[][2]= {{0,1},{0,-1},{1,0},{-1,0}};
bool v[101][101];
struct node {
    int x,y,s=0;
};
int bfs(int x,int y){
    int f1=0,f2=0,ans1=0,ans2=0;
    memset(v,0,sizeof v);v[x][y]=1;
    node no;no.x=x;no.y=y;no.s=0;
    queue<node> q;q.push(no);
    while(!q.empty()){
        node t=q.front();q.pop();
        if(f1&&f2) return ans1+ans2;
        if(t.x==stx&&t.y==sty&&!f1){
            f1=1;
            ans1=t.s;
        }
        if(t.x==qix&&t.y==qiy&&!f2){
            f2=1;
            ans2=t.s;
        }
        for(int i=0;i<4;i++){
            int xx=t.x+d[i][0],yy=t.y+d[i][1];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&1!=a[xx][yy]&&!v[xx][yy]){
                v[xx][yy]=1;
                node nod;nod.x=xx;nod.y=yy;nod.s=t.s+1;
                q.push(nod);
            }
        }
    }
    return INT_MAX;
}
int main() {
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=m; j++) {
            cin>>a[i][j];
            if(a[i][j]==2)stx=i,sty=j;
            if(a[i][j]==3)qix=i,qiy=j;
        }
    }
    for(int i=1; i<=n; i++) 
        for(int j=1; j<=m; j++) 
            if(a[i][j]==4) 
                ans=min(ans,bfs(i,j));
    if(ans==INT_MAX) cout<<-1;
    else cout<<ans;
    return 0;
}

D：骨头收藏家

知识点：动态规划、背包

思路：令d[j]表示体积为j时最大的骨头价值。则

当不收集第i个骨头时，其值就是上一个值继承下来，d[j]=d[j];

当收集第i个骨头时，其值就是体积减少第i个骨头的体积加上第i个骨头的价值d[j]=d[j-weight[i]]+val[i];

综合考虑取其最大值d[j]=max(d[j],d[j-weight[i]]+val[i])即可。

注意多组数据需要每轮清空。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int t,n,v,val[1001],weight[1001],d[1001];
int main(){
    cin>>t;
    while(t--){
        cin>>n>>v;
        memset(d,0,sizeof d);
        for(int i=1;i<=n;i++)cin>>val[i];
        for(int i=1;i<=n;i++)cin>>weight[i];
        for(int i=1;i<=n;i++)
            for(int j=v;j>=weight[i];j--)
                d[j]=max(d[j],d[j-weight[i]]+val[i]);
        cout<<d[v]<<endl;
    }
    return 0;
}