疯狂游戏笔试

最恶心输入输出，没有之一

编程两道，简答一道
简答题压根没看，最后一道编程题本地都过了，牛客编译器编译失败。

编程题1：

最少硬币问题，要输出每种硬币的数量
纠结完全背包，贪心和回溯好久，不记得完全背包怎么搞硬币数量了，最终回溯过了90%

#include<bits/stdc++.h>
using namespace std;
vector<int> Nums(4,0);
long long sum = INT_MAX;
long long a=0,b=0,c=0;
void dfs(long long value)
{
    if(value<0) return;
    if(value==0)
    {
        long long curSum = Nums[1]+Nums[2]+Nums[3];
        if(curSum<sum)
        {
            sum = curSum;
            a=Nums[1];b=Nums[2];c=Nums[3];
        }
        return;
    }
    Nums[3]++;
    dfs(value-5);
    Nums[3]--;
    Nums[2]++;
    dfs(value-4);
    Nums[2]--;
    Nums[1]++;
    dfs(value-1);
    Nums[1]--;
}

int main()
{
    long long value;
    while(cin>>value)
    {
        dfs(value);
        cout<<a<<','<<b<<','<<c<<endl;
        a=0;b=0;c=0;
    }

}

编程题2：

也是纸币组合问题
输入1,2,3,4,5;5
表示分别有面值1，2，3，4，5的纸币各1张，凑出最后的5块钱
输出5;1,4;2,3;
输出要保证每组输出从小到大，size最小顺序，size相同要按字典序，真的无语
本地代码跑过了，放到牛客上先是报一堆警告，不能用int和vector里的unsigned int比较，所有int改成了unsigned int，然后发现报错66行编译失败，大意是一些本应带有返回值的函数到达结尾后可能并没有返回任何值，发现本地vscode确实也报警告了，脑子抽了一直找不到哪里没return值了，时间gg，下次一定先做简答题。。。结束后恍然大悟，可惜，但感觉这个暴力回溯应该也不能AC，如果有AC的朋友希望说下方法。
笔试代码：

#include<bits/stdc++.h>
using namespace std;
vector<vector<int>> res;
vector<int> path;

void dfs(vector<int>& M,int start,int total,int sum)
{
    if(sum>total) return;
    if(sum==total)
    {
        res.push_back(path);
        return;
    }
    for(int i=start;i<M.size();++i)
    {
        path.push_back(M[i]);
        dfs(M,i+1,total,sum+M[i]);
        path.pop_back();
    }

}

int main()
{
    vector<int> M;
    int total;
    string s;
    cin>>s; 
    for(int i=0;i<s.size();++i)
    {
        if(s[i]==',')continue;
        else if(s[i]==';')
        {
            total = s[i+1]-'0';
            break;
        }else{
            M.push_back(s[i]-'0');
        }
    }

    sort(M.begin(),M.end());
    dfs(M,0,total,0);

    for(int i=0;i<res.size();++i)
    {
        sort(res[i].begin(),res[i].end());
    }

    sort(res.begin(),res.end(),[](vector<int>& a,vector<int>& b){
        if(a.size()<b.size())
        {
            return a>b;
        }else if(a.size()==b.size())
        {
            for(int i=0;i<a.size();++i)
            {
                if(a[i]<b[i])
                {
                    return a>b;
                }else if(a[i]>b[i])
                {
                    return a<b;
                }else continue;
            }
        }else return a<b;
    });

    for(int i=0;i<res.size();++i)
    {
        for(int j=0;j<res[i].size();++j)
        {
            cout<<res[i][j];
            if(j!=res[i].size()-1) cout<<",";
        }
        if(i!=res.size()-1)cout << ";";
    }
    system("pause");
}

编译问题更改：

sort(res.begin(),res.end(),[](vector<int>& a,vector<int>& b){
        if(a.size()<b.size())
        {
            return a>b;
        }else if(a.size()==b.size())
        {
            for(int i=0;i<a.size();++i)
            {
                if(a[i]<b[i])
                {
                    return a>b;
                }else if(a[i]>b[i])
                {
                    return a<b;
                }else{//笔试时改成了这样，感觉应该ok了还是不行，这里暴露的问题是对编译和运行时的情况不清楚。。。
                    if(i==a.size()-1) return a<b;
                }              
            }
            //return a<b; 楞是没想到在for循环外边return，无语啊。。。
        }else return a<b;
    });