A 牛牛分蛋糕

题解：暴力。要想最少的盘子中蛋糕最多，就要均匀分配最好，设装第一种蛋糕盘子数为，则第二种为，然后暴力枚举即可

class Solution {
public:
    /**
     * 处理函数，返回在所有分法中，蛋糕数量最少的盘子中分到最多的蛋糕数量
     * @param n int整型 n个盘子
     * @param a int整型 a蛋糕数量
     * @param b int整型 b蛋糕数量
     * @return int整型
     */
    int solve(int n, int a, int b) {
        // write code here
        if(a+b == n) return 1;
        int ans=1;
        for(int i=1; i<n; i++){
            int tmp1=a/i;
            int tmp2=b/(n-i);
            ans=max(ans,min(tmp1,tmp2));
        }
        //cout<<ans<<endl;
        return ans;
    }
};

B 牛牛凑数字

题解：贪心。先找最小的价钱的数字，如果最小价钱的数字都买不起，就输出-1；否则尽量买最多的数字，然后如果剩余了钱，就把对应数字“后悔”，加剩余钱去买更大的数字替换掉最开始的数字，循环就好了。

class Solution {
public:
    /**
     * 得到牛牛能够凑到的最大的数字
     * @param n int整型 牛牛能够承受的价格
     * @param a int整型vector 1-9这九个数字的价格数组
     * @return string字符串
     */
    string solve(int n, vector<int>& a) {
        // write code here
        std::vector<char> an;
        int ans=0x3f3f3f3f;
        int k=-1;
        for(int i=0; i<(int)a.size(); i++){
            if(a[i] <= ans){
                ans=a[i];
                k=i+1;
            }
        }
        string no="-1";
        if(ans > n) return no;
        int num=n/ans;
        int tmp=n%ans;
        for(int i=0; i<num; i++){
            an.emplace_back('0'+k);
        }
        //cout<<tmp<<endl;
        int j=0;
        while(tmp){
            int tt=ans+tmp;
            bool ok=false;
            for(int i=0; i<(int)a.size(); i++){
                if(tt>=a[i]){
                    an[j]='0'+i+1;
                    ok=true;
                    tmp=tt-a[i];
                }
            }
            j++;
            if(j == (int)an.size() || !ok) break;
        }
        string s;
        for(auto i:an){
            s+=i;
        }
        return s;
    }
};

C 牛妹的野菜

题解：记忆化搜索。保存每个节点向下走的最大价值和对应下一个节点的编号，然后搜索就好了。

const int maxn = 1e6+10;
const int inf=0x3f3f3f3f;
int dp[maxn][2];
struct edge{
    int to,nex;
}e[maxn<<1];
int head[maxn],ecnt;
void init(){
    memset(head,0,sizeof head);
    memset(dp,-1,sizeof dp);
    ecnt=0;
}
void add(int from,int to){
    e[++ecnt].to=to;
    e[ecnt].nex=head[from];
    head[from]=ecnt;
}
void dfs(int root,int par,vector<int>& potatoNum){
    if(dp[root][0] != -1) return ;
    bool ok=false;
    for(int i=head[root]; i; i=e[i].nex){
        int son=e[i].to;
        if(son == par) continue;
        ok=true;
        dfs(son,root,potatoNum);
        if(dp[son][0] > dp[root][0]){
            dp[root][0]=dp[son][0];
            dp[root][1]=son;
        }
    }
    if(!ok) dp[root][0]=potatoNum[root-1];
    else dp[root][0]+=potatoNum[root-1];
}
string cal(int x){
    string s="";
    while(x){
        s+= (x%10+'0');
        x/=10;
    }
    string ans="";
    for(int i=s.length()-1; i>=0; i--) ans+=s[i];
    return ans;
}
class Solution {
public:
    /**
     *
     * @param potatoNum int整型vector 依次表示序号为1,2,3..的番薯洞各有多少个番薯
     * @param connectRoad int整型vector<vector<>> 每个一维数组[x,y]表示从第x号番薯洞到第y号有路
     * @return string字符串
     */
    string digSum(vector<int>& potatoNum, vector<vector<int> >& connectRoad) {
        // write code here
        init();
        for(auto i:connectRoad){
            add(i[0],i[1]);
        }
        int ans=-1;
        int k=-1;
        for(int i=1; i<=(int)potatoNum.size(); i++){
            dfs(i,0,potatoNum);
        }
        for(int i=1; i<=(int)potatoNum.size(); i++){
            if(dp[i][0] > ans){
                ans=dp[i][0];
                k=i;
            }
        }
        string ss=cal(k);
        while(dp[k][1] != -1){
            ss+="-";
            ss+=cal(dp[k][1]);
            k=dp[k][1];
        }
        return ss;
    }
};

只会暴力QAQ